Author |
Topic: Finding specified digits of PI (Read 468 times) |
|
Richard Russell
Administrator
member is offline
 
Posts: 1348
|
 |
Finding specified digits of PI
« Thread started on: Sep 8th, 2015, 1:29pm » |
|
There are several algorithms for finding the value of PI to large numbers of digits (more than a million is practical in LBB) but they mostly work by starting at the beginning! A post on the Just BASIC forum queried whether it is possible to calculate just a few digits starting at a specific position, without finding the preceding digits.
This is a particularly interesting problem, especially when you are counting decimal digits - after all there's nothing 'natural' about base-10! Somewhat surprisingly it is possible, although the method was devised as recently as about twenty years ago. The program below, copied from my post to the JB forum, does it, although it's quite slow for large digit positions.
Because LBB calculates with greater floating-point precision than JB, the program should be good for more than 10 consecutive digits (probably up to about 14 or 15 should be OK, but I wouldn't want to guarantee it):
Code: INPUT "Enter the required starting digit of PI: "; D
INPUT "Enter the number of digits wanted (max 10): "; C
N = INT((D+20) * LOG(10) / LOG(2))
acc = 0
A = 3
WHILE A <= 2*N
M = INT(LOG(2*N) / LOG(A))
P = A ^ M
S = 0
U = 1
L = 1
V = 0
Q = 1
R = 1
FOR K = 1 TO N
T = K
IF Q >= A THEN
DO
T = INT(T/A)
V = V-1
LOOP UNTIL T MOD A
Q = 0
END IF
Q = Q+1
U = (U * T) MOD P
T = 2*K - 1
IF R >= A THEN
IF R = A THEN
DO
T = INT(T/A)
V = V+1
LOOP UNTIL T MOD A
END IF
R = R-A
END IF
L = (L * T) MOD P
R = R+2
IF V > 0 THEN
T = inv.mod(L, P)
T = (T * U) MOD P
T = (T * K) MOD P
FOR I = V TO M-1
T = (T * A) MOD P
NEXT
S = S+T
IF S >= P THEN S = S-P
END IF
NEXT K
T = pow.mod(10, D-1, P)
S = (S * T) MOD P
acc = acc + S / P
acc = acc - INT(acc)
A = next.prime(A)
SCAN
WEND
PRINT "Decimal digits of PI at position "; D; ": "; STR$(INT(acc * 10^C))
END
FUNCTION next.prime(N)
DO
N = N+1
LOOP UNTIL is.prime(N)
next.prime = N
END FUNCTION
FUNCTION is.prime(N)
IF N MOD 2 = 0 THEN is.prime = 0 : EXIT FUNCTION
FOR I = 3 TO SQR(N) STEP 2
IF N MOD I = 0 THEN is.prime = 0 : EXIT FUNCTION
NEXT
is.prime = 1
END FUNCTION
FUNCTION pow.mod(A, B, M)
R = 1
DO
IF B AND 1 THEN R = (R * A) MOD M
B = INT(B/2)
IF B = 0 THEN EXIT DO
A = (A * A) MOD M
LOOP UNTIL 0
pow.mod = R
END FUNCTION
FUNCTION inv.mod(X, Y)
V = Y
C = 1
DO
Q = INT(V / X)
T = C
C = A-Q*C
A = T
T = X
X = V-Q*X
V = T
LOOP UNTIL X = 0
A = A MOD Y
IF A<0 THEN A = A+Y
inv.mod = A
END FUNCTION
Richard.
|
|
|
|
Richard Russell
Administrator
member is offline
Posts: 1348
|
|
Re: Finding specified digits of PI
« Reply #2 on: Sep 9th, 2015, 12:48pm » |
|
on Sep 9th, 2015, 12:02pm, lancegary wrote:| I haven't studied your algorithm in detail (too much other work) but I think you are using the Spigot algorithm? |
|
If I understand correctly, the Spigot algorithm is the one I use in the earlier program I published, which finds digits of PI starting from the beginning. Crucially it uses an array, so the number of digits you can find depends (in principle) on the amount of memory available.
The most recent program, which finds digits starting at a specified position, has very small memory requirements. There is no array, and therefore the digits which you can find do not depend, even in principle, on the memory available. The general method is called the BBP Formula after the discoverers Bailey-Borwein-Plouffe.
Richard.
|
|
 Logged
|
|
|
|
lancegary
New Member
member is offline
Posts: 9
|
|
Re: Finding specified digits of PI
« Reply #3 on: Sep 9th, 2015, 3:59pm » |
|
Thanks.
Lance
|
|
Logged
|
|
|
|
|
