Drip algorithm

A drip algorithm is an algorithm for calculating mathematical constants such as the circle number or Euler's number , in which the digits are calculated one after the other and then no longer needed, so to speak trickle out. Such algorithms often get by with small whole numbers for the calculation, so an implementation has no problems with rounding errors and does not require long number arithmetic . The first algorithm of this type is considered to be an algorithm for calculating the Euler number, published by AHJ Sale in 1968. The English name spigot algorithm (literally: tap algorithm ) appears for the first time in 1991 by Stanley Rabinowitz, who specified a drip algorithm for . ${\ displaystyle \ pi}$ ${\ displaystyle e}$ ${\ displaystyle \ pi}$

Basic principle

Drip algorithms are based on the following simple algorithm for determining the digits:

Find the integer part of the number and write it down.
Replace the number with the fractional part, so subtract the whole number part.
Multiply by 10.

If you repeat these steps, the first step results in the part before the decimal point, and in all further steps the next decimal number. If you multiply with another number instead of 10, the representation does not result in the decimal system , but analogously in any place value system .

Often, droplet algorithms are based on mixed bases . While the usual representation of Euler's number is ultimately a conventional notation for ${\ displaystyle e = 2 {,} 718 \ dots}$

{\ displaystyle e = 2 + {\ tfrac {1} {10}} (7 + {\ tfrac {1} {10}} (1 + {\ tfrac {1} {10}} (8+ \ dots)) )}

,

the following representation can be obtained from the formula : ${\ displaystyle e = \ sum _ {n = 0} ^ {\ infty} {\ frac {1} {n!}}}$

{\ displaystyle e = 2 + {\ tfrac {1} {2}} (1 + {\ tfrac {1} {3}} (1 + {\ tfrac {1} {4}} (1+ \ dots)) )}

This is an extension of the faculty-based number system to real numbers, in which Euler's number can be written as . ${\ displaystyle e = 2 {,} 111 \ dots}$

In this representation, the integer and fractional part of a number can be determined just as easily as in the ordinary decimal system by taking the part before and after the decimal point. The multiplication can be as usual perform only the transfer the mixed base is observed.

Droplet algorithm for Euler's number

This idea results in the following algorithm for calculating the decimal places of the Euler number in the decimal system: ${\ displaystyle n}$

Determine so that it has at least positions. ${\ displaystyle m}$ ${\ displaystyle m!}$ ${\ displaystyle n}$
Write down two rows A and B with columns each . The first column remains free, row A is filled with numbers 1, row B with numbers from 2 to . ${\ displaystyle m}$ ${\ displaystyle m-1}$ ${\ displaystyle m}$
Note another line, in the first column a 2, then the 1 times. The 2 is already the number before the comma. ${\ displaystyle m-1}$
Add another line below and fill it in from right to left using the following steps:
1. Find the next number by doing the following:
  1. Multiply the number in the current column in the previous row by 10 and add the carry from the previous column (for the column on the far right, the carry is 0).
  2. Divide the result with remainder by the number on row B and write down the remainder.
  3. Multiply the quotient by the number from row A, this is the carry over for the next column. (Since the number in row A is always 1 here, the multiplication can be omitted.) Repeat step 4.1 until the second column is filled.
2. Note the carryover from the second column in the first column, it is the next digit of . Repeat step 4 until you have calculated digits. ${\ displaystyle e}$ ${\ displaystyle n}$

example

The following example carries out the algorithm for the calculation of 4 decimal places , whereby the choice is made because it has the necessary 4 places for the application of this drip algorithm: ${\ displaystyle m = 7}$ ${\ displaystyle 7! = 5040}$

A.		1	1	1	1	1	1
B.		2	3	4th	5	6th	7th
	2	1	1	1	1	1	1
	7th	0	1	0	1	5	3
	1	1	1	3	4th	0	2
	8th	0	1	2	0	2	6th
	2	1	0	0	4th	4th	4th

The 3 in the fourth line on the far right is the remainder of 10 when divided by 7. This results in a carry 1, so that in the next column 11 is divided by 6, which results in the remainder 5 and the carry 1. The other entries are calculated accordingly.

Droplet algorithm for π

Stanley Rabinowitz found a similar algorithm for calculating . It is based on a mixed broken basis, the following applies: ${\ displaystyle \ pi}$

{\ displaystyle \ pi = 2 + {\ tfrac {1} {3}} (2 + {\ tfrac {2} {5}} (2 + {\ tfrac {3} {7}} (2+ \ dots) ))}

So with respect to the mixed fractional basis ${\ displaystyle (1; {\ tfrac {1} {3}}, {\ tfrac {2} {5}}, {\ tfrac {3} {7}}, \ dots)}$ ${\ displaystyle \ pi = 2 {,} 222 \ dots}$

The added difficulty here is that the “fractional part” can be larger than 1, so that the whole number and fractional part can no longer be determined so easily. This leads to the following algorithm to determine decimal places of: ${\ displaystyle n}$ ${\ displaystyle \ pi}$

Determine sufficiently large, mostly enough . ${\ displaystyle m}$ ${\ displaystyle m = \ lfloor 10 (n + 1) / 3 \ rfloor}$
Write down two rows A and B with columns each . The first column remains free, row A is filled with the numbers from 1 to , row B with the odd numbers from 3 to . ${\ displaystyle m}$ ${\ displaystyle m-1}$ ${\ displaystyle 2m-1}$
Write down another line with times the number 2. ${\ displaystyle m}$
Add another line below and fill it in from right to left using the following steps:
1. Find the next number by doing the following:
  1. Multiply the number in the current column in the previous row by 10 and add the carry from the previous column (for the column on the far right, the carry is 0).
  2. Divide the result with remainder by the number on row B and write down the remainder.
  3. Multiply the quotient by the number from row A, this is the carry over for the next column. Repeat step 4.1 until the second column is filled.
2. Multiply the entry in the first column from the previous row by 10 and add the carryover from the second column.
3. Divide the result with remainder by 10 and write the remainder in the first column.
4. The quotient is the next preliminary digit. It can range from 0 to 10. Depending on their size, do one of the following:
  - 0–8: Output all previous provisional digits and only keep the new one.
  - 9: Append the new digit to the previous provisional digits.
  - 10: Increase all previous provisional digits by 1 (9 becomes 0) and output them. The new provisional digit is 0.
5. Repeat step 4 until you have calculated digits. ${\ displaystyle n}$

example

The following example performs the algorithm for calculating decimal places; for this the number of columns required is : ${\ displaystyle n = 3}$ ${\ displaystyle m = \ lfloor 10 (3 + 1) / 3 \ rfloor = 13}$

A.		1	2	3	4th	5	6th	7th	8th	9	10	11	12
B.		3	5	7th	9	11	13	15th	17th	19th	21st	23	25th
	2	2	2	2	2	2	2	2	2	2	2	2	2
3	0	2	2	4th	3	10	1	13	12	1	20th	20th	20th
1	3	1	3	3	5	5	4th	8th	5	8th	17th	20th	0
4th	1	1	0	0	0	4th	12	9	4th	10	6th	16	0
1	1	0	4th	3	1	3	1	3	10	8th	0	22nd	0

In fact, you cannot be sure that the third decimal place is 1, it could happen that it would have to be increased to 2 in the next step. In reality, this case occurs for the first time at the 31st place after the decimal point, here the algorithm initially delivers 4, only in the next step it is corrected to 5. This problem can be partially avoided by calculating one more digit (and choosing a correspondingly larger one), but in this case too it can happen that you get fewer secured digits than desired, namely when a chain of 9 is present at the end. If is normal , an average of one of the 20 provisional digits must be corrected afterwards. ${\ displaystyle m}$ ${\ displaystyle \ pi}$

More drip algorithms

Drip algorithms can also be found for other numbers. Jeremy Gibbons found a number of special algorithms for calculating . While with the above algorithm you have to specify the number of desired digits at the beginning (it is bounded , i.e. restricted), the Gibbons algorithm can be carried out from fixed starting values for any length of time in order to obtain any number of digits ( unbounded , i.e. unlimited). ${\ displaystyle \ pi}$

Individual evidence

↑ AHJ Sale: The calculation of e to many significant digits. The Computer Journal, Vol. 11 (2), 1968. pp. 229-230. ( online )

↑ Stanley Rabinowitz, Stan Wagon : A Spigot Algorithm for the Digits of Pi. American Mathematical Monthly, Vol. 102 (3), 1995. pp. 195-203. ( online ( Memento of the original from February 28, 2013 in the Internet Archive ) Info: The archive link has been inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. ) @1@ 2

↑ Jeremy Gibbons: Unbounded Spigot Algorithms for the Digits of Pi. American Mathematical Monthly, Vol. 113 (4), 2006. pp. 318-328. ( online )

literature

Jörg Arndt, Christoph Haenel: Pi. Algorithms, computers, arithmetic. Springer, 2nd edition 2000. ISBN 978-3-540-66258-7 .
Ian Stewart : Drip Algorithms. Spectrum of Science 12/1995, page 10. ( online )

Web links

Trickle algorithms , with implementations
Algorithms , with detailed explanations
Eric W. Weisstein : Spigot algorithm . In: MathWorld (English).

[1] AHJ Sale: The calculation of e to many significant digits. The Computer Journal, Vol. 11 (2), 1968. pp. 229-230. ( online )