On May 17, 8:50 am, RJB 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 Pyth
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
On Sat, May 21, 2011 at 3:07 AM, Steven D'Aprano
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, rem
On Fri, May 20, 2011 at 10:07 AM, Steven D'Aprano
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, re
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.
There is a nice matrix representation of consecutive Fibonacci
numbers: [[1, 1], [1, 0]] ** n = [[F_n+1, F_n], [F_n, F_n-1]]. Using
the third party mpmath module, which uses arbitrary precision floating
point arithmetic, we can calculate the n'th Fibonacci number for an
arbitrary n as follows:
imp
2011/5/20 Ian Kelly :
> def fib_decimal(n):
> with localcontext() as ctx:
> ctx.prec = n // 4 + 1
> sqrt_5 = Decimal('5').sqrt()
> phi = (1 + sqrt_5) / 2
> numerator = (phi ** n) - (1 - phi) ** n
> return int((numerator / sqrt_5).to_integral_value())
Note that
On Thu, May 19, 2011 at 11:58 PM, Steven D'Aprano
wrote:
> 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 *accurat
On Fri, May 20, 2011 at 4:26 PM, harrismh777 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
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.
On Fri, May 20, 2011 at 3:58 PM, Steven D'Aprano
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
On Fri, 20 May 2011 09:37:59 +1000, Chris Angelico wrote:
> On Fri, May 20, 2011 at 8:47 AM, Steven D'Aprano
> 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
On Thu, May 19, 2011 at 3:47 PM, Steven D'Aprano
wrote:
> 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 li
On Fri, May 20, 2011 at 8:47 AM, Steven D'Aprano
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 exponentia
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
assum
On May 18, 7:27 pm, RJB wrote:
> Thank you! Very cool and clear. I
> hoped that there was something that Python made natural I couldn't see
> after 50 years in other languages.
>
> I'd like to work on combining both approaches. It may take a while...
>From the Knuth identity F[n+m] = ..
you p
On May 17, 9:36 am, rusi wrote:
> On May 17, 8:50 pm, RJB 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
On May 18, 2:04 am, Wolfram Hinderer
wrote:
> On 17 Mai, 20:56, geremy condra wrote:
>
>
>
> > On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen
>
> > wrote:
> > > geremy condra writes:
>
> > >> or O(1):
>
> > >> ö = (1 + sqrt(5)) / 2
> > >> def fib(n):
> > >> numerator = (ö**n) - (1 - ö)*
On Tue, May 17, 2011 at 2:04 PM, Wolfram Hinderer
wrote:
> On 17 Mai, 20:56, geremy condra wrote:
>> On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen
>>
>> wrote:
>> > geremy condra writes:
>>
>> >> or O(1):
>>
>> >> ö = (1 + sqrt(5)) / 2
>> >> def fib(n):
>> >> numerator = (ö**n) - (1 -
On 17 Mai, 20:56, geremy condra wrote:
> On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen
>
> wrote:
> > geremy condra writes:
>
> >> or O(1):
>
> >> ö = (1 + sqrt(5)) / 2
> >> def fib(n):
> >> numerator = (ö**n) - (1 - ö)**n
> >> denominator = sqrt(5)
> >> return round(numerator/d
On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen
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 somewh
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.
--
http:
On Tue, May 17, 2011 at 9:36 AM, rusi wrote:
> On May 17, 8:50 pm, RJB 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 o
On May 17, 8:50 pm, RJB 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 Pyth
On May 17, 8:50 pm, RJB 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 Pyth
On Tue, May 17, 2011 at 9:50 AM, RJB 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
26 matches
Mail list logo
