Difference between two large numbers C#

Question

Difference between two large numbers C#

There are already solutions to this problem for small numbers:

I'll summarise the answer to them all:

Math.Abs(a - b)

The problem is when the numbers are large this gives the wrong answer (by means of an overflow). Worse still, if (a - b) = Int32.MinValue then Math.Abs crashes with an exception (because Int32.MaxValue = Int32.MinValue - 1):

System.OverflowException occurred
HResult=0x80131516
Message=Negating the minimum value of a twos complement number is invalid.
Source=mscorlib
StackTrace: at System.Math.AbsHelper(Int32 value) at System.Math.Abs(Int32 value)

Its specific nature leads to difficult-to-reproduce bugs.

Maybe I'm missing some well known library function, but is there any way of determining the difference safely?

c#

math

difference

integer-overflow

asked on Stack Overflow Aug 1, 2016 by

c z • edited Mar 12, 2018 by

RBT

4 Answers

As suggested by others, use BigInteger as defined in System.Numerics (you'll have to include the namespace in Visual Studio) Then you can just do:

BigInteger a = new BigInteger();
BigInteger b = new BigInteger();
// Assign values to a and b somewhere in here...
// Then just use included BigInteger.Abs method
BigInteger result = BigInteger.Abs(a - b);

Jeremy Thompson's answer is still valid, but note that the BigInteger namespace includes an absolute value method, so there shouldn't be any need for special logic. Also, Math.Abs expects a decimal, so it will give you grief if you try to pass in a BigInteger.

Keep in mind there are caveats to using BigIntegers. If you have a ludicrously large number, C# will try to allocate memory for it, and you may run into out of memory exceptions. On the flip side, BigIntegers are great because the amount of memory allotted to them is dynamically changed as the number gets larger.

Check out the microsoft reference here for more info: https://msdn.microsoft.com/en-us/library/system.numerics.biginteger(v=vs.110).aspx

answered on Stack Overflow Aug 1, 2016 by

Verbal Kint • edited Aug 1, 2016 by

Verbal Kint

The question is, how do you want to hold the difference between two large numbers? If you're calculating the difference between two signed long (64-bit) integers, for example, and the difference will not fit into a signed long integer, how do you intend to store it?

long    a = +(1 << 62) + 1000;
long    b = -(1 << 62);

long dif = a - b;    // Overflow, bit truncation

The difference between a and b is wider than 64 bits, so when it's stored into a long integer, its high-order bits are truncated, and you get a strange value for dif.

In other words, you cannot store all possible differences between signed integer values of a given width into a signed integer of the same width. (You can only store half of all of the possible values; the other half require an extra bit.)

Your options are to either use a wider type to hold the difference (which won't help you if you're already using the widest long integer type), or to use a different arithmetic type. If you need at least 64 signed bits of precision, you'll probably need to use BigInteger.

answered on Stack Overflow Aug 1, 2016 by

David R Tribble

The BigInteger was introduced in .Net 4.0.

There are some open source implementations available in lower versions of the .Net Framework, however you'd be wise to go with the standard.

If the Math.Abs still gives you grief you can implement the function yourself; if the number is negative (a - b < 0) simply trim the negative symbol so its unsigned.

Also, have you tried using Doubles? They hold much larger values.

answered on Stack Overflow Aug 1, 2016 by

Jeremy Thompson

Here's an alternative that might be interesting to you, but is very much within the confines of a particular int size. This example uses Int32, and uses bitwise operators to accomplish the difference and then the absolute value. This implementation is tolerant of your scenario where a - b equals the min int value, it naturally returns the min int value (not much else you can do, without casting things to the a larger data type). I don't think this is as good an answer as using BigInteger, but it is fun to play with if nothing else:

    static int diff(int a, int b)
    {
        int xorResult = (a ^ b);
        int diff = (a & xorResult) - (b & xorResult);
        return (diff + (diff >> 31)) ^ (diff >> 31);
    }

Here are some cases I ran it through to play with the behavior:

        Console.WriteLine(diff(13, 14)); // 1
        Console.WriteLine(diff(11, 9)); // 2
        Console.WriteLine(diff(5002000, 2346728)); // 2655272
        Console.WriteLine(diff(int.MinValue, 0)); // Should be 2147483648, but int data type can't go that large. Actual result will be -2147483648.

answered on Stack Overflow Aug 1, 2016 by

mars-red

User contributions licensed under CC BY-SA 3.0