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
