Thread overview
Obscure Isssue #1
Aug 05, 2022
Ruby The Roobster
Aug 05, 2022
H. S. Teoh
Aug 05, 2022
Ruby The Roobster
Aug 05, 2022
H. S. Teoh
Aug 05, 2022
Ruby The Roobster
Aug 05, 2022
Ruby The Roobster
Aug 05, 2022
Ruby The Roobster
August 05, 2022

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?

August 05, 2022
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
August 05, 2022
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.
August 05, 2022
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.
August 05, 2022
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.

August 05, 2022
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
August 05, 2022
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.