www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 7993] New: BigInt divide-by-1 error

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7993

           Summary: BigInt divide-by-1 error
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: c.m.brandenburg gmail.com



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

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 26 2012
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7993


SomeDude <lovelydear mailmetrash.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |lovelydear mailmetrash.com



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

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 27 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7993






 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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 27 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7993






 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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 27 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7993




$ 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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 28 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7993




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.


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).


2—rather


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;
   }
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 28 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7993




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));
    }

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 28 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7993




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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 01 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7993


Don <clugdbug yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |clugdbug yahoo.com.au
         Resolution|                            |FIXED


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 03 2012