On May 17, 8:50 am, 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
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
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.pyt...@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
On Fri, May 20, 2011 at 3:58 PM, Steven D'Aprano
steve+comp.lang.pyt...@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'
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 4:26 PM, harrismh777 harrismh...@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.
On Thu, May 19, 2011 at 11:58 PM, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info 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
2011/5/20 Ian Kelly ian.g.ke...@gmail.com:
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 /
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:
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.
On Fri, May 20, 2011 at 10:07 AM, Steven D'Aprano
steve+comp.lang.pyt...@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,
On Sat, May 21, 2011 at 3:07 AM, Steven D'Aprano
steve+comp.lang.pyt...@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)
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
On Fri, May 20, 2011 at 8:47 AM, Steven D'Aprano
steve+comp.lang.pyt...@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
On Thu, May 19, 2011 at 3:47 PM, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info 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
On May 17, 9:36 am, rusi rustompm...@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
On May 18, 7:27 pm, RJB rbott...@csusb.edu 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
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
On Tue, May 17, 2011 at 9:50 AM, 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
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
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
On Tue, May 17, 2011 at 9:36 AM, rusi rustompm...@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
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.
--
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
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)
On Tue, May 17, 2011 at 2:04 PM, 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
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
27 matches
Mail list logo
