Algorithmensammlung: Zahlentheorie: Fibonacci-Folge

Algorithmensammlung: Zahlentheorie

Programme zur Berechnung des n-ten Wertes $F_{n}$ der Fibonacci-Folge aus den Startwerten $F_{0}=0$ und $F_{1}=1$ und dem rekursiven Bildungsgesetz

$F_{n}=F_{n-1}+F_{n-2}$ für $n\geq 2$ .

Algorithmen

Eine direkte Implementierung durch die Rekursion

F(n) = F(n-1) + F(n-2)

wäre unsinnig, weil die Rechenzeit mit steigendem n extrem stark ansteigt. Für n > 1 würde die Funktion (in Pseudocode)

function fib(n)
     if n < 2
         return n
     return fib(n-1) + fib(n-2)

(F_n + L_n - 1) mal aufgerufen, dabei ist L_n das n-te Glied der Lucas-Folge, die wie die Fibonacci-Folge berechnet wird, nur mit anderen Startwerten $L_{0}=2$ und $L_{1}=1$ .

Für n = 43 (F₄₃ = 433494437) wären das 1402817465, also über 1,4 Milliarden Aufrufe.

Besser sind z. B. iterative Algorithmen, wie

function fib(n)
    if n < 2
        return n
    f2 = 0    // vorletzter Wert
    f1 = 1    // letzter Wert
    while n > 1
        n = n - 1
        f = f1 + f2
        f2 = f1
        f1 = f
    return f

.

Basic C64

 5 REM FIBONACCI 
 10 A = 1
 20 B = 1
 30 FOR X = 1 TO 20
 40 PRINT A
 50 PRINT B
 60 A = A + B
 70 B = A + B
 80 NEXT

Gibt es ein Programm mit nur einer Variablen A ?

Ja, wenn man den goldenen Schnitt heranzieht.

 10 PHI = (1 + 5^0.5) / 2
 20 FOR N = 1 TO 20
 30 FIB = INT(((PHI^N - (1-PHI)^N) / 5^0.5)+0.5)
 40 PRINT N,FIB
 50 NEXT

Wegen Rundungsfehlern ist die Folge nicht ganz korrekt.

Eine Variante mit einem Array

 10 REM FIBONACCI-FOLGE
 20 CLS
 30 REM DER ARRAY F WIRD MIT DEN FIBONACCI ZAHLEN GEFUELLT
 40 DIM F(50) 
 50 F(0) = 0
 60 F(1) = 1
 70 N = 1
 80 LET F(N+1) = F(N) + F(N-1)
 90 LET N = N + 1
 100 PRINT F(N);", ";
 110 REM STOP NACH 50 ZAHLEN
 120 IF N < 50 THEN GOTO 80

Basic X11

 REM FIBONACCI 
 A = 1 
 B = 1 
 FOR X = 1 TO 20 
 PRINT A 
 PRINT B 
 A = A + B 
 B = A + B 
 NEXT

Visual Basic for Applications (VBA)

Public Function Fibonacci(n As Long) As Variant
    Dim i As Long, a, b
    
    a = 0 ' =F(0)
    b = 1 ' =F(1)
    
    For i = 2 To n Step 2
        ' Abwechselnd a und b erhöhen
        a = a + b
        b = a + b
    Next i
    
    ' Zutreffenden Wert zurückgeben
    Fibonacci = IIf(n Mod 2 = 0, a, b)
End Function

Der Rückgabewert ist je nach Größe vom Datentyp Long oder Double. Die Funktion enthält keine Fehlerbehandlung bei n < 0.

Haskell

Werden Matrizen der Form

{\begin{pmatrix}a&b\\b&a+b\end{pmatrix}}

addiert oder multipliziert, ergibt sich erneut eine Matrix dieser Form. Für die Darstellung solcher Matrizen ist die zweite Zeile redundant. Außerdem ist

{\begin{pmatrix}0&1\\1&1\end{pmatrix}}^{n}={\begin{pmatrix}F_{n-1}&F_{n}\\F_{n}&F_{n+1}\end{pmatrix}}

.

data M r = M !r !r deriving (Eq, Show)

instance Num r => Num (M r) where
    fromInteger n = M (fromInteger n) 0
    M a b + M c d = M (a+c) (b+d)
    M a b - M c d = M (a-c) (b-d)
    M a b * M c d = M (a*c+b*d) (a*d+b*c+b*d)
    abs = undefined
    signum = undefined
    
fib :: Num r => Integer -> r
fib n = b where
    M a b = M 0 1 ^ n

Hier wird eine Num-Instanz für Matrizen der angegebenen Form definiert. Diese wird von der vordefinierten Exponentiation (^) :: (Integral b, Num a) => a -> b -> a benutzt, welche ihrerseits als binäre Exponentiation implementiert ist.

Eine Lösung mit Listengenerierung per Rekursion:

fibs = 0:1:zipWith (+) fibs (tail fibs)

Die Funktion fibs ruft man dann ohne Parameter auf. Zurückgegeben wird die endlose Fibonacci-Folge. Ausgeben kann man die nicht, aber zuweisen oder einen Wert herauspicken fibs!!100, oder einen Teil der Liste extrahieren take 101 fibs.

Dass das überhaupt funktioniert, kann verblüffen. Möglich ist das nur wegen Haskells Konzept der späten Auswertung (Lazy Evaluation), welches hier schamlos ausgenutzt wird. Eine detaillierte Erklärung, was intern abläuft, kann man finden, wenn man die Funktion als Suchbegriff in eine Suchmaschine eingibt.

Python

Die folgende Implementierung ist rekursiv:

# Getestet unter Python 3.4, sollte mit allen 3.x-Versionen funktionieren
def fib(n):
    if n > 1:
        return fib(n-1) + fib(n-2)
    else:
        return n

Diese Funktion stimmt direkt mit der Definition der Folge überein und allenfalls für Lernzwecke geeignet. Die Geschwindigkeit ist allerdings nicht ausreichend für einen praktischen Einsatz: die Laufzeit steigt in etwa proportional zum Funktionswert (nicht zum Wert des Parameters n). Dieser Mangel lässt sich z. B. mit Memoisation teilweise ausmerzen. Sobald die Zahlen allerdings etwas größer werden, ist die direkte Berechnung der Werte über die Formel von Moivre-Binet weitaus schneller:

# Getestet unter Python 3.4, sollte mit allen 3.x-Versionen funktionieren
import math


def moivre_binet(n):
    näherung = (1/math.sqrt(5)) * (((1+math.sqrt(5))/2)**n - ((1-math.sqrt(5))/2)**n)
    return int(abs(näherung))
    # nötig wegen möglicherweise irritierender Rundungsfehler durch mangelhafte 
    # maschineninterne Darstellung der irrationalen Wurzel aus 5

Geschwindigkeitstechnisch lässt sich da auch noch dran feilen, dazu lese man den dazugehörigen Wikipedia-Artikel, für die ersten Schritte sollte der Quelltext aber genügen.

Weitere Implementierungen

def fibonacciIterativ(n: int) -> int:
    assert n >= 0, "n must be a non-negative integer"
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a


def fibonacciFunktional(n: int) -> int:
    assert n >= 0, "n must be a non-negative integer"
    return reduce(lambda x, _: (x[1], x[0] + x[1]), range(n), (0, 1))[0]


def fibonacciEnd(n: int) -> int:
    assert n >= 0, "n must be a non-negative integer"
    return _fibonacciEnd(n, 0, 1)

def _fibonacciEnd(n: int, a: int, b: int) -> int:
    if n == 0:
        return a
    else:
        return _fibonacciEnd(n - 1, b, a + b)


def fibonacciMatrix(n: int) -> int:
    assert n >= 0, "n must be a non-negative integer"
    from numpy import array
    from numpy.linalg import matrix_power
    return matrix_power(array([[1, 1], [1, 0]]), n).item((0, 1))


def fibonacciTuple(n: int) -> int:
    assert n >= 0, "n must be a non-negative integer"
    return _fibonacciTuple(n)[0]

def _fibonacciTuple(n: int) -> Tuple[int, int]:
    if n == 0:
        return (0, 1)
    else:
        a, b = _fibonacciTuple(n - 1)
        return (b, a + b)


def fibonacciDoubling(n: int) -> int:
    assert n >= 0, "n must be a non-negative integer"
    return _fibonacciDoubling(n)[0]

def _fibonacciDoubling(n: int) -> Tuple[int, int]:
    if n == 0:
        return (0, 1)
    else:
        x, y = _fibonacciDoubling(n // 2)
        a = x * (y * 2 - x)
        b = x * x + y * y
        if n % 2 == 0:
            return (a, b)
        else:
            return (b, a + b)

FreePascal

Der Vollständigkeit halber, wie es schnurstracks geradewegaus rekursiv implementiert wird:

{**
	implements fibonacci sequence recursively
	
	\param n the index of the Fibonacci number to retrieve
	\returns the Fibonacci value at n
}
function fibonacci(const n: byte): qword;
begin
	// optimization: then part gets executed most of the time
	if n > 1 then
	begin
		fibonacci := fibonacci(n - 2) + fibonacci(n - 1);
	end
	else
	begin
		// since the domain is restricted to non-negative integers
		// we can bluntly assign the result to n
		fibonacci := n;
	end;
end;

Natürlich will man lieber iterativ rechnen.

{**
	implements Fibonacci sequence iteratively
	
	\param n the index of the Fibonacci number to calculate
	\returns the Fibonacci value at n
}
function fibonacci(const n: longword): qword;
type
	/// more meaningful identifiers than simple integers
	relativePosition = (previous, current, next);
var
	/// temporary iterator variable
	i: longword;
	/// holds preceding fibonacci values
	f: array[relativePosition] of qword;
begin
	f[previous] := 0;
	f[current] := 1;
	
	// note, in Pascal for-loop-limits are inclusive
	for i := 1 to n do
	begin
		f[next] := f[previous] + f[current];
		f[previous] := f[current];
		f[current] := f[next];
	end;
	
	// assign to previous, bc f[current] = f[next] for next iteration
	fibonacci := f[previous];
end;

Es ist eigentlich lächerlich, die Fibonacci-Sequenz in Assembler zu programmieren, weil moderne Compiler bereits gut optimieren. Zum Beispiel setzt FPC die Summenbildung auf x86-64-Platformen mittels der Zeiger-Arithmetik-Instruktion lea (“load effective address”) um. Zu Demonstrationszwecken aber trotzdem mal. Die folgende Implementation beachtet insbesondere einen Ganzzahlüberlauf (was mit lea nicht möglich ist, da diese Instruktion keine flags setzt).

{**
	calculates Fibonacci number iteratively in ALU
	
	\param n the index of the Fibonacci number to calculate
	\returns the Fibonacci number at n
*}
function fibonacci(const n: longword): qword; assembler;
{$goto on}
label
	fibonacci_iterate, fibonacci_done;
{$asmMode intel}
asm
	// instructions that modify flags before the cmp
	xor rax, rax // rax := 0
	xor r10, r10 // r10 := 0
	// used by cmov in loop, bc cmov can not handle immediates
	mov r12, 1   // r12 := 1
	xor r13, r13 // r13 := 0
	
	cmp n, rax   // rax = n [n = 0]
	// ecx is used as counter variable by loop-instruction
	mov ecx, n   // ecx := n
	mov r11, 1   // r11 := 1
	je fibonacci_done // if n = 0 then goto done

fibonacci_iterate:
	mov rax, r10 // rax := r10        | effectively:
	add rax, r11 // rax := rax + r11  | rax := r10 + r11
	
	// xchg would be slower, since we wanna _drop_ one of the values
	mov r10, r11 // r10 := r11
	// possibly save to restore last valid value
	cmovnc r11, rax // if not CF then r11 := rax
	
	// destroy loop on overflow:
	// set ecx to 1, so decrementing hits zero (loop abort condition)
	cmovc ecx, r12 // if CF then ecx := 1
	cmovc r10, r13 // if CF then r10 := 0
	loop fibonacci_iterate // dec(ecx)
	// if ecx <> 0 then goto iterate
	
	
	// F_{93} is the largest value a qword can hold
	cmp n, 93      // 93 = n ?
	cmove r10, r11 // r10 := r11  | restore last value
	
fibonacci_done:
	// the @result macro represents the function's return value
	mov @result, r10 // result := r10
end;