Autor |
Beitrag |
Througer
      
Beiträge: 21
|
Verfasst: Mi 28.03.07 18:34
Hallo, ich wollte mal versuchen bis zu einem gewissen Punkt Pi selbst zu berechnen. Jetzt sind ein paar Probleme aufgetreten.
Zunächst hatte ich das Problem, dass ich nicht wusste wie man Exponenten berechnet. Das habe ich jetzt mit der Unit "Math" und "Power" gelöst. Doch jetzt habe ich ein Problem. Die Formet zur berechnung sieht so aus:
1/16^k * ( (4/8k+1) - (2/8k+4) - (1/8k+5) - (1/8k+6) )
Hierbei muss k zu Beginn 0 sein und dann immmer um 1 steigen. Heißt einmal mit 0 durchrechnen, dann mit 1, dann mit 2 und die jeweiligen Ergebnissse addieren. Aber wie schreibe ich jetzt 1/16^k?
16^k ist ja
Delphi-Quelltext 1:
| ergebnis := Power(16, k); |
Dann kann ich ja eine Variable k deklarieren, die in jeder Schleife erhöht wird.
Kann mir jemand bei dem aufstellen der Formel in Delphi helfen?
MfG Througer:
|
|
Heiko
      
Beiträge: 3169
Erhaltene Danke: 11
|
Verfasst: Mi 28.03.07 18:53
Througer hat folgendes geschrieben: | Aber wie schreibe ich jetzt 1/16^k? |
z.B. Power(1/16, 5); Von Power gibt es in der Math-Unit 3 Implementierungen, die je verschiedene Datentypen annehmen. Von daher geht das so  .
@Formel: Da musste mal die mathematische Formel geben, denn mal sinken bei dir die Achtel und irgendwann nicht mehr...
|
|
Througer 
      
Beiträge: 21
|
Verfasst: Mi 28.03.07 19:06
Danke, ich habe mir hier schon einen abgebrochen. Dachte ich müsste das Ergebnis nehmen und dann eine neue Variable aufstellen in der ich dann 1/Ergebnis teile.
Die Formel habe ich doch oben geschrieben. Die ist schon richtig so. Zumindest habe ich die so bekommen. Weiß auch nicht den zusammenhang, aber so berechnet man Pi.
Danke, probiere dann mal weiter.
|
|
Heiko
      
Beiträge: 3169
Erhaltene Danke: 11
|
Verfasst: Mi 28.03.07 19:54
Througer hat folgendes geschrieben: | Danke, ich habe mir hier schon einen abgebrochen. Dachte ich müsste das Ergebnis nehmen und dann eine neue Variable aufstellen in der ich dann 1/Ergebnis teile. |
Dürfte IMHO das gleiche rauskommen und ggf. sogar schneller sien, da Gleitkomma auf den CPUs langsamer sind, als Ganzzahl-OPs.
Througer hat folgendes geschrieben: | Die Formel habe ich doch oben geschrieben. Die ist schon richtig so. Zumindest habe ich die so bekommen. |
Achso, also sollt ihr genau mit der Rechnen und keine genauere Genauigkeit durch mehr Teile errreichen. Dann würde der Quelli so aussehen:
Delphi-Quelltext 1: 2: 3: 4: 5:
| MyPi:=0; for k:=0 to 100 do begin MyPi:=MyPi + 1/Power(16, k) * ( (0.5*k+1) - (0.25*k + 4) - (0.125*k+5) - (0.125*k+6) ) end; |
wobei das ganze ein bissl zusammenfassen kann  .
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 01.04.07 12:34
Wer mit der BBP-Formel arbeiten will, sollte sich ein wenig die BEschreibung durchlesen und würde dann sehen, dass diese Formel keine reine Rechenforschrift ist, sondern eine Stellenwert-Vorschrift ...
Moment, ich such mal den Link aus meiner Semester-Arbeit kurz raus, wo wir das zitiert hatten ...
Zitat des TeX-Dokuments der Doku hat folgendes geschrieben: |
\url{crd.lbl.gov/~dhbaile...bpapers/bbp-alg.pdf} \\
Description of the BBP (Bailey-Borwein-Plouffe) algorithm that can be used
to evaluate $\log2$ and $\pi$ really fast.
|
Ich zitier mal einige Dinge:
Seite 3 ganz unten hat folgendes geschrieben: | To compute the hexadecimal digits of # beginning after the first d hex digits (i.e., beginning at position d+1): Let {·} denote the fractional part as before. Given an integer d > 0, we can write, from formula (4), {16^d Pi} = {4{16^d S1} - 2{16^d S4} - {16^d S5} - {16^d S6}}, [....] |
Wer dort nun genau liest, erhält folgenden WICHTIGEN Hinweis:
Seite 4 hat folgendes geschrieben: | [...]
Now apply the binary exponentiation algorithm to (7), in a similar way as described above in the scheme for log 2, to compute {16^d Sj} for j = 1, 4, 5, 6. Combine these four results, as shown in (5). Add or subtract integers, as necessary, to reduce the final result to within 0 and 1. The resulting fraction, computing when expressed in hexadecimal notation, gives the first few hex digits of Pi that follow position d (i.e., the first few hex digits starting at position d+1). As an example, when d = 1,000,000, we compute compute
S1 = 0.181039533801436067853489346252 . . .
S2 = 0.776065549807807461372297594382 . . .
S3 = 0.362458564070574142068334335591 . . .
S4 = 0.386138673952014848001215186544 . . .
Combining these as in (5) yields
{16^d Pi} = 0.423429797567540358599812674109 . . . |
Soll heißen: Allein mit dem berechnen dieses Ausdrucks ist's nicht getan (weshalb wir uns in unserer Arbeit vorerst auch gegen die Umsetzung der BBP-Formel entschieden hatten ...
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Througer 
      
Beiträge: 21
|
Verfasst: Mo 02.04.07 12:39
Hallo, tut mir leid, dass ich erst jetzt antworte.
@ Heiko
Habe das ein wenig anders gelöst. Jetzt geht es aber wenn ich für k eine Zahl einsetzen lasse. Nur habe ich jetzt ein anderes Problem.
Ich bekomme es nicht umgesetzt, dass die Werte für die verschiedenen k addiert werden. Wenn k=0, dann soll dieser Wert gemerkt werden. Wenn k=1, dann soll dieser Wert zu k=0 addiert werden, usw.
Wie könnte ich das denn lösen?
@BenBE
Was du geschrieben, bzw. zitiert hast verstehe ich nicht, aber bei den Semester-Arbeiten bin ich noch nicht.  Trotzdem danke.
MfG Througer:
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Mo 02.04.07 12:58
Througer hat folgendes geschrieben: | Hallo, tut mir leid, dass ich erst jetzt antworte.
@ Heiko
Habe das ein wenig anders gelöst. Jetzt geht es aber wenn ich für k eine Zahl einsetzen lasse. Nur habe ich jetzt ein anderes Problem.
Ich bekomme es nicht umgesetzt, dass die Werte für die verschiedenen k addiert werden. Wenn k=0, dann soll dieser Wert gemerkt werden. Wenn k=1, dann soll dieser Wert zu k=0 addiert werden, usw.
Wie könnte ich das denn lösen?
@BenBE
Was du geschrieben, bzw. zitiert hast verstehe ich nicht, aber bei den Semester-Arbeiten bin ich noch nicht. Trotzdem danke.
MfG Througer: |
Genau das ist die Sache: Die Berechnung \ Addition der einzelnen Dinge von k=1 zu k=0 ist nicht trivial, sondern benötigt eine Normalisierung, die in dem verlinkten Dokument beschrieben ist. Dass Du das besagte Dokument nicht verstehst, kann ich gut nachvollziehen ... Ich bin selbst noch nicht ganz dahintergestiegen (und ich studier inzwischen) ...
Du solltest Dir vorerst einfachere Methoden (z.B. ATN, Leibniz-Formel, ... suchen, da diese Reihen wesentlich einfacher umzusetzen gehen. Vgl: In unserer finalen Version haben wir eine Reihe genommen, die etwa lineare Zeit benötigt. Mit 200 Folgengliedern kamen wir dabei auf 280 Nachkommastellen [~4 Sekunden] (was für unseren Fall reichte). Und dabei wurde auf einige tausend Stellen die Mantisse mitberechnet ...
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 02.04.07 13:31
Hallo,
@BenBe:
Das war wohl ein Schreibfehler:
4 Sekunden für 280 Stellen wäre aber recht lahm.
Da ist ein Turbo Pascal Programm Nr 8 aus www.hjcaspar.de/hpxp/piprog.htm schneller.
www.delphi-forum.de/viewtopic.php?t=51429 und wie dort geschrieben nur 5 Schutzstellen bei 2e5 Stellen in 23.6 Sekunden und dies bei einem Verfahren mit quadratischer Laufzeit.(Halbe Stellenzahl ~ 1/4 Laufzeit)
Die Schutzstellenzahl reichte völlig aus, wie ein Vergleich mit einem Programm (piFast) das eine Textdatei mit den ersten 1 Mio Stellen erstellte.
Gruß Horst
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Sa 07.04.07 00:55
Da ich grad mal ein wenig lange Weile hatte, habsch mal eben den C-Source für die Berechnung nach BBP-Algo nach Delphi portiert ...
Sieht dann so aus:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135:
| program Project1;
{$APPTYPE CONSOLE}
Uses SysUtils, Math;
function series (m, id: Integer) : Extended ;forward; procedure ihex (x: Extended; m: Integer; var chx: String); forward; Function expm (p, ak: Extended ): Extended ;forward;
const NHX= 16; eps =1e-17; ntp= 25;
var tp: array [0..ntp-1] of Extended ; tp1 : Integer= 0;
procedure main; var pid, s1, s2, s3, s4: Extended; id: integer; chx : String; begin while ( True ) do begin WriteLn(#13#10'Pi hex digit computation: enter position (enter 0 to quit)'#13#10); ReadLn(id); if ( id < 0 ) Then break;
if ( id >= 10000000 ) Then begin WriteLn('Warning: program not reliable for such a large position.'#13#10); end;
s1 := series (1, id); s2 := series (4, id); s3 := series (5, id); s4 := series (6, id); pid := 4 * s1 - 2 * s2 - s3 - s4; pid := Frac(pid); if (pid < 0.0) Then pid := pid + 1.0; chx := ''; ihex (pid, NHX, chx); WriteLn (Format(' position = %d'#13#10' fraction = %.15f '#13#10' hex digits = %10.10s'#13#10, [id, pid, chx])); end; end;
procedure ihex (x: Extended; m: Integer; var chx: String); const hx = '0123456789ABCDEF'; var i: Integer; y: Extended; begin y := abs (x); for i := 0 to nhx -1 do begin y := 16 * Frac(y); chx := chx + hx[1+Trunc(y)]; end; end;
function series (m, id: Integer) : Extended ; var k: Integer; ak, p, s, t: Extended; begin
s := 0.;
for k := 0 to id - 1 do begin ak := 8 * k + m; p := id - k; t := expm (p, ak); s := frac(s + t / ak); end;
for k := id to id + 100 do begin ak := 8 * k + m; t := power (16., (id - k)) / ak; if (t < eps) Then break; s := Frac(s + t); end; Result := s; end;
Function expm (p, ak: Extended ): Extended ; var i, j: integer; p1, pt, r: Extended;
begin
if (tp1 = 0) then begin tp1 := 1; tp[0] := 1.;
for i := 1 to ntp - 1 do tp[i] := 2. * tp[i-1]; end;
if (ak = 1) then Begin Result := 0.; Exit; end;
I := ntp - 1; While (tp[i] > p) do Dec(I);
pt := tp[i]; p1 := p; r := 1.;
for j := 1 to i do begin if (p1 >= pt) then begin r := 16. * r; r := r - Trunc (r / ak) * ak; p1 := p1 - pt; end; pt := 0.5 * pt; if (pt >= 1) Then begin r := r * r; r := r - Trunc (r / ak) * ak; end; end;
Result := r; end;
begin main; end. |
Hat allerdings noch paar Macken (die ich noch nicht lokalisieren konnte)... Ich vermute aber in expm.
MfG,
BenBE.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
|