4. Pi in 26 adischer darstellung

Pi in 26 adischer darstellung

  • L

    hallo,

    ich wuerde gerne einen pattern matching algo schreiben, der in Pi nach woertern sucht, dazu wuerde ich Pi mit beliebiger genauigkeit als 26-adische zahl darestellen.

    mir faellt da aber so recht nix ein, gibet da was vorgefertigtes auf das ich dann meinen suchalgo ausfuehren kann, oder hat vlt jemand schon soetwas geschrieben?

    mfg lookias

    0
  • ?

    Noe, da faellt mir jetzt nichts ein. Was ist denn an der Division mit Rest so schwierig?

    0
  • ?

    Ich moechte jetzt nicht wieder ins Fettnaepfchen treten 🙂 aber mein Ansatz waere:
    - Berechne PI mittels einer Potenzreihe. BSP: |2*arccos(0)|=PI --> in einer Formelsammlung unter Potenzreihe.
    - Wandle das ganze mittels Division mit Rest in eine Polyadische Zahl zur Basis 26 um.
    - Jetzt kannst Du suchen

    0
  • ?

    Hi

    Für Pattern-Matching z.B. den Algorithmus von Rabin-Karp verwenden. Naiver Algorithmus ist zu langsam.

    PI für diese Aufgabe mit einer Potenzreihe zu berechnen ist auch viel zu langsam. Die Gebrüder Borwein haben erst 1992 ein Iterationsverfahren entwickelt, imho auf einer Formel von Ramanunjan basierend, das wahnsinnig schnell gegen PI konvergiert. Nach gerade mal 15 Iterationen liefert es 2 Milliarden korrekte Dezimalstellen.

    Ich tippe es einfach mal ab:

    y0:=2−1y_0 := \sqrt{2}-1

    a0:=6−42a_0 := 6-4\sqrt{2}

    yn+1=1−(1−y_n4)141+(1−y_n4)14y_{n+1} = \frac{1-(1-y\_n^4)^{\frac{1}{4}}}{1+(1-y\_n^4)^{\frac{1}{4}}}

    an+1=(1+yn+14)4a_n−22n+3y_n+1(1+yn+1+yn+12)a_{n+1}=(1+y_{n+1}^4)^4a\_n-2^{2n+3}y\_{n+1}(1+y_{n+1}+y_{n+1}^2)

    Es gilt damit
    lim1an=π\lim \frac{1}{a_n} = \pi

    (Quelle: Teubner-Taschenbuch der Mathematik)

    Damit hast du noch zwei Probleme:
    Wurzel aus 2 hinreichend genau zu berechenen und mit solch vielen Stellen überhaupt rechnen zu können. Imho aber ein brauchbarer Ansatz wegen der hohen Konvergenzrate und genau die brauchst du ja für ein Vorhaben. Ich würde die Zahl aber nicht erst im Nachhinein in einen 26-adischen Bruch umwandeln, sondern direkt in diesem System rechen. Evtl. vorgefertigte Klasse suchen oder eben selbst eine bauen.

    Gruß, space

    0

  • [edit]Tut nichts zur Sache. Entschuldige Lookias. Neuer Thread...[/edit]

    0
  • L

    also mir ist eigentlich nur mein pattern matching wichtig, ich hab hier mal ne sehr genaue darstellung von Pi gefunden.

    ftp://pi.super-computing.org/.1/pi200m/pi200m.ascii.01of20

    kann ich diese zahl einfach in eine 26-adische darstellung umwandeln?

    es reicht mir dann das in einer datei zu speichern.

    mfg lookias

    0
  • H

    Es gibt einen Algorithmus (in Spektrum der Wisenschaft wurde dieser Tröpfelalgorithmus genannt), der in der Lage war, immer die nächste Ziffer von Pi auszuspucken. Müastest den aber etwas umschreiben, da er für das dekadische Zahlensystem gedacht war. Sollte aber geeignet sein.

    0
  • L

    henselstep schrieb:

    Es gibt einen Algorithmus (in Spektrum der Wisenschaft wurde dieser Tröpfelalgorithmus genannt), der in der Lage war, immer die nächste Ziffer von Pi auszuspucken. Müastest den aber etwas umschreiben, da er für das dekadische Zahlensystem gedacht war. Sollte aber geeignet sein.

    ok ich habs mir angeschaut, ich koennte den algo auch schreiben das wuerde auch gut mit basis 26 klappen, schonmal danke fuer den tip.

    leider kann ich den mathematischen hintergrund dieser radix konvertierung welche dort auf diese reihendarstellung 2+1/3(2+...)) angewand wird nicht nachvollziehen und finde auch nix im netz dazu.

    wuerde aber gerne mehr darueber erfahren, weiss jemand naeheres dazu?

    gruss lookias

    0
Anmelden zum Antworten