digitalmars.D.learn - Obscure Isssue #1
- Ruby The Roobster (251/251) Aug 05 2022 My code (as seen below) is failing due to a single line.
- H. S. Teoh (8/9) Aug 05 2022 Is the imported module available anywhere? I'm trying to run your code
- Ruby The Roobster (3/10) Aug 05 2022 You can cut that and the Number class out. They're not relevant
- H. S. Teoh (20/30) Aug 05 2022 It's actually not a bug. Running the code in the debugger shows that
- Ruby The Roobster (5/10) Aug 05 2022 I have no idea how the program generated a 18k+ digit number, but
- Ruby The Roobster (3/14) Aug 05 2022 Oop. Just realized that was because I commented out the line
- Ruby The Roobster (2/17) Aug 05 2022 Turns out that using negative numbers breaks it.
My code (as seen below) is failing due to a single line.
That line is:
```d
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.
```d
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:
```d
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?
Aug 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
Aug 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: [...]You can cut that and the Number class out. They're not relevant to the bug. Sorry for not mentioning that.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
Aug 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.
Aug 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] TI have no idea how the program generated a 18k+ digit number, but apparently changing the `+` to a `*` on line 158 solved the problem.
Aug 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]Oop. Just realized that was because I commented out the line involving the bugIn 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] TI have no idea how the program generated a 18k+ digit number, but apparently changing the `+` to a `*` on line 158 solved the problem.
Aug 05 2022
Ruby The Roobster <rubytheroobster yandex.com> 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:Turns out that using negative numbers breaks it.On Friday, 5 August 2022 at 15:07:18 UTC, H. S. Teoh wrote: [SNIP]Oop. Just realized that was because I commented out the line involving the bugIn 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] TI have no idea how the program generated a 18k+ digit number, but apparently changing the `+` to a `*` on line 158 solved the problem.
Aug 05 2022