Bug 7993 – BigInt divide-by-1 error

It seems that dividing a BigInt by 1 has the same effect as multiplying by 2. The following program: import std.bigint; import std.stdio; void main() { BigInt foo = 10; writeln(foo / 1); writeln(foo / 2); } Outputs: $ ./main 20 5

Which version are you using ? I get the correct result (10, 5) with dmd 2.059

(In reply to comment #1) > Which version are you using ? I get the correct result (10, 5) with dmd 2.059 $ dmd | head -n3 DMD64 D Compiler v2.059 Copyright (c) 1999-2012 by Digital Mars written by Walter Bright Documentation: http://www.dlang.org/index.html I get this errant BigInt behavior both on an Arch Linux installation, using the community dmd package. And I get this errant behavior on Ubuntu 11.10 using gdc and on Ubuntu 12.04 using the dmd deb file gotten from the dlang.org download page (http://ftp.digitalmars.com/dmd_2.059-0_amd64.deb). These are all the combinations of versions I've tried. Indeed, I have yet to see D produce correct behavior for BigInt divide-by-1.

(In reply to comment #1) > Which version are you using ? I get the correct result (10, 5) with dmd 2.059 By the way, these are all on x86_64. I've modified the 'Platform' field in the bug record to reflect that.

$ dmd | head -n3 DMD64 D Compiler v2.059 Copyright (c) 1999-2012 by Digital Mars written by Walter Bright Documentation: http://www.dlang.org/index.html I do _not_ get this error when using the 32-bit v2.059 compiler. This appears to be a problem specific to the 64-bit compiler. Also, I've tested this only on Linux systems—Arch, Ubuntu 11.10, and Ubuntu 12.04.

After debugging the code, I discovered the root cause. (Code snippets below.) BigInt uses BigUint.divInt() for performing the underlying division operation. BigUint.divInt() has two cases: (1) the divisor is a power of 2, and (2) the divisor is not a power of 2. In the case of dividing by 1, the divisor is a power of two and case #1 is followed (if ((y&(-y))==y)). However, the number of bits to shift is 0. But multibyteShr() explicitly states that the number of bits to shift must not be 0 (numbits must be in the range 1..31). By changing BigUint.divInt() to treat y==1 as case #2—not a power of 2—rather than case #1, the problem is fixed. Code snippets: this is the runtime code that ships with my DMD/Phobos package. /usr/include/d/std/internal/math/biguintcore.d:549: // return x / y static BigUint divInt(T)(BigUint x, T y) if ( is(T==uint) ) { uint [] result = new BigDigit[x.data.length]; if ((y&(-y))==y) { assert(y!=0, "BigUint division by zero"); // perfect power of 2 uint b = 0; for (;y!=1; y>>=1) { ++b; } multibyteShr(result, x.data, b); } else { result[] = x.data[]; uint rem = multibyteDivAssign(result, y, 0); } return BigUint(removeLeadingZeros(result)); } /usr/include/d/std/internal/math/biguintnoasm.d:150 /** dest[] = src[] >> numbits * numbits must be in the range 1..31 */ void multibyteShr(uint [] dest, const(uint) [] src, uint numbits) { ulong c = 0; for(ptrdiff_t i = dest.length; i!=0; --i) { c += (src[i-1] >>numbits) + (cast(ulong)(src[i-1]) << (64 - numbits)); dest[i-1] = cast(uint)c; c >>>= 32; } }

Here's my modified BigUint.divInt() as a proof-of-concept of the fix. // return x / y static BigUint divInt(T)(BigUint x, T y) if ( is(T==uint) ) { uint [] result = new BigDigit[x.data.length]; uint b; if ((y&(-y))==y) { assert(y!=0, "BigUint division by zero"); // perfect power of 2 for (;y!=1; y>>=1) { ++b; } } if (1 <= b && b <= 31) { multibyteShr(result, x.data, b); } else { result[] = x.data[]; uint rem = multibyteDivAssign(result, y, 0); } return BigUint(removeLeadingZeros(result)); }

Commit pushed to master at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/a79bb20ea79955da2422b32b6291ed464530c86d Fix issue 7993 BigInt divide-by-1 error Thanks to c.m.brandeburg for the fix.