How do programming languages handle huge number arithmetic

Question

For a computer working with a 64 bit processor, the largest number that it can handle would be 2⁶⁴ = 18,446,744,073,709,551,616. How does programming languages, say Java or be it C, C++ handle arithmetic of numbers higher than this value. Any register cannot hold it as a single piece. How was this issue tackled?

Answer 1

Programming languages that handle truly massive numbers use custom number primitives that go beyond normal operations optimized for 32, 64, or 128 bit CPUs. These numbers are especially useful in computer security and mathematical research.

The GNU Multiple Precision Library is probably the most complete example of these approaches.

You can handle larger numbers by using arrays. Try this out in your web browser. Type the following code in the JavaScript console of your web browser:

The point at which JavaScript fails

console.log(9999999999999998 + 1)
// expected 9999999999999999
// actual  10000000000000000  oops!

JavaScript does not handle plain integers above 9999999999999998. But writing your own number primitive is to make this calculation work is simple enough. Here is an example using a custom number adder class in JavaScript.

Passing the test using a custom number class

// Require a custom number primative class
const {Num} = require('./bases')

// Create a massive number that JavaScript will not add to (correctly)
const num = new Num(9999999999999998, 10)

// Add to the massive number
num.add(1)

// The result is correct (where plain JavaScript Math would fail)
console.log(num.val)  // 9999999999999999

How it Works

You can look in the code at class Num { ... } to see details of what is happening; but here is a basic outline of the logic in use:

Classes:

• The Num class contains an array of single Digit classes.
• The Digit class contains the value of a single digit, and the logic to handle the Carry flag

Steps:

1. The chosen number is turned into a string
2. Each digit is turned into a Digit class and stored in the Num class as an array of digits
3. When the Num is incremented, it gets carried to the first Digit in the array (the right-most number)
4. If the Digit value plus the Carry flag are equal to the Base, then the next Digit to the left is called to be incremented, and the current number is reset to 0
5. ... Repeat all the way to the left-most digit of the array

Logistically it is very similar to what is happening at the machine level, but here it is unbounded. You can read more about about how digits are carried here; this can be applied to numbers of any base.

Answer 2

More-or-less the same way that you do. In school, you memorized single-digit addition, multiplication, subtraction, and division. Then, you learned how to do multiple-digit problems as a sequence of single-digit problems.

If you wanted to, you could multiply two twenty-digit numbers together using nothing more than knowledge of a simple algorithm, and the single-digit times tables.

Answer 3

Ada actually supports this natively, but only for its typeless constants ("named numbers"). For actual variables, you need to go find an arbitrary-length package. See Arbitrary length integer in Ada

Answer 4

Most languages store them as array of integers. If you add/subtract two to of these big numbers the library adds/subtracts all integer elements in the array separately and handles the carries/borrows. It's like manual addition/subtraction in school because this is how it works internally.

Some languages use real text strings instead of integer arrays which is less efficient but simpler to transform into text representation.

Answer 5

There are lots of specialized techniques for doing calculations on numbers larger than the register size. Some of them are outlined in this wikipedia article on arbitrary precision arithmetic

Low level languages, like C and C++, leave large number calculations to the library of your choice. One notable one is the GNU Multi-Precision library. High level languages like Python, and others, integrate this into the core of the language, so normal numbers and very large numbers are identical to the programmer.

Answer 6

Think of one machine-size number as a digit and apply the algorithm for multi-digit multiplication from primary school. Then you don't need to keep the whole numbers in registers, just the digits as they are worked on.

Answer 7

As a thought experiment, imagine the numbers stored as a string. With functions to add, multiply, etc these arbitrarily long numbers.

In reality these numbers are probably stored in a more space efficient manner.

Answer 8

You assume the wrong thing. The biggest number it can handle in a single register is a 64-bits number. However, with some smart programming techniques, you could just combined a few dozens of those 64-bits numbers in a row to generate a huge 6400 bit number and use that to do more calculations. It's just not as fast as having the number fit in one register.

Even the old 8 and 16 bits processors used this trick, where they would just let the number overflow to other registers. It makes the math more complex but it doesn't put an end to the possibilities.

However, such high-precision math is extremely unusual. Even if you want to calculate the whole national debt of the USA and store the outcome in Zimbabwean Dollars, a 64-bits integer would still be big enough, I think. It's definitely big enough to contain the amount of my savings account, though.

Answer 9

In general, the language itself doesn't handle high-precision, high-accuracy large number arithmetic. It's far more likely that a library is written that uses alternate numerical methods to perform the desired operations.

For example (I'm just making this up right now), such a library might emulate the actual techniques that you might use to perform that large number arithmetic by hand. Such libraries are generally much slower than using the built-in arithmetic, but occasionally the additional precision and accuracy is called for.