On May 15, 4:32 am, rusi rustompm...@gmail.com wrote:
On May 15, 2:19 am, Ian Kelly ian.g.ke...@gmail.com wrote:
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
On May 15, 8:20 pm, Mark Dickinson dicki...@gmail.com wrote:
On May 15, 4:32 am, rusi rustompm...@gmail.com wrote:
On May 15, 2:19 am, Ian Kelly ian.g.ke...@gmail.com wrote:
Yup, linear. Assuming you optimize the even case so that it doesn't
actually call fib(n//2) twice, the call tree
On May 14, 2:48 am, Mark Dickinson dicki...@gmail.com wrote:
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
On Sat, May 14, 2011 at 11:24 AM, rusi rustompm...@gmail.com wrote:
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 --
On May 15, 2:19 am, Ian Kelly ian.g.ke...@gmail.com wrote:
On Sat, May 14, 2011 at 11:24 AM, rusi rustompm...@gmail.com wrote:
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
On May 12, 3:06 am, Hans Mulder han...@xs4all.nl wrote:
On 03/05/2011 09:52, rusi wrote:
[If you believe it is, then try writing a log(n) fib iteratively :D ]
It took me a while, but this one seems to work:
from collections import namedtuple
Triple = namedtuple('Triple', 'hi mid lo')
On Fri, May 13, 2011 at 5:11 AM, rusi rustompm...@gmail.com wrote:
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.
Oh, nice! I did
On 13/05/2011 13:11, rusi wrote:
On May 12, 3:06 am, Hans Mulderhan...@xs4all.nl wrote:
On 03/05/2011 09:52, rusi wrote:
[If you believe it is, then try writing a log(n) fib iteratively :D ]
It took me a while, but this one seems to work:
from collections import namedtuple
Triple =
On May 11, 11:06 pm, Hans Mulder han...@xs4all.nl wrote:
On 03/05/2011 09:52, rusi wrote:
[If you believe it is, then try writing a log(n) fib iteratively :D ]
It took me a while, but this one seems to work:
from collections import namedtuple
Triple = namedtuple('Triple', 'hi mid lo')
On 03/05/2011 09:52, rusi wrote:
[If you believe it is, then try writing a log(n) fib iteratively :D ]
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 *
On May 3, 10:29 am, Chris Angelico ros...@gmail.com wrote:
On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg drsali...@gmail.com wrote:
Doh.
Usually when someone gives a recursive solution to this problem, it's
O(logn), but not this time.
Here's a logn one:
:-) Ok so you beat me to it :D
I
On 01/-10/-28163 02:59 PM, rusi wrote:
On May 3, 10:29 am, Chris Angelicoros...@gmail.com wrote:
On Tue, May 3, 2011 at 3:27 PM, Dan Strombergdrsali...@gmail.com wrote:
Doh.
Usually when someone gives a recursive solution to this problem, it's
O(logn), but not this time.
Here's a logn
On May 3, 3:32 pm, Dave Angel da...@ieee.org wrote:
What I'm surprised at is that nobody has pointed out that the logn
version is also generally more accurate, given traditional floats.
Usually getting the answer accurate (given the constraints of finite
precision intermediates) is more
On Tue, May 3, 2011 at 8:32 PM, Dave Angel da...@ieee.org wrote:
What I'm surprised at is that nobody has pointed out that the logn version
is also generally more accurate, given traditional floats. Usually getting
the answer accurate (given the constraints of finite precision
intermediates)
On Tue, 03 May 2011 21:04:07 +1000, Chris Angelico wrote:
And that, Your Honour, is why I prefer bignums (especially for integers)
to floating point. Precision rather than performance.
I'm intrigued by your comment especially for integers, which implies
that you might use bignums for
On Tue, May 3, 2011 at 10:49 PM, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
On Tue, 03 May 2011 21:04:07 +1000, Chris Angelico wrote:
And that, Your Honour, is why I prefer bignums (especially for integers)
to floating point. Precision rather than performance.
I'm intrigued
On Tue, May 3, 2011 at 5:49 AM, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
On Tue, 03 May 2011 21:04:07 +1000, Chris Angelico wrote:
And that, Your Honour, is why I prefer bignums (especially for integers)
to floating point. Precision rather than performance.
I'm
On May 3, 2:50 am, harrismh777 harrismh...@charter.net wrote:
The thing about this problem that puzzles me, is why we might consider
recursion for a possible solution in the first place
This can be answered directly but a bit lengthily.
Instead let me ask a seemingly unrelated (but actually
On Tue, May 3, 2011 at 11:48 AM, rusi rustompm...@gmail.com wrote:
What are their space/time complexities?
Which do you prefer?
They're pretty similar actually. If you rework the first one to not
use range() but instead have a more classic C style of loop, they'll
be almost identical:
def
On Mon, May 2, 2011 at 7:13 PM, Chris Angelico ros...@gmail.com wrote:
On Tue, May 3, 2011 at 11:48 AM, rusi rustompm...@gmail.com wrote:
What are their space/time complexities?
Which do you prefer?
They're pretty similar actually. If you rework the first one to not
use range() but
On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg drsali...@gmail.com wrote:
But the recursive solution has time complexity of O(logn). The iterative
solution has time complexity of O(n). That's a significant difference for
large n - a significant benefit of the recursive version.
Are you sure?
On Mon, May 2, 2011 at 11:27 PM, Dan Stromberg drsali...@gmail.com wrote:
But the recursive solution has time complexity of O(logn). The iterative
solution has time complexity of O(n). That's a significant difference for
large n - a significant benefit of the recursive version.
It's linear
On Mon, May 2, 2011 at 10:29 PM, Chris Angelico ros...@gmail.com wrote:
On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg drsali...@gmail.com wrote:
But the recursive solution has time complexity of O(logn). The iterative
solution has time complexity of O(n). That's a significant difference
23 matches
Mail list logo
