Hmm, shouldn't today's compilers be smart enough to detect and

optimize tail-recursion? As in:

double fib(int n)

{

return fib_iter(1, 0, n);

}

double fib_iter(double old, double older, int count)

{

return count ? fib_iter(old + older, old, --count) : older;

}

(Excuse me for butting in... it's an irresistible subject for

a scheme fan ;)

--

// }{idehiko ()gata "I hope I didn't hurt you too much

\X/ Amiga since '86 when I killed you..." - Elmer Fudd

bekkoame is a classic Japanese candybar.

"Hidehiko Ogata" < XXXX@XXXXX.COM > writes:

I don't mind at all. The topic was already straying from the Apple ][.

GNU cc doesn't do this optimization. I'll leave the topic of whether it

should to others.

I was hoping that somebody would bite on my direct calculation for the

Fibonacci sequence, wondering where my "magic constants" came from, and

why it works. I guess most people either already know, or don't care.

Scott

--

Scott Hemphill XXXX@XXXXX.COM

"This isn't flying. This is falling, with style." -- Buzz Lightyear

I don't mind at all. The topic was already straying from the Apple ][.

GNU cc doesn't do this optimization. I'll leave the topic of whether it

should to others.

I was hoping that somebody would bite on my direct calculation for the

Fibonacci sequence, wondering where my "magic constants" came from, and

why it works. I guess most people either already know, or don't care.

Scott

--

Scott Hemphill XXXX@XXXXX.COM

"This isn't flying. This is falling, with style." -- Buzz Lightyear

<snip>

the

and

care.

Hmm. Well, I care! :)

Please, elaborate? I haven't had a chance to even try it, yet!

Ben

Might as well... at least the growth is linear, so it shouldn't suck

as bad :).

Or scared of the scantiest smell of hard math? 8)

ObOT: is there any minor revision among ROM3? I have two ROM3 IIgs'es

which put up different control panels.

--

// }{idehiko ()gata "I hope I didn't hurt you too much

\X/ Amiga since '86 when I killed you..." - Elmer Fudd

bekkoame is a classic Japanese candybar.

XXXX@XXXXX.COM " < XXXX@XXXXX.COM > writes:

The first step is to find a closed form for the Fibonacci sequence. Let's

call any sequence starts with two numbers a0 and a1 and then is further

defined by a2=a1+a0, a3=a2+a1, etc. an "additive sequence". If you

multiply an additive sequence {a0,a1,a2,...} by a constant, then the

result is an additive sequence. If you add two different additive

sequences {a0,a1,a2,...} and {b0,b2,b2,...} together, the result is also

an additive sequence. Suppose we know a closed form for calculating two

different additive sequences. Then we can "mix" them by multiplying the

first sequence by one constant, the second sequence by another constant,

and adding that together. If we are careful about choosing the constants,

we can arrange that the first number of the resulting additive sequence is

zero and the second number is one, and the sequence will therefore be the

Fibonacci sequence.

Here's how this works:

Look at the sequence {1,g,g^2,g^3,...}. If g^2=g+1, then the sequence

is additive because (multiplying both sides of the equation by g) g^3=g^2+g.

If you keep multiplying both sides of the equation by you wind up with

g^4=g^3+g^2, etc.

So what does "g" have to be to make this sequence additive? The quadratic

equation g^2-g-1=0 has two roots, (1+sqrt(5))/2 and (1-sqrt(5))/2.

The first solution is the "golden ratio", 1.618... and the second is

-0.618.... From this point on, I'll use "g" to refer to the golden ratio,

and "1-g" to refer to the other solution of g^2-g-1=0.

So we have just come up with closed forms for two additive sequences:

{1,g,g^2,...} and {1,1-g,(1-g)^2,...}.

We want to mix these by multiplying each by a constant and adding that

together in such a way as to form the Fibonacci sequence.

c {1,g,g^2,...} + d {1,1-g,(1-g)^2,...} = {0,1,1,2,...}

If the first number of the sequence is going to be zero, then c + d = 0,

or d = -c. Then we have:

c {1,g,g^2,...} - c {1,1-g,(1-g)^2,...} = {0,1,1,2,...}

If the second number of the sequence is going to be one, then c*g-c*(1-g)=1,

or c=1/(2*g-1)=1/sqrt(5).

So we now have a closed form for the nth term of the Fibonacci sequence:

(g^n-(1-g)^n)/sqrt(5)

Now look at what happens as n gets bigger and bigger. "g" is bigger than

one, so g^n keeps growing. However (1-g) has absolute value less than one,

so (1-g)^n keeps getting closer and closer to zero. If n is large enough,

we can forget about the (1-g)^n term completely. So lets look at the

sequence defined by g^n/sqrt(5):

{0.447214, 0.723607, 1.17082, 1.89443, 3.06525, 4.95967, 8.02492,

12.9846, 21.0095, 33.9941, 55.0036, ...}

We can see that it gets closer and closer to the Fibonacci sequence. The

contribution of the (1-g)^n is small enough that we can ignore it completely

for all n>=0. All we have to do is to round the sequence to the nearest

integer, and it will be correct for all n.

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}

So the equation implementing the closed form solution looks something like:

round(pow(g,n)/sqrt(5)), where g = 1.6180339887498948482045868343656

and sqrt(5) = 2.2360679774997896964091736687313

round is not a standard C function, but can be implemented as floor(0.5+ ...)

Since pow(g,n) might overflow in cases where pow(g,n)/sqrt(5) is still

within the representable range of numbers, and who knows, exp might be

faster than po

The first step is to find a closed form for the Fibonacci sequence. Let's

call any sequence starts with two numbers a0 and a1 and then is further

defined by a2=a1+a0, a3=a2+a1, etc. an "additive sequence". If you

multiply an additive sequence {a0,a1,a2,...} by a constant, then the

result is an additive sequence. If you add two different additive

sequences {a0,a1,a2,...} and {b0,b2,b2,...} together, the result is also

an additive sequence. Suppose we know a closed form for calculating two

different additive sequences. Then we can "mix" them by multiplying the

first sequence by one constant, the second sequence by another constant,

and adding that together. If we are careful about choosing the constants,

we can arrange that the first number of the resulting additive sequence is

zero and the second number is one, and the sequence will therefore be the

Fibonacci sequence.

Here's how this works:

Look at the sequence {1,g,g^2,g^3,...}. If g^2=g+1, then the sequence

is additive because (multiplying both sides of the equation by g) g^3=g^2+g.

If you keep multiplying both sides of the equation by you wind up with

g^4=g^3+g^2, etc.

So what does "g" have to be to make this sequence additive? The quadratic

equation g^2-g-1=0 has two roots, (1+sqrt(5))/2 and (1-sqrt(5))/2.

The first solution is the "golden ratio", 1.618... and the second is

-0.618.... From this point on, I'll use "g" to refer to the golden ratio,

and "1-g" to refer to the other solution of g^2-g-1=0.

So we have just come up with closed forms for two additive sequences:

{1,g,g^2,...} and {1,1-g,(1-g)^2,...}.

We want to mix these by multiplying each by a constant and adding that

together in such a way as to form the Fibonacci sequence.

c {1,g,g^2,...} + d {1,1-g,(1-g)^2,...} = {0,1,1,2,...}

If the first number of the sequence is going to be zero, then c + d = 0,

or d = -c. Then we have:

c {1,g,g^2,...} - c {1,1-g,(1-g)^2,...} = {0,1,1,2,...}

If the second number of the sequence is going to be one, then c*g-c*(1-g)=1,

or c=1/(2*g-1)=1/sqrt(5).

So we now have a closed form for the nth term of the Fibonacci sequence:

(g^n-(1-g)^n)/sqrt(5)

Now look at what happens as n gets bigger and bigger. "g" is bigger than

one, so g^n keeps growing. However (1-g) has absolute value less than one,

so (1-g)^n keeps getting closer and closer to zero. If n is large enough,

we can forget about the (1-g)^n term completely. So lets look at the

sequence defined by g^n/sqrt(5):

{0.447214, 0.723607, 1.17082, 1.89443, 3.06525, 4.95967, 8.02492,

12.9846, 21.0095, 33.9941, 55.0036, ...}

We can see that it gets closer and closer to the Fibonacci sequence. The

contribution of the (1-g)^n is small enough that we can ignore it completely

for all n>=0. All we have to do is to round the sequence to the nearest

integer, and it will be correct for all n.

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}

So the equation implementing the closed form solution looks something like:

round(pow(g,n)/sqrt(5)), where g = 1.6180339887498948482045868343656

and sqrt(5) = 2.2360679774997896964091736687313

round is not a standard C function, but can be implemented as floor(0.5+ ...)

Since pow(g,n) might overflow in cases where pow(g,n)/sqrt(5) is still

within the representable range of numbers, and who knows, exp might be

faster than po

1. Recursion in Java: Question for those who understand recursion well.

2. Recursion:Recursion: Recursion:Recursion

3. My Understanding of the Recursion in Reduction Procedures

6. Help me understand why and where recursion performs better

7. Understanding why Recursion is necessary

10. recursion vs allow-recursion

11. One thing that I don't understand about CD hardware(One out of many)

12. Recursion or iteration (was Fibonacci series recursion error)

13. views, recursion, and allow-recursion

14. One thing that I don't understand about CD hardware(One out of many)

5 post • Page:**1** of **1**