Fibonacci Zahl berechnen.

Question

Hallo:) Bei dieser Aufgabe bräuchte ich Hilfe:

Berechne F₁₀₀ mod 100 mit schneller Exponentiation

Answer 1

Ich würde es über die Matrixversion machen, also berechnen

$$M^{100}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{100} $$

und zwischendurch immer mod 100 reduzieren.   

Gemäß der Beschreibung bei

https://de.wikipedia.org/wiki/Binäre_Exponentiation#Algorithmus

ginge es wohl so

100 = 64+32+4 = (1100100)₂

Das führt (in der Notation von Wikipedia zu

QM QM Q Q QM Q Q und nach dem Streichen

Q      M      Q         Q     Q             M          Q          Q

Kontrolle:

M² M³  M⁶   M¹²    M²⁴     M²⁵   M⁵⁰    M¹⁰⁰

Passt also. Dann mal los:

M² =  2    1
            1    1

mal M gibt    3   2
                    2    1

quadrieren   13   8
                     8    5

quadrieren   233   144
                     144    89

reduzieren mod 100      33   44
                                      44    89

quadrieren  und reduzieren  25   68
                                             68   57

mal M und reduzieren      93    25
                                         25    68

quadrieren  und reduzieren  74   25
                                             25   49

quadrieren  und reduzieren  01   75
                                             75   26

Also endet f₁₀₀ auf 75.