fibonacci series what Iam is missing ?
Rustom Mody
rustompmody at gmail.com
Tue Mar 24 02:28:42 EDT 2015
On Tuesday, March 24, 2015 at 11:50:40 AM UTC+5:30, Rustom Mody wrote:
> On Tuesday, March 24, 2015 at 10:51:11 AM UTC+5:30, Ian wrote:
> > On Mon, Mar 23, 2015 at 4:53 PM, Terry Reedy wrote:
> > > Iteration with caching, using a mutable default arg to keep the cache
> > > private and the function self-contained. This should be faster.
> > >
> > > def fib(n, _cache=[0,1]):
> > > '''Return fibonacci(n).
> > >
> > > _cache is initialized with base values and augmented as needed.
> > > '''
> > > for k in range(len(_cache), n+1):
> > > _cache.append(_cache[k-2] + _cache[k-1])
> > > return _cache[n]
> > >
> > > print(fib(1), fib(3), fib(6), fib(5))
> > > # 1 2 8 5
> >
> > Iteration in log space. On my desktop, this calculates fib(1000) in
> > about 9 us, fib(100000) in about 5 ms, and fib(10000000) in about 7
> > seconds.
> >
> > def fib(n):
> > assert n >= 0
> > if n == 0:
> > return 0
> >
> > a = b = x = 1
> > c = y = 0
> > n -= 1
> >
> > while True:
> > n, r = divmod(n, 2)
> > if r == 1:
> > x, y = x*a + y*b, x*b + y*c
> > if n == 0:
> > return x
> > b, c = a*b + b*c, b*b + c*c
> > a = b + c
>
> This is rather arcane!
> What are the identities used above?
Seems to be close to these (with some spices added!)
f₂ₙ = (fₙ)² + 2fₙ₋₁fₙ
f₂ₙ₊₁ = (fₙ)² + (fₙ₊₁)²
More information about the Python-list
mailing list