where the function has problem? n = 900 is OK , but n = 1000 is ERROR

[jc]

# Get Fibonacci Value
# Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2)
#
# n = 900 is OK
# n = 1000 is ERROR , Why
#
# What Wrong?
#

cache = []

def fibo( n ):

try:
if cache[n] != -1:
return cache[n]
else:
if 0 == n:
r = 0
elif 1 == n:
r = 1
else:
r = fibo(n-1) + fibo(n-2)

cache[n] = r
return r
except:
print "EXCEPT: " + str(n)


if __name__ == '__main__':

# This n = 900 is OK
# But n = 1000 is ERROR

n = 900
cache = range(0 , n + 1 , 1)

for i in cache:
cache = -1

print "Fibo(" + str(n) + ") = " + str(fibo(n))
print "\n"
print "\n"

 

[Steven D'Aprano]

# Get Fibonacci Value
# Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2)
#
# n = 900 is OK
# n = 1000 is ERROR , Why

How should we know? Please tell us what the error is, don't expect us to
guess.


[...]

if __name__ == '__main__':
# This n = 900 is OK
# But n = 1000 is ERROR

Hint: how big is the cache? If the cache has 900 items, what makes you think
you can look up the 1000th item?

n = 900
cache = range(0 , n + 1 , 1)
for i in cache:
cache = -1

This is a waste of time. Better to write:

cache = [-1]*900

Even better is to use a dict instead of a list.

 

[Ulrich Eckhardt]

n = 900
cache = range(0 , n + 1 , 1)
for i in cache:
cache = -1

This is a waste of time. Better to write:

cache = [-1]*900

Since he's computing the Fibonacci number of n, and n is 900, he needs
cache = [-1] * (n + 1)

;^)

Even better is to use a dict instead of a list.

Simpler, yes. Better for a beginner, of course. Better, maybe not. The use
case here will cause the cache to be used from index 1 upwards, so using an
array to store the element is faster and smaller. I'd consider resizing the
cache dynamically though.


Cheers!

Uli

 

[Dave Angel]

# Get Fibonacci Value
# Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2)
#
# n = 900 is OK
# n = 1000 is ERROR , Why
#
# What Wrong?
#

cache = []

def fibo( n ):

try:
if cache[n] != -1:
return cache[n]
else:
if 0 == n:
r = 0
elif 1 == n:
r = 1
else:
r = fibo(n-1) + fibo(n-2)

cache[n] = r
return r
except:
print "EXCEPT: " + str(n)


if __name__ == '__main__':

# This n = 900 is OK
# But n = 1000 is ERROR

n = 900
cache = range(0 , n + 1 , 1)

for i in cache:
cache = -1

print "Fibo(" + str(n) + ") = " + str(fibo(n))
print "\n"
print "\n"

It'd be really nice if you bothered to state what "ERROR" you get. Show
the traceback or since the output is pretty long, at least show part of
it. copy/paste it from the shell.

In any case, it's clearly a recursion problem, due to the default limit
of the CPython stack (1000). This succeeds for 999, and gets a stack
overflow at 1000.

A solution that lets you go much higher would be to insert before the lines:

if cache[n] != -1:
return cache[n]

The following:

if n > MAXDEPTH:
if n%MAXDEPTH:
for i in xrange(0, n, 200):
fibo(i) #calc value just to prefill the cache

where an easy value for MAXDEPTH is 200.

Think about what this does, and you should see why it'll help.

I tried it for 100,000 and it doesn't blow up. I didn't however check
any of the other logic.

DaveA

 

[Billy Mays]

# Get Fibonacci Value
# Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2)
#
# n = 900 is OK
# n = 1000 is ERROR , Why
#
# What Wrong?
#

I have fixed the problem for you:


def fibo(n):
phi = (1+5**.5)/2; iphi = 1-phi;
return (phi**n - iphi**n) / (5**.5)

 

[Thomas Rachel]

Am 01.08.2011 11:11 schrieb jc:

except:
print "EXCEPT: " + str(n)

If you catch all exceptions here, it is clear that you only get this.

Why don't you do

except Exception, e:
print "EXCEPT: " + str(n), e

? Then you could at least ask "why do I get a unsupported operand
type(s) for +: 'NoneType' and 'long'"?

Well, these are the consequences of returning nothing (aka None) in the
case of earlier errors. The first of these errors comes from

EXCEPT: 4 maximum recursion depth exceeded

so - you simply go too deep.


If you "pre-calculate" the stuff before, calling fibo(n/2) before the
line with 'print "Fibo(" + str(n) + ") = " + str(fibo(n))', it succeeds.


Thomas

 

[Steven D'Aprano]

I have fixed the problem for you:


def fibo(n):
phi = (1+5**.5)/2; iphi = 1-phi;
return (phi**n - iphi**n) / (5**.5)

Does your definition of "fixed" mean "gives wrong results for n >= 4 "?
False

 

[Billy Mays]

Does your definition of "fixed" mean "gives wrong results for n>= 4 "?

False

Well, I don't know if you're trolling or just dumb:

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

In [2]: for i in range(10):
...: print fibo(i)
...:
...:
0.0
1.0
1.0
2.0
3.0
5.0
8.0
13.0
21.0
34.0

 

[Alain Ketterlin]

Billy Mays

Well, I don't know if you're trolling or just dumb:

Steven is right, and you look dumb.
3.0000000000000004

Even though the math is correct, your program is wrong. It doesn't even
produce integers. And it will fail with overflow for big values.

-- Alain.

 

[Billy Mays]

produce integers. And it will fail with overflow for big values.

If it would make you feel better I can use decimal.

Also, perhaps I can name my function billy_fibo(n), which is defined as
billy_fibo(n) +error(n) = fibo(n), where error(n) can be made
arbitrarily small. This runs in constant time rather than linear
(memoized) or exponential (fully recursive) at the cost of a minutia of
accuracy. I find this tradeoff acceptable.

 

[Steven D'Aprano]

If it would make you feel better I can use decimal.

Also, perhaps I can name my function billy_fibo(n), which is defined as
billy_fibo(n) +error(n) = fibo(n), where error(n) can be made
arbitrarily small.

So you say, but I don't believe it. Given fibo, the function you provided
earlier, the error increases with N:
2.92786721937918e+23

Hardly "arbitrarily small".


Your function also overflows for N = 1475:
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 3, in fibo
OverflowError: (34, 'Numerical result out of range')


The correct value only has 307 digits, so it's not that large a number for
integer math. I won't show them all, but it starts and ends like this:

8077637632...87040886025

This runs in constant time rather than linear
(memoized)

A good memoisation scheme will run in constant time (amortised).

or exponential (fully recursive)

Good heavens no. Only the most naive recursive algorithm is exponential.
Good ones (note plural) are linear. Combine that with memoisation, and you
have amortised constant time.

at the cost of a minutia of accuracy.

I'm reminded of a time my wife was travelling across the US with her band's
roadies. At some point crossing the miles and miles of highway through the
desert, she pointed out that they were lost and nowhere even close to the
city where they were supposed to be playing. The driver answered, "Who
cares, we're making great time!"

(True story.)

I find this tradeoff acceptable.

Given that Fibonacci numbers are mostly of interest to number theorists, who
care about the *actual* Fibonacci numbers and not almost-but-not-quite
Fibonacci numbers, I'm having a lot of difficulty imagining what sort of
application you have in mind that could legitimately make that trade-off.

 

[Billy Mays]

So you say, but I don't believe it. Given fibo, the function you provided
earlier, the error increases with N:

2.92786721937918e+23

Hardly "arbitrarily small".

Perhaps the individual number is big, but compare that to:

(fibo(n) - fib(n)) / fib(n)

The number is still quite close to the actual answer.

Your function also overflows for N = 1475:

Traceback (most recent call last):
File "<stdin>", line 1, in<module>
File "<stdin>", line 3, in fibo
OverflowError: (34, 'Numerical result out of range')


The correct value only has 307 digits, so it's not that large a number for
integer math. I won't show them all, but it starts and ends like this:

8077637632...87040886025

Yes, I mentioned possibly using the decimal class, which I suppose does
lose the constant access time depending on how its implemented.

A good memoisation scheme will run in constant time (amortised).

Amortized perhaps, but this assumes the call happening a number of
times. Also, this requires linear memory to store previous values.

Good heavens no. Only the most naive recursive algorithm is exponential.
Good ones (note plural) are linear. Combine that with memoisation, and you
have amortised constant time.

Not all recursive functions can be memoized (or they can but for
practically no benefit). What I was getting at was that a closed form
expression of a recurrence might be significantly faster at an
acceptable loss in accuracy. For an example, see the Ackermann function.

Given that Fibonacci numbers are mostly of interest to number theorists, who
care about the *actual* Fibonacci numbers and not almost-but-not-quite
Fibonacci numbers, I'm having a lot of difficulty imagining what sort of
application you have in mind that could legitimately make that trade-off.

I was trying to show that there is an alternate method of calculation.
Accuracy losses are really a problem with the underlying machinery
rather than the high level code. If the recursive form of fib() were
written in c, the integers would have overflown a long while ago
compared to float.

One other note, Fibonacci numbers grow exponentially fast (with respect
to the number of bits), and python's integer multiplication takes
exponential time (karatsuba rather than fft). If we are going to
discuss the behavior of python's numeric types, then lets talk about how
slow python will become for the nth Fibonacci integer and how much space
it will take compared to the floating point short concise and almost as
close form.