## Singly Exponential vs. Doubly Exponential by Tereso del Rio

Photographs of piles of sand of size 2^n (left) and 2^(2^n) (right)

Singly Exponential vs Doubly Exponential by Tereso del Rio

The first 22 piles (without the big one) containing singly exponential number of grains (2^n)
versus
the first 6 piles (including the big one) containing doubly exponential number of grains (2^(2^n)).

This image comparison illustrates how terrifying doubly exponential behaviour is.

You may have heard about the legend where an ancient King of India promised to gift the inventor of chess one grain of wheat for the first square of the board, two for the second one, four for the third one and so on, thinking that this would be small compared to his fortune. However, due to the fast growth of this exponential sequence, the king could not afford this gift. The mathematical moral of this story is how difficult it is for humans to understand exponential growth.

Some mathematical algorithms, such as Cylindrical Algebraic Decomposition or those needed to compute a Gröbner basis have doubly exponential complexity in the number of variables [1,2]. However, even mathematicians struggle to understand how fast doubly exponential growth actually is. To ease the understanding of this behaviour I decided to illustrate it in the same fashion as in the legend of the chess inventor, using grains of wheat.

For me, this illustration changed the way I perceived doubly exponential behaviour, seeing how after 22 steps the exponential sequence was far from reaching the size of the wheat mountain while the doubly exponential sequence reached it in only six steps.

And even more scary than the fast growth that could be illustrated is the one that couldn't, for producing the seventh pile it would be needed to plant the whole earth, including deserts, mountains and oceans 40 times!!
Moreover, not even all known stars and planets have the surface needed to harvest the wheat needed for the eight pile, which would occupy a sphere of seven times the radius of the earth!!!!
This sphere would need to have 32 million light years of radius when speaking about the ninth iteration and will contain a googol of wheat grains!!!!!!!!!!!!!!!!
Finally, and after this, it doesn't make any sense to continue, the tenth pile, corresponding with 2^(2^9) would occupy a sphere of ten sextillion times the size of the observable universe!^256

 > # All weights are in grams, lengths in meters, surfaces in square meters and volumes in square meters. Measures are based on the first harvest of my cousin. grams_of_wheat_per_sq_meter := 270/130*10^2: weight_of_one_grain := 12.5/512: wheat_density := 769000: earth_surface := 5.1*10^14: sun_radius := 9.96*10^8: light_year := 9.46*10^15: observable_universe_length := 1.3*10^26:
 > surface_needed := proc(n)     description "Returns the number of harvested square meters needed to get 2^(2^n) grains.":     return 2^(2^n)*weight_of_one_grain/grams_of_wheat_per_sq_meter: end proc: volume_needed := proc(n)     description "Returns the volume 2^(2^n) grains occupy.":     return 2^(2^n)*weight_of_one_grain/wheat_density: end proc: radius_of_sphere_needed := proc(n)     description "Returns the radius (in meters) of a sphere made out of 2^(2^n) grains.":     return root(volume_needed(n),3)/Pi/(4/3): end proc:
 > surface_needed(6)/earth_surface; # Four earths
 (1)
 (2)
 (3)
 > evalf(radius_of_sphere_needed(9) / observable_universe_length); # Fourteen sextillion times the size of the observable universe
 (4)

[1] Brown, Christopher & Davenport, James. (2007). The Complexity of Quantifier Elimination and Cylindrical Algebraic Decomposition. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC. 54-60. https://doi.org/10.1145/1277548.1277557.
[2] Magali Bardet, Jean-Charles Faugère, Bruno Salvy (2015). On the complexity of the F5 Gröbner basis algorithm, Journal of Symbolic Computation, 70, 49-70, ISSN 0747-7171,

https://doi.org/10.1016/j.jsc.2014.09.025.
I want to thank my cousin Pablo Borque Almajano for letting me use his grain for mathematical purposes.