fibonacci series what Iam is missing ?

[Rustom Mody]

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?