HP Forum Archive 14

[ Return to Index | Top of Index ]

announcing "deep pi" Message #1 Posted by hugh steers (the other hugh) on 25 Apr 2004, 2:34 p.m. greetings all. a while back on this forum there was a discussion of various calculator efforts to find 1000 digits of pi. there were some good results, but it seems that after about 1000 digits, too much space is required and so the programs competed on speed. i had an idea for a different kind of pi calculation. here is "deep pi" for the 41c. it only calculates 6 digits of pi but it can do this starting from any given point of the decimal expansion. for example 1 XEQ "DPI" gives 141592 and 999 (the 1000'th digit counting the 3) XEQ "DPI" gives 893809. so, in order to get as much pi as you like, start at 1, then 7 then 13 and so on. the start of the program could be modified into a simple loop that prints out successive 6-digits onto the print roll indefintely (until its out of paper). there is no state retained between each run and the internal numbers do not become large or overflow. however, and this is catch; it gets slower the further along you start. the 6 digits at 999 take some time indeed. if you'd like to try this program. here is a text file compatible with the excellent V41 emulator http://www.voidware.com/calcs/pi.txt its not very well commented and i recommend liberal use of the "turbo" mode. if you're interesting in improving the algorithm or the program, feel free to do so. this is the first attempt and this version1 could well have bugs. ive tested it enough to know its not completely wrong, but there's always one somewhere. also note that i do not format the output string in any way, so for example 307 xeq gives 6606 which really means 006606!. here are the first 1000 digits (after 3) found using this method: 141592653589793238462643383279502884197169399375105820974944 592307816406286208998628034825342117067982148086513282306647 093844609550582231725359408128481117450284102701938521105559 644622948954930381964428810975665933446128475648233786783165 271201909145648566923460348610454326648213393607260249141273 724587006606315588174881520920962829254091715364367892590360 011330530548820466521384146951941511609433057270365759591953 092186117381932611793105118548074462379962749567351885752724 891227938183011949129833673362440656643086021394946395224737 190702179860943702770539217176293176752384674818467669405132 000568127145263560827785771342757789609173637178721468440901 224953430146549585371050792279689258923542019956112129021960 864034418159813629774771309960518707211349999998372978049951 059731732816096318595024459455346908302642522308253344685035 261931188171010003137838752886587533208381420617177669147303 598253490428755468731159562863882353787593751957781857780532 1712268066130019278766111959092164201989 good luck,

Re: announcing "deep pi" Message #2 Posted by Katie on 26 Apr 2004, 10:12 a.m., in response to message #1 by hugh steers (the other hugh) Hugh, This is *very* interesting! Which algorithm are you using, I don't think that anyone has found an O(NlogN) in base 10 yet. The BBP base 16 algorithm doesn't generalize to other bases but there has been some recent work on direct-digit computations using other methods. Here's the best paper tha I know of that discusses all this: http://numbers.computation.free.fr/Constants/Algorithms/nthdigit.html Thanks for writing and posting this! More comments in your 41C program would be much appreciated, it's pretty hard to understnad as is. -Katie

Re: announcing "deep pi" Message #3 Posted by hugh steers on 27 Apr 2004, 6:34 a.m., in response to message #2 by Katie thanks! i'm glad you like it. i dont take any credit for the algorithm. the results are from the same paper you have cited. when i read this originally, it occurred to me that the low memory requirement would make it a good example for a calculator program. at first, i planned a 71b version, but then i decided it would be more fun to do a 41c version, albeit quite slow. the first step was to take frabrice bellard's original program here http://fabrice.bellard.free.fr/pi/pi1.c and start experimenting. although i havent changed the algorithm, there was substantial hackery required to prepare it for calculator consumption. one of the problems is that some parts of the calculation overflow 10 digits. after some investigation, it turns out that this only happens for case 2. the algorithm has to walk the primes from 2. what i then did is unroll case 2 and write a special purpose a*b mod 2^n subroutine. for other primes, p, a*b mod p^n did not overflow (much) so it works with normal precision. if i had not done this, the whole thing would have been really really slow indeed. i also simplified the 2 case somewhat. anyone interested in investigating the program should get my hacked around C version here: http://www.voidware.com/tmp/pi3.c and continue hacking! following the 41 program should then make sense. if i can lay my hands on a 41 printer, i'd like to run a test leaving it going for a few days and see how far it gets. incidently, does anyone know a neat way to format the output so leading zeros are not suppressed. ie 1234 -> 001234? best wishes,

Re: announcing "deep pi" Message #4 Posted by Veli-Pekka Nousiainen on 27 Apr 2004, 7:32 a.m., in response to message #3 by hugh steers I would love to see both A) 71B version B) 28/48S/48G/49 version Too lazy to do it myself [VPN]

Re: announcing "deep pi" Message #5 Posted by hugh steers on 27 Apr 2004, 4:28 p.m., in response to message #4 by Veli-Pekka Nousiainen i am very tempted to write a 71b version. it would be a lot clearer to understand and somewhat faster.

Re: leading zeroes Message #6 Posted by Paul Brogger on 27 Apr 2004, 10:18 a.m., in response to message #3 by hugh steers Move the decimal point [n] digits to the left before display/output? Or, display (for example) six-digit results only after adding them to 1,000,000, and ignore the leading "1". Edited: 27 Apr 2004, 11:30 a.m.

Re: announcing "deep pi" - ALPHA register? Message #7 Posted by Vieira, Luiz C. (Brazil) on 27 Apr 2004, 4:08 p.m., in response to message #3 by hugh steers Hi, Hugh; I'd like to congratulate you as well, O.K.? About leading zeroes: I saw the listing but I did not read it. I guess it can be changed so that instead of building the output data in X you could do it in ALPHA; this way, leading zeroes would be visible. I cannot try it right now, but I promise I'll try to do it later, if no one else tries it. Best regards. Luiz (Brazil)

[ Return to Index | Top of Index ]

Go back to the main exhibit hall