"Kranik", or an algorithm for finding digits of Pi
Hi, Habr! Recently faced with the task of counting the number of Pi to the character whose number the user will choose. Immediately I went to Wikipedia , to read what kind of beast it is, this is Pi, and how to find it with a given accuracy. Formulas describing the number of Pi, a lot. But to solve my problem, everything in these formulas rests on either the accuracy and length of the basic language types (I chose Java), or (to solve the previous problem) in a long arithmetic, which I didn’t really want to realize. I wanted to find some kind of algorithm that allows finding the Pi number up to a given sign, and exactly up to this sign, rather than finding a long number, and then cutting it to give the user what he asked for.
And I found such an algorithm, the very algorithm of "tap" . The word tap sounds strange here, but I have not found a better way to translate the name of this algorithm from English, how to translate it literally. In general, in the original it sounds like “A Spigot Algorithm for the Digits of Pi”. The authors of the algorithm and their names are the American mathematicians Stanley Rabinowitz (Stanley Rabinowitz) and Stan Wagon. The two comrades in 1995 created their own algorithm for finding the digits of Pi. The very idea of ​​the algorithm came from the pen of a certain Sale (Sale) back in 1968, and that algorithm was designed to find the digits of the number e.
In general, English-Russian dictionaries provide a translation of the word spigot as “sleeve”. This translation of clarity does not give any. Therefore, I translated this word as “tap”, since spigot in English is described as a mechanism regulating the flow of fluid. The idea of ​​the algorithm lies in the fact that in one iteration we get exactly one digit of Pi and then we don’t use it. That is, the figures seem to follow from the algorithm, like water from a tap.
')
Now the algorithm itself. I will not get into all the mathematics (which I actually did not do when analyzing the algorithm), you can read more about it here . By the way, under this link, there is also an implementation of the algorithm for finding 1000 digits of Pi in Pascal, which I decided to use immediately because of my laziness. Rewrote in Java, but no - it did not work. Deduced by some incomprehensible to me rubbish. I also threw this business, since you yourself know how to debug a code you do not know how to extinguish burning oil with water. Therefore, I decided to sort out the algorithm myself.
To find n characters 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. Initialize all the cells in the array with the number 2 .
Further, in order to find one digit of Pi, it is necessary to go through all the cells of the array from the end to the beginning and perform simple actions. On the example of the 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 integer type. Fill them all with the number 2. Now let's start searching for the first digit ...
We start at the end of the array. We take the last element (number 9, if we start the score from 0. We will call this number the numerator, and the one below it in the table is the denominator) - it is 2. We 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-hand operation. Of course, to the right we did not count anything, so this number is equal to 0. The result is written in the "amount". In the "remainder" we write the remainder of dividing the sum by the denominator: 20 mod 19 = 1 . And now we consider the “transfer” for the next step. It will be equal to the result of dividing the sum by the denominator multiplied by the numerator: (20/19) * 9 = 9 . And 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, the remainder and transfer 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, the array element is 2, and the transfer from the previous step is 10. As in the previous steps, we multiply the array element by 10 and add the transfer to it. In total, we received 30. And now we divide the sum 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 the cherished first digit of Pi. And the remainder 0 is written to the cell assigned to it. What were the leftovers for? They need to be used in the next iteration - to find the next digit of Pi. Therefore, it is reasonable to store the residuals in our initial array of size 10 * n / 3 . Thus, it is clear that the capabilities of the algorithm rest 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 limitations can be circumvented).
But that's not all. There is one nuance. 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 number Pi is 10. Strange, yes? After all, the numbers 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 number by 1 (and standing before the last one, if the latter is 9, etc.). Thus, the appearance of one ten, can change one or more of the previously found numbers. How to track such situations? It is necessary to consider the found new digit initially invalid. To do this, it is enough to have one variable that will count the number of invalid digits. Found one digit - increased the number of invalid digits by 1. If the next digit found is neither 9 nor 10, then we begin to consider the numbers found earlier (and marked as invalid) as real, i.e. we reset the number of invalid digits to 0, and we begin to consider the found new digit as invalid (that is, we can immediately reset to 1). If the next digit found is 9, then we increase the number of invalid digits by 1. If the next digit is 10, then we increment all invalid digits by 1, instead of 10, we write 0 and this 0 is considered invalid. If these situations are not monitored, then single incorrect numbers (or more) will appear.
That's the whole algorithm, which the authors compared with the crane. Below is the code for a method implemented in Java that returns a string with the number Pi.
For the sake of interest, I conducted a test of the performance of the algorithm depending on the value of n (the number of digits to be found). This is the result:
It took more than eight and a half hours to find a million digits. I conducted tests without printing the results and used not a StringBuilder, but a byte array.
So 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. But the main drawback I consider the limitations of the algorithm (memory).
PS: The algorithm based on the Bailey – Borwein – Plouffe formula from the “Kranikovykh” category was previously discussed at 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 algorithm of "tap" . The word tap sounds strange here, but I have not found a better way to translate the name of this algorithm from English, how to translate it literally. In general, in the original it sounds like “A Spigot Algorithm for the Digits of Pi”. The authors of the algorithm and their names are the American mathematicians Stanley Rabinowitz (Stanley Rabinowitz) and Stan Wagon. The two comrades in 1995 created their own algorithm for finding the digits of Pi. The very idea of ​​the algorithm came from the pen of a certain Sale (Sale) back in 1968, and that algorithm was designed to find the digits of the number e.
In general, English-Russian dictionaries provide a translation of the word spigot as “sleeve”. This translation of clarity does not give any. Therefore, I translated this word as “tap”, since spigot in English is described as a mechanism regulating the flow of fluid. The idea of ​​the algorithm lies in the fact that in one iteration we get exactly one digit of Pi and then we don’t use it. That is, the figures seem to follow from the algorithm, like water from a tap.
')
Now the algorithm itself. I will not get into all the mathematics (which I actually did not do when analyzing the algorithm), you can read more about it here . By the way, under this link, there is also an implementation of the algorithm for finding 1000 digits of Pi in Pascal, which I decided to use immediately because of my laziness. Rewrote in Java, but no - it did not work. Deduced by some incomprehensible to me rubbish. I also threw this business, since you yourself know how to debug a code you do not know how to extinguish burning oil with water. Therefore, I decided to sort out the algorithm myself.
To find n characters 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. Initialize all the cells in the array with the number 2 .
Further, in order to find one digit of Pi, it is necessary to go through all the cells of the array from the end to the beginning and perform simple actions. On the example of the 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 integer type. Fill them all with the number 2. Now let's start searching for the first digit ...
We start at the end of the array. We take the last element (number 9, if we start the score from 0. We will call this number the numerator, and the one below it in the table is the denominator) - it is 2. We 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-hand operation. Of course, to the right we did not count anything, so this number is equal to 0. The result is written in the "amount". In the "remainder" we write the remainder of dividing the sum by the denominator: 20 mod 19 = 1 . And now we consider the “transfer” for the next step. It will be equal to the result of dividing the sum by the denominator multiplied by the numerator: (20/19) * 9 = 9 . And 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, the remainder and transfer 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, the array element is 2, and the transfer from the previous step is 10. As in the previous steps, we multiply the array element by 10 and add the transfer to it. In total, we received 30. And now we divide the sum 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 the cherished first digit of Pi. And the remainder 0 is written to the cell assigned to it. What were the leftovers for? They need to be used in the next iteration - to find the next digit of Pi. Therefore, it is reasonable to store the residuals in our initial array of size 10 * n / 3 . Thus, it is clear that the capabilities of the algorithm rest 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 limitations can be circumvented).
But that's not all. There is one nuance. 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 number Pi is 10. Strange, yes? After all, the numbers 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 number by 1 (and standing before the last one, if the latter is 9, etc.). Thus, the appearance of one ten, can change one or more of the previously found numbers. How to track such situations? It is necessary to consider the found new digit initially invalid. To do this, it is enough to have one variable that will count the number of invalid digits. Found one digit - increased the number of invalid digits by 1. If the next digit found is neither 9 nor 10, then we begin to consider the numbers found earlier (and marked as invalid) as real, i.e. we reset the number of invalid digits to 0, and we begin to consider the found new digit as invalid (that is, we can immediately reset to 1). If the next digit found is 9, then we increase the number of invalid digits by 1. If the next digit is 10, then we increment all invalid digits by 1, instead of 10, we write 0 and this 0 is considered invalid. If these situations are not monitored, then single incorrect numbers (or more) will appear.
That's the whole algorithm, which the authors compared with the crane. Below is the code for 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 a test of the performance of the algorithm depending on the value of n (the number of digits to be found). This is the result:
It took more than eight and a half hours to find a million digits. I conducted tests without printing the results and used not a StringBuilder, but a byte array.
So 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. But the main drawback I consider the limitations of the algorithm (memory).
PS: The algorithm based on the Bailey – Borwein – Plouffe formula from the “Kranikovykh” category was previously discussed at 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/
Source: https://habr.com/ru/post/188700/
All Articles