Fibonacci series recursion error

[Hans Mulder]

[If you believe it is, then try writing a log(n) fib iteratively ]

It took me a while, but this one seems to work:

from collections import namedtuple

Triple = namedtuple('Triple', 'hi mid lo')
Triple.__mul__ = lambda self, other: Triple(
self.hi * other.hi + self.mid * other.mid,
self.hi * other.mid + self.mid * other.lo,
self.mid * other.mid + self.lo * other.lo,
)

def fib(n):
f = Triple(1, 1, 0)
a = Triple(1, 0, 1)
while n:
if n& 1:
a *= f
f *= f
n>>= 1
return a.mid

-- HansM

Bravo! Can you explain this?

The tightest way I knew so far was this:
The 2x2 matrix
0 1
1 1
raised to the nth power gives the nth fibonacci number. [And then use
a logarithmic matrix mult]
Your version is probably tighter than this.

My method is just a thinly disguised version of your method: your 2x2
matrices are symmetrical, i.e. the number in the upper right is equal
to the number in the lower left. So I can save some memory and some
CPU time by working with only three numbers.

Yet one could argue that this is 'cheating' because you (and I) are
still solving the power problem.

That's true.

What I had in mind was to use fib results like:
f_(2n) = f_n^2 + f_(n+1)^2
and use these in the same way (from first principles) like we use the
equation
x^2n = (x*x)^n
to arrive at a logarithmic power algo.

To compute f(4n) this way, you need to compute both f(2n) and f(2n+1)
first, and to compute those, you need f(n) and f(n+1) and f(n+2)....

I think I can construct an O(log(n)**2) algorithm this way.

And it would still be 'cheating', because we'd still use some special
property of the Fibonacci sequence to reduce our problem to the power
problem. I think this sort of cheating can't be avoided: there is no
general method to compute recurrent sequences faster than O(n);
Fibonacci is just a special case.

-- HansM

 

[Mark Dickinson]

[If you believe it is, then try writing a log(n) fib iteratively ]

It took me a while, but this one seems to work:

from collections import namedtuple

Triple = namedtuple('Triple', 'hi mid lo')
Triple.__mul__ = lambda self, other: Triple(
     self.hi * other.hi + self.mid * other.mid,
     self.hi * other.mid + self.mid * other.lo,
     self.mid * other.mid + self.lo * other.lo,
)
[...]

You can even get away with pairs rather than triples:

----

from collections import namedtuple

Pair = namedtuple('Pair', 'z o')
Pair.__mul__ = lambda self, other: Pair(
self.z * other.z + self.o * other.o,
self.z * other.o + self.o * other.z + self.o * other.o,
)

def fib(n):
f = Pair(0, 1)
a = Pair(1, 0)
while n:
if n & 1:
a *= f
f *= f
n >>= 1
return a.o

----

I don't see this (or Hans' version) as cheating at all. This really
*is* the power algorithm, just in a different number system from the
usual one. For those with a bit of abstract algebra, the above
algorithm is just computing x^n in the ring Z[x] / (x^2 - x - 1). A
pair 'Pair(a, b)' represents the element 'a + bx' (more precisely, the
image of 'a + bx' under the natural quotient map Z[x] -> Z[x] / (x^2 -
x - 1)) of that ring. And this *can* be generalised to other
sequences given by a linear recurrence.

Mark

 

[rusi]

I don't see this (or Hans' version) as cheating at all.

Yeah sure -- cheating is a strong word

This really *is* the power algorithm, just in a different number system from the
usual one.

Yes that was my point. If we take the standard logarithmic power algo
as trivial (in the sense that it is well known) then all these
solutions do heavy-lifting to transform fib to power and then use the
'trivial' algo.

A more direct approach would be to use the identities:

f_2n = f_n ^ 2 + 2*f_n * f_(n-1)
f_(2n-1) = f_n ^ 2 + f_(n-1) ^ 2


The naive python implementation of which is:

def even(n): return n % 2 == 0
def sq(x): return x * x

def fib(n):
if n==1 or n==2:
return 1
elif even(n):
return sq(fib (n//2)) + 2 * fib(n//2) * fib(n//2 - 1)
else:
return sq(fib (n//2 + 1)) + sq(fib(n // 2))

This is a strange algo -- logarithmic because it halves the n,
exponential because of the double (triple) calls. [I cannot say I
know how to work out its exact complexity but I would guess its about
linear]

 

[Ian Kelly]

def fib(n):
   if n==1 or n==2:
       return 1
   elif even(n):
       return sq(fib (n//2)) + 2 * fib(n//2) * fib(n//2 - 1)
   else:
       return sq(fib (n//2 + 1)) + sq(fib(n // 2))

This is a strange algo  -- logarithmic because it halves the n,
exponential because of the double (triple) calls.  [I cannot say I
know how to work out its exact complexity but I would guess its about
linear]

Yup, linear. Assuming you optimize the even case so that it doesn't
actually call fib(n//2) twice, the call tree can be approximated as a
balanced binary tree with height log(n). The total number of nodes in
the tree is thus O(2 ** log(n)) = O(n).

 

[rusi]

def fib(n):
   if n==1 or n==2:
       return 1
   elif even(n):
       return sq(fib (n//2)) + 2 * fib(n//2) * fib(n//2 - 1)
   else:
       return sq(fib (n//2 + 1)) + sq(fib(n // 2))

This is a strange algo  -- logarithmic because it halves the n,
exponential because of the double (triple) calls.  [I cannot say I
know how to work out its exact complexity but I would guess its about
linear]

Yup, linear.  Assuming you optimize the even case so that it doesn't
actually call fib(n//2) twice, the call tree can be approximated as a
balanced binary tree with height log(n).  The total number of nodes in
the tree is thus O(2 ** log(n)) = O(n).

It would be linear if the base of the log were 2.
I am not sure it is.
You see the naive fib has a complexity which is fib itself. [Earlier
discussion with Steven]
fib is exponential but with radix < 2 [phi = (1 + sqrt(5))/2 ]
This would suggest that this algo is slightly better than linear.

But I have no idea of the exact complexity.

 

[Mark Dickinson]

Yup, linear.  Assuming you optimize the even case so that it doesn't
actually call fib(n//2) twice, the call tree can be approximated as a
balanced binary tree with height log(n).  The total number of nodes in
the tree is thus O(2 ** log(n)) = O(n).

It would be linear if the base of the log were 2.
I am not sure it is.
You see the naive fib has a complexity which is fib itself. [Earlier
discussion with Steven]
fib is exponential but with radix < 2 [phi = (1 + sqrt(5))/2 ]
This would suggest that this algo is slightly better than linear.

Nope. It's linear, just as Ian Kelly said. If g(n) is the total
number of fib calls made for fib(n), then it's easy to show (e.g., by
induction) that:

(a) g(n) is an increasing function of n, and
(b) g(2^k) = 2^k - 1 for all k >= 1.

Hence g(n) is O(n).

Mark

 

[Mark Dickinson]

It would be linear if the base of the log were 2.
I am not sure it is.
You see the naive fib has a complexity which is fib itself. [Earlier
discussion with Steven]
fib is exponential but with radix < 2 [phi = (1 + sqrt(5))/2 ]
This would suggest that this algo is slightly better than linear.

Nope.  It's linear, just as Ian Kelly said.  If g(n) is the total
number of fib calls made for fib(n), then it's easy to show (e.g., by
induction) that:

(a) g(n) is an increasing function of n, and
(b) g(2^k) = 2^k - 1 for all k >= 1.

Hence g(n) is O(n).

Hmm. It's even easier: g(n) is:

* 1 if n == 1
* n if n > 1, n odd
* n-1 if n > 1, n even

So definitely linear.