Computing With (really) Very Big Numbers

Numbers, they are everywhere, we use them constantly : to measure something, to buy furnitures, to count time... although they are intangible and invisible. But we can't live without them.

Most of us can precisely evaluate a number of up to ten objects at a glance, but when there are more we need to count them one by one or by small groups. We use numbers up to 100 or even 1000 daily, and of course we know that nations and a few people in the world are wealthy up to the billion.

But are there numbers that are so huge that it's difficult both to imagine them and write them? And how can we compute with these numbers?

That is the subject of this Instructable: we will see how to define these numbers, how to write them concisely, how to calculate with them (and what 'calculate' means in this context) and use a microcontroler to deal with them.

When dealing with big numbers, i.e. when those numbers are made of many digits, mathematicians use specific notations, such as the scientific and the engineering notations. We know them because modern calculators use them to represent such big numbers.

Contrary to computers, we humans count using base 10 numbers, probably because we have ten fingers, which makes it easier to visualize the numbers. The scientific notation uses powers of ten to write very big (or very small) numbers: 100 is 10^2, one million is 10^6 meaning a 1 followed by 6 zeros. This enables a compact representation of numbers. Writing 10^x is equivalent to writing a 1 followed by x zeros, by is much more compact.

Humans

Big numbers can be found in nature: as an example there are currently 7 861 304 740 people in the world. This number must have grown since the moment I wrote this Instructable, and you can check it in Worldometer. This is a really big number : 7 billion 8 hundred and more than sixty million people.

That's already a big one, not easy to handle, as most of us have never seen more than maybe 10 000 people at a time. It's more than 4 times the number of seconds I have lived up to now, which is around 1 770 000 000.

Trees

OK, let's look for something bigger: how many trees are there on this planet? Acording to green-future, there are approximately 3.04 trillion trees in the world: 3 040 000 000 000. That's almost 40 000 trees for each human! This estimate was provided a few years ago by scientists at Yale University, who analyzed satellite images.

Insects

Can we find bigger? Let's have a look at insects... Entomologists say that there are 30 million insect species in the world. But how many insects are there? That's not an easy question... Many insect species live in places where human beings can not access. They have remarkable reproductive abilities which lead to huge numbers of offspring. In fact, the queen of an African termite can lay one egg every 2 seconds which is 43 000 eggs in a day. A housefly can have 190 quintillion descendants in just 5 months.

Wait a minute! "Quintillion" ??? In English, a quintillion is equal to 10^18, a 1 followed by 18 zeros (one billion of billions). By the way, this wikipedia web page will give you more details about the names of big numbers.

So how many insects? Statistics indicates that there are about 200 million insects for one human being at any time. That's of course an approximation, as both the number of humans and the number of insects vary very quickly in time. To calculate it, let's use the scientific notation : 200 million is 200 followed by 6 zeros, so 2 * 10^8. And 8 billion humans is 8 * 10^9.

Multiplying these numbers can be made in 2 steps :

1. multiply the mantissae : 2 times 8 is 16
2. add the exponents : 9 plus 8 is 17

So we get the result : 16 * 10^17 insects on Earth, which is 1.6 quintillion or 160 millions of billion.

Sand

Can we find bigger? Let's talk about sand: how many grains of sand are there in the world? Not an easy one also... but it was dealt with here. The author imagined that all the grains of sand are spherical and of equal size and that they form an even layer, 10 cm thick, over the entire surface of the earth. Why did they chose that hypothesis? To that question, I'll answer 'why not?'...

The surface of the Earth is roughly 510 million square km, which leads to a volume of sand of 5 * 10^13 cubic metres. Divide this by the average number of a grain of sand in a cubic metre, this leads to 6.63 * 10^22 grains of sand on Earth.

For those familiar with it, this number looks very similar to the Avogadro number (6.02 * 10^23, a big one too) which is the number of particles in one mole of a given substance (22.4 liters for a gaz).

When we compare all those numbers, using the scientific notation, the difference does not seem very impressive. 10^17 insects, 10^22 grains of sand, the difference is only a 5 in the exponent... Not a big deal.

But as the difference lies in the exponent, you must be aware that we are talking of a ratio of 10^5, which is 100 thousand. So there are about 100 000 grains of sand for each insect in the world, and 100 000 times 200 million grains of sand for each human being on Earth. That is 20 000 billion grains for all of us !!! All your grains would fit in 1/5 of a cubic metre, which is a cube of 60 cm side. That's not very big, but put 8 billion of these cubes next to the others and you'll have all the sand of the world...

Atoms

Bigger? You can see that to find bigger numbers, you just need to count smaller things. What smaller thing can we find? Let's have a look at atoms: atoms are very small things. The 'standard' size of an atom (for a metal) is roughly 0.2 nanometers. A nanometer is the billionth part of a metre: there are one billion nanometers in a meter. To visualize that, let's say that the diameter of a human hair strand is 1/1000 of an inch: there are 40 million nanometers in the diameter of a human hair strand...

So how many atoms on Earth? The mass of the Earth is roughly 6 * 10^27 grams (our new record number so far). Taking into account the atomic structure of the core of the Earth (35% iron, 30% oxygen, 15% silicon, magnesium, etc) scientists have calculated the share of weight of all these elements, and found the number of atoms on Earth to be 1.3 * 10^50. This would be called 130 quindecillion...

More?

To find more, we just need to count even smaller things in a bigger space. How many atoms are there in the known universe? This question enables us to go out of our planet and explore the universe, and its structure. You all know that the Earth is part of the solar system, which is part of the Milky Way, our galaxy. Astrophysicians estimate that they are100 billion galaxies in the universe (10^11) which are gathered in groups, and those groups in clusters, sometimes making superclusters. Anyways, how many atoms are there?

On average, each galaxy contains about one hundred sextillion or 10^23 stars. Stars come in different sizes, but a typical star, like the Sun, has a mass of around 2 x 10^30 kilograms. Dividing this mass by the mass of an atom of hydrogen, which is the most present element in the universe (74%), you find that the Sun contains approximately 10^57 atoms of hydrogen. Multiply both numbers and you get an evaluation of the number of atoms in the universe : 10^80. This number has currently no name : I propose to call it one Atomillion, (although some people call it the Eddington number).

Now it seems difficult to find bigger numbers with a physical meaning. We could count the number of nanometers in the width of our galaxy or even in the entire universe, but that doesn't have any meaning.

Anyways, let's have a look : our galaxy's width is roughly 80 000 light years. A light year is the distance travelled by light in one year. Light travels at 300 000 kilometres per second, so one light year is 9 460 800 000 000 km, almost 10 * 10^12 kilometres, or 10 * 10^21 nanometres. Multiply this by 80 000 leads to the deceving number of 8 * 10^26 nanometres form one side of the galaxy to the other. An estimate of the size of the universe is 90 billion light years, only 1.12 million times the size of the Milky Way. So we get 900 * 10^30 nanometres (900 nonillion).

Even if we count in Planck's length instead of nanometres, we obtain a mere 10^59, which is still smaller than before.

So better forget about physical meaning, and get back to pure maths. In 1940, the mathematician Edward Kasner popularized a very big number by the name of Googol (not to be confused with the name of a well known company), equal to 10^100. Wikipedia says 'a googol has no special significance in mathematics', it's only a one followed by 100 zeros.

However, mathematics have a very efficient way of producing very big numbers: the factorial function. The factorial of a number n, denoted by n!, is the product of all positive integers less than or equal to n.

n! = 1 * 2 * 3 * ... * (n-1) * n

As an example, 70! is close to the Googol : 70! = 1.197 857 166 996 989 ... * 10^100.

Factorials are used in statictics and combinatorics: there are n! different ways of arranging n distinct objects into a sequence. So if you want to park 100 different cars in a parking lot, there are 100! possibilities of doing it, and this number is close to 9 * 10^157, almost 10^158.

This is a bigger number, which we can relate to something concrete and practical. Imagine the parking of your preferred supermarket, estimate the number of cars parked in it and count the ways of arranging them in the different spots. I guess sometimes there are even more than 500 cars: this leads to 500! = 1. 2 * 10^1134 ...

This is WAY bigger than the atomillion! And it can be found on Earth, at the corner of the street! In fact, this number is so big that there is no way of describing it. If you are familiar with the scientific notation, no problem. Otherwise, comparing it to the atomillion is impossible. I can tell you that 500! is 10^1054 times greater than the atomillion, but... how can you handle this new number?

One way to understand its size, would be to relate it to something we can measure. Let's look first to 100! How long would it take to test all possibilities if we could change every nanosecond? It would take around 30 * 10^140 years, which is huge compared to the age of the universe (16 billion years, that is 16 * 10^9).

How about writing this number on paper sheets? Imagine we take a white paper and write 100 digits on each line, 50 lines on each side: this leads to 100 * 100 digits on both sides of the sheet, which is 10 000. To write all the digits of 100!, we would need 10^154 sheet of paper. You need 200 sheets to reach an inch in thickness, almost 8 000 sheets for one metre. So the pile of paper needed to fully write 100! is around 10^150 metres high! Compared to the size of the known universe... we would need to align 10^123 universes to fit this book of 100! We actually need more universes than there are atoms in this universe.

That's an interesting paradox: we can imagine how to arrange 100 cars in 100 park places, but the universe is way too small to write the number of possibilities.

Standard scientific calculators can handle numbers up to 9.9999 *10^99. I use one that can compute 9999! = 2.8 * 10^35655 but cannot compute 10000!

Computers can handle 32-bit single precision floating point numbers up to 2^128 = 3.4 * 10^38 and 64-bit double precision numbers up to 2 ^1024 roughly equal to 1.79 * 10^308. They cannot compute the factorial above 170.

But we have seen above much greater numbers, and it's easy to think of even bigger ones. So how to compute with them and how to display them?

Use the scientific notation

The basic idea to manipulate big numbers is to use the scientific notation, which displays the number as the product of the mantissa and a power of 10. The main recipe is the following:

1. write the numbers using the scientific notation,
2. compute your operation separately on the mantissae and the exponents,
3. build the result using the results of step 2.

This is what we used earlier when we calculated the number of sheets of paper necessary to write all the digits of 100!

• 10^4 digits on a single sheet of paper,
• 8 * 10^3 sheets in one metre,
• one light year is 10 * 10^15 metres
• the universe is 90 * 10^9 light years wide
• so we can write 10^4 * 8 * 10^3 * 10 * 10^15 * 90 * 10^9 = (8*10*90) * 10^(4+3+15+9) = 7200 * 10^31 digits in the width of the universe
• so we need 9 * 10^157 / (7200 * 10^31) = 9/7200 * 10^(157-31) = 0.00125 * 10^126 = 10^123 universes to write all the digits of 100!

As another example, how much is the factorial of 100! ...? This is factorial of 9 * 10^157 or (9 * 10^157)! This number is actually equal to 10^(1.470074060553 * 10^160). It can be easily computed using an approximation of the factorial function, which is quite accurate for big numbers: the Stirling formula.

Compute in scientific notation

This formula is interesting because it provides the natural logarithm of the factorial of n. And when dealing with a number displayed using the scientific notation, the exponent is related to the logarithm in base 10 (a.k.a. log_10) of the number.

n = 10^(log_10 n)

log_10 n is the sum of an integer and a fractional part: log_10 n = int_10 + frac_10. Using the rules of exponentiation, we get

n = 10^(int_10 + frac_10) = 10^(int_10) * 10^(frac_10)

The first component 10^(int_10) is the exponent part of the scientific notation, the second one is the mantissa.

Let's apply this to a simple example: take n = 5500. log_10 n = 3.740362689... as any scientific calculator can confirm. int_10 is here equal to 3 and frac_10 to 0.740362689. So we can write

5500 = 10^3 * 10^0.740362689 where this last number is 5.5 : 5500 = 5.5 * 10^3.

Bigger factorials

Back to Stirling, using a little maths, this formula can be changed to provide the logarithm in base 10 of n!. We just have to apply the above process and find the integer and fractional parts to obtain the desired value.

So we can easily create very big numbers by stacking the factorials, such as: 100!!!!!! (6 factorials).

100!!!!!! = 10^( 10^( 10^( 10^( 10^(1.470074060553 10^160)))))

I see this notation as a building with 7 floors, each one written as M * 10^E, 'M' being the mantissa, and 'E' the exponent. When stacking floors, the exponent is replaced by the notation of the next floor. For 3 and 4 floors, we have:

• M1 * 10^( M2 * 10 ^E2)
• M1 * 10^( M2 * 10 ^(M3 * 10^E3))

This shows that we can define a big number by the number of floors, the set of mantissae and the exponent of the last floor. This will be the basis of the code in the next step.

The problem with multiple factorials is that, after the first one, the process only consists in stacking the results using 10^ of the previous one. It's not really exciting... but it shows one significant thing related to such big numbers: after a certain limit, the mantissae of each floor do not have any real meaning.

Exponentiation

Another way of generating very big numbers is the exponentiation. 'b^n', spelled 'b' to the power of 'n', is equal to 'b' multiplied by itself 'n' times:

So what would be b^n^m ? There are 2 ways of seeing that:

1. The usual way is (b^n) multiplied by itself 'm' times
2. Or, 'b' multiplied by itself 'n^m' times

Which one leads to the biggest numbers? Have a guess, and read the rest...

Let's try an example: 2^3^4

1. The first way is (2^3)^4 = 8^4 = 4 096
2. The second way is 2^(3^4) = 2^81 = 2 417 851 639 229 349 412 352 which is roughly 2 * 10^24 !!!

So obviously, we get very big numbers if we compute the exponents from right to left. This will be implemented in the code in the next step. If I want to compute 2^3^4^5 this way, it's beyond the capacity of my calculator. So just by using 4 very small digits, it is possible to compute a number as big as 10^(1.12402146607 * 10^488) ... You can verify this in the next step.

I have written a C++ code that does very simple computation on big numbers. First create a folder called BigNumbers and put inside the attached files.

To run the code, first open the BigNumbers.ino file with the arduino IDE, connect your ESP32 and upload the code. The serial terminal displays a welcome message and waits for your operation (choose 115200 baud as communication rate).

A few operations are available for now:

• addition, multiplication,
• tree exponentiation,
• factorial and multiple factorials,
• comparison.

To input an operation, just type it in the input zone. The result will be displayed in the display zone. Using the up arrow of your keyboard will recall the previous operation.

The code uses a simple syntax to recognize the operation. Here are the main features:

• Type h or ? to get some help,
• Use e or E for the exponent,
• Use ^ or p or P (for 'power') for exponentiation,
• + and *
• Use <, > or = for comparison

Allowed characters are: digits, h ? e E ^ p P + * ! . < > = a A. All unknown characters are ignored.

Here are a few examples of big numbers that you can type:

• 12245
• 1e45 is 1 * 10^45
• 3e45e56 is 3 * 10 ^ (45 * 10^56)
• 3.45 E 4.56 e 6.78 E 7.89 is 3.45 * 10^( 4.56 * 10^(6.78 * 10^7.89) : in this case, the code will provide a simplification of the number
• 3^4^5^6 is 3^(4^(5^6)) as seen earlier (power tower)
• 3p4P5^6 is the same as above.

There are 2 ways of using it.

1: Type the operations

The simplest way is to type the operation you want, and the code will (try to) recognize it and provide the result. This is limited to simple calculations.

For example, you can enter:

• 12345 !!
• but not (123 !! + 456 ! ) !

Entering 12345!! will answer:

> 12345!!
  1.234500000000 10^4 !! =
 10^(1.554806049671 10^45155)

Entering 3^4^5^6 answers:

> 3^4^5^6
10^(7.3450247455 10^9407)

An addition: 2e3e4+3e3.00001e4 leads to

> 2e3e4+3e3.00001e4
2.000000000050 10^30000 + 3.776776235369 10^30000 
= 5.776776235420 10^30000

And a multiplication:

> 2e3e4*4e5e6
2.000000000050 10^30000 * 4.000000000000 10^5000000 
= 8.000000000000 10^5030000

For the comparison:

> 2e3e4e5>3e4e5
2.000000000000 10^(3.000000000804 10^400000) > 3.000000000804 10^400000 
true

2: Program your operations

Another way is to use the API, i.e. the available functions, to deal directly in C with the big numbers and do more complex calculations.

To create an instance of a big number, first declare it:

BigNumber N;

Then you can affect a value to it using the set function. To set the value to 2 * 10^( 34 * 10^(1.2 * 10^58.6) it's as easy as

N = set({2, 34, 1.2, 58.6});

BigNumber are just a regular vectors of integers on 64 bits:

using BigNumber = std::vector<int64_t>;

so if you are familiar with them, you can also use the associated functions (such as push_back). I chose this kind of storage to keep the maximum possible accuracy.

To display the value of a big number, there are 2 possibilities:

displayBigNumber(N);
displayStruct(N);

The first one displays the value of the big number using the scientific notation. The second shows the structure of the number, with all floors and mantissa / exponent.

For example:

N = set({2, 34, 1.2, 58.6});
displayBigNumber(N); Serial.println();

displays on the monitor:

2.0000000000 10^(3.4000000000 10^(4.7772860466 10^58))

and

displayStruct(N); Serial.println();

provides:

4 floors
mant: 2.0000000000000000
floor 2 expo: 3.400000000000
floor 3 expo: 4.777286046641
floor 4 expo: 58

You can see that the fractional part of the last exponent has been moved to the previous floor: the value 1.2 has become 4.777. displayBigNumber accepts an integer as second argument to limit the number of digits displayed.

Available functions are:

// operators

• bool isEqual (BigNumber const &, BigNumber const &);
• bool lessThan (BigNumber const &, BigNumber const &);
• bool lessEqual (BigNumber const &, BigNumber const &);
• bool greaterThan (BigNumber const &, BigNumber const &);
• bool greaterEqual (BigNumber const &, BigNumber const &);

// binary operations

• BigNumber bigAdd (BigNumber &, BigNumber &);
  
• BigNumber bigMult (BigNumber &, BigNumber &);
• BigNumber bigPower (BigNumber &, BigNumber &);

// unary operations

• BigNumber bigStirling (BigNumber &);

and for the display:

• void displayBigNumber (BigNumber const &, uint8_t = 10);
• void displayStruct (BigNumber const &);

As an example:

N1 = set({2, 7, 23, 36, 89});
N = bigStirling(N1);
displayBigNumber(N1, 2); Serial.print("! =");
displayBigNumber(N, 10); Serial.println();

will answer:

2.00 10^(7.00 10^(2.30 10^(3.60 10^(9.00 10^1)))) ! = 10^(1.4000000000 10^(7.0000000000 10^(2.3000000000 10^(3.6000000000 10^90))))

To compute the value of (123 !! + 456 ! ) !, you can run the following code:

BigNumber N1, N2, N3, N4, N;
N1 = set({123});
N2 = bigStirling(N1);
N3 = bigStirling(N2);
N1 = set({456});
N2 = bigStirling(N1);
N4 = bigAdd(N2, N3);
N = bigStirling(N4);
displayBigNumber(N, 10); Serial.println();

and it will answer:

10^(2.4847173221 10^(2.4847173221 10^207))

Knuth arrow notation

This notation for very large integers, introduced by Donald Knuth in 1976, as an extension to the standard exponentiation. It quickly leads to very large number, sometimes out of the scope of this program. Indeed, in the .h file, there is a parameter that can be changed:

#define MAXFLOORS 100

It's the maximum number of 'floors' the program can handle. As an example, the previous result has 4 floors (with numbers 1, 2.48, 2.48, 207). If you want bigger numbers, just increase the value of this parameter, there is no real physical limit as the memory of the ESP32 is very large: you can think one million floors, but it would be difficult to display them.

In Knuth's notation, one up-arrow is similar to the normal exponentation.

But 2 arrows are much more powerful, as shown in the following example:

I implemented the Knuth's notation for 2 and 3 arrows using the character 'a': the previous example can be computed inputting 2aa4. The second argument (after the aa) must remain under 250 to prevent overflows. Use it with precautions...

Notation with 3 arrows leads to numbers too big for this programme, only 2aaa3 and 3aaa2 are possible to compute...

I hope this has given you new insights about (big) numbers and that you will enjoy playing with them. For more information, please have a look at the wiki of Googology, an online encyclopedia and community dedicated to large numbers. Another interesting website was made by Lawrence Hollom, with interesting tentative names for big numbers families.

Have fun!