Der Bailey-Borwein-Plouffe (BBP) Algorithmus, angewendet auf Pi
=========================================
1996 entdeckte der PC von David Harold Bailey (der darauf Ferguson's PSLQ algorithm laufen lies) eine neuartige Möglichkeit, bekannte mathematische Konstanten als unendliche Reihe (sog. BBP-Reihe) darzustellen. Das tolle daran: Man kann damit die einzelnen Ziffern AB EINER BELIEBIG VORGEGEBENEN NACHKOMMASTELLE (hier: u&) damit berechnen, ohne die vorangehenden Stellen zu kennen. Dummerweise funktioniert das mit den Nachkommastellen bisher nur in Zahlensystemen, die auf 2-hoch oder einem Vielfachen davon basieren, also NICHT IM DEZIMALSYSTEM!
Pi im IEEE-Binärsystem lautet :-)bekanntlich:-) 0[=+] 10000000000[=1023+2^1] (implizit_1)1001 00100001 11111011 01010100 01000100 00101101 00011000 (wie das untenstehende Hilfsprogramm zeigt). Will ich nun wissen ob die 40000. Stelle nach der impliziten 1 den Wert 0 oder 1 hat, benötigt man ein Arithmetikpaket, daß nur wenig besser als jenes von XProfan ist.
Hier ein Progrämmchen (nun v1.02), daß die BBP-Formel dezimal verifiziert.
WindowTitle "Bailey-Borwein-Plouffe (BBP)-Reihen angewendet auf Pi"
' Umsetzung in XProfan 11.2a (CL) Copyleft 2012-10 by spechtp, Wien
' Quelle: http://crd-legacy.lbl.gov/~dhbailey/dhbpapers/bbp-alg.pdf
' (ausgehend von http://de.wikipedia.org/wiki/Kreiszahl#BBP-Reihen)
WindowStyle 1048
Window 0,0-%maxx,%maxy
set("decimals",15)
print " ";BBP4(0,22)
print 1/3+BBP4(1,22)-pi(); " = Unterschied zum Profan-pi() "
Waitinput
end
proc BBP4
parameters u&,v&
declare k&,sum!,wert!
whileloop u&,v&:k&=&Loop
sum!=sum!+(1-2*(k& mod 2))/(4^k&)*(2/(4*k&+1)+2/(4*k&+2)+/(4*k&+3))
endwhile
return sum!
' This formula was discovered by a computer, using
' Bailey's implementation of Ferguson's PSLQ algorithm.
Endproc
Alles anzeigen
P.S.: Mit dieser Formel konnte man z.B. auch die echte Unabhängigkeit aller Stellen der Kreiszahl Pi voneinander beweisen (also anders als z.B. bei den Stellen der Eulerschen Zahl e)
PPS: Hier noch ein Hilfsprogramm "Pi im Binärsystem"
cls
declare b#,w$
dim b#,8
float b#,0= pi()
w$ = right$("00000000"+bin$(byte(b#,7)),8) + " " +\
right$("00000000"+bin$(byte(b#,6)),8) + " " +\
right$("00000000"+bin$(byte(b#,5)),8) + " " +\
right$("00000000"+bin$(byte(b#,4)),8) + " " +\
right$("00000000"+bin$(byte(b#,3)),8) + " " +\
right$("00000000"+bin$(byte(b#,2)),8) + " " +\
right$("00000000"+bin$(byte(b#,1)),8) + " " +\
right$("00000000"+bin$(byte(b#,0)),8)
clearclip
putclip w$
print w$
WaitInput
Alles anzeigen
PPPS: Hier verschiedene Darstellungen und Näherungen für Pi.
So sähe u.a. eine Binärstellen-zusammgensetzte Darstellung von Pi aus:
Windowtitle "Darstellungen von Pi"
cls:font 2:set("decimals",18):declare pi!,z!,n!
print "3.1415926535897932384626433832795028841971693993751..."
waitinput 1000
print 3.1415926535897932384626433832795028841971693993751
waitinput 1000
print pi()
waitinput 1000
print 4*arctan(1)
waitinput 1000
print 1*2^1+1*2^0+0*2^-1+0*2^-2+1*2^-3+0*2^-4+0*2^-5+1*2^-6+0*2^-7+0*2^-8+0*2^-9+0*2^-10+\
1*2^-11+1*2^-12+1*2^-13+1*2^-14+1*2^-15+1*2^-16+0*2^-17+1*2^-18+1*2^-19+0*2^-20+1*2^-21+\
0*2^-22+1*2^-23+0*2^-24+1*2^-25+0*2^-26+0*2^-27+0*2^-28+1*2^-29+0*2^-30+0*2^-31+0*2^-32+\
1*2^-33+0*2^-34+0*2^-35+0*2^-36+0*2^-37+1*2^-38+0*2^-39+1*2^-40+1*2^-41+0*2^-42+1*2^-43+\
0*2^-44+0*2^-45+0*2^-46+1*2^-47+1*2^-48+0*2^-49+0*2^-50+0*2^-51
waitinput 1000
print 2^1+2^0+2^-3+2^-6+2^-11+2^-12+2^-13+2^-14+2^-15+2^-16+2^-18+2^-19+2^-21+\
2^-23+2^-25+2^-29+2^-33+2^-38+2^-40+2^-41+2^-43+2^-47+2^-48
waitinput 1000
print 2 + 1 + 1/8 + 1/64 + 1/2048 + 1/4096 + 1/8192 + 1/16384 + 1/32768 + 1/65536 + 1/262144 \
+ 1/524288 + 1/2097152 + 1/8388608 + 1/33554432 + 1/536870912 + 1/8589934592 + 1/274877906944 \
+ 1/1099511627776 + 1/2199023255552 + 1/8796093022208 + 1/140737488355328 + 1/281474976710656
waitinput 1000
pi!=2 + 1 + 1/8 + 1/64 + 1/2048 + 1/4096 + 1/8192 + 1/16384 + 1/32768 + 1/65536 + 1/262144 \
+ 1/524288 + 1/2097152 + 1/8388608 ' + 1/33554432 + 1/536870912 + 1/8589934592 + 1/274877906944 \
' + 1/1099511627776 + 1/2199023255552 + 1/8796093022208 + 1/140737488355328 + 1/281474976710656
print pi!, pi!-pi(), "Test 'Brüche abknipsen' "
waitinput 1000
print 355 / 113, pi() - 355/113, "= 355/113"
waitinput 1000
print 22 /7, pi() - 22/7, "= 22 / 7 "
waitinput 1000
' Wallis: pi!= 2 *2/1* 2/3*4/3*4/5*6/5*6/7*8/7*8/9*10/9*8/9 * ...
z!= 0 : n!= 1 : pi!=2
whileLoop 0,1000
if (&Loop mod 2)=0 ' gerade: Zähler erhöhen um 2
z!=z!+2
else ' ungerade: Nenner erhöhen um 2
n!=n!+2
endif
' : print z!,n! : waitinput
pi!=pi!*z!/n!
endwhile
print pi!, pi() - pi!, "als Wallissches Produkt"
print "ok."
waitinput
Alles anzeigen