Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #5572 > unrolled thread

Faster Recursive Fibonacci Numbers

Back to article view | Back to comp.lang.python

Contents

  Faster Recursive Fibonacci Numbers RJB <rbotting@csusb.edu> - 2011-05-17 08:50 -0700
    Re: Faster Recursive Fibonacci Numbers Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-17 10:23 -0600
    Re: Faster Recursive Fibonacci Numbers rusi <rustompmody@gmail.com> - 2011-05-17 09:25 -0700
    Re: Faster Recursive Fibonacci Numbers rusi <rustompmody@gmail.com> - 2011-05-17 09:36 -0700
      Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-17 10:02 -0700
        Re: Faster Recursive Fibonacci Numbers Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2011-05-17 20:19 +0300
          Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-17 11:56 -0700
            Re: Faster Recursive Fibonacci Numbers Wolfram Hinderer <wolfram.hinderer@googlemail.com> - 2011-05-17 14:04 -0700
              Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-17 14:59 -0700
              Re: Faster Recursive Fibonacci Numbers rusi <rustompmody@gmail.com> - 2011-05-17 21:43 -0700
        Re: Faster Recursive Fibonacci Numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-19 22:47 +0000
          Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-20 09:37 +1000
            Re: Faster Recursive Fibonacci Numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-20 05:58 +0000
              Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-20 16:06 +1000
                Re: Faster Recursive Fibonacci Numbers harrismh777 <harrismh777@charter.net> - 2011-05-20 01:26 -0500
                  Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-20 16:54 +1000
                    Re: Faster Recursive Fibonacci Numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-20 17:07 +0000
                      Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-20 11:43 -0700
                      Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-21 10:44 +1000
                Re: Faster Recursive Fibonacci Numbers Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-05-21 20:49 +1200
              Re: Faster Recursive Fibonacci Numbers Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-20 01:26 -0600
              Re: Faster Recursive Fibonacci Numbers Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-20 01:32 -0600
                Re: Faster Recursive Fibonacci Numbers SigmundV <sigmundv@gmail.com> - 2011-05-20 03:53 -0700
          Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-19 17:03 -0700
    Re: Faster Recursive Fibonacci Numbers Raymond Hettinger <python@rcn.com> - 2011-05-24 16:44 -0700

Page 1 of 2  [1] 2  Next page →

#5572 — Faster Recursive Fibonacci Numbers

I noticed some discussion of recursion..... the trick is to find a
formula where the arguments are divided, not decremented.
I've had a "divide-and-conquer" recursion for the Fibonacci numbers
for a couple of years in C++ but just for fun rewrote it
in Python.  It was easy.  Enjoy.  And tell me how I can improve it!

def fibo(n):
	"""A Faster recursive Fibonaci function
Use a formula from Knuth Vol 1 page 80, section 1.2.8:
	   If F[n] is the n'th Fibonaci number then
		   F[n+m] = F[m]*F[n+1] + F[m-1]*F[n].
  First set m = n+1
   F[ 2*n+1 ] = F[n+1]**2 + F[n]*2.

  Then put m = n in Knuth's formula,
	   F[ 2*n ] = F[n]*F[n+1] + F[n-1]* F[n],
   and replace F[n+1] by F[n]+F[n-1],
	   F[ 2*n ] = F[n]*(F[n] + 2*F[n-1]).
"""
	if n<=0:
		return 0
	elif n<=2:
		return 1
	elif n%2==0:
		half=n//2
		f1=fibo(half)
		f2=fibo(half-1)
		return f1*(f1+2*f2)
	else:
		nearhalf=(n-1)//2
		f1=fibo(nearhalf+1)
		f2=fibo(nearhalf)
		return f1*f1 + f2*f2


RJB the Lurker
http://www.csci.csusb.edu/dick/cs320/lab/10.html

[toc] | [next] | [standalone]

#5574

On Tue, May 17, 2011 at 9:50 AM, RJB <rbotting@csusb.edu> wrote:
> I noticed some discussion of recursion..... the trick is to find a
> formula where the arguments are divided, not decremented.
> I've had a "divide-and-conquer" recursion for the Fibonacci numbers
> for a couple of years in C++ but just for fun rewrote it
> in Python.  It was easy.  Enjoy.  And tell me how I can improve it!
>
> def fibo(n):
>        """A Faster recursive Fibonaci function
> Use a formula from Knuth Vol 1 page 80, section 1.2.8:
>           If F[n] is the n'th Fibonaci number then
>                   F[n+m] = F[m]*F[n+1] + F[m-1]*F[n].
>  First set m = n+1
>   F[ 2*n+1 ] = F[n+1]**2 + F[n]*2.
>
>  Then put m = n in Knuth's formula,
>           F[ 2*n ] = F[n]*F[n+1] + F[n-1]* F[n],
>   and replace F[n+1] by F[n]+F[n-1],
>           F[ 2*n ] = F[n]*(F[n] + 2*F[n-1]).
> """
>        if n<=0:
>                return 0
>        elif n<=2:
>                return 1
>        elif n%2==0:
>                half=n//2
>                f1=fibo(half)
>                f2=fibo(half-1)
>                return f1*(f1+2*f2)
>        else:
>                nearhalf=(n-1)//2
>                f1=fibo(nearhalf+1)
>                f2=fibo(nearhalf)
>                return f1*f1 + f2*f2

Thanks for posting!  Actually, it looks like this is the same O(n)
algorithm that rusi posted.  There was also a O(log n) algorithm
discussed that is based on vector math.  You might want to take a
look.

Cheers,
Ian

[toc] | [prev] | [next] | [standalone]

#5575

On May 17, 8:50 pm, RJB <rbott...@csusb.edu> wrote:
> I noticed some discussion of recursion..... the trick is to find a
> formula where the arguments are divided, not decremented.
> I've had a "divide-and-conquer" recursion for the Fibonacci numbers
> for a couple of years in C++ but just for fun rewrote it
> in Python.  It was easy.  Enjoy.  And tell me how I can improve it!
>
> def fibo(n):
>         """A Faster recursive Fibonaci function
> Use a formula from Knuth Vol 1 page 80, section 1.2.8:
>            If F[n] is the n'th Fibonaci number then
>                    F[n+m] = F[m]*F[n+1] + F[m-1]*F[n].
>   First set m = n+1
>    F[ 2*n+1 ] = F[n+1]**2 + F[n]*2.
>
>   Then put m = n in Knuth's formula,
>            F[ 2*n ] = F[n]*F[n+1] + F[n-1]* F[n],
>    and replace F[n+1] by F[n]+F[n-1],
>            F[ 2*n ] = F[n]*(F[n] + 2*F[n-1]).
> """
>         if n<=0:
>                 return 0
>         elif n<=2:
>                 return 1
>         elif n%2==0:
>                 half=n//2
>                 f1=fibo(half)
>                 f2=fibo(half-1)
>                 return f1*(f1+2*f2)
>         else:
>                 nearhalf=(n-1)//2
>                 f1=fibo(nearhalf+1)
>                 f2=fibo(nearhalf)
>                 return f1*f1 + f2*f2
>
> RJB the Lurkerhttp://www.csci.csusb.edu/dick/cs320/lab/10.html

[toc] | [prev] | [next] | [standalone]

#5577

On May 17, 8:50 pm, RJB <rbott...@csusb.edu> wrote:
> I noticed some discussion of recursion..... the trick is to find a
> formula where the arguments are divided, not decremented.
> I've had a "divide-and-conquer" recursion for the Fibonacci numbers
> for a couple of years in C++ but just for fun rewrote it
> in Python.  It was easy.  Enjoy.  And tell me how I can improve it!
>
> def fibo(n):
>         """A Faster recursive Fibonaci function
> Use a formula from Knuth Vol 1 page 80, section 1.2.8:
>            If F[n] is the n'th Fibonaci number then
>                    F[n+m] = F[m]*F[n+1] + F[m-1]*F[n].
>   First set m = n+1
>    F[ 2*n+1 ] = F[n+1]**2 + F[n]*2.
>
>   Then put m = n in Knuth's formula,
>            F[ 2*n ] = F[n]*F[n+1] + F[n-1]* F[n],
>    and replace F[n+1] by F[n]+F[n-1],
>            F[ 2*n ] = F[n]*(F[n] + 2*F[n-1]).
> """
>         if n<=0:
>                 return 0
>         elif n<=2:
>                 return 1
>         elif n%2==0:
>                 half=n//2
>                 f1=fibo(half)
>                 f2=fibo(half-1)
>                 return f1*(f1+2*f2)
>         else:
>                 nearhalf=(n-1)//2
>                 f1=fibo(nearhalf+1)
>                 f2=fibo(nearhalf)
>                 return f1*f1 + f2*f2
>
> RJB the Lurkerhttp://www.csci.csusb.edu/dick/cs320/lab/10.html

-------------------------------------------------------------
Its an interesting problem and you are 75% there.
You see the halving gives you logarithmic behavior and the double
calls give exponential behavior.

So how to get rid of double calls?  Its quite simple: Just define your
function in terms of return pairs of adjacent pairs ie (fib(n), fib(n
+1)) for some n rather then a single number fib(n)

Here's a straightforward linear function:

def fp(n):  #fibpair
    if n==1:
        return (1,1)
    else:
        a,b = fp(n-1)
        return (b, a+b)

def fib(n):
    a,b = fp(n)
    return a

---------------
Now use this (pairing) idea with your (halving) identities and you
should get a logarithmic algo.

[If you cant do it ask again but yes its fun to work out so do
try :-) ]

[toc] | [prev] | [next] | [standalone]

#5581

On Tue, May 17, 2011 at 9:36 AM, rusi <rustompmody@gmail.com> wrote:
> On May 17, 8:50 pm, RJB <rbott...@csusb.edu> wrote:
>> I noticed some discussion of recursion..... the trick is to find a
>> formula where the arguments are divided, not decremented.
>> I've had a "divide-and-conquer" recursion for the Fibonacci numbers
>> for a couple of years in C++ but just for fun rewrote it
>> in Python.  It was easy.  Enjoy.  And tell me how I can improve it!
>>
>> def fibo(n):
>>         """A Faster recursive Fibonaci function
>> Use a formula from Knuth Vol 1 page 80, section 1.2.8:
>>            If F[n] is the n'th Fibonaci number then
>>                    F[n+m] = F[m]*F[n+1] + F[m-1]*F[n].
>>   First set m = n+1
>>    F[ 2*n+1 ] = F[n+1]**2 + F[n]*2.
>>
>>   Then put m = n in Knuth's formula,
>>            F[ 2*n ] = F[n]*F[n+1] + F[n-1]* F[n],
>>    and replace F[n+1] by F[n]+F[n-1],
>>            F[ 2*n ] = F[n]*(F[n] + 2*F[n-1]).
>> """
>>         if n<=0:
>>                 return 0
>>         elif n<=2:
>>                 return 1
>>         elif n%2==0:
>>                 half=n//2
>>                 f1=fibo(half)
>>                 f2=fibo(half-1)
>>                 return f1*(f1+2*f2)
>>         else:
>>                 nearhalf=(n-1)//2
>>                 f1=fibo(nearhalf+1)
>>                 f2=fibo(nearhalf)
>>                 return f1*f1 + f2*f2
>>
>> RJB the Lurkerhttp://www.csci.csusb.edu/dick/cs320/lab/10.html
>
> -------------------------------------------------------------
> Its an interesting problem and you are 75% there.
> You see the halving gives you logarithmic behavior and the double
> calls give exponential behavior.
>
> So how to get rid of double calls?  Its quite simple: Just define your
> function in terms of return pairs of adjacent pairs ie (fib(n), fib(n
> +1)) for some n rather then a single number fib(n)
>
> Here's a straightforward linear function:
>
> def fp(n):  #fibpair
>    if n==1:
>        return (1,1)
>    else:
>        a,b = fp(n-1)
>        return (b, a+b)
>
> def fib(n):
>    a,b = fp(n)
>    return a
>
> ---------------
> Now use this (pairing) idea with your (halving) identities and you
> should get a logarithmic algo.
>
> [If you cant do it ask again but yes its fun to work out so do
> try :-) ]
> --
> http://mail.python.org/mailman/listinfo/python-list
>

or O(1):

φ = (1 + sqrt(5)) / 2
def fib(n):
    numerator = (φ**n) - (1 - φ)**n
    denominator = sqrt(5)
    return round(numerator/denominator)

Testing indicates that it's faster somewhere around 7 or so.

Geremy Condra

[toc] | [prev] | [next] | [standalone]

#5583

geremy condra writes:

> or O(1):
> 
> φ = (1 + sqrt(5)) / 2
> def fib(n):
>     numerator = (φ**n) - (1 - φ)**n
>     denominator = sqrt(5)
>     return round(numerator/denominator)
> 
> Testing indicates that it's faster somewhere around 7 or so.

And increasingly inaccurate from 71 on.

[toc] | [prev] | [next] | [standalone]

#5595

On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen
<jpiitula@ling.helsinki.fi> wrote:
> geremy condra writes:
>
>> or O(1):
>>
>> φ = (1 + sqrt(5)) / 2
>> def fib(n):
>>     numerator = (φ**n) - (1 - φ)**n
>>     denominator = sqrt(5)
>>     return round(numerator/denominator)
>>
>> Testing indicates that it's faster somewhere around 7 or so.
>
> And increasingly inaccurate from 71 on.

Yup. That's floating point for you. For larger values you could just
add a linear search at the bottom using the 5f**2 +/- 4 rule, which
would still be quite fast out to about 10 times that. The decimal
module gets you a tiny bit further, and after that it's time to just
use Dijkstra's, like rusi suggested. In any event, I still think this
formulation is the most fun ;).

Geremy Condra

[toc] | [prev] | [next] | [standalone]

#5616

On 17 Mai, 20:56, geremy condra <debat...@gmail.com> wrote:
> On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen
>
> <jpiit...@ling.helsinki.fi> wrote:
> > geremy condra writes:
>
> >> or O(1):
>
> >> ö = (1 + sqrt(5)) / 2
> >> def fib(n):
> >>     numerator = (ö**n) - (1 - ö)**n
> >>     denominator = sqrt(5)
> >>     return round(numerator/denominator)
>
> >> Testing indicates that it's faster somewhere around 7 or so.
>
> > And increasingly inaccurate from 71 on.
>
> Yup. That's floating point for you. For larger values you could just
> add a linear search at the bottom using the 5f**2 +/- 4 rule, which
> would still be quite fast out to about 10 times that. The decimal
> module gets you a tiny bit further, and after that it's time to just
> use Dijkstra's, like rusi suggested. In any event, I still think this
> formulation is the most fun ;).

I think you can write it even more funny

def fib(n):
    return round(((.5 + .5 * 5 ** .5) ** n -  (.5 - .5 * 5 ** .5) **
n) * 5 ** -.5)

;-)

[toc] | [prev] | [next] | [standalone]

#5623

On Tue, May 17, 2011 at 2:04 PM, Wolfram Hinderer
<wolfram.hinderer@googlemail.com> wrote:
> On 17 Mai, 20:56, geremy condra <debat...@gmail.com> wrote:
>> On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen
>>
>> <jpiit...@ling.helsinki.fi> wrote:
>> > geremy condra writes:
>>
>> >> or O(1):
>>
>> >> ö = (1 + sqrt(5)) / 2
>> >> def fib(n):
>> >>     numerator = (ö**n) - (1 - ö)**n
>> >>     denominator = sqrt(5)
>> >>     return round(numerator/denominator)
>>
>> >> Testing indicates that it's faster somewhere around 7 or so.
>>
>> > And increasingly inaccurate from 71 on.
>>
>> Yup. That's floating point for you. For larger values you could just
>> add a linear search at the bottom using the 5f**2 +/- 4 rule, which
>> would still be quite fast out to about 10 times that. The decimal
>> module gets you a tiny bit further, and after that it's time to just
>> use Dijkstra's, like rusi suggested. In any event, I still think this
>> formulation is the most fun ;).
>
> I think you can write it even more funny
>
> def fib(n):
>    return round(((.5 + .5 * 5 ** .5) ** n -  (.5 - .5 * 5 ** .5) **
> n) * 5 ** -.5)
>
> ;-)

Ok, that's amusing. It does hide the interaction with the golden ratio
though, which is what I find so fascinating about the earlier one.

Geremy Condra

[toc] | [prev] | [next] | [standalone]

#5649

On May 18, 2:04 am, Wolfram Hinderer <wolfram.hinde...@googlemail.com>
wrote:
> On 17 Mai, 20:56, geremy condra <debat...@gmail.com> wrote:
>
>
>
> > On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen
>
> > <jpiit...@ling.helsinki.fi> wrote:
> > > geremy condra writes:
>
> > >> or O(1):
>
> > >> ö = (1 + sqrt(5)) / 2
> > >> def fib(n):
> > >>     numerator = (ö**n) - (1 - ö)**n
> > >>     denominator = sqrt(5)
> > >>     return round(numerator/denominator)
>
> > >> Testing indicates that it's faster somewhere around 7 or so.
>
> > > And increasingly inaccurate from 71 on.
>
> > Yup. That's floating point for you. For larger values you could just
> > add a linear search at the bottom using the 5f**2 +/- 4 rule, which
> > would still be quite fast out to about 10 times that. The decimal
> > module gets you a tiny bit further, and after that it's time to just
> > use Dijkstra's, like rusi suggested. In any event, I still think this
> > formulation is the most fun ;).
>
> I think you can write it even more funny
>
> def fib(n):
>     return round(((.5 + .5 * 5 ** .5) ** n -  (.5 - .5 * 5 ** .5) **
> n) * 5 ** -.5)
>
> ;-)

VOW!
Tour de Force - Thanks
[I am going to trouble some class of students with that :-) ]

[toc] | [prev] | [next] | [standalone]

#5794

On Tue, 17 May 2011 10:02:21 -0700, geremy condra wrote:

> or O(1):
> 
> φ = (1 + sqrt(5)) / 2
> def fib(n):
>     numerator = (φ**n) - (1 - φ)**n
>     denominator = sqrt(5)
>     return round(numerator/denominator)

I'd just like to point out that, strictly speaking, it's only O(1) if you 
assume that exponentiation is O(1). Computer scientists often like to 
make this simplifying assumption, and it might even be true for floats, 
but for long ints and any numeric data types with unlimited precision, it 
won't be.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#5795

On Fri, May 20, 2011 at 8:47 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Tue, 17 May 2011 10:02:21 -0700, geremy condra wrote:
>
>> or O(1):
>>
>> φ = (1 + sqrt(5)) / 2
>>     numerator = (φ**n) - (1 - φ)**n
>
> I'd just like to point out that, strictly speaking, it's only O(1) if you
> assume that exponentiation is O(1). Computer scientists often like to
> make this simplifying assumption, and it might even be true for floats,
> but for long ints and any numeric data types with unlimited precision, it
> won't be.
>

Python doesn't have arbitrary precision non-integers, does it? So this
is going to be done with floats.

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#5817

On Fri, 20 May 2011 09:37:59 +1000, Chris Angelico wrote:

> On Fri, May 20, 2011 at 8:47 AM, Steven D'Aprano
> <steve+comp.lang.python@pearwood.info> wrote:
>> On Tue, 17 May 2011 10:02:21 -0700, geremy condra wrote:
>>
>>> or O(1):
>>>
>>> φ = (1 + sqrt(5)) / 2
>>>     numerator = (φ**n) - (1 - φ)**n
>>
>> I'd just like to point out that, strictly speaking, it's only O(1) if
>> you assume that exponentiation is O(1). Computer scientists often like
>> to make this simplifying assumption, and it might even be true for
>> floats, but for long ints and any numeric data types with unlimited
>> precision, it won't be.
>>
>>
> Python doesn't have arbitrary precision non-integers, does it? So this
> is going to be done with floats.

Sure, which is why the above fib() function will become increasing 
inaccurate beyond some given n, by memory about n=71 or so. Er, at least 
the fib() function that *was* above until you deleted most of it :)

If you want an *accurate* fib() function using exponentiation of φ, you 
need arbitrary precision non-integers.

Nevertheless, at some point you will hit the limit of floats, which 
thanks to the exponential growth of the Fibonacci sequence won't take 
that long: it takes roughly 1475 iterations to exceed the range of Python 
floats.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#5818

On Fri, May 20, 2011 at 3:58 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> ... until you deleted most of it :)

Minimalist quoting practice! :)

> If you want an *accurate* fib() function using exponentiation of φ, you
> need arbitrary precision non-integers.

I believe the 'bc' command-line calculator can do a-p non-i, and I
know REXX can, but it seems to be quite an unusual thing. Is it that
much harder than a-p integer that it's just not worthwhile? It seems
strange to smoothly slide from native integer to long integer and just
keep on going, and yet to be unable to do the same if there's a
fractional part on it.

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#5820

Chris Angelico wrote:
> I believe the 'bc' command-line calculator can do a-p non-i, and I
> know REXX can

  Yes, bc is wonderful in this regard. Actually, bc does this sort of 
thing in 'circles' around Python. This is one of Python's weaknesses for 
some problem solving... no arbitrary precision. And its not just that bc 
does arbitrary precision--- its that it does it fast!

Actually, it should be relatively easy to incorporate parts of bc into 
Python as C extensions. On the other hand, when needing specialized math 
work from bc, its probably just better to use bc and leave Python alone.

On the other hand, most of the time (and I mean 99.999% of the time) 
floats are going to work just fine... usually folks don't even need 
doubles....   :)

With fifteen or twenty digits of PI we can calculate the circumference 
of the visible universe to within the width of a proton... er, I mean 
hadron... and you know what... how many folks need to do that anyway??


Don't get me wrong... I absolutely love playing around with bignums, but 
then, I'm a math geek...    ;-)



kind regards,
m harris

[toc] | [prev] | [next] | [standalone]

#5825

On Fri, May 20, 2011 at 4:26 PM, harrismh777 <harrismh777@charter.net> wrote:
> Actually, it should be relatively easy to incorporate parts of bc into
> Python as C extensions. On the other hand, when needing specialized math
> work from bc, its probably just better to use bc and leave Python alone.

If someone has time to kill (as if!), it'd be awesome to get a new
numeric type that uses bc's code; any other numeric type (int, long,
float) could autopromote to it, removing the dilemma of which to
promote out of long and float. Hmm... Python 4.0, 'bc' is the new
default integer and everything else is a performance optimization?
Heh.

> On the other hand, most of the time (and I mean 99.999% of the time) floats
> are going to work just fine... usually folks don't even need doubles....
> :)

99.9% of the time int will work fine, too. Most people don't need
arbitrary precision OR floating point.

> Don't get me wrong... I absolutely love playing around with bignums, but
> then, I'm a math geek...    ;-)

Absolutely. Bring on the geekiness.

I've used bignums for things other than straight arithmetic, actually.
In REXX, where everything is a string, I've done some fascinating (and
completely useless) analyses that involve taking internal digits from
a number, performing arithmetic on them, getting huge numbers back,
and then searching for substrings (ie digit strings) in the result.
What's the lowest power of 2 that has 5 consecutive digits in it? All
10 digits? (That is, it has '0123456789' somewhere in its decimal
representation.)

Like I said, completely useless... but how many of you immediately
pondered which language to implement the search in?

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#5860

On Fri, 20 May 2011 16:54:06 +1000, Chris Angelico wrote:

> If someone has time to kill (as if!), it'd be awesome to get a new
> numeric type that uses bc's code; any other numeric type (int, long,
> float) could autopromote to it, removing the dilemma of which to promote
> out of long and float. Hmm... Python 4.0, 'bc' is the new default
> integer and everything else is a performance optimization? Heh.

The problem is, it isn't *just* a performance optimization, there is a 
semantic difference too. Consider:

>>> x = 1e-300
>>> x*x == 0
True

But using something with more precision:

>>> from fractions import Fraction
>>> x = Fraction(10)**-300
>>> x*x == 0
False


So you get different behaviour between floats and arbitrary precision 
numbers.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#5871

On Fri, May 20, 2011 at 10:07 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Fri, 20 May 2011 16:54:06 +1000, Chris Angelico wrote:
>
>> If someone has time to kill (as if!), it'd be awesome to get a new
>> numeric type that uses bc's code; any other numeric type (int, long,
>> float) could autopromote to it, removing the dilemma of which to promote
>> out of long and float. Hmm... Python 4.0, 'bc' is the new default
>> integer and everything else is a performance optimization? Heh.
>
> The problem is, it isn't *just* a performance optimization, there is a
> semantic difference too. Consider:
>
>>>> x = 1e-300
>>>> x*x == 0
> True
>
> But using something with more precision:
>
>>>> from fractions import Fraction
>>>> x = Fraction(10)**-300
>>>> x*x == 0
> False
>
>
> So you get different behaviour between floats and arbitrary precision
> numbers.

And this shows up in the above implementation; reimplementing it using
Fractions and a truncated continuing fraction approximation of phi and
the square root of 5 gets us up to about 500, at the cost of a very
long computation time.

Geremy Condra

[toc] | [prev] | [next] | [standalone]

#5893

On Sat, May 21, 2011 at 3:07 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Fri, 20 May 2011 16:54:06 +1000, Chris Angelico wrote:
>
>> If someone has time to kill (as if!), it'd be awesome to get a new
>> numeric type that uses bc's code; any other numeric type (int, long,
>> float) could autopromote to it, removing the dilemma of which to promote
>> out of long and float. Hmm... Python 4.0, 'bc' is the new default
>> integer and everything else is a performance optimization? Heh.
>
> The problem is, it isn't *just* a performance optimization, there is a
> semantic difference too. Consider:

Sure, but I'm thinking here that the "gold standard" is accuracy, with
other types allowing a programmer to forfeit some accuracy in favour
of performance. (Oh, and I should have said "new default numeric
type".)

And, of course, I was thinking in a stupid hypothetical way that's
extremely unlikely ever to happen.

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#5908

Chris Angelico wrote:
> It seems
> strange to smoothly slide from native integer to long integer and just
> keep on going, and yet to be unable to do the same if there's a
> fractional part on it.

The trouble is that if you always compute exact results
by default, the number of digits required can blow up
very quickly.

There's a story that ABC (the predecessor to Python)
calculated everything using rationals. People found that
sometimes a calculation would take an unexpectedly long
time, and it turned out to be because internally it was
creating fractions with huge numerators and denominators.

As a consequence, Guido decided that Python would *not*
use rationals by default.

The same problem doesn't arise with ints, because the
only time you get an int with a large number of digits
is when you genuinely need a large int. So expanding
ints automatically to however many digits is needed
doesn't do any harm.

In Python 2.6 and later, there's a fractions module for
when you need it.

-- 
Greg

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web