BigInteger division in C#

Question

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!

How many digits do you need in the result? In general, when you divide two numbers, like `10/7`, the mathematical result has an infinite number of decimals. That's hard to represent in a computer. — Jeppe Stig Nielsen, Aug 08 '12 at 06:54
Note: This might be getting close to the answer I was looking for:http://stackoverflow.com/questions/2863388/what-is-the-equivalent-of-the-java-bigdecimal-class-in-c — Matthew Layton, Aug 08 '12 at 06:54
For too many decimals use Math.Round(result,2) for e.g. 2 digits — abc, Aug 08 '12 at 06:56
@AVD The numbers in the example do not fit in a `System.Decimal` as they stand, so you must provide details. — Jeppe Stig Nielsen, Aug 08 '12 at 06:56
Jeppe, it does not need to be infinitely accurate (and I would never expect a computer to compute such a number). 2-4 deimcal places will suffice! — Matthew Layton, Aug 08 '12 at 06:57
I know this is not an entirely orthodox idea...but could I technically port Java's BigDecimal class to C# and use that? — Matthew Layton, Aug 08 '12 at 07:00
@MatthewLayton is it OK if they're not decimal places but binary places? Shifting by 10 is faster than multiplying and dividing by 1000. — harold, Aug 08 '12 at 07:09
@harold. I'm not sure exactly what you mean, but the calculation will not always be dividing by a power of 10, sometimes it may divide by 999, 1123 etc. — Matthew Layton, Aug 08 '12 at 07:17
@MatthewLayton that's ok, it's not about the denominator, it's about the format of the result. You could multiply the numerator by 1000 and get 3 decimal digits after the dot, or you could shift left by 10 (faster than multiplying) and get 10 bits after the dot. Having fractional bits is more useful when doing more arithmetic, having fractional decimals is more useful when converting to string. — harold, Aug 08 '12 at 07:22
@harold. I will look into this! It may just be the ace up my sleeve! — Matthew Layton, Aug 08 '12 at 07:26
Using rationals will give you the option of getting the precision you need at the time of converting the number to string. And an implementation does exist as I finally managed to figure out. — jpe, Aug 08 '12 at 08:42

Jeppe Stig Nielsen · Accepted Answer · 2012-08-08T07:11:30.117

17

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.

edited Aug 08 '12 at 07:11

answered Aug 08 '12 at 07:03

Jeppe Stig Nielsen

60,409
11
110
181

This seems to be the closest thing I can find. It is working in my implementation! – Matthew Layton Aug 08 '12 at 07:59
A lot of precision is lost, of course. But the last method works in some cases. Like if `x` has 1005 digits and `y` has 1000 digits, neither is convertible to `double`, but the `result` is still OK (has circa 5 digits before the decimal point). However, if `x` has 2007 digits and `y` has 1000 digits, the `result` will be infinity. No exception is thrown. **Note:** If `x` and `y` may be non-positive, you have to take absolute value of each, and then deal with the sign in the end. – Jeppe Stig Nielsen Aug 08 '12 at 08:21

Ilmo Euro · Answer 2 · 2012-08-08T07:05:11.400

8

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

edited Aug 08 '12 at 07:05

answered Aug 08 '12 at 06:56

Ilmo Euro

4,925
1
27
29

Another way to write the same: `double result = (double)(1000 * x / y) / 1000.0;` (does not re-assign `x` however). The `result` may become `PositiveInfinity` or `NegativeInfinity`. – Jeppe Stig Nielsen Aug 08 '12 at 08:58

jpe · Answer 3 · 2012-08-08T08:32:26.343

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.

Good point, thanks for pointing out, missed that tiny detail. — jpe, Aug 08 '12 at 07:09
It raises a good point though! Why does C# not have these classes!? DOH! — Matthew Layton, Aug 08 '12 at 07:14
I editied my answer to reflect the "slight" difference in language. It seems that there is something brewing for C# in the right direction too! — jpe, Aug 08 '12 at 07:16

score 0 · Answer 4 · edited May 23 '17 at 12:02

0

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.

edited May 23 '17 at 12:02

Community

1
1

answered Aug 08 '12 at 06:57

Rafal

12,391
32
54

score 0 · Answer 5 · answered Aug 08 '12 at 07:17

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

score 0 · Answer 6 · answered Jan 19 '18 at 15:02

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

score -1 · Answer 7 · answered Aug 08 '12 at 06:54

-1

Parse it to double:

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

Console.WriteLine(a / b);

answered Aug 08 '12 at 06:54

abc

2,285
5
29
64

I used the same idea. However, I'm not sure `Convert.ToDouble` is possible, but that's a detail. – Jeppe Stig Nielsen Aug 08 '12 at 07:06
BigInteger does not implement IConvertible :-( no such luck! – Matthew Layton Aug 08 '12 at 07:19

BigInteger division in C#

7 Answers7

Linked

Related