HP Forums
announcing "deep pi" - Printable Version

+- HP Forums (https://archived.hpcalc.org/museumforum)
+-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html)
+--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html)
+--- Thread: announcing "deep pi" (/thread-55868.html)

announcing "deep pi" - hugh steers - 04-25-2004

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:

598253490428755468731159562863882353787593751957781857780532 1712268066130019278766111959092164201989

good luck,

Re: announcing "deep pi" - Katie - 04-26-2004


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.


Re: announcing "deep pi" - hugh steers - 04-27-2004

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

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" - V-PN - 04-27-2004

I would love to see both

A) 71B version

B) 28/48S/48G/49 version

Too lazy to do it myself


Re: leading zeroes - Paul Brogger - 04-27-2004

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? - Vieira, Luiz C. (Brazil) - 04-27-2004

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)

Re: announcing "deep pi" - hugh steers - 04-27-2004

i am very tempted to write a 71b version. it would be a lot clearer to understand and somewhat faster.