Matroids Matheplanet Forum Index
Moderiert von Spock mire2
Mathematische Software & Apps » Mathematica » Wie berechnet Mathematica die Fibonacci-Zahlen?
Druckversion
Druckversion
Autor
Universität/Hochschule J Wie berechnet Mathematica die Fibonacci-Zahlen?
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3226
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2012-06-21


Hallo.Die Frage steht schon im Titel:

Wie berechnet Mathematica die Fibonacci-Zahlen?

In den Implementation Notes zu "Combinatorial Functions" findet man folgendes "Fibonacci[n] uses an iterative method based on the binary digit sequence of n."

Weiß jemand hierzu etwas genaueres?

Gruß endy




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Gockel
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 22.12.2003
Mitteilungen: 25545
Wohnort: Jena
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2012-06-21


Hi.

fed-Code einblenden

mfg Gockel.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3226
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2012-06-21


Hallo Gockel,danke für die Antwort.
Dies führt dann ,wenn ich dich richtig verstanden habe,auf die Gleichungen <math>\displaystyle F_{2n}=2\cdot F_n \cdot F_{n-1}+F_n^2</math> und  <math>\displaystyle F_{2n+1}=F_n^2+F_{n+1}^2</math>.Damit kann man die Fibos schon einmal wirklich schnell ausrechnen.Diese Identität kenne ich aber schon und ich glaube nicht,dass mathematica die Fibos so ausrechnet;denn man braucht keine Konvertierung von n ins Binärsystem.
Gruß endy
 

[ Nachricht wurde editiert von endy am 23.06.2012 14:40:27 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Gockel
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 22.12.2003
Mitteilungen: 25545
Wohnort: Jena
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2012-06-21


Ob man das "braucht" ist ja egal. Auf jeden Fall kann man es mit einer Binärdarstellung von n die Square-and-multiply-Routine ganz einfach implementieren.

mfg Gockel.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ehemaliges_Mitglied
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2012-06-21


Ich habe einen Link der dir vielleicht weiterhelfen dürfte, ist leider Code von Matlab.
In dem Package sind sehr viele Algorithmen und Formeln zur Berechnung von großen Fibonaccizahlen beschrieben. Ich kann mich an eine Implementierung mit Binärumwandlung erinnern.

http://www.mathworks.com/matlabcentral/fileexchange/34766-the-fibonacci-sequence

Oder hier das Package (keine Anmeldung erforderlich):

http://dl.dropbox.com/u/22358873/FibonacciSequence.zip

Grüße Hoinzy



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3226
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2012-06-23


Danke für die Antworten.Also ich will die Fibonacci-Zahlen mittels mathematica möglichst schnell berechnen.Wenn ich die implementiere Fibonaccifunktion Fibonacci verwende ,braucht diese bei mir etwa 37 Sekunden um Fibonacci[109] zu berechnen.
mathematica
Timing[Fibonacci[10^9];]

Mit den Gleichungen aus Beitrag Nr. 2 dauert es etwa 56 Sekunden
mathematica
Clear[fib]
$RecursionLimit := Infinity
fib[0] := 0
fib[1] := 1
fib[n_?EvenQ] := fib[n] = 2 fib[n/2 - 1]*fib[n/2] + fib[n/2]^2
fib[n_ ? OddQ] := fib[n] = fib[(n - 1)/2 + 1]^2 + fib[(n - 1)/2]^2
Timing[fib[10^9];]

Frage:Sieht jemand eine Möglichkeit die Fibonaccizahlen mittels mathematica schneller als mit der Methode aus Beitrag Nr. 2 zu berechnen,ohne die eingebaute Funktion Fibonacci zu benutzen?

Gruß endy

PS:
@hoinzy:Willkommen im Forum.Deine Links sind nicht klickbar.
 

[ Nachricht wurde editiert von endy am 23.06.2012 16:43:10 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
OmmO
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 01.12.2006
Mitteilungen: 2310
Wohnort: Kiel
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2012-06-23


Hallo,
wie genau soll das denn sein?
Und wie lange dauert die Formel von Binet? Evtl kann man sich da auf die größte Potenz beschränken.
Gruß OmmO



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3226
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2012-06-23


2012-06-23 15:02 - OmmO in Beitrag No. 6 schreibt:
Hallo,
wie genau soll das denn sein?
Exakt

Und wie lange dauert die Formel von Binet? Evtl kann man sich da auf die größte Potenz beschränken.

Binet ist viel zu langsam.
mathematica
binet[n_] := Round[1/Sqrt[5]*((1 + Sqrt[5])/2)^n]
Timing[binet[10^7];]

braucht bei mir etwa 7.4 Sekunden und fib[107] etwa 0.4 Sekunden.

Gruß endy
 




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rlk
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.03.2007
Mitteilungen: 11012
Wohnort: Wien
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2012-06-26


Hallo endy,
ich tippe auch auf eine Methode wie die in Beitrag 2.

In dem Programm in Beitrag 5 kommt fib[n/2] zweimal vor. Ist Mathematica so schlau, es nur einmal zu berechnen?

Einige Methoden zur effizienten Berechnung der Fibonacci-Zahlen werden im HAKMEM besprochen.

Grüße,
Roland




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3226
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2012-06-28


Hallo,danke für die Antwort.Mit
mathematica
f[x_]:=f[x]=functionbody

definiert man in mathematica rekursive Funktionen,die memorisiert sind.Also werden die Werte nicht doppelt berechnet.Dies kann man sich auch mittels Trace anzeigen lassen.

In HAKMEN lese ich gerade;hast du hier selber schon einmal vor langer Zeit auf dem MP verlinkt. smile

Ich habe es noch mit einem weiteren Divide und Conquer Algorithmus probiert und über Matrixpotenzen;aber beide Methoden sind langsamer als die Methode aus Beitrag Nr.5 .

Gruß endy


[ Nachricht wurde editiert von endy am 28.06.2012 19:38:59 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
halirutan
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 11.11.2008
Mitteilungen: 1143
Wohnort: Leipzig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2012-07-04


Moin,

mehrere Methoden sind auch in Computer Science with MATHEMATICA beschrieben. Daraus:
Mathematica
fibh[n_] := 
 Module[{r11 = 1, r12 = 0, r22 = 1, digits = IntegerDigits[n - 1, 2], 
   i, t},
  Do[ If[digits[[i]] == 1,
    {r11, r22} = {r11 (r11 + 2 r12), r12 (r11 + r22)};
    r12 = r11 - r22,
    t = r12 (r11 + r22);
    {r11, r12} = {r11 (r11 + 2 r12) - t, t};
    r22 = r11 - r12
    ],
   {i, Length[digits] - 1}
   ];
  If[digits[[-1]] == 1,
   r11 (r11 + 2 r12),
   r11 (r11 + r22) - (-1)^((n - 1)/2)
   ]
  ];
 
Timing[fibh[10^9];]
 
(*
  {10.760000, Null}
*)

und zum Vergleich, da mein Rechner relativ flott ist und die Absolutwerte keine Aussagekraft haben

Mathematica
Clear[fib]
$RecursionLimit := Infinity
fib[0] := 0
fib[1] := 1
fib[n_?EvenQ] := fib[n] = 2 fib[n/2 - 1]*fib[n/2] + fib[n/2]^2
fib[n_?OddQ] := fib[n] = fib[(n - 1)/2 + 1]^2 + fib[(n - 1)/2]^2
Timing[fib[10^9];]
 
(* 
  {16.860000, Null}
*)
 
Timing[Fibonacci[10^9];]
 
(*
  {8.460000, Null}
*)

Deine Implementierung braucht also ca die 2fache Zeit wie die BuildIn Funktion von Mathematica, wohingegen die Implementierung von Roman nur das 1.2fache an Zeit braucht.

Cheers
Patrick



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3226
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2012-07-06


Hallo.Danke für die Methode.Die Methode ist iterativ und nicht rekursiv wie die fib-Methode.Bei beiden handelt es sich um einen Divide und Conquer Algorithmus.Der Vorteil von der Methode von Maeder ist,dass sie nicht so viel Speicherplatz verbraucht wie die fib- Methode.Für die 109te Fibonaccizahl braucht man nur Bruchteile eines Mbytes,wohingegen man bei der fib-Methode 250 Mbyte braucht.

Die Methode wird auch ähnlich in A new kind of science angegeben  hier
mathematica
Clear[fibwolfram, f]
f[{a_, b_, s_}, 0] = {a (a + 2 b), s + a (2 a - b), 1};
f[{a_, b_, s_}, 1] = {-s + (a + b) (a + 2 b), a (a + 2 b), -1};
fibwolfram[n_] := 
 First[Fold[f, {1, 0, -1}, Rest[IntegerDigits[n, 2]]]]
Timing[fibwolfram[10^9];]
 

Da sie iterativ ist und auf einer Binärdarstellung beruht,wird es sich wohl im wesentlichen um die implementierte Fibonacci Funktion in mathematica handeln.

Gruß endy


[ Nachricht wurde editiert von endy am 17.07.2012 22:41:22 ]


-----------------
Dean Koontz : Zwielicht

Unzählige verschlungene Nachtpfade zweigen vom Zwielicht ab.
Etwas bewegt sich inmitten der Nacht,das nicht gut und nicht richtig ist.

The Book of Counted Sorrows.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3226
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2013-08-25


Hallo.

Ein Algorithmus der schneller ist als der von Maeder.Er ist knapp 10% langsamer als die in Mathematica implementierte Fibonaccifunktion:
mathematica
(*In*)
 
Clear @ fibrule
 
fibrule @ 0 := 0
fibrule @ 1 := 1
fibrule [x_?IntegerQ /; x >= 2] := 
 fibrule @ x = 
  QuotientRemainder[x, 
    2] /. {{m_, 0} :> 
     fibrule[m] (2*fibrule[m - 1] + fibrule[m]), {m_, 1} :> 
     fibrule[m + 1]^2 + fibrule[m]^2}
 
10^9 // fibrule ; // Timing // First
 
(* Out *)
39.921
 

Noch besser ist folgender Algorithmus,der Produkte von Lucaszahlen berechnet:

 Daisuke Takahashi:A fast algorithm for computing large Fibonacci number
mathematica
(* In *)
 
Clear @ fibtakahashi
 
fibtakahashi @ 0 = 0;
fibtakahashi @ 1 = 1;
fibtakahashi @ 2 = 1;
 
fibtakahashi[n_?IntegerQ /; n >= 3] := 
 Module[{f = 1, l = 1, sgn = -1, mask = 2^(Floor[Log[2, n]] - 1), 
   temp},
  For[j = 1, j <= Log[2, n] - 1, j++,
   temp = f*f;
   f = (f + l)/2;
   f = 2*(f*f) - 3 temp - 2 sgn;
   l = 5 temp + 2 sgn;
   sgn = 1;
   If[BitAnd[mask, n] != 0,
    temp = f; f = (f + l)/2; l = f + 2 temp; sgn = -1];
   mask = mask/2
   ];
  If[BitAnd[mask, n] == 0,
   f = f*l,
   f = (f + l)/2;
   f = f*l - sgn];
  f
  ]
 
10^9 // fibtakahashi; // Timing // First
10^9 // Fibonacci; // Timing // First
 
(* Out *)
 
28.345
36.536
 

Gruß endy




-----------------
Dean Koontz : Zwielicht

Unzählige verschlungene Nachtpfade zweigen vom Zwielicht ab.
Etwas bewegt sich inmitten der Nacht,das nicht gut und nicht richtig ist.

The Book of Counted Sorrows.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Amateur
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.10.2012
Mitteilungen: 826
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2013-08-26


2012-06-21 17:58 - endy im Themenstart schreibt:
... Wie berechnet Mathematica die Fibonacci-Zahlen?...

Hallo endy,
falls die Frage noch aktuell ist: Mathematica verwendet anscheinend die GMP-Funktion mpz_fib_ui.

GMP source code used in Mathematica:
www.wolfram.com/LGPL/GMP/
(gmp-4.3.2\mpz\fib_ui.c)

Im den GMP-Manuals 4.3.2 / 5.1.2 wird die Arbeitsweise von mpz_fib_ui identisch beschrieben.
 
GMP Manual (5.1.2): 15.7.4 Fibonacci Numbers(mpz_fib_ui)
gmplib.org/manual/Fibonacci-Numbers-Algorithm.html#Fibonacci-Numbers-Algorithm
gmplib.org/gmp-man-5.1.2.pdf

Viele Grüße A.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3226
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2013-08-31


@ Amateur: Danke.Wieder ein Problem gelöst.

Gruß endy






-----------------
Dean Koontz : Zwielicht

Unzählige verschlungene Nachtpfade zweigen vom Zwielicht ab.
Etwas bewegt sich inmitten der Nacht,das nicht gut und nicht richtig ist.

The Book of Counted Sorrows.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hieron
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 02.02.2013
Mitteilungen: 282
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2013-09-27


hi endy

genau so berechnet Mathematica7 die Fibonacci Zahlen

 😮
Mathematica
Attributes[Fibonacci] = {Listable, NumericFunction, Protected, ReadProtected}
 
Derivative[1][Fibonacci] ^:= Evaluate[(GoldenRatio^(2*#1)*Log[GoldenRatio] + Cos[#1*Pi]*Log[GoldenRatio] + Pi*Sin[#1*Pi])/(Sqrt[5]*GoldenRatio^#1)] & 
 
Derivative[0, 1][Fibonacci] ^:= Evaluate[(2*#1*Fibonacci[#1 - 1, #2] + (#1 - 1)*#2*Fibonacci[#1, #2])/(4 + #2^2)] & 
 
Derivative[1, 0][Fibonacci] ^:= Evaluate[(Pi + 2*ArcSinh[#2/2]*Cot[#1*Pi])*Csc[#1*Pi]*Fibonacci[-#1, #2] + 
       (Pi*Cot[#1*Pi] + ArcSinh[#2/2]*(Cot[#1*Pi]^2 + Csc[#1*Pi]^2))*Fibonacci[#1, #2]] & 
 
Fibonacci /: System`Private`InternalSeries[HoldPattern[Fibonacci[System`SeriesDump`n_, System`SeriesDump`w_]], 
      {System`SeriesDump`z_, System`SeriesDump`p_, System`SeriesDump`nn_Integer}] := 
     Module[{System`SeriesDump`re}, System`SeriesDump`re = Sin[(Pi*System`SeriesDump`n)/2]^2*System`SeriesDump`Hyp2F1All[(1 - System`SeriesDump`n)/2, 
            (1 + System`SeriesDump`n)/2, 1/2, -(System`SeriesDump`w^2/4), False, System`SeriesDump`z, System`SeriesDump`p, System`SeriesDump`nn] + 
          ((System`SeriesDump`n*System`SeriesDump`w)/2)*Cos[(Pi*System`SeriesDump`n)/2]^2*System`SeriesDump`Hyp2F1All[1 - System`SeriesDump`n/2, 
            1 + System`SeriesDump`n/2, 3/2, -(System`SeriesDump`w^2/4), False, System`SeriesDump`z, System`SeriesDump`p, System`SeriesDump`nn]; 
        System`SeriesDump`re = System`Private`InternalSeries[System`SeriesDump`re, {System`SeriesDump`z, System`SeriesDump`p, System`SeriesDump`nn}]; 
        System`SeriesDump`re /;  !FreeQ[System`SeriesDump`re, SeriesData] && FreeQ[System`SeriesDump`re, System`Private`InternalSeries | $Failed | 
            Indeterminate]] /; System`SeriesDump`nn >= 0 &&  !Internal`DependsOnQ[System`SeriesDump`n, System`SeriesDump`z] && 
       Internal`DependsOnQ[System`SeriesDump`w, System`SeriesDump`z] && System`SeriesDump`limitPointAccessibleQ[System`SeriesDump`w, 
        System`SeriesDump`z, System`SeriesDump`p]
 
Fibonacci /: System`Private`InternalSeries[HoldPattern[Fibonacci[System`SeriesDump`w_, System`SeriesDump`a_]], 
      {System`SeriesDump`z_, System`SeriesDump`p_, System`SeriesDump`nn_Integer}] := 
     Module[{System`SeriesDump`exp, System`SeriesDump`re}, 
       System`SeriesDump`exp = ((System`SeriesDump`a + Sqrt[4 + System`SeriesDump`a^2])^(2*System`SeriesDump`w) - 
           4^System`SeriesDump`w*Cos[System`SeriesDump`w*Pi])/(2^System`SeriesDump`w*(System`SeriesDump`a + Sqrt[4 + System`SeriesDump`a^2])^
            System`SeriesDump`w*Sqrt[4 + System`SeriesDump`a^2]); System`SeriesDump`re = System`Private`InternalSeries[System`SeriesDump`exp, 
          {System`SeriesDump`z, System`SeriesDump`p, System`SeriesDump`nn}]; System`SeriesDump`re /;  !FreeQ[System`SeriesDump`re, SeriesData] && 
          FreeQ[System`SeriesDump`re, System`Private`InternalSeries | $Failed | Indeterminate]] /; 
      System`SeriesDump`nn >= 0 &&  !Internal`DependsOnQ[System`SeriesDump`a, System`SeriesDump`z] && Internal`DependsOnQ[System`SeriesDump`w, 
        System`SeriesDump`z] && System`SeriesDump`limitPointAccessibleQ[System`SeriesDump`w, System`SeriesDump`z, System`SeriesDump`p]
 
Fibonacci /: System`Private`InternalSeries[HoldPattern[Fibonacci[System`SeriesDump`w_]], {System`SeriesDump`z_, System`SeriesDump`p_, 
       System`SeriesDump`nn_Integer}] := Module[{System`SeriesDump`re, System`SeriesDump`a}, 
       System`SeriesDump`re = System`Private`InternalSeries[Fibonacci[System`SeriesDump`w, System`SeriesDump`a], 
          {System`SeriesDump`z, System`SeriesDump`p, System`SeriesDump`nn}]; System`SeriesDump`re = 
         System`SeriesDump`re /. {System`SeriesDump`a -> 1} /. {System`SeriesDump`c_SeriesData :> ReplacePart[System`SeriesDump`c, 
             (Together[Expand[#1]] & ) /@ System`SeriesDump`c[[3]], 3]}; System`SeriesDump`re /;  !FreeQ[System`SeriesDump`re, SeriesData] && 
          FreeQ[System`SeriesDump`re, System`Private`InternalSeries | $Failed | Indeterminate]] /; 
      System`SeriesDump`nn >= 0 && Internal`DependsOnQ[System`SeriesDump`w, System`SeriesDump`z] && System`SeriesDump`limitPointAccessibleQ[
        System`SeriesDump`w, System`SeriesDump`z, System`SeriesDump`p]
 
Fibonacci[-1] = 1
 
Fibonacci[0] = 0
 
Fibonacci[1] = 1
 
Fibonacci[(System`FibonacciDump`n_Integer)?Positive] := System`FibonacciDump`fibposint[System`FibonacciDump`n]
 
Fibonacci[System`FibonacciDump`n_Integer] := (If[EvenQ[System`FibonacciDump`n], -#1, #1] & )[System`FibonacciDump`fibposint[-System`FibonacciDump`n]]
 
Fibonacci[(System`FibonacciDump`x_)?InexactNumberQ] := System`FibonacciDump`fibfloat[System`FibonacciDump`x, -1]
 
Fibonacci[1, _] := 1
 
Fibonacci[0, _] := 0
 
Fibonacci[-1, _] := 1
 
Fibonacci[System`FibonacciDump`n_, 1] := Fibonacci[System`FibonacciDump`n]
 
Fibonacci[System`FibonacciDump`n_, -1] := Fibonacci[-System`FibonacciDump`n]
 
Fibonacci[System`FibonacciDump`n_, 0] := Sin[(Pi*System`FibonacciDump`n)/2]^2
 
Fibonacci[System`FibonacciDump`n_, System`FibonacciDump`z_] := System`FibonacciDump`fibfloat2[System`FibonacciDump`n, System`FibonacciDump`z] /; 
     InexactNumberQ[System`FibonacciDump`n] || InexactNumberQ[System`FibonacciDump`z]
 
Fibonacci[(System`FibonacciDump`n_Integer)?Positive, (System`FibonacciDump`z_)?NumberQ] := System`FibonacciDump`fibposintnum[System`FibonacciDump`n, 
     System`FibonacciDump`z]
 
Fibonacci[System`FibonacciDump`n_Integer, (System`FibonacciDump`z_)?NumberQ] := (If[EvenQ[System`FibonacciDump`n], -#1, #1] & )[
     System`FibonacciDump`fibposintnum[-System`FibonacciDump`n, System`FibonacciDump`z]]
 
Fibonacci[(System`FibonacciDump`n_Integer)?Positive, (System`FibonacciDump`z_)?System`FibonacciDump`NonNumericQ] := 
    System`FibonacciDump`fibpoly[System`FibonacciDump`n, System`FibonacciDump`z]
 
Fibonacci[System`FibonacciDump`n_Integer, (System`FibonacciDump`z_)?System`FibonacciDump`NonNumericQ] := 
    (If[EvenQ[System`FibonacciDump`n], System`FibonacciDump`fpsimplify[-#1], #1] & )[System`FibonacciDump`fibpoly[-System`FibonacciDump`n, 
      System`FibonacciDump`z]]
 
System`FibonacciDump`e:Fibonacci[System`FibonacciDump`args___] := System`FibonacciDump`e /; 
     ArgumentCountQ[Fibonacci, Length[Unevaluated[{System`FibonacciDump`args}]], 1, 2]
 
HoldPattern[Fibonacci[System`SeriesDump`n_, System`SeriesDump`ser_SeriesData]] := 
    System`Private`SeriesSingularityHandler[Fibonacci, System`SeriesDump`n, System`SeriesDump`ser] /; 
      !Internal`DependsOnQ[System`SeriesDump`n, First[System`SeriesDump`ser]]
 
HoldPattern[Fibonacci[System`SeriesDump`ser_SeriesData, System`SeriesDump`a_]] := 
    System`Private`SeriesSingularityHandler[Fibonacci, System`SeriesDump`ser, System`SeriesDump`a] /; 
      !Internal`DependsOnQ[System`SeriesDump`a, First[System`SeriesDump`ser]]
 
HoldPattern[Fibonacci[System`SeriesDump`ser_SeriesData]] := System`Private`SeriesSingularityHandler[Fibonacci, System`SeriesDump`ser]
 
Fibonacci /: MakeBoxes[BoxForm`apat$:HoldPattern[Fibonacci[___]], TraditionalForm] := BoxForm`BoxFormAutoLoad[MakeBoxes, BoxForm`apat$, 
      TraditionalForm, "Typeset`Combinatorial`", {{BernoulliB, TraditionalForm}, {BellB, TraditionalForm}, {CatalanNumber, TraditionalForm}, 
       {Fibonacci, TraditionalForm}, {HarmonicNumber, TraditionalForm}, {EulerE, TraditionalForm}, {StirlingS1, TraditionalForm}, 
       {StirlingS2, TraditionalForm}, {ClebschGordan, TraditionalForm}, {ThreeJSymbol, TraditionalForm}, {SixJSymbol, TraditionalForm}, 
       {LucasL, TraditionalForm}, {NorlundB, TraditionalForm}, {BoxForm`MakeTraditionalExpression, 
        HoldPattern[BoxForm`MakeTraditionalExpression[SubscriptBox[TagBox[_, BernoulliB | BellB | EulerE | Fibonacci | LucasL | NorlundB | 
             CatalanNumber, ___], _]]]}, {TraditionalForm, HoldPattern[MakeExpression[SubscriptBox[
           InterpretationBox["H", HarmonicNumber, BlankNullSequence[]]
           , _], TraditionalForm]]}, {TraditionalForm, HoldPattern[MakeExpression[SubsuperscriptBox[
           InterpretationBox["H", HarmonicNumber, BlankNullSequence[]]
           , __], TraditionalForm]]}, {TraditionalForm, HoldPattern[MakeExpression[SubscriptBox[TagBox[_, BernoulliB | BellB | EulerE | Fibonacci | 
             LucasL | NorlundB | CatalanNumber, ___], _], TraditionalForm]]}, {TraditionalForm, 
        HoldPattern[MakeExpression[SubsuperscriptBox[TagBox[_, StirlingS1 | StirlingS2, ___], _, _], TraditionalForm]]}, 
       {TraditionalForm, HoldPattern[MakeExpression[TagBox[_, ClebschGordan, ___], TraditionalForm]]}, 
       {TraditionalForm, HoldPattern[MakeExpression[TemplateBox[_, "BernoulliB2" | "NorlundB3" | "BellB2" | "Fibonacci2" | "LucasL2" | 
            "HarmonicNumber2" | "EulerE2", ___], TraditionalForm]]}}]

Gruß hieron  😎



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 898
Wohnort: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2013-09-28


Nachdem ich das gelesen habe, ist mir ein wenig kariert im Hirn.

Woher hast du diesen Code?

mfg
thureduehrsen



-----------------
sammeltlemmas.blogspot.de/

https://www.informatik.uni-kiel.de/~tdu/



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hieron
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 02.02.2013
Mitteilungen: 282
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2013-09-28


Direkt von der Quelle, von Mathematica7

Es ist eben der Implementierungscode von Fibonacci

Augenblick mal, mach mich nicht schwach, bin ich vielleicht der einzige in diesem Forum,  der weiß, wie man Implementierungscodes auslesen kann???

 😵  😮   ☹️



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3226
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2013-09-28


Hallo.

Ich habe es bis eben nicht gewusst,aber du hast etwa folgendes gemacht:

Mittels Definition erkennt man, dass Fibonacci ReadProtected ist und dieses Attribut kann man aufheben und dann die Definition lesen:

mathematica
ClearAttributes[Fibonacci, ReadProtected]
Fibonacci
Definition @ Fibonacci

Gruß endy




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hieron
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 02.02.2013
Mitteilungen: 282
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2013-09-28


clever endy  😉

ja, in etwa so ...
statt Definition kann man auch FullDefinition verwenden.

und um die Ausgabe kopierbar bzw. editierbar zu machen, hänge ich noch ein InputForm an.

Fibonacci//FullDefinition//InputForm

gruß hieron



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46376
Wohnort: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2013-09-28


Hi,
mir scheint, das wirkliche Wesen der Frage läuft eigentlich bei solch extremen Anforderungen wie Fib[109] darauf hinaus, wie Mathematica die Durchführung von Integer-Multiplikationen effektiv durchführt.

Dass man es mit Methoden wie aus Beitrag #1 machen muss, ist völlig klar, die naive Rekursion fn = fn-1 + fn-2 nützt natürlich nichts.

Der eigentliche Engpaß besteht dann darin, dass man sehr große Integer-Zahlen multiplizieren muss, und das kann man nun wiederum gänzlich naiv machen, oder sich auf ausgefeilte Algorithmen, wie den von Schönhage-Strassen, stützen.

Ich sehe zwar nicht, wo dies in dem von hieron mitgeteilten Quelltext geschieht, aber irgendwo wird das schon versteckt sein, sonst könnte man solch hervorragende Timing-Ergebnisse nicht erreichen.
Gruß Buri




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3226
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, vom Themenstarter, eingetragen 2013-09-29


Hallo Buri,

im wesentlichen ist es die Methode fibrule aus Beitrag Nr.12,zumindestens was den mathematica-Code betrifft.

fib(109) hat 208.987.640 Stellen.Da im mathematica Kern  die  GNU_Multi-Precision_Library  implementiert ist,wird der Schönhage-Strassen  Algorithmus benutzt;zumindestens für die großen Multiplikationen,siehe  Schönhage-Strassen-algorithm.

Gruß endy



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
endy hat die Antworten auf ihre/seine Frage gesehen.
endy hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


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-2021 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]