BigInteger division in C#

问题:

I am writing a class which needs accurate division of the BigInteger class in C#.

Example:

BigInteger x = BigInteger.Parse("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
BigInteger y = BigInteger.Parse("2000000000000000000000000000000000000000000000000000000000000000000000000000000000000");

x /= y;

Console.WriteLine(x.ToString());

//Output = 0

The problem is that being an Integer, naturally it does not hold decimal values. How can I overcome this to get the real result of 0.5 (given example).

P.S. The solution must be able to accurately divide any BigInteger, not just the example!

回答1:

In the above example, the numbers are still small enough to be converted to double, so in this case you can say

double result = (double)x / (double)y;

If x and y are too huge for a double but still comparable, maybe this great trick is helpful:

double result = Math.Exp(BigInteger.Log(x) - BigInteger.Log(y));

But in general, when the BigInteger are huge, and their quotient is huge too, this is hard to do without importing a third-party library.

回答2:

What accuracy you need for the division? One way would be:

• Multiply the numerator by, say, 1000
• Divide the numbers
• Convert the result to double and divide by 1000

The same in code:

BigInteger x = BigInteger.Parse("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
BigInteger y = BigInteger.Parse("2000000000000000000000000000000000000000000000000000000000000000000000000000000000000");

x *= 1000;
x /= y;
double result = (double)x;
result /= 1000;
Console.WriteLine(result);

回答3:

If you need to keep full precision, use an implementation of rationals (the Java equivalent would be the Fraction class from Apache Commons Math library). There are various implementations lurking around, but the most light weight solution for .NET 4.0 (as it has System.Numerics.BigInteger built in) would be the following:

        System.Numerics.BigInteger x = System.Numerics.BigInteger.Parse("10000000000000000000000000000000000000000000000000000");

        System.Numerics.BigInteger y = System.Numerics.BigInteger.Parse("20000000000000000000000000000000000000000000000000000");

        // From BigRationalLibrary
        Numerics.BigRational r = new Numerics.BigRational(x,y);

        Console.Out.WriteLine(r.ToString());
        // outputs "1/2", but can be converted to floating point if needed.

To get this to work you need the System.Numberics.BigInteger from .Net 4.0 System.Numerics.dll and the BigRational implementation from CodePlex.

There is a Rational structure implemented in the Microsoft Solver Foundation 3.0 too. At the time of writing, the www.solverfoundation.com site was broken, thus a link to the archive.

回答4:

As you might know division of integers will not produce decimal values so your result is truncated to 0. According to this question big double implementation can be found here, but last release of it was in 2009. If you look further you might find newer one or this one is simply finished.

回答5:

Sound like a job for Fixed Point (rather than floating point).

Simply pre-shift the numerator by the number of fractional bits you need, like this:

BigInteger quotient = (x << 10) / y;

That would give you 10 bits after the dot (approximately 3 decimal digits).

回答6:

//b = 10x bigger as a => fraction should be 0.1
BigInteger a = BigInteger.Pow(10, 5000);
BigInteger b = BigInteger.Pow(10, 5001);

//before the division, multiple by a 1000 for a precision of 3, afterwards 
//divide the result by this.
var fraction = (double) BigInteger.Divide(a * 1000, b) / 1000;

回答7:

I found a pure BigInteger version :

static BigInteger FlooredIntDiv(BigInteger a, BigInteger b)
{
    if (a < 0)
    {
        if (b > 0)
            return (a - b + 1) / b;
    }
    else if (a > 0)
    {
        if (b < 0)
            return (a - b - 1) / b;
    }
    return a / b;
}

source (for long type) here : Floored integer division

回答8:

Parse it to double:

double a = Convert.ToDouble(x);
double b = Convert.ToDouble(y);

Console.WriteLine(a / b);