Project Euler 25: 1000-digit Fibonacci number

Ännu ett problem som har med Fibonacci-sekvensen att göra.

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

För ovanlighetens skulle så var det svårast med detta problem att uttrycka den övre gränsen för hur många fibonacci-tal som ska beräknas. Erlangs math:pow multiplicerar inte tal om och om igen utan använder flyttal och en snabb-algoritm för att beräkna potenser. Det betyder att det finns en övre gräns för hur stora tal math:pow kan användas för och vi passerar denna gräns med råge. Vi får alltså göra en helt egen variant och manuellt beräkna den övre gränsen.

Eftersom vi vill att programmet ska bli klart inom vår livstid så börjar vi med de två första talen i sekvensen och jobbar oss uppåt. Använder man istället Fib(N) = Fib(N-1) + Fib(N-2) så är tidskomplexiteten T(N) = O(1.618)^N istället för linjär tid.

problem_25() ->
    Start = os:timestamp(),
    Max_Size = powers(10, 999, 1),
    Resultat = fib(1,1,2, Max_Size),
    io:format("Svaret är ~p och tog ~f sekunder att berakna~n", [Resultat, timer:now_diff(os:timestamp(), Start) / 1000000]).

powers(N, 0, Count) ->
    Count;
powers(N, M, Count) ->
    powers(N, M-1, Count*N).

fib(N, _, Count, Max_Size) when N > Max_Size ->
    Count;
fib(N, N_Old, Count, Max_Size) -> 
fib(N+N_Old, N, Count+1, Max_Size).

Länk till github