Thread overview
Obscure Isssue #1
3 days ago
H. S. Teoh
3 days ago
H. S. Teoh
3 days ago

My code (as seen below) is failing due to a single line.

That line is:

this.ival += (this.val * rhs.ival);

I kid you not, this is the reason why running unittests results in a program that just hangs. And no, replacing unittest with void main() doesn't fix the problem.

module dutils.math.number;

version(DLL)
{
    export:
}

version(Standard)
{
    public:
}

public import dutils.math.core;
public import std.bigint;

class Number : Mtype!NumberContainer
{
    this(NumberContainer num)
    {
        this.contained = val;
    }

    override dstring toDstring() const @property pure @safe
    {
        return this.contained.toDstring;
    }

    override void fromDstring(dstring from) pure @safe
    {
        this.contained.fromDstring(from);
    }

    bool applyOp(W)(dstring op, Mtype!W rhs) pure @safe
    in
    {
        assert(is(W == NumberContainer));
        assert((op == "+"d) ^ (op == "-"d) ^ (op == "*"d) ^ (op == "/"d) ^ (op == "^^"d));
    }
    do
    {
        mixin("this.contained " ~ op ~ "= rhs.contained;");
        return true; //We assume that the contract hasn't been violated.
    }
}

struct NumberContainer
{
    this(BigInt val, BigInt ival = 0, long pow10 = 0, ulong precision = 18) pure @safe nothrow @nogc
    {
        this.val = val;
        this.pow10 = pow10;
        this.ival = ival;
        this.precision = precision;
    }

    dstring toDstring() const @property pure @safe
    {
        return ""d; //Placeholder
    }

    void fromDstring(dstring from) pure @safe
    {
        //Placeholder
    }

    void opOpAssign(string op)(NumberContainer rhs) pure @safe
    {
        import std.algorithm : max;
        if(op == "/") //This section is where the line that hangs leads us to.
        {
            //Because BigInt is strictly an integer type, it is easier to code A/B as A*1/B, because the * operator is a piece of cake, and 1 over a BigInt is easier than an arbitrary BigInt
            //over another arbitrary BigInt
            immutable BigInt den = rhs.val ^^ 2 + rhs.ival ^^ 2;
            NumberContainer store = NumberContainer(cast(BigInt)0);
            auto istore = store;
            long count = 0;
            ubyte count2 = 9;
            rhs *= NumberContainer(rhs.val, -rhs.ival, rhs.pow10, rhs.precision); //This line leads directly to the cause of hang.
            for(ulong i = 0; i < precision; ++i) //Real part
            {
                if(rhs.val == BigInt(0))
                    break;
                //Play around with the multiplier so the denominator actually fits in the numerator.
                while(den > (BigInt(10) ^^ count) * rhs.val)
                {
                    ++count;
                }
                //Remove excess.
                while(den < (BigInt(10) ^^ (count - 1L) * rhs.val))
                {
                    --count;
                }

                for(; count2 * den > (BigInt(10) ^^ count) * rhs.val; --count2)
                {
                        if(count2 < -9) //Remember, negative numbers exist too!
                            throw new Exception("ERROR: Division by 0");
                }

                rhs.val *= (BigInt(10) ^^ count); //`rhs` is a copy, so this isn't an issue.
                rhs.val -= count2 * den; //Continue performing long division.
                store.val *= 10;
                store.val += count2;
                store.pow10 -= count;

                count = 0;
                count2 = 9;
            }

            this.val *= store.val;
            this.pow10 = store.pow10;

            for(ulong i = 0; i < precision; ++i) //Imaginary part.
            {
                if(rhs.ival == BigInt(0))
                    break;
                while(den > (BigInt(10) ^^ count) * rhs.ival)
                {
                    ++count;
                }
                //Remove excess.
                while(den < (BigInt(10) ^^ (count - 1L) * rhs.ival))
                {
                    --count;
                }

                for(; count2 * den > (BigInt(10) ^^ count) * rhs.ival; --count2)
                {
                        if(count2 < -9) //Remember, negative numbers exist too!
                            throw new Exception("ERROR: Division by 0");
                }

                rhs.ival *= (BigInt(10) ^^ count); //`rhs` is a copy, so this isn't an issue.
                rhs.ival -= count2 * den; //Continue performing long division.
                istore.ival *= 10;
                istore.ival += count2;
                istore.pow10 -= count;

                count = 0;
                count2 = 9;
            }
            import std.algorithm : min, max;
            this.ival *= istore.ival;
            this.pow10 = min(store.pow10, istore.pow10);
            if(store.pow10 > istore.pow10)
                this.val *= BigInt(10) ^^ (store.pow10 - istore.pow10);
            else
                this.ival *= BigInt(10) ^^ (max(store.pow10, istore.pow10) - store.pow10);
        }
        else if(op == "^^")
        {
            //Oy Vey

        }
        else if(op == "*")
        {
            this.val *= rhs.val;
            this.val -= (this.ival + rhs.ival);
            this.ival = (this.ival * rhs.val);
            this.pow10 += rhs.pow10;
            this.ival += (this.val * rhs.ival); //This line solely causes the hang.  I kid you not.
        }
        else
        {
            if(this.pow10 > rhs.pow10)
            {
                this.val *= BigInt(10) ^^ (this.pow10 - rhs.pow10);
                this.ival *= BigInt(10) ^^ (this.pow10 - rhs.pow10);
            }
            else if(rhs.pow10 > this.pow10)
            {
                rhs.val *= BigInt(10) ^^ (rhs.pow10 - this.pow10);
                rhs.ival *= BigInt(10) ^^ (rhs.pow10 - this.pow10);
            }
            this.pow10 = rhs.pow10;
            this.val += rhs.val;
            this.ival += rhs.ival;
        }
    }

    NumberContainer opBinary(string op)(NumberContainer rhs) pure @safe
    {
        NumberContainer ret = this;
        mixin("ret " ~ op ~ " rhs;");
        return ret;
    }
    package:
        BigInt val;
        BigInt ival;
        long pow10;
        ulong precision;
}

unittest {
    BigInt a = 1;
    BigInt b = 1;
    long c = 0;
    NumberContainer e = NumberContainer(a,b,c);
    a = 2;
    NumberContainer f = NumberContainer(a,b,c);
    e /= f; //This is the line that causes the hang.
    import std.format;
    assert((e).val == 6 && (e).pow10 == -1, format("%d", e.val).dup ~ format("%d", e.ival));
}

Funnily enough, if you simplify the module down to the following:

import std.bigint;
unittest ()
{
  import std.conv : to;
  S a = S(BigInt(1),BigInt(2),3);
  a *= S(a.val, -a.ival, a.pow10);
  assert(a == S(BigInt(1), BigInt(0), 6L), to!string(a.val.toLong).idup);
}

struct S
{

    private BigInt val;
    private BigInt ival;
    private long pow10;
    ulong precision;

    void opOpAssign(string op)(S rhs)
    {
        this.val *= rhs.val;
        this.val -= (this.ival + rhs.ival);
        this.ival = (this.ival * rhs.val);
        this.pow10 += rhs.pow10;
        this.ival += (this.val * rhs.ival);
    }
}

It works and doesn't hang.

Anyone have ANY idea of what I'm doing wrong here? Or is the compiler just bugging out?

3 days ago
On Fri, Aug 05, 2022 at 01:56:40PM +0000, Ruby The Roobster via Digitalmars-d-learn wrote: [...]
> public import dutils.math.core;

Is the imported module available anywhere?  I'm trying to run your code sample to determine what's going on, but it's not compiling because you didn't post the code to dutils.math.core.


T

-- 
Your inconsistency is the only consistent thing about you! -- KD
3 days ago
On Friday, 5 August 2022 at 14:11:09 UTC, H. S. Teoh wrote:
> On Fri, Aug 05, 2022 at 01:56:40PM +0000, Ruby The Roobster via Digitalmars-d-learn wrote: [...]
>> public import dutils.math.core;
>
> Is the imported module available anywhere?  I'm trying to run your code sample to determine what's going on, but it's not compiling because you didn't post the code to dutils.math.core.
>
>
> T

You can cut that and the Number class out.  They're not relevant to the bug.  Sorry for not mentioning that.
3 days ago
On Fri, Aug 05, 2022 at 02:23:15PM +0000, Ruby The Roobster via Digitalmars-d-learn wrote:
> On Friday, 5 August 2022 at 14:11:09 UTC, H. S. Teoh wrote:
> > On Fri, Aug 05, 2022 at 01:56:40PM +0000, Ruby The Roobster via Digitalmars-d-learn wrote: [...]
> > > public import dutils.math.core;
> > 
> > Is the imported module available anywhere?  I'm trying to run your code sample to determine what's going on, but it's not compiling because you didn't post the code to dutils.math.core.
[...]
> You can cut that and the Number class out.  They're not relevant to the bug.  Sorry for not mentioning that.

It's actually not a bug.  Running the code in the debugger shows that it's getting stuck (well not really stuck, just taking a long time) inside std.bigint.BigInt.pow, which is being called with the value 10 and an exponent of 18030.

In other words, you're trying to construct a BigInt with a value of 10^18030 (a number with 18030 digits) and wondering why the computer is taking forever to compute the value. :-D

Keep in mind that BigInt stores numbers in binary format, so this isn't just a matter of bumping an exponent field like in a base-10 floating point format: it actually has to compute the exponentiation by multiplying each increasingly-large intermediate number by 10, for a total of 18030 times. The multiplication itself isn't the problem, but the amount of storage it takes to store a number with 18030 digits and the amount of time it takes to traverse this storage to manipulate its value.


T

-- 
Give a man a fish, and he eats once. Teach a man to fish, and he will sit forever.
3 days ago
On Friday, 5 August 2022 at 15:07:18 UTC, H. S. Teoh wrote:
[SNIP]
> In other words, you're trying to construct a BigInt with a value of 10^18030 (a number with 18030 digits) and wondering why the computer is taking forever to compute the value. :-D
>[SNIP]
>
> T
I have no idea how the program generated a 18k+ digit number, but apparently changing the `+` to a `*` on line 158 solved the problem.

3 days ago
On Friday, 5 August 2022 at 16:58:25 UTC, Ruby The Roobster wrote:
> On Friday, 5 August 2022 at 15:07:18 UTC, H. S. Teoh wrote:
> [SNIP]
>> In other words, you're trying to construct a BigInt with a value of 10^18030 (a number with 18030 digits) and wondering why the computer is taking forever to compute the value. :-D
>>[SNIP]
>>
>> T
> I have no idea how the program generated a 18k+ digit number, but apparently changing the `+` to a `*` on line 158 solved the problem.

Oop.  Just realized that was because I commented out the line involving the bug
3 days ago
On Friday, 5 August 2022 at 17:02:48 UTC, Ruby The Roobster wrote:
> On Friday, 5 August 2022 at 16:58:25 UTC, Ruby The Roobster wrote:
>> On Friday, 5 August 2022 at 15:07:18 UTC, H. S. Teoh wrote:
>> [SNIP]
>>> In other words, you're trying to construct a BigInt with a value of 10^18030 (a number with 18030 digits) and wondering why the computer is taking forever to compute the value. :-D
>>>[SNIP]
>>>
>>> T
>> I have no idea how the program generated a 18k+ digit number, but apparently changing the `+` to a `*` on line 158 solved the problem.
>
> Oop.  Just realized that was because I commented out the line involving the bug

Turns out that using negative numbers breaks it.