www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - BigInt Bug or just me?

reply "Tyro[17]" <nospam home.com> writes:
Why does the following implementation of the binomial coefficient 
yield two different answers?

import std.stdio, std.bigint;

void main()
{
     // Correct result when using long
     writeln("(40  20) = ", binomial(40L, 20L));

     // 2 times the expected result when using BigInt
     writeln("(40  20) = ", binomial(BigInt(40), BigInt(20))/2);
}

T binomial(T)(T n, T k)
{
     T iter(T n, T k, T i, T prev)
     {
         if (i >= k) return prev;
         return iter(n, k, i+1, ((n-i)*prev)/(i+1));
     }

     if (k > (n-1)) return iter(n, k, cast(T)0, cast(T)1);
     return iter(n, (n-k), cast(T)0, cast(T)1);
}

Additionally, why is there no implicit conversion from integer to 
BigInt?
Surely now precision will be lost when performing this 
conversion. All
those casts are butt ugly if you ask me. I believe one should be 
able to
assign any integral value to BigInt and reasonably expect that it 
be
implicitly converted.

Thanks,
Andrew
Apr 21 2012
next sibling parent reply Jordi Sayol <g.sayol yahoo.es> writes:
Al 21/04/12 16:07, En/na Tyro[17] ha escrit:
 Why does the following implementation of the binomial coefficient yield two
different answers?
 

Only happens when compiling to 32-bit. 32-bit: (40 20) = 137846528820 (40 20) = 68923264410 64-bit: (40 20) = 137846528820 (40 20) = 137846528820 -- Jordi Sayol
Apr 21 2012
parent Jordi Sayol <g.sayol yahoo.es> writes:
Al 21/04/12 16:42, En/na Tyro[17] ha escrit:
 Actually, in that case it only happens when compiling to 64-bit.
 
 Note: comb1(BigInt(40), BigInt(20))/2; The the BigInt version is
 being divided by two (on MAC OS X) in order to yield the
 correct result.
 

You are right, sorry. My test was done in a Linux 64-bit. -- Jordi Sayol
Apr 21 2012
prev sibling parent "Tyro[17]" <nospam home.com> writes:
On Saturday, 21 April 2012 at 14:30:49 UTC, Jordi Sayol wrote:
 Al 21/04/12 16:07, En/na Tyro[17] ha escrit:
 Why does the following implementation of the binomial 
 coefficient yield two different answers?
 

Only happens when compiling to 32-bit. 32-bit: (40 20) = 137846528820 (40 20) = 68923264410 64-bit: (40 20) = 137846528820 (40 20) = 137846528820

Actually, in that case it only happens when compiling to 64-bit. Note: comb1(BigInt(40), BigInt(20))/2; The the BigInt version is being divided by two (on MAC OS X) in order to yield the correct result.
Apr 21 2012