August 2, 2013 at 18:45"Kranik", or an algorithm for finding digits of Pi
Hello, Habr! Recently I was faced with the task of counting the number Pi to the sign whose number the user will choose. Immediately climbed onto Wikipedia , read what kind of beast this is, Pi, and how to find it with the given accuracy. Formulas describing the number of Pi, a lot. But to solve my problem, everything in these formulas rests either on the accuracy and length of the basic types of language (I chose Java), or (to solve the previous problem) long arithmetic, which I did not really want to implement. I wanted to find some kind of algorithm that allows you to find the Pi number up to a given character, and exactly up to that character, and not find a long number, and then trim it to give the user what he requested.
And I found such an algorithm, the very “faucet” algorithm. The word faucet sounds strange here, but I did not find a better way to translate the name of this algorithm from English, how to translate verbatim. In general, in the original it sounds like “A Spigot Algorithm for the Digits of Pi”. The authors of the algorithm and its denominators are American mathematicians Stanley Rabinowitz (Stanley Rabinowitz) and Stan Wagon (Stan Wagon). These two comrades created their algorithm for finding the digits of the number Pi in 1995. The very idea of the algorithm came out of the pen of a certain Sale (Sale) back in 1968, and that algorithm was intended to find the digits of the number e.
In general, English-Russian dictionaries give a translation of the word spigot as “sleeve”. This translation of clarity does not give any. Therefore, I translated this word as “faucet”, since spigot in English is described as a mechanism that regulates the flow of fluid. The idea of the algorithm lies in the fact that for one iteration we get exactly one digit of the number Pi and then we do not use it. That is, the numbers seem to follow from the algorithm, like water from a tap.
Now the algorithm itself. I will not go into all the math (which I, in fact, did not do, analyzing the algorithm), you can read more about it here. By the way, on this link, there is also an implementation of the algorithm for finding 1000 digits of the Pi number in Pascal, which I decided to use immediately, in my laziness. I rewrote it in Java, but no - it did not work. It brought out some obscure me rubbish. I threw this thing away, as you can debug a code that you don’t understand, you yourself know how to extinguish a burning oil with water. Therefore, I decided to deal with the algorithm myself.
To find n digits of Pi, you need an array of length [10 * n / 3] . And integers. The peculiarity of the algorithm is that only integer arithmetic is used. We initialize all cells of the array with the number 2 .
Next, to find one digit of the Pi number, you need to go through all the cells of the array from the end to the beginning and perform simple actions. On the example of a table, we will consider everything in order. Suppose we want to find 3 digits of Pi. To do this, we need to reserve 3 * 10/3 = 10 cells of an integer type. We fill them all with the number 2. Now we begin to search for the first digit ...
We start from the end of the array. We take the last element (under number 9, if we start the count from 0. The same number will be called the numerator, and the one below it in the table is the denominator) - it is 2. Multiply it by 10 (2 * 10 = 20). To the resulting number 20 we add the number from the “Transfer” cell - the number that is transferred from the more right operation. Of course, to the right we did not count anything, therefore this number is 0. The result is written in the "sum". In the "remainder" we write the remainder of dividing the sum by the denominator: 20 mod 19 = 1 . Now we consider the “transfer” for the next step. It will be equal to the result of dividing the sum by the denominator times the numerator: (20/19) * 9 = 9. And we write the resulting number in the cell with the "transfer", standing to the left of the current column. We perform the same actions with each element of the array (multiply by 10, calculate the sum, remainder and carry over to the next step) until we reach the element with number 0. Here the actions are slightly different. So, let's see what we have in the table. Under zero - an array element equal to 2, and the transfer from the previous step equal to 10. As in the previous steps, multiply the array element by 10 and add the transfer to it. In total, we got 30. And now we divide the amount not by the denominator, but by 10 (!). As a result, we get 30/10 = 3 + 0(where 0 is the remainder). The resulting number 3 will be that cherished first digit of the number Pi. And the remainder 0 is written in the cell allocated to him. What were the leftovers for? They need to be used in the next iteration - to find the next digit of Pi. Therefore, it’s wise to store the leftovers in our original 10 * n / 3 array . Thus, it is clear that the capabilities of the algorithm rest precisely on the size of this array. Therefore, the number of digits found is limited by the available memory of the computer or the language in which you implement the algorithm (of course, language restrictions can be circumvented).
But that's not all. There is one caveat. At the end of each iteration, an overflow situation may occur. Those. in the zero column in the "sum" we get a number greater than 100 (this situation occurs quite rarely). Then the next Pi figure is 10. Strange, huh? After all, the digits in the decimal number system are only from 0 to 9. In this case, instead of 10, you need to write 0, and increase the previous digit by 1 (and the one before the last if the last is 9, etc.). Thus, the appearance of one dozen can change one or more of the previously found numbers. How to track such situations? It is necessary to initially find the new figure invalid. To do this, it is enough to have one variable, which will count the number of invalid digits. Found one digit - increased the number of invalid digits by 1. If the next digit found is not equal to 9 or 10, then we begin to consider the previously found digits (and marked as invalid) valid, i.e. we reset the number of invalid digits to 0, and begin to consider the found new digit invalid (i.e., you can immediately reset to 1). If the next digit found is 9, then increase the number of invalid digits by 1. If the next digit is 10, then we increase all invalid digits by 1, instead of 10, write 0 and consider this 0 invalid. If these situations are not monitored, then single incorrect numbers (or more) will appear. can be immediately reset to 1). If the next digit found is 9, then increase the number of invalid digits by 1. If the next digit is 10, then we increase all invalid digits by 1, instead of 10, write 0 and consider this 0 invalid. If these situations are not monitored, then single incorrect numbers (or more) will appear. can be immediately reset to 1). If the next digit found is 9, then increase the number of invalid digits by 1. If the next digit is 10, then we increase all invalid digits by 1, instead of 10, write 0 and consider this 0 invalid. If these situations are not monitored, then single incorrect numbers (or more) will appear.
That's the whole algorithm that the authors compared with the tap. Below is the code of a method implemented in Java that returns a string with the number Pi.
For the sake of interest, I conducted an algorithm performance test depending on the value of n (the number of digits to be found). Here is the graph:
To find a million digits, it took more than eight and a half hours. I conducted the tests without printing the results and used not a StringBuilder, but a byte array.
So to summarize. The main advantages of the algorithm are its simplicity (you can count without problems and hands), as well as the use of integer arithmetic only, which speeds up the calculation process and adds accuracy. The main drawback, I consider the limitations of the algorithm (memory).
PS: The algorithm based on the Bailey – Borwein – Plouffe formula from the discharge category was previously discussed on Habré in this article .
http://en.wikipedia.org/wiki/Pi
http://en.wikipedia.org/wiki/Spigot_algorithm
http://www.mathpropress.com/stan/bibliography/spigot.pdf
http: //www.pi314 .net / eng / goutte.php
http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula
http://habrahabr.ru/post/179829/
And I found such an algorithm, the very “faucet” algorithm. The word faucet sounds strange here, but I did not find a better way to translate the name of this algorithm from English, how to translate verbatim. In general, in the original it sounds like “A Spigot Algorithm for the Digits of Pi”. The authors of the algorithm and its denominators are American mathematicians Stanley Rabinowitz (Stanley Rabinowitz) and Stan Wagon (Stan Wagon). These two comrades created their algorithm for finding the digits of the number Pi in 1995. The very idea of the algorithm came out of the pen of a certain Sale (Sale) back in 1968, and that algorithm was intended to find the digits of the number e.
In general, English-Russian dictionaries give a translation of the word spigot as “sleeve”. This translation of clarity does not give any. Therefore, I translated this word as “faucet”, since spigot in English is described as a mechanism that regulates the flow of fluid. The idea of the algorithm lies in the fact that for one iteration we get exactly one digit of the number Pi and then we do not use it. That is, the numbers seem to follow from the algorithm, like water from a tap.
Now the algorithm itself. I will not go into all the math (which I, in fact, did not do, analyzing the algorithm), you can read more about it here. By the way, on this link, there is also an implementation of the algorithm for finding 1000 digits of the Pi number in Pascal, which I decided to use immediately, in my laziness. I rewrote it in Java, but no - it did not work. It brought out some obscure me rubbish. I threw this thing away, as you can debug a code that you don’t understand, you yourself know how to extinguish a burning oil with water. Therefore, I decided to deal with the algorithm myself.
To find n digits of Pi, you need an array of length [10 * n / 3] . And integers. The peculiarity of the algorithm is that only integer arithmetic is used. We initialize all cells of the array with the number 2 .
Next, to find one digit of the Pi number, you need to go through all the cells of the array from the end to the beginning and perform simple actions. On the example of a table, we will consider everything in order. Suppose we want to find 3 digits of Pi. To do this, we need to reserve 3 * 10/3 = 10 cells of an integer type. We fill them all with the number 2. Now we begin to search for the first digit ...
We start from the end of the array. We take the last element (under number 9, if we start the count from 0. The same number will be called the numerator, and the one below it in the table is the denominator) - it is 2. Multiply it by 10 (2 * 10 = 20). To the resulting number 20 we add the number from the “Transfer” cell - the number that is transferred from the more right operation. Of course, to the right we did not count anything, therefore this number is 0. The result is written in the "sum". In the "remainder" we write the remainder of dividing the sum by the denominator: 20 mod 19 = 1 . Now we consider the “transfer” for the next step. It will be equal to the result of dividing the sum by the denominator times the numerator: (20/19) * 9 = 9. And we write the resulting number in the cell with the "transfer", standing to the left of the current column. We perform the same actions with each element of the array (multiply by 10, calculate the sum, remainder and carry over to the next step) until we reach the element with number 0. Here the actions are slightly different. So, let's see what we have in the table. Under zero - an array element equal to 2, and the transfer from the previous step equal to 10. As in the previous steps, multiply the array element by 10 and add the transfer to it. In total, we got 30. And now we divide the amount not by the denominator, but by 10 (!). As a result, we get 30/10 = 3 + 0(where 0 is the remainder). The resulting number 3 will be that cherished first digit of the number Pi. And the remainder 0 is written in the cell allocated to him. What were the leftovers for? They need to be used in the next iteration - to find the next digit of Pi. Therefore, it’s wise to store the leftovers in our original 10 * n / 3 array . Thus, it is clear that the capabilities of the algorithm rest precisely on the size of this array. Therefore, the number of digits found is limited by the available memory of the computer or the language in which you implement the algorithm (of course, language restrictions can be circumvented).
But that's not all. There is one caveat. At the end of each iteration, an overflow situation may occur. Those. in the zero column in the "sum" we get a number greater than 100 (this situation occurs quite rarely). Then the next Pi figure is 10. Strange, huh? After all, the digits in the decimal number system are only from 0 to 9. In this case, instead of 10, you need to write 0, and increase the previous digit by 1 (and the one before the last if the last is 9, etc.). Thus, the appearance of one dozen can change one or more of the previously found numbers. How to track such situations? It is necessary to initially find the new figure invalid. To do this, it is enough to have one variable, which will count the number of invalid digits. Found one digit - increased the number of invalid digits by 1. If the next digit found is not equal to 9 or 10, then we begin to consider the previously found digits (and marked as invalid) valid, i.e. we reset the number of invalid digits to 0, and begin to consider the found new digit invalid (i.e., you can immediately reset to 1). If the next digit found is 9, then increase the number of invalid digits by 1. If the next digit is 10, then we increase all invalid digits by 1, instead of 10, write 0 and consider this 0 invalid. If these situations are not monitored, then single incorrect numbers (or more) will appear. can be immediately reset to 1). If the next digit found is 9, then increase the number of invalid digits by 1. If the next digit is 10, then we increase all invalid digits by 1, instead of 10, write 0 and consider this 0 invalid. If these situations are not monitored, then single incorrect numbers (or more) will appear. can be immediately reset to 1). If the next digit found is 9, then increase the number of invalid digits by 1. If the next digit is 10, then we increase all invalid digits by 1, instead of 10, write 0 and consider this 0 invalid. If these situations are not monitored, then single incorrect numbers (or more) will appear.
That's the whole algorithm that the authors compared with the tap. Below is the code of a method implemented in Java that returns a string with the number Pi.
public static String piSpigot(final int n) {
// найденные цифры сразу же будем записывать в StringBuilder
StringBuilder pi = new StringBuilder(n);
int boxes = n * 10 / 3; // размер массива
int reminders[] = new int[boxes];
// инициализируем масив двойками
for (int i = 0; i < boxes; i++) {
reminders[i] = 2;
}
int heldDigits = 0; // счётчик временно недействительных цифр
for (int i = 0; i < n; i++) {
int carriedOver = 0; // перенос на следующий шаг
int sum = 0;
for (int j = boxes - 1; j >= 0; j--) {
reminders[j] *= 10;
sum = reminders[j] + carriedOver;
int quotient = sum / (j * 2 + 1); // результат деления суммы на знаменатель
reminders[j] = sum % (j * 2 + 1); // остаток от деления суммы на знаменатель
carriedOver = quotient * j; // j - числитель
}
reminders[0] = sum % 10;
int q = sum / 10; // новая цифра числа Пи
// регулировка недействительных цифр
if (q == 9) {
heldDigits++;
} else if (q == 10) {
q = 0;
for (int k = 1; k <= heldDigits; k++) {
int replaced = Integer.parseInt(pi.substring(i - k, i - k + 1));
if (replaced == 9) {
replaced = 0;
} else {
replaced++;
}
pi.deleteCharAt(i - k);
pi.insert(i - k, replaced);
}
heldDigits = 1;
} else {
heldDigits = 1;
}
pi.append(q); // сохраняем найденную цифру
}
if (pi.length() >= 2) {
pi.insert(1, '.'); // добавляем в строчку точку после 3
}
return pi.toString();
}
For the sake of interest, I conducted an algorithm performance test depending on the value of n (the number of digits to be found). Here is the graph:
To find a million digits, it took more than eight and a half hours. I conducted the tests without printing the results and used not a StringBuilder, but a byte array.
So to summarize. The main advantages of the algorithm are its simplicity (you can count without problems and hands), as well as the use of integer arithmetic only, which speeds up the calculation process and adds accuracy. The main drawback, I consider the limitations of the algorithm (memory).
PS: The algorithm based on the Bailey – Borwein – Plouffe formula from the discharge category was previously discussed on Habré in this article .
http://en.wikipedia.org/wiki/Pi
http://en.wikipedia.org/wiki/Spigot_algorithm
http://www.mathpropress.com/stan/bibliography/spigot.pdf
http: //www.pi314 .net / eng / goutte.php
http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula
http://habrahabr.ru/post/179829/