The golden number to 5 000 000 000 digits

version española version française

Definition:

When the ratio between two numbers is equal to the ratio between the biggest and the sum of both numbers, that ratio is called the golden number. It's noted φ (phi)

It satisfies the equation (1+φ)/φ=φ, which solves in φ=(1+√5)/2.

Like square root of 5, φ is an irrational number.

It means that its decimal extension i sinfinite and that the digits don't repeat following a periodic scheme.

The 100 first digits of the decimal extension are:

1.6180339887 4989484820 4586834365 6381177203 0917980576
2862135448 6227052604 6281890244 9707207204 1893911374...

The 100 digits between positions 4 999 999 901 and 5 000 000 000 are:

...6089692906 9707937213 9434061731 6077179133 8533106050
1642076415 1471697644 4495847980 4736378983 3399537060...

Conjectures:

There are two main conjectures about phi's digits:

- Is φ a normal number?

A normal number is a number in which the probability of finding each digit is 1/10, finding each 2 digit sequence is 1/100, finding each 3 digit sequence is 1/1000, etc.

See data collected on the 5000000000 first digits (future)

- Is φ a universe number ?

A universe number is a number where you could find whatever digit sequence you want , provided that you look sufficiently far.

See data collected on the 5000000000 first digits (future)

Algorithm used:

First calculate square root of 5 with Newton's algorithm. Then, add 1 and divide by 2.

The square root of 5 can be computed this way:

Use iteration xn <- xn + xn*(5-xn2)/10 beginning with an aproximated value of √5
(for example the number 2)

Complexity of the calculation:

To calculate n digits, as the accuracy doubles at each iteration, log2(n) iterations are needed.
Each iteration is essentially made of two multiplications.
If only the necessary accuracy is used at each iteration, then the calculation can be reduced to a constant number of multiplications (less than 3).
The multiply algorithm used is Karatsuba. Its complexity is O(nlog2(3))=O(n1.585).
That algorithm is not the best in terms of execution time but helps saving computer memory.

Calculation completed on 10/17/2007 after 144 hours.

Verification:

To prevent any design, programming, computation, transmitting or storage error to be introduced into the digits, the following verifying procedure was used:

- calculate 5000000000 digits of φ.
- store the result in a text file.
- calculate an MD5 footprint of the file.
- re-read the file.
- calculate φ2-φ. It should be 1.
- measure real error, which should be less that the expected accuracy.
- As long as the file verifies the stored MD5 footprint, one can be sure of the exactness of the digits.

Verificacion completed on 10/22/2007 after 115 hours.

Computing configuration:

Program written in C language.
Low level multiplication algorithm written in 64 bits assembly.

CPU: AMD Sempron 2400+
Nominal frequency 1.6 GHz, overclocked to 2.4 GHz,
aircooling.

256Ko of L2 cache, 2Gib DDR memory,
20 Gb swap partition

GNU/Linux Ubuntu 7.04 64 bits system,
gcc 4.1.2 compiler

Previous calculations:

1998 : 10 000 000 digits, Simon Plouffe

2000 : 1 500 000 000 digits, Xavier Gourdon and Pascal Sebah

2002 : 3 141 000 000 digits, Xavier Gourdon and Pascal Sebah

The author, Alexis IRLANDE

I've got a PhD in computer science, I am presently assistent professor at the math department of the Universidad Nacional de Colombia, in Bogotá.
I am teaching (among other things) algorithms, cryptography, numerical analysis, networks, computation theory, programmation in C, differential equations and linear algebra.

Contact me: airlande at unal.edu.co