1. You know what laserlight, I had an unfortunate IO error (That would be "Idiot Operator" not "Input/Output"). Yeah it works fine.. I am just a boob sometimes.

And yeah I tried the non-trigonometric version when I was looking at the derivation which is why I wasn't following how come my results weren't working. But it works fine.

2. Originally Posted by MK27
Oh malarky

Code:
```#include <stdio.h>

int main () {
int a=0, b=1, n=a+b,i,ii;
puts("Number of iterations");
scanf("&#37;d",&ii);
printf("%d %d ",a,b);
for (i=0;i<ii;i++) {
n=a+b;
printf("%d ",n);
a=b;b=n;
}
}```
I don't know much math, so I'd be really interested to read how you could make this computation "more efficient".

 i guess this is actually iterative, and not recursive
That was a challenge! Here is my contest entry:
Code:
```int fib(int n) {
int a[2] = { 0, 1 }, i;
for (i = n + 1 >> 1 ; i; i--)
a[0] += a[1] += a[0];
return a[n & 1]; }```
This takes about 1/2 the time yours does. But caution: highest legit value is 64. Gives 1,640,636,603 which is the largest integer that fits into 32 bit. I could go 64-bit but for timing purposes I just threw the two functions into another loop - executing factorial(64) 10,000,000 times.

Mine is around 6-7 seconds.
(Mac laptop 1.33 GHz PowerPC G4)

3. Code:
`a[0] += a[1] += a[0];`
isn't that UB?

Code:
`i = (n + 1) >> 1`
??

--
Mats

4. um, excuse me, may I rephrase my question?
Code:
```/* http://goldennumber.net/five(5).htm */
#define PHI pow(M_E, asinh(0.5))

/* http://goldennumber.net/five(5).htm */
double fib (unsigned int n)
{
return((pow(PHI, (double)n)) / sqrt(5.0));
}```
I need to get the right result from the function fib(), because when n=71, n=76, and after n=79 the function returns incorrect result (f[n]!=f[n-1]+f[n-2]).

5. Originally Posted by cph
I need to get the right result from the function fib(), because when n=71, n=76, and after n=79 the function returns incorrect result (f[n]!=f[n-1]+f[n-2]).
64-bit numbers?
GMP?

You are asking how to reach above and beyond a hardware limitation. You are asking how to make your computer do something that is beyond the implementation of your algorithm. Right? I mean you see how I arrive at that conclusion, right?

6. Originally Posted by matsp
Code:
`a[0] += a[1] += a[0];`
isn't that UB?

Code:
`i = (n + 1) >> 1`
??

--
Mats
+= associativity is right-to-left just as any assignment, so I assume it is executed in that order.

(n + 1) >> 1 - true, but I abhor extra parenthesis when they're not needed. Operator precedence is such that addition is done before the shift.

7. Originally Posted by nonoob
I abhor extra parenthesis when they're not needed.
They do add to clarity though, and your post was a good example of that.

QuantumPete

8. Originally Posted by nonoob
+= associativity is right-to-left just as any assignment, so I assume it is executed in that order.
Order of evaluation and associativity are not the same thing. However, I think that matsp is wrong - there is no undefined behaviour as far as I can tell. I recall a thread some time ago where the conclusion was that the XOR swap of a and b written as a ^= b ^= a ^= b; resulted in undefined behaviour, but I believe that is because a is modified twice within consecutive sequence points. In your code, however, both a[0] and a[1] are modified exactly once within consecutive sequence points.

9. Thanks for that explanation, laserlight. i was starting to get worried that I am misunderstanding associativity in any standard precedence chart. What is it then if "right-to-left" is not related to execution order? The right argument is evaluated first, I thought.

10. Originally Posted by nonoob
What is it then if "right-to-left" is not related to execution order? The right argument is evaluated first, I thought.
The order of evaluation of operands is unspecified. In this case, it does not matter, but consider this contrived example:
Code:
```#include <stdio.h>

int *foo(int *x, int y)
{
printf("&#37;d\n", y);
return x;
}

int main(void)
{
int a = 1;
int b = 2;
*foo(&a, 1) += *foo(&b, 2) += *foo(&a, 3);
return 0;
}```
It is possible that on one implementation the output is "1\n2\n3\n" while on another it is "3\n2\n1\n".

11. Sorry to bump an old thread, but I came accross this accidentally and wanted to share my thoughts.

First of all, the problem with this method posted above:
Code:
`pow(PHI, n) / sqrt(5.0)`
is that it's simply incorrect, or incomplete. It's only half of the Fibonacci recurrence relation.

The correct way would be:
Code:
```int Fib( int n )
{
static const double s = sqrt(5.0);
return int( (pow(1+s,n)-pow(1-s,n))/(pow(2.0,n)*s) );
}```
(use long long instead of int for large n, as the result will obviously not fit in 32 bit integers).

There is, however, an even much faster way. After quite some experimenting with several approaches and lotsa optimizing, this is imho the ultimate solution: (besides using a direct lookup or caching table of course)
Code:
```unsigned int Fib( unsigned int n )
{
n--;
unsigned int a=1,b=0,c=1,p=1,t;
while (p<=n) p += p;
do
{
p >>= 1;
t = b*b;
b *= a+c;
a = a*a + t;
c = c*c + t;
if (n&p)
{
c = b;
b = a;
a += c;
}
}
while (p>1);
return a;
}```
This performs about 3 times as fast as the pow / √5 method. Of course, again, use long long for large n.

12. Originally Posted by Phuzzillogic
Sorry to bump an old thread, but I came accross this accidentally and wanted to share my thoughts.
That is okay; I maintain that it is fine to post in an ancient thread when you have something worthwhile to contribute, especially if it is an important correction.

Originally Posted by Phuzzillogic
is that it's simply incorrect, or incomplete. It's only half of the Fibonacci recurrence relation.
It is not incorrect in its idea since the idea is that the other half can be ignored as it has negligible contribution in the approximation. I demonstrated a correct way to perform this approximation in post #45.

13. Originally Posted by laserlight
It is not incorrect in its idea since the idea is that the other half can be ignored as it has negligible contribution in the approximation. I demonstrated a correct way to perform this approximation in post #45.
Ah I see, you're right, the correction you applied indeed makes up for the missing term.

Nonetheless, when I compare this "single pow" method to my integer version, the latter is still almost 15% faster.