-1
$\begingroup$

Hi mathgeeks,

Given an extremely large fibonacci number X, and it's position in the fibonacci sequence N, is there any way to determine the N-1th fibo num, WITHOUT doing the bruteforce dance of counting from 1 upwards?

I've tried attacking the problem by dividing the number by two, and determining the difference between the N-1th, and N-2th, but that would require calculating Fib(n-3)/2, which makes the problem circular.

Also would be interested, if this can be proven not to be possible, thanks

$\endgroup$
3
  • 3
    $\begingroup$ Just divide by the golden mean and round to the nearest integer. This gives the correct (n-1)st Fibonacci provided that F_n is greater than 1. $\endgroup$
    – Todd Trimble
    Dec 26, 2010 at 15:34
  • $\begingroup$ @Todd, that's a very similar approach to the one suggested below by J.C. Ottem. $\endgroup$ Dec 26, 2010 at 15:41
  • $\begingroup$ Yes, I see that now. Anyway, I vote to close this question as being not anywhere near research level. $\endgroup$
    – Todd Trimble
    Dec 26, 2010 at 15:42

3 Answers 3

5
$\begingroup$

For large $n$, $\frac{f_{n+1}}{f_n} \approx \phi = 1.618..$. Hence you can get $f_n$ from $f_{n+1}$ by rounding $\frac{f_{n+1}}{\phi}$ to the nearest integer.

$\endgroup$
1
$\begingroup$

The n-th Fibonacci number can be calculated in log n steps, see, e.g., here

$\endgroup$
0
$\begingroup$

Yes, mathgeeks can compute a large fibonacci number without doing any kind of dance.

http://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratio

$\endgroup$
1
  • 1
    $\begingroup$ But here the idea is that you know one of the numbers and want the previous one. Using Binet's formula in the obvious way forgets that piece of information. $\endgroup$ Dec 26, 2010 at 15:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.