Fibonacci Reverse Calculation?

[Amy Valhausen]

Fibonacci Reverse Calculation?

Hi All!

I was reading Dr Knotts entries about Binets formula on his fibonacci page
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html

I entered the formula into an Excel spreadsheet to see how this would work ;

Binet Formula
Fib(n) =  (1.6180339^n – (–0.6180339..)^n) / 2.236067977..

Its fascinating to see how I can enter any number for (n) and see the
correct fibonacci number returned!

I have a question though, I am a newbie computer programmer using
VB and Python and my math skills are average at best but I am very
interest and curious about math and especially fibonacci numbers!

Say I wanted to reverse and change the process.

I have a very large fibonacci number and I want to know what the
fibonacci number is at a specified position BEFORE it, how would
I compute this, what would the formula be?

So for example I have the 301 st fibo number of ;

359579325206583560961765665172189099052367214309267232255589801

And I want to be able to find what the fibonacci value would be (n) numbers
BEFORE this... so I might want to know what the fibo value would be 50
numbers before or the 251st fibo number.  How would I do that?

[Francesco Bonazzi]

Hi there!

Are you asking about the math or about a programming strategy?

From a programming point of view, you could use a vector of pre-computed Fibonacci numbers if the numbers you're dealing with aren't too big.

Otherwise, I'd give a try to use the closed formula for Fibonacci numbers with SymPy's equation solver.

Anyway, I suggest to ask about mathematical details on

http://math.stackexchange.com/

[Aaron Meurer]

It seems SymPy's solve() is not able to solve fibonacci(n) -
359579325206583560961765665172189099052367214309267232255589801, even
if you rewrite fibonacci(n) using GoldenRatio or using the explicit
value for GoldenRatio (or even the floating point value).

The Wikipedia article gives a way to invert Binet's formula
https://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers.
That should be useful for calculating what you want.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/5b6e68d0-8b65-495a-bd8b-0c601bdef403%40googlegroups.com.
>
> For more options, visit https://groups.google.com/d/optout.

[Amy Valhausen]

Hi Aaron, thanks for your reply!

Do you feel this is due to the size of the 301st number?

I tried something different, I picked the 29th fibonacci number of ; 514229

And then tried to step down, backwards to the fourth preceeding fibo value using this
code ;

from sympy import mpmath
mpmath.mp.dps = 2000
x = (mpmath.mpf('0.618008776') **4)
x=x*514229
print(x)

Got this value ; 75012.7581
a result very close to the correct fibo number ; 75025

In your opinion, is it that the 301st fibo number is over the limit that symopy can handle
for computing fibo numbers occurring before it?

[Aaron Meurer]

Even though you set the precision to 2000, you're still only using 9
digits of the golden ratio. I recommend using mpmath.phi and
1/mpmath.phi. (Also, "from sympy import mpmath" no longer works in the
lastet version of SymPy, just use "import mpmath").

Or, using SymPy, you can use sympy.GoldenRatio, and use evalf() to get a number

In [34]: (1/GoldenRatio**4*514229).evalf()
Out[34]: 75024.9999973910

This number is accurate to 15 digits (the default precision), so I
think it's close to, but not exactly an integer. You can also see this
by rewriting the GoldenRatio using square roots and expanding it

In [1]: (1/GoldenRatio**4*514229).rewrite(sqrt).expand()
Out[1]:
514229
────────
3⋅√5 7
──── + ─
2 2

I guess this calculation uses the fact that the golden ratio phi ≈
F_n/F_{n-1}, so F_29/phi^4 ≈
F_29/[(F_28/F_27)*(F_27/F_26)*(F_26/F_25)*(F_25/F_24)] = F_24. But
this is only an approximation (although it's quite accurate even for
smaller n). So if you use it to compute fibonacci numbers, it's
necessary to use round() to round to the nearest integer (assuming n
is large enough that it's within 0.5 of the answer).

Here's the calculation going from the 301st to the 251st number:

In [9]: (359579325206583560961765665172189099052367214309267232255589801/GoldenRatio**50).evalf(100)
Out[9]: 12776523572924732586037033894655031898659556447352249.00000000000000000000000000000000000000000000000

In [10]: fibonacci(251)
Out[10]: 12776523572924732586037033894655031898659556447352249

The important thing is to use evalf(100) (you actually only need
evalf(53)), as the default evalf() only gives 15 digits, which isn't
enough.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/dc81edc9-866e-4c13-962e-b0446fb294a0%40googlegroups.com.

[Amy Valhausen]

Hi Aaron thanks so much for the reply will try this!  Is there any way to get more than 15 digits of accuracy?

[Aaron Meurer]

Yes, the number you pass to evalf is the digits of precision, like expr.evalf(100) for 100 digits. 

Aaron Meurer

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/637dc9eb-184d-41dd-b808-95d5ee378fee%40googlegroups.com.

[Amy Valhausen]

Hi Aaron!  I have been trying to follow your suggestions to try

mpmath.phi & sympy.GoldenRatio but I keep getting command line errors when I
try to reference these.

When I enter this at the command line for example ;

(1/GoldenRatio**4*514229).evalf()

It errors out - I suspect I am not referencing it properly or defining it somehow?

I tried looking this up on a number of sites online, the best links I could find
were these ones ; http://nullege.com/codes/search/sympy.GoldenRatio

and http://www.programcreek.com/python/example/23863/sympy.GoldenRatio

I find the references a bit confusing, am I supposed to define them as
and 'abs' type, or do I use the key word 'assert' before it?

Is sympy.GoldenRatio an mpmath function?

Do I have to import mpmath before I use "sympy.GoldenRatio"  what is the
difference between "sympy.GoldenRatio" and mpmath.phi ?

Also do you know what the numeric value limit of the argument I pass to
"evalf()" is?  Can I pass it up to 6000 as a value?

[Aaron Meurer]

On Sat, Apr 9, 2016 at 3:13 AM, Amy Valhausen <amy.vau...@gmail.com> wrote:
>
> Hi Aaron! I have been trying to follow your suggestions to try
>
> mpmath.phi & sympy.GoldenRatio but I keep getting command line errors when I
> try to reference these.

These are referencing the names from the modules. To get
sympy.GoldenRatio you first need to run

import sympy

Alternately, you can run

from sympy import GoldenRatio

and just use "GoldenRatio". Or you can run

from sympy import *

and it will import all the functions from SymPy (including GoldenRatio).

>
> When I enter this at the command line for example ;
>
> (1/GoldenRatio**4*514229).evalf()
>
> It errors out - I suspect I am not referencing it properly or defining it
> somehow?
>
> I tried looking this up on a number of sites online, the best links I could
> find
> were these ones ; http://nullege.com/codes/search/sympy.GoldenRatio
>
> and http://www.programcreek.com/python/example/23863/sympy.GoldenRatio

Those don't seem like great resources. They are just finding instances
of "GoldenRatio" from SymPy's source code.

I would recommend using docs.sympy.org. Here are the docs for
GoldenRatio http://docs.sympy.org/latest/modules/core.html#sympy.core.numbers.GoldenRatio
(note that S.GoldenRatio is an additional way to access it).

>
> I find the references a bit confusing, am I supposed to define them as
> and 'abs' type, or do I use the key word 'assert' before it?
>
> Is sympy.GoldenRatio an mpmath function?
>
> Do I have to import mpmath before I use "sympy.GoldenRatio" what is the
> difference between "sympy.GoldenRatio" and mpmath.phi ?

mpmath is a purely numeric library. It is used internally by SymPy.
You do not need to import mpmath unless you want to use it explicitly.
If you use SymPy functions, they will use mpmath internally
automatically. I would recommend just using SymPy, unless you have a
specific reason to use mpmath (for instance, you want to use a mpmath
function that isn't implemented in SymPy).

SymPy represents things symbolically, and can do symbolica
manipulation. For instance

In [23]: expand_func(GoldenRatio)
Out[23]:
1 √5
─ + ──
2 2

This is not possible with mpmath because mpmath just represents the
golden ratio as the number 1.61803398874989.

>
> Also do you know what the numeric value limit of the argument I pass to
> "evalf()" is? Can I pass it up to 6000 as a value?

You can pass whatever number you want. You can use it to compute a
billion digits of the golden ratio if you want. The algorithms
implemented work with arbitrary precision, meaning you can pick any
number of digits and it will compute with that many (limited by your
computer's memory of course).

Aaron Meurer

>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/c906cb9a-d348-4377-8278-2367a976bf2b%40googlegroups.com.