announcing "deep pi"



#2

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,


#3

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


#4

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,


#5

I would love to see both

A) 71B version

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

Too lazy to do it myself

[VPN]


#6

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

#7

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.

#8

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)


Possibly Related Threads...
Thread Author Replies Views Last Post
  [OT] Mathematica free for Raspberry PI BruceH 32 1,459 11-23-2013, 05:24 AM
Last Post: Nick_S
  Computing pi with the PC-1300S Kiyoshi Akima 0 149 11-17-2013, 12:24 AM
Last Post: Kiyoshi Akima
  Calculating Pi LHH 9 456 09-27-2013, 10:50 PM
Last Post: Gerson W. Barbosa
  Visualization of pi Bruce Bergman 13 572 08-17-2013, 05:00 PM
Last Post: Howard Owen
  OT: Happy Pi Day! Eddie W. Shore 13 599 03-22-2013, 10:44 AM
Last Post: Les Koller
  Totally OT ... Pi Day for my car Maximilian Hohmann 18 764 03-10-2013, 01:15 PM
Last Post: chris smith
  [WP34S] A funny bug in Pi (prod) Eduardo Duenez 3 277 01-28-2013, 03:41 AM
Last Post: Walter B
  28S Pi Functionality Matt Fegenbush 3 255 10-17-2012, 02:15 AM
Last Post: Nick_S
  e^pi - pi + 9/10^4 + 1/(10^4*ln(2) + sqrt(10)/6)^2 Gerson W. Barbosa 47 1,950 08-08-2012, 10:58 PM
Last Post: Les Koller
  [OT] 355/113 and pi David Hayden 28 1,017 07-27-2012, 10:01 AM
Last Post: Egan Ford

Forum Jump: