Calculators working with larger numbers than 18446744073709551615-CodePudding

When I Initialize a ulong with the value 18446744073709551615 and then add a 1 to It and display to the Console It displays a 0 which is totally expected. I know this question sounds stupid but I have to ask It. if my Computer has a 64-bit architecture CPU how is my calculator able to work with larger numbers than 18446744073709551615? I suppose floating-point has a lot to do here. I would like to know exactly how this happens.

Thank you.

CodePudding user response：

working with larger numbers than 18446744073709551615

"if my Computer has a 64-bit architecture CPU" --> The architecture bit size is largely irrelevant.

Consider how you are able to add 2 decimal digits whose sum is more than 9. There is a carry generated and then used when adding the next most significant decimal place.

The CPU can do the same but with base 18446744073709551616 instead of base 10. It uses a carry bit as well as a sign and overflow bit to perform extended math.

CodePudding user response：

I suppose floating-point has a lot to do here.

This is nothing to do with floating point. ; you say you're using ulong, which means your using unsigned 64-but arithmetic. The largest value you can store is therefore "all ones", for 64 bits - aka UInt64.MaxValue, which as you've discovered: https://docs.microsoft.com/en-us/dotnet/api/system.uint64.maxvalue

If you want to store arbitrarily large numbers: there are APIs for that - for example BigInteger. However, arbitrary size cones at a cost, so it isn't the default, and certainly isn't what you get when you use ulong (or double, or decimal, etc - all the compiler-level numeric types have fixed size).

So: consider using BigInteger

CodePudding user response：

You either way have a 64 bits architecture processor and limited to doing 64 bits math - your problem is a bit hard to explain without taking an explicit example of how this is solved with BigInteger in System.Numerics namespace, available in .NET Framework 4.8 for example. The basis is to 'decompose' the number into an array representation. mathematical expression 'decompose' here meaning : "express (a number or function) as a combination of simpler components."

Internally BigInteger uses an internal array (actually multiple internal constructs) and a helper class called BigIntegerBuilder. In can implicitly convert an UInt64 integer without problem, for even bigger numbers you can use the operator for example.

BigInteger bignum = new BigInteger(18446744073709551615); 
bignum  = 1;

You can read about the implicit operator here: https://referencesource.microsoft.com/#System.Numerics/System/Numerics/BigInteger.cs

 public static BigInteger operator  (BigInteger left, BigInteger right)
    {
        left.AssertValid();
        right.AssertValid();
 
    if (right.IsZero) return left;
    if (left.IsZero) return right;

    int sign1 =  1;
    int sign2 =  1;
    BigIntegerBuilder reg1 = new BigIntegerBuilder(left, ref sign1);
    BigIntegerBuilder reg2 = new BigIntegerBuilder(right, ref sign2);

    if (sign1 == sign2)
        reg1.Add(ref reg2);
    else
        reg1.Sub(ref sign1, ref reg2);

    return reg1.GetInteger(sign1);
}

In the code above from ReferenceSource you can see that we use the BigIntegerBuilder to add the left and right parts, which are also BigInteger constructs.

Interesting, it seems to keep its internal structure into an private array called "_bits", so that is the answer to your question. BigInteger keeps track of an array of 32-bits valued integer array and is therefore able to handle big integers, even beyond 64 bits.

You can drop this code into a console application or Linqpad (which has the .Dump() method I use here) and inspect :

BigInteger bignum = new BigInteger(18446744073709551615); 
bignum.GetType().GetField("_bits", 
BindingFlags.NonPublic | BindingFlags.Instance).GetValue(bignum).Dump();

A detail about BigInteger is revealed in a comment in the source code of BigInteger on Reference Source. So for integer values, BigInteger stores the value in the _sign field, for other values the field _bits is used.

Obviously, the internal array needs to be able to be converted into a representation in the decimal system (base-10) so humans can read it, the ToString() method converts the BigInteger to a string representation.

For a better in-depth understanding here, consider doing .NET source stepping to step way into the code how you carry out the mathematics here. But for a basic understanding, the BigInteger uses an internal representation of which is composed with 32 bits array which is transformed into a readable format which allows bigger numbers, bigger than even Int64.

// For values int.MinValue < n <= int.MaxValue, the value is stored in sign
// and _bits is null. For all other values, sign is  1 or -1 and the bits are in _bits