Algorithmensammlung: Zahlentheorie: Fibonacci-Folge

Aus Wikibooks
Wechseln zu: Navigation, Suche

Algorithmensammlung: Zahlentheorie

Programme zur Berechnung des n-ten Wertes Fn der  Fibonacci-Folge aus den Startwerten F0 = 0 und F1 = 1

Basic C64[Bearbeiten]

Fibonaccizahlen in binärer Darstellung
 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 ?

 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[Bearbeiten]

 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)[Bearbeiten]

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[Bearbeiten]

Werden Matrizen der Form

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

.
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.

Julia[Bearbeiten]

Rekursiver naiver Fibonacci-Algorithmus in Julia.

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

Python[Bearbeiten]

Die folgende Implementierung ist rekursiv:

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

Diese Funktion stimmt direkt mit der Definition der Folge überein und ist somit gut für Lernzwecke geeignet. Die Geschwindigkeit ist allerdings nicht ausreichend für einen praktischen Einsatz. 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.

FreePascal[Bearbeiten]

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;