Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

Ticket #1878 (closed defect: fixed)

Opened 2 years ago

Last modified 2 years ago

BigInt Division/Modulus Not Working

Reported by: Sage Rat Assigned to: Don Clugston
Priority: major Milestone: 1.0
Component: Tango Version: 0.99.9 Kai
Keywords: BigInt division modulus Cc: larsivi

Description

I'm on a 64-bit Vista, using the "Quick install with a bundled compiler - Windows" zip pack of 0.99.9 Kai. I'm not sure whether that's using BignumNoAsm? or BignumX86 underneath.

Division gives the wrong values:

	BigInt a = 10;
	BigInt b = 2;
	a /= b;
	Stdout.format("{}\n", a.toInt()); // prints 2

Modulus crashes:

	BigInt a = 10;
	BigInt b = 2;
	a %= b; // throws object.Exception: Win32 Exception
	Stdout.format("{}\n", a.toInt());

Change History

03/11/10 17:45:37 changed by Sage Rat

I've done some debugging myself. BigUintCore?.d -> divInt() should be modified from:

        uint b = 0;
        for (;y!=0; y>>=1) {
            ++b;
        }
        multibyteShr(result, x.data, b);

To:

        uint b = 0;
        y>>=1; // pre-shift once
        for (;y!=0; y>>=1) {
            ++b;
        }
        multibyteShr(result, x.data, b);

This only fixes division by powers of two. Division by anything else seems to make its way to BignumX86.d -> multibyteDivAssign(), which then throws an "object.Exception: Access Violation" error. For whatever reason dest.length is being corrupted when the function is called. If I force the system to use BignumNoAsm?.d this problem doesn't occur and both division and modulus seem to work alright (if the division by powers error is fixed.)

I couldn't say what's causing the array corruption error. I'm using v1.056 of the dmd compiler, which comes bundled with 0.99.9 Kai.

03/11/10 18:36:47 changed by kris

  • cc set to larsivi.

thanks, Sage Rat ... will apply this and set BigNumNoAsm? as the default until the corruption issue is resolved

(follow-up: ↓ 4 ) 03/11/10 23:16:16 changed by kris

hrm, BigInt.d now passes all unittests on WinXP/dmd-1.056 with version=TangoBignumNoAsm; enabled or disabled ... is that the case with Vista64 also?

(in reply to: ↑ 3 ) 03/13/10 07:04:37 changed by Sage Rat

Replying to kris:

hrm, BigInt.d now passes all unittests on WinXP/dmd-1.056 with version=TangoBignumNoAsm; enabled or disabled ... is that the case with Vista64 also?

Hm...I'm not sure. I tried running bob like so:

build\bin\win32\bob -vu -cdmd -rdmd -o="-unittest" .

This ran through just fine and popped out tango.lib. Then I tried adding my own unittest to the bottom of BigInt?.d (outside of the debug(UnitTest?) area), like so:

unittest {
	BigInt a = 12;
	BigInt b = 4;
	a = a/b;
	assert( a.toInt() == 147 );	
}

Nothing happened. It compiled through and popped out tango.lib again, indicating that my unittest wasn't actually being run at all. So then I revised it to this:

unittest {
	pragma(msg, "HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO!");
	
	BigInt a = 12;
	BigInt b = 4;
	a = a/b;
	assert( a.toInt() == 147 );
	assert( a.toInt() == 1 );
	assert( a.toInt() == 3 );
}

But as you see, it prints and just keeps on going merrily:

dmd -c -I./tango/core -I. -I./tango/core/vendor -unittest -oftango-math-BigInt?-u nittest.obj ./tango/math/BigInt.d HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HELLO! HEL LO! HELLO! HELLO! HELLO! HELLO! HELLO! dmd -c -I./tango/core -I. -I./tango/core/vendor -unittest -oftango-math-Bracket- unittest.obj ./tango/math/Bracket.d dmd -c -I./tango/core -I. -I./tango/core/vendor -unittest -oftango-math-Elliptic -unittest.obj ./tango/math/Elliptic.d dmd -c -I./tango/core -I. -I./tango/core/vendor -unittest -oftango-math-ErrorFun? ction-unittest.obj ./tango/math/ErrorFunction.d

Minus the -o="-unittest", my "HELLO!" disappears. But either way, everything runs through to completion.

We appear to be having a problem with our compiler, indeed.

(follow-up: ↓ 6 ) 03/13/10 09:18:09 changed by larsivi

bob won't actually help you run the unittests (at least not yet), so what you need to do is compile the library using

-o="-unittest -debug=UnitTest?"

and then link it with a minimal main.

(in reply to: ↑ 5 ) 03/13/10 19:30:19 changed by Sage Rat

Replying to larsivi:

bob won't actually help you run the unittests (at least not yet), so what you need to do is compile the library using -o="-unittest -debug=UnitTest?" and then link it with a minimal main.

Ahah, as you might detect, I've not yet used the unittest functionality. I thought it checked stuff during compilation.

Doing a clean, vanilla build from the repository, it loads and runs fine. My main() is like this:

import tango.io.Stdout;

int main() {
	Stdout("Hello").flush;

	return 0;
}

But then if I add my own unittest to the end of BigInt?.d:

struct BigInt {
	...

	unittest {
		BigInt a = 12;
		BigInt b = 4;
		a = a/b;
		assert( a.toInt() == 3 );
	}
}

Then I get an assert error. tango.core.Exception.AssertException@tango.math.BigInt(396): Assertion failure

04/24/10 18:14:26 changed by kris

  • owner changed from kris to Don Clugston.

any ideas on this one, Don?

04/26/10 08:04:42 changed by Don Clugston

Svn 5422 (23 March 2010) should have fixed both of these issues. Can someone check if it still fails?

04/26/10 08:29:32 changed by larsivi

  • status changed from new to closed.
  • resolution set to fixed.

As long as the unittests cover the issue, and do not fail, I see no reason to keep this ticket open.