Matroids Matheplanet Forum Index
Moderiert von Spock mire2
Mathematische Software & Apps » Mathematica » Suche schnellsten Algorithmus für Tribonacci(10^7); Folge A000073
Autor
Universität/Hochschule Suche schnellsten Algorithmus für Tribonacci(10^7); Folge A000073
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Themenstart: 2021-03-08

Hallo zusammen, eigene Recherchen haben ergeben, dass der schnellste mir bekannte Algorithmus für ganze Tribonacci Zahlen ( https://mathworld.wolfram.com/TribonacciNumber.html und http://oeis.org/A000073 ) etwa 325 mal langsamer als der der Fibonacci Zahlen ist! Das bekommen wir doch schneller hin - oder? Zunächst starte ich mit dem Argument n=10^7 (10 Mio.), um nicht zu lange warten zu müssen. Um objektiv vergleichen zu können, müssen bei der Zeitmessung auch die letzten 30 dezimalen Ziffern mit angegeben werden: Mod[Funktion[10^7], 10^30] // Timing Algorithmus 1: Aus dem Forum hier gibt es ja den bekannte Weg zur Ermittlung der expliziten Funktion auch bekannt als "BINET'S FORMULA FOR THE TRIBONACCI SEQUENCE" https://www.fq.math.ca/Scanned/20-2/spickerman.pdf Algorithmus 2: Hypergeometrische Funktion aus den beiden Summen: \sourceon nameDerSprache Tribonacci(n) = Sum_ {i = 0 .. floor ((n - 2)/4)} ((-1)^i* binomial (n - 2 - 3*i, i)*2^(n - 2 - 4*i)) - Sum_ {i = 0 .. floor ((n - 3)/4)} ((-1)^i* binomial (n - 3 - 3*i, i)*2^(n - 3 - 4*i)); = 2^(-3 + n) (2 HypergeometricPFQ[... \sourceoff Algorithmus 3: Reduzierung der BINET'S FORMEL + Rundung Ergebnisse: https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Tribonacci.PNG \sourceon Berechnungszeiten für Tribonacci(10^7) Algo 1: 10.8 s BINET'S FORMULA Algo 2: 79.8 s hypergeometrische Funktion Algo 3: 5.1 s BINET'S FORMULA reduziert + gerundet --------- ab hier YMP ------------------------------------ MatrixPo 0.59s siehe Beitrag 2 + 4 TribonacciBinet 0.4 s Beitrag 19!! TribonacciTac 0.33 s Beitrag 17 zum Vergleich Fibonacci: 0.015625 s \sourceoff Jegliche Rekursionen (aus Vorgängern) sind bei solch großen Argumenten unbrauchbar (oder stoßen schnell an RAM-Grenzen). Kennt jemand schnellere Algorithmen oder Abkürzungen? Oder kann man die Tribonacci-Zahlen aus den Fibonacci Zahlen berechnen? Grüße Gerd


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Beitrag No.1, vom Themenstarter, eingetragen 2021-03-08

Interessant ist der Algorithmus von Pari/GP: \sourceon Pari/GP a(n)=([0, 1, 0; 0, 0, 1; 1, 1, 1]^n)[1, 3] a(10^7)%10^30 -> 1.54 s (3.37 mal schneller als Mathematica! Algo 3) a(10^8)%10^30 -> 16 s (4.8 mal schneller als Mathematica!) a(10^9)%10^30 -> 3 min 26,9 s \sourceoff Mathematicas TribLinRecur[n_] := LinearRecurrence[{1, 1, 1}, {0, 0, 1}, n] // Last; erlaubt nur Argumente bis n=10^5 bei 32 GB RAM! Gibt es da noch einen anderen Syntax?


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Beitrag No.2, vom Themenstarter, eingetragen 2021-03-08

Hab's: Der Syntax nennt sich MatrixPower: \sourceon mathematica TribMatrixPow[n_]:=MatrixPower[{{0,1,0},{0,0,1},{1,1,1}},n-2][[3]]//Last; Mod[TribMatrixPow[10^7], 10^30] -> 0.31 s (Timing) -> ganze Zahl RAM-Disk: 0.59 s Mod[TribMatrixPow[10^8], 10^30] -> 4.59 s (Timing) -> ganze Zahl RAM-Disk: 9 s Mod[TribMatrixPow[10^9], 10^30] -> 59.66 s (Timing) -> ganze Zahl RAM-Disk:128.8 s \sourceoff Damit kommen wir in die Geschwindigkeitsregion von Fibonacci! Interessant: Mathematica nutzt dafür 3 CPU-Kerne! (deshalb schneller als Pari GP)


   Profil
Fabi
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 03.03.2002
Mitteilungen: 4584
  Beitrag No.3, eingetragen 2021-03-08

\quoteon(2021-03-08 19:54 - hyperG in Beitrag No. 2) Hab's: Der Syntax nennt sich MatrixPower: \sourceon mathematica TribMatrixPow[n_]:=MatrixPower[{{0,1,0},{0,0,1},{1,1,1}},n-2][[3]]//Last; Mod[TribMatrixPow[10^7], 10^30] -> 0.31 s Mod[TribMatrixPow[10^8], 10^30] -> 4.59 s Mod[TribMatrixPow[10^9], 10^30] -> 59.66 s \sourceoff Damit kommen wir in die Geschwindigkeitsregion von Fibonacci! Interessant: Mathematica nutzt dafür 3 CPU-Kerne! (deshalb schneller als Pari GP) \quoteoff Hi, Willst du die komplette Zahl haben, oder reichen dir von vornherein nur die letzten 30 Stellen? Zweiteres geht um Größenordnungen schneller. vG, Fabi


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Beitrag No.4, vom Themenstarter, eingetragen 2021-03-08

Hallo Fabi, Du hast recht -> ich werde es noch eindeutiger kennzeichnen: Es geht analog zu Fibonacci(10^9) Benchmarks um das vollständige Speichern der kompletten Dezimalzahl auf einem schnellen Medium. Da eine RAM-Disk bei diesen Größen weniger als 0.4 % ausmacht, kann man es vernachlässigen. Was man aber nicht vernachlässigen darf, ist die Hex-> Dez Wandlung. Ich dachte, dass dies mit Modulo 10 schon halb erledigt sei, aber auch hier haben viele Programme viel optimiert, also der richtige Code zur Geschwindigkeitsmessung: \sourceon mathematica TribMatrixPow[n_]:=MatrixPower[{{0,1,0},{0,0,1},{1,1,1}},n-2][[3]]//Last; startT0=AbsoluteTime[]; Export["r:\\TribMatrixPow(1Mrd).CSV",TribMatrixPow[10^9],"CSV"]; Print[ AbsoluteTime[]-startT0]; 128.8026730 s \sourceoff Das sind also 69,14 s mehr, als wenn man nur die letzten 30 Stellen ausgibt. Ich werde die Tabelle im Beitrag 2 erweitern. Damit ist Tribonacci im Vergleich zu Fibonacci unter mathematica bei n=10^9 nur noch 2,274 mal langsamer. Dafür werden ja auch 55,7 Mio. Stellen mehr berechnet! Um das mit YMP mit allen 20 Kernen noch zu beschleunigen, fehlt mir noch ein effektiver Algorithmus für die MatrixPower Funktion. endy hatte da mal einen Mathematica Befehl, wie das "Innere" abgearbeitet wird...


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2548
  Beitrag No.5, eingetragen 2021-03-08

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\) $\begin{pmatrix} 0&1&0\\ 0&0&1\\ 1&1&1 \end{pmatrix}^n$ enthält in der ersten Spalte Tribonacci-Zahlen rund um den Index $n$. Die Potenz lässt sich schnell mit Square-and-Multiply berechnen. Alternativ kann man auch im Ring $\mathbb Z[X]/(X^3-X^2-X-1)$ die Potenz $X^n$ ausrechnen. [Die Antwort wurde vor Beitrag No.1 begonnen.]\(\endgroup\)


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Beitrag No.6, vom Themenstarter, eingetragen 2021-03-08

Hallo tactac, genau darum geht es ja gerade, was die "abgekürzte Schreibweise" beim Potenzieren einer quadratischen Matrix eigentlich bedeutet. (Array-Summe aus Feldmultiplikationen!!!) Hier habe ich das mal in bekannte Array-Operationen für n=2^5-1...2^5+4 aufgeschlüsselt: \sourceon mathematica MatrixPow2[m_]:=Table[Sum[m[[i]][[k]]*m[[k]][[j]],{k,3}],{i,3},{j,3}]; a3={{0,1,0},{0,0,1},{1,1,1}}; m5=Fold[MatrixPow2[#1]&,a3,Range[5]] m2=MatrixPow2[a3]; m7=Table[Sum[m5[[i]][[k]]*m2[[k]][[j]],{k,3}],{i,3},{j,3}] Table[MatrixPower[{{0,1,0},{0,0,1},{1,1,1}},k][[1]]//Last,{k,2^5-1,2^5+4,1}] {m5[[1]]//First,m5[[1]]//Last,m5[[2]]//Last,m5[[3]]//Last,m7[[2]]//Last,m7[[3]]//Last} Out[119]= {{29249425,45152016,53798080},{53798080,83047505,98950096},{98950096,152748176,181997601}} Out[121]= {{98950096,152748176,181997601},{181997601,280947697,334745777},{334745777,516743378,615693474}} Out[122]= {29249425,53798080,98950096,181997601,334745777,615693474} Out[123]= {29249425,53798080,98950096,181997601,334745777,615693474} \sourceoff Die beiden letzte Zeilen stimmen überein, sind also Tribonacci(2^5-1)...Tribonacci(2^5+4) Das mit der abgekürzten Schreibweise "Ring" habe ich noch nie gehört.


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2548
  Beitrag No.7, eingetragen 2021-03-09

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\) \quoteon(2021-03-08 23:36 - hyperG in Beitrag No. 6) Das mit der abgekürzten Schreibweise "Ring" habe ich noch nie gehört. \quoteoff Zum Rechnen damit kann man so vorgehen: Die Elemente haben die Form $a+bX+cX^2$ mit $a,b,c \in \IZ$, mit unbekanntem $X$ (sind also eigentlich Tripel ganzer Zahlen), jedoch weiß man von dem $X$, dass $X^3 = 1+X+X^2$, weswegen man Koeffizienten für die höheren Potenzen nicht braucht. Dies ergibt, wie addiert und multipliziert werden muss, und darauf basierend kann potenziert werden. Man rechnet also statt mit 9 Zahlen im Fall der Matrix nur mit 3. Das könnte durchaus schneller sein.\(\endgroup\)


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Beitrag No.8, vom Themenstarter, eingetragen 2021-03-09

Vergleich der Geschwindigkeiten: \sourceon mathematica startT0=AbsoluteTime[];zweihoch=26; MatrixPow2[m_]:=Table[Sum[m[[i]][[k]]*m[[k]][[j]],{k,3}],{i,3},{j,3}]; a3={{0,1,0},{0,0,1},{1,1,1}}; m5=Fold[MatrixPow2[#1]&,a3,Range[zweihoch]];//Timing Print[AbsoluteTime[]-startT0]; Mod[m5[[1]]//Last,10^30] Print[AbsoluteTime[]-startT0]; tartT0=AbsoluteTime[]; Mod[MatrixPower[{{0,1,0},{0,0,1},{1,1,1}},2^zweihoch][[1]]//Last,10^30] //Timing Print[AbsoluteTime[]-startT0]; Test 1 kostenlose wolframcloud: ################################### {26.612,Null} 26.633396 192181029491212121499150319616 26.70 {30.0164,192181029491212121499150319616} <- hiermit hat Cloud Probleme! 37.060348 Test 2 Cloud 2. Durchlauf: ######################################## {26.464,Null} 26.473404 192181029491212121499150319616 26.495252 {28.8386,192181029491212121499150319616} <-- Timing zeigt in der Cloud Müll! 10.006397...12.8 <-- stimmt mit Stoppuhr Test 3 Version 12\MatrixPower nutzt ja beim i9 3 Kerne (offline):##### Out[4]= {7.578125,Null} 7.8887829 Out[6]= 192181029491212121499150319616 7.9 Out[8]= {0.046875,192181029491212121499150319616} <-- 0.04 s für internen Hex Wert 10.8724600 <-- stimmt mit Stoppuhr \sourceoff MatrixPower ist gegenüber der "Sum-Nachprogrammierung" etwa 125 mal schneller! Mit etwas If-Optimierung der Sum-Schleife (doppelt vorkommende Werte kopieren -> statt 27 Mul nur noch 21 Mul) konnte ich die 7.9 s auf 5.9 s drücken, was aber immer noch 95 mal langsamer als der gut optimierte Mathematica Befehl (3 Threads) ist.


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Beitrag No.9, vom Themenstarter, eingetragen 2021-03-09

\quoteon(2021-03-09 00:00 - tactac in Beitrag No. 7) \quoteon(2021-03-08 23:36 - hyperG in Beitrag No. 6) Das mit der abgekürzten Schreibweise "Ring" habe ich noch nie gehört. \quoteoff ... statt mit 9 Zahlen im Fall der Matrix nur mit 3. ... \quoteoff Also bei mir hat eine "Matrix-Multiplikation" eines 3*3-Arrays: Table[Sum[m[[i]][[k]]*m[[k]][[j]],{k,3}],{i,3},{j,3}] 3*3*3= 27 Multiplikationen Für die beiden hinteren Felder (i>1) kann man je 3 mal kopieren statt multiplizieren, was 27-2*3= 21 Multiplikationen macht. (und meine Geschwindigkeitssteigerung um Faktor 1.34 praktisch zeigt) Wie man das bei Mio-stelligen Zahlen mit X[...]³=1+X[...]+X[...]² noch weiter vereinfachen will, verstehe ich nicht. Gibt's da keine LINKs oder praktisches Zahlenbeispiel statt "abgekürzte Schreibweise" ?


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2548
  Beitrag No.10, eingetragen 2021-03-09

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\) \quoteon(2021-03-09 19:14 - hyperG in Beitrag No. 9) \quoteon(2021-03-09 00:00 - tactac in Beitrag No. 7) \quoteon(2021-03-08 23:36 - hyperG in Beitrag No. 6) Das mit der abgekürzten Schreibweise "Ring" habe ich noch nie gehört. \quoteoff ... statt mit 9 Zahlen im Fall der Matrix nur mit 3. ... \quoteoff Also bei mir hat eine "Matrix-Multiplikation" eines 3*3-Arrays: Table[Sum[m[[i]][[k]]*m[[k]][[j]],{k,3}],{i,3},{j,3}] 3*3*3= 27 Multiplikationen Für die beiden hinteren Felder (i>1) kann man je 3 mal kopieren statt multiplizieren, was 27-2*3= 21 Multiplikationen macht. (und meine Geschwindigkeitssteigerung um Faktor 1.34 praktisch zeigt) Wie man das bei Mio-stelligen Zahlen mit X[...]³=1+X[...]+X[...]² noch weiter vereinfachen will, verstehe ich nicht. Gibt's da keine LINKs oder praktisches Zahlenbeispiel statt "abgekürzte Schreibweise" ? \quoteoff Ich habe doch alles beschrieben: Man rechnet mit Tripeln $(a,b,c)$, die für $a+bX+cX^2$ stehen. Zusammen mit der Festlegung, dass $X^3 = 1+X+X^2$ sein soll, ergibt sich, wie zwei solcher Tripel zu multiplizieren sind. (Das ist so ähnlich wie mit komplexen Zahlen, nur, dass dort mit Paaren der Form $a+bX$ und der Festlegung $X^2 = -1$ gerechnet wird.) Nämlich: $(a,b,c) \cdot (d,e,f) = (k_0,k_1,k_2)$ mit: * $k_0 = ad + k_3$, * $k_1 = ae + bd + k_3 + k_4$, * $k_2 = af + be + cd + k_3 + k_4$, * $k_3 = bf + ce + k_4$, * $k_4 = cf$. So. $X$ selbst ist das Tripel $(0,1,0)$. Jedes $X^n$ ist ein Tripel $(a_n,b_n,c_n)$, das man effizient mit square-and-multiply auf der Basis der Multiplikation der Tripel (in der 9 Multiplikationen in $\IZ$ vorkommen) ausrechnen kann. Die so entstehenden Folgen $(a_n)_{n\in\IN}$ und $(c_n)_{n\in\IN}$ sind Folgen von Tribonacci-Zahlen (nicht beim Index 0 beginnend, sondern leicht verschoben). Z.B. ist $T_n = c_{n+1}$, wenn $T_0 = 0, T_1 = 1, T_2 = 1$. \(\endgroup\)


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Beitrag No.11, vom Themenstarter, eingetragen 2021-03-10

Input n= 2^28 Mathematica 3 + 1 Kern: 28.9 s YMP 1 Kern & 21-Mul-Algorithmus bin ich bei: https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Tribonacci2hoch28_17s.PNG also 17.5 s Das geht noch schneller... Also tactac, immer noch zu viele abgekürzte Symbole, zu viele Sprünge, unfertig umgestellte Formeln (X²=-1), aus dem Nichts auftauchende k3 , k4... weder sehe ich Input noch Output, wie es sich für einen Algorithmus mit "roten Faden" gehört. Ich zeige das mal morgen am Beispiel von Input: n=2^3 Algo: MatrixPower[{{0, 1, 0}, {0, 0, 1}, {1, 1, 1}}, 2^3][[1]] // Last Output: 24


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2079
  Beitrag No.12, eingetragen 2021-03-10

Hallo, ... um tactac zu verstehen sollte man erst mal einen Schluck Zaubertrank nehmen. (Avatar von tactac) ... Viele Grüße Ronald


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3171
  Beitrag No.13, eingetragen 2021-03-10

tactac's "Mathematisch" übersetzt in "Python für Arme" sähe ganz naiv so aus: \sourceon Python def mult(A,B): a1,a2,a3 = A b1,b2,b3 = B k4 = a3*b3 k3 = a2*b3 + a3*b2 + k4 k2 = a1*b3 + a2*b2 + a3*b1 + k3 + k4 k1 = a1*b2 + a2*b1 + k3 + k4 k0 = a1*b1 + k3 return (k0,k1,k2) def pow(T,n): if n==1: return T if n%2==0: return pow(mult(T,T),n//2) return mult(pow(T,n-1),T) def Tribonacci(n): if n == 0: return 0 T = (0,1,0) a,b,c = pow(T,n+1) return c \sourceoff


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 7002
Wohnort: Niedersachsen
  Beitrag No.14, eingetragen 2021-03-10

Ein Bemerkung: Möchte man T(n) von vornherein nur modulo einer bestimmten Zahl M berechnen, so wächst die notwendige Rechenzeit nur logarithmisch mit n, also linear mit der Stellenzahl(!) von n(*). Ist man an einem exakten Ergebnis interessiert (also ohne modulo), dann wächst die Zahl der Stellen, die dafür berechnet werden müssen linear mit n, was zu einem Gesamtaufwand von $O(n\log n)$ führt. Algorithmisch ist das Problem sehr leicht, für die Berechnung von T(109) reichen ein paar hundert Multiplikationen und Additionen aus. Das einzige Problem ist die Länge der beteiligten Zahlen. (*) Modulo 106 rechnet Matlab T(109) in unter einer Millisekunde aus. Größere Module sind problematisch, weil Matlab (zumindest in meiner Version) kein Zahlenformat für lange Ganzzahlen hat. [Die Antwort wurde nach Beitrag No.12 begonnen.]


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2548
  Beitrag No.15, eingetragen 2021-03-10

Für Leute, die Python nicht so gut lesen können, vll. noch eine Haskell-Version: \sourceon Haskell data T n = T n n n deriving (Eq, Ord, Show) instance Num n => Num (T n) where -- der Vollständigkeit halber auch mit + und -, auch wenn -- das für's vorliegende Problem nicht benötigt wird fromInteger n = T (fromInteger n) 0 0 T a b c + T d e f = T (a+d) (b+e) (c+f) T a b c - T d e f = T (a-d) (b-e) (c-f) T a b c * T d e f = T k0 k1 k2 where k0 = a*d + k3 k1 = a*e + b*d + k3 + k4 k2 = a*f + b*e + c*d + k3 + k4 k3 = b*f + c*e + k4 k4 = c*f abs = undefined signum = undefined tribo :: Int -> Integer tribo n = let T _ _ c = T 0 1 0 ^ (n+1) in c \sourceoff [Die Antwort wurde nach Beitrag No.13 begonnen.]


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Beitrag No.16, vom Themenstarter, eingetragen 2021-03-10

\quoteon(2021-03-10 09:24 - DerEinfaeltige in Beitrag No. 13) tactac's "Mathematisch" übersetzt in "Python für Arme" sähe ganz naiv so aus: \sourceon Python def mult(A,B): a1,a2,a3 = A b1,b2,b3 = B k4 = a3*b3 k3 = a2*b3 + a3*b2 + k4 k2 = a1*b3 + a2*b2 + a3*b1 + k3 + k4 k1 = a1*b2 + a2*b1 + k3 + k4 k0 = a1*b1 + k3 return (k0,k1,k2) ... \sourceoff \quoteoff Oh, danke DerEinfaeltige, jetzt sieht man doch genau, dass der tactac-Array-Mul-Algorithmus mit 9 "echten Multiplikationen" auskommt. Danke tactac. In Mathematica sind das 3 Zeilen: \sourceon mathematica MulTac[a_,b_]:=Module[{k4=a[[3]]*b[[3]]},k3=a[[2]]*b[[3]]+a[[3]]*b[[2]]+k4;ret={a[[1]]*b[[1]]+k3,a[[1]]*b[[2]]+a[[2]]*b[[1]]+k3+k4,a[[1]]*b[[3]]+a[[2]]*b[[2]]+a[[3]]*b[[1]]+k3+k4};ret]; PowTac[T_,n_]:=If[n==1,T,If[Mod[n,2]==0,PowTac[MulTac[T,T],Quotient[n,2]],MulTac[PowTac[T,n-1],T]]]; TribonacciTac[n_]:=Module[{aT},aT=PowTac[{0,1,0},n];aT[[3]]]; Probe: Table[{TribonacciTac[k],MatrixPower[{{0,1,0},{0,0,1},{1,1,1}},k][[1]]//Last},{k,10}]//Grid nach n-Offset Korrektur stimmen beide: 0 0 1 1 1 1 2 2 4 4 7 7 13 13 24 24 44 44 81 81 \sourceoff Nun kann ich das nach YMP wandeln (sehr Hardware-nah: FFT-Mul, AVX2, Multitasking) & mit Mio.-stelligen Zahlen testen... Bei meinem gestrigen Programm (21 Multiplikationen) konnte ich nun auch die 20 Kerne zuschalten & die Berechnungszeit der 71 Mio. stelligen Zahl von 17.5 s auf 4.4 s reduzieren! https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Tribonacci2hoch28_20K_4s.PNG Mit 9 Mul sollte das noch zu halbieren sein...


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Beitrag No.17, vom Themenstarter, eingetragen 2021-03-10

Tatsächlich, YMP kann mit dem 9-Mul-Algorithmus die Rechenzeit halbieren: https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Tribonacci2hoch28_20K_2s.PNG https://matheplanet.com/matheplanet/nuke/html/images/forum/subject/shocked.gif \sourceon Tribonacci(2^28) Mathematica MatrixPow 28.9 s 3 Threads Mathematica TribonacciTac 26.6 s 1 Thread YMP Tribonacci2h 21 Mul 4.4 s 20 Threads YMP TribonacciTac 9 Mul 2.3 s 20 Threads \sourceoff YMP TribonacciTac(10^7) braucht nur 0.33 s -> Startbeitrag. YMP TribonacciTac(10^9) -> 35 s 264649443 Bytes Super! Vielen Dank an alle Mitwirkenden! Grüße Gerd


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Beitrag No.18, vom Themenstarter, eingetragen 2021-03-10

\sourceon Benchmark Tribonacci(10^9) incl. RAM-Disk Mathematica 9 Mul 297.9 s 1 Thread Mathematica MatrixPower 128.8 s 3 Threads YMP 9-Mul 35.0 s 20 Threads YMP BINET's Formula 33.48s 20 Threads Beitrag 19 \sourceoff Während bei 2^28 der tactac's 9 Mul Algo noch vorn lag, holte Mathematicas 3 Thread Befehl MatrixPower bei 10^9 auf. Es kann auch sein, dass MatrixPower durch folgende Optimierung schneller wurde: https://en.wikipedia.org/wiki/Addition-chain_exponentiation


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Beitrag No.19, vom Themenstarter, eingetragen 2021-03-12

Nur weil Mathematica bei BINET's Formel so langsam ist, muss das bei YMP nicht auch so sein! Also habe ich ALLES von Ganzzahl auf Gleitkommazahl umgestellt. Wurzel-Iteration gab es schon für 1/Sqrt(x) -> also Sqrt(x)=x*1/Sqrt(x) (es geht bei Rekorden möglichst darum, die langsame Division zu vermeiden) Für 3. Wurzel = x^(1/3) habe ich aber keine schnelle Iteration gefunden -> also die altbekannte Newton-Iteration. Für n=10^7 kam tatsächlich 0,4 s heraus! Das macht optimistisch -> also n=10^9 https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Tribonacci10hoch9_Binet_33_4s.PNG Rekord! 2 s schneller! Der Wert stimmt exakt: 5574879143...871128684941792256.00 UNGLAUBLICH !!! https://matheplanet.com/matheplanet/nuke/html/images/forum/subject/shocked.gif Falls sich noch eine schnellere Iteration für die 3. Wurzel findet als \sourceon nameDerSprache r0=x/2.5; r:=2*r/3+x/(3*r*r) lim r = x^(1/3) \sourceoff ...oder jemand eine Iteration ohne die beiden Divisionen kennt... ...kann sich ja mal melden. Grüße Gerd


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8980
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.20, eingetragen 2021-03-13

Kenne jetzt den Thread nicht... Hattest du schon die OEIS gecheckt? A000073 Da stehen viele Formeln und auch Programme. PARI ist doch auch sehr flott bei solchen Geschichten. Hier noch etwas zur n-ten Zahl: Simon Plouff Gruß, Slash


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1730
  Beitrag No.21, vom Themenstarter, eingetragen 2021-03-13

\quoteon(2021-03-13 00:20 - Slash in Beitrag No. 20) Kenne jetzt den Thread nicht... Hattest du schon die OEIS gecheckt? A000073 Da stehen viele Formeln und auch Programme. PARI ist doch auch sehr flott bei solchen Geschichten. Hier noch etwas zur n-ten Zahl: Simon Plouff Gruß, Slash \quoteoff Man merkt, dass Du fast nichts gelesen hast: - A000073 Startbeitrag - PARI -> Beitrag Nr. 1 - daraus entwickelte sich die schnellere MatrixPower - plouffe.fr -> hat noch 4 3. Wurzeln 2000 Stellen -> ich 2 und gehe gegen 1 Mrd Stellen Meine letzte Frage ging Richtung: 3. Wurzel Iteration, denn da hat der Weltmeister bereits tolle Ideen zur 2. Wurzel. (Beitrag 19) Solche 1/x * Faktor Iteration habe ich aber noch nicht gefunden.


   Profil
hyperG hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]