Sections

Square root, the Babylonian way
The Golden Ratio
The big number

This post is part of a series. Other posts are:

Once we learned how to handle numbers with many decimals (as much as we want, as long as they fit in the computer’s memory), we can try to calculate other irrational values. The rationals are easy.

Maybe the first irrational number that people discovered was \(\sqrt{2}\). This is the length of the diagonal of a square of side 1, as can be seen using Pythagoras’ Theorem. One legend says that Hippasus, a student of Pythagoras, realized that \(\sqrt{2}\) cannot be represented by a rational number, the only ones that the ancient Greeks accepted as valid. According to the legend, the other students killed Hippasus to hide the secret. \(\sqrt{2}\) was a mortal trick

The legend is probably false. In fact we do not know if Pythagoras ever proved the theorem, and we have a lot of evidence that it was know many centuries earlier in India and Babylon. We should not forget that Babylonians had a developed mathematical science, and we keep rediscovering their results.

One of the tools created in Babylon¹ more than 4000 years ago was a method to calculate square roots. I think my dad taught me this method when I was teenager. I’ve seen that MIT professors use this as an example in their first class of computer science and programming, and I like the way they tell the story. It goes like this

To find the square root of \(a,\) start by guessing it. Call this guess \(x.\)
See if \(x^2\) is close enough to \(a.\) One good way to test that is to see if \(x\) and \(a/x\) are similar. If so, finish.
Otherwise, then either \(x\) is larger than \(\sqrt{a}\) and \(a/x\) is smaller, or the other way around. In any case, the result is somewhere in the middle. Thus, an improved guess is their average.
Replace \(x\) by \((x+a/x)/2\) and jump back to step 2.

Basically, we just need to add and divide, as we did in our previous post. There is only one detail that needs our attention: dividing \(a\) by \(x.\) This time both numbers represent real number with many decimals. In the previous post we only divided by integers. So if we have

a = 10**40
x = 3 * 10**40

then the division cannot be

a // x

Instead we have to insert more “decimals” before dividing

a*10**40 // x

3333333333333333333333333333333333333333

With this issue in mind, we are ready to replicate the wise Babylonians.

Square root, the Babylonian way

We begin by choosing the precision num_decimals, and creating a variable one representing the number 1 as a long integer.

num_decimals = 80
one = 10**num_decimals

We need to find an initial guess for the square root of \(a\). If \(a>1\) then its square root will be less than a, and will be somewhere between 1 and \(a\). If \(a<1\) then the square root will be larger than \(a,\) and be between \(a\) and 1. Thus, one easy solution is to guess that the square root is near the average of \(a\) and 1. We store that guess in y and we test for the square root of 2.

a = 2*one
y = (a + one) // 2
x = a * one // y

We will update x and y on each step. It can happen that these two numbers are close but do not change after updating. The Babylonians were wise when they asked us to verif if the two results are “close enough”. In this case we can say that x and y are close enough if their only difference is the last digit. In our represenation, all but the last digits are the same if abs(x-y)>10.

while abs(x-y)>10:
    y = (x + y) // 2
    x = a * one // y
print(x)

141421356237309504880168872420969807856967187537694807317667973799073247846210704

Is this result correct? It is easy to test. We only need to see if x*x is 2.

print(x*x//one)

200000000000000000000000000000000000000000000000000000000000000000000000000000000

Close enough.

The golden ratio

Another number that appears often in books and other social media (because books were the social media of ancient times) is the golden ratio², usually represented by the greek letter \(φ\).

Take a segment of any length 𝐿 and split it in two parts, a small of lenght \(𝑎\) and a large one of length \(𝑏\). Choose \(𝑎\) and \(𝑏\) carefully so the proportion of the large part to the small one is the same as the total segment to the large part. That proportion is \(φ\). In other words \[φ=\frac{b}{a}=\frac{a+b}{b}.\]

Let’s find the value of \(φ\). From the first equation we deduce that \(b=φ a.\) Then \[φ=\frac{a+φa}{φa}=\frac{1+φ}{φ}\] and therefore \(φ\) does not depend on 𝑎 or 𝑏. Instead \(φ\) is the solution of the equation \[φ^2-φ-1=0.\]

Using the second-degree formula we learned in high school, we find that³ \[φ=\frac{1+\sqrt{5}}{2}.\] Let’s calculate it using our new tool.

a = 5*one
y = (a + one) // 2
x = a * one // y
while abs(x-y)>10:
    y = (x + y) // 2
    x = a * one // y

φ = (one + x)//2
print(φ)

161803398874989484820458683436563811772030917980576286213544862270526046281890245

This is real gold.

The big number

Let’s go for the big number. We will calculate ten thousand decimals of the square root of two.

num_decimals = 10000
one = 10**num_decimals
a = 2*one
y = (a + one) // 2
x = a * one // y
while abs(x-y)>10:
    y = (x + y) // 2
    x = a * one // y

If everything is right, we should have the result in x. It will be boring to print it here in this webpage. Instead, we write it into a file that you can download if you like.

with open("square-root-of-2.txt", mode="w") as out:
    print(x, file=out)

Now the result should be here. I hope the Pythagorians do not get angry with me.