On May 15, 8:20 pm, Mark Dickinson wrote:
> On May 15, 4:32 am, rusi wrote:
>
> > On May 15, 2:19 am, Ian Kelly 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
On May 15, 4:32 am, rusi wrote:
> On May 15, 2:19 am, Ian Kelly 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 log(n). The total number of nodes in
> >
On May 15, 2:19 am, Ian Kelly wrote:
> On Sat, May 14, 2011 at 11:24 AM, rusi 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)
On Sat, May 14, 2011 at 11:24 AM, rusi 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 -- logarithmic because i
On May 14, 2:48 am, Mark Dickinson 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 the standard log
On May 11, 11:06 pm, Hans Mulder 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')
> Triple.
On 13/05/2011 13:11, rusi wrote:
On May 12, 3:06 am, Hans Mulder 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', '
On Fri, May 13, 2011 at 5:11 AM, rusi 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 it this way once
On May 12, 3:06 am, Hans Mulder 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')
> Triple._
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 * othe
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'
On Tue, May 3, 2011 at 10:49 PM, Steven D'Aprano
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 by your comment "especially f
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 non-i
On Tue, May 3, 2011 at 8:32 PM, Dave Angel 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 impo
On May 3, 3:32 pm, Dave Angel 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 important than p
On 01/-10/-28163 02:59 PM, rusi wrote:
On May 3, 10:29 am, Chris Angelico wrote:
On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg 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
On May 3, 10:29 am, Chris Angelico wrote:
> On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg 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 was trying to arrive at an answer
On Mon, May 2, 2011 at 10:29 PM, Chris Angelico wrote:
> On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg 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 signifi
On Mon, May 2, 2011 at 11:27 PM, Dan Stromberg 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 as written. I th
On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg 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? It will produce
On Mon, May 2, 2011 at 7:13 PM, Chris Angelico wrote:
> On Tue, May 3, 2011 at 11:48 AM, rusi 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
On Tue, May 3, 2011 at 11:48 AM, rusi 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 powI(x,n):
result = 1
On May 3, 2:50 am, harrismh777 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 much the same)
questi
23 matches
Mail list logo
