Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Reelya]

This was the linear version I stuck together earlier for testing:

Spoiler (click to show/hide)

Code: [Select]

long long fibonacci_l(int n)
{
long long fibonacci_last = 0;
long long fibonacci_curr = (n>0);
long long  fibonnaci_temp = 0;
while(n>1)
{
fibonnaci_temp = fibonacci_curr + fibonacci_last;
fibonacci_last = fibonacci_curr;
fibonacci_curr = fibonnaci_temp;
n--;
}

return fibonacci_curr;
}

This version has 1 addition and two copy operations per iteration. Modulus is a division, so it's slow. The ring versions, since it uses modulus, uses 3 divisions, two subtractions, one addition, and three pointer additions ("[ ]") per iteration. Gut feeling says this is slower, even if it's "less code".

I tested both with this framework:

Spoiler (click to show/hide)

Code: [Select]

int main()
{
time_t t,nt;
long long x;
t = time(0);
for(int j=0;j<=1000000;++j)
for(int i=0;i<=90;++i)
x = fibonacci_l(i);
nt = time(0);
cout << nt-t << " seconds" << endl;
t = time(0);
for(int j=0;j<=1000000;++j)
for(int i=0;i<=90;++i)
x = fibonacci_ring(i);
nt = time(0);
cout << nt-t << " seconds" << endl;

while(1==1);
return 0;
}


The result on my PC was that the ring version took 56 seconds, and the "dumb" version took 20 seconds.

[Mephisto]

Python, the "Duplo" of programming languages.

This is clearly a rational argument and I will accept it without explanation or evidence.

[Reelya]

Duplo is large and blocky and easy to put together, and the results are colorful but clunky. Fits Python pretty well.

BTW there seems to be minor bugs in the ring version. Buffer should actually be like this:

Code: [Select]

int buffer[] = { 0, 1, 1 };otherwise it gives some wrong answers

I was thinking this can be massively sped-up. Get rid of the modulus, and thus the division-by-three. This can be achieved by first changing the ring to have period 4, then using a bitmask of the lowest two bits rather than a modulus.

This one is now four times faster than the modulus version, and faster than my original version:

Code: [Select]

long long fibonacci_ring(int n)
{
long long buffer[] = { 0, 1, 1, 2 };

for (int i = 4; i <= n; i++)
buffer[i & 3] = buffer[(i - 1) & 3] + buffer[(i - 2) & 3];

return buffer[n & 3];
}


[Bumber]

BTW there seems to be minor bugs in the ring version. Buffer should actually be like this:

Code: [Select]

int buffer[] = { 0, 1, 1 };otherwise it gives some wrong answers

Depends which Fibonacci set you're using. There's a 0,1,1,2... one and a 1,1,2... one. I programmed the latter.

I tested both with this framework:

Spoiler (click to show/hide)

Code: [Select]

int main()
{
time_t t,nt;
long long x;
t = time(0);
for(int j=0;j<=1000000;++j)
for(int i=0;i<=90;++i)
x = fibonacci_l(i);
nt = time(0);
cout << nt-t << " seconds" << endl;
t = time(0);
for(int j=0;j<=1000000;++j)
for(int i=0;i<=90;++i)
x = fibonacci_ring(i);
nt = time(0);
cout << nt-t << " seconds" << endl;

while(1==1);
return 0;
}


The result on my PC was that the ring version took 56 seconds, and the "dumb" version took 20 seconds.

Did a similar test using the <chrono> library with 100 runs of fibonacci(1000000) versus fibonacci_l(1000000) and got around 2959ms versus 538ms.

[Reelya]

Depends which Fibonacci set you're using. There's a 0,1,1,2... one and a 1,1,2... one.

you wrote "2,1,1" in your post though.

http://en.wikipedia.org/wiki/Fibonacci_number
And if you look at wikipedia, you can start at f(0) = 0 or at f(1) = 1, the sequence is the same after that for any value 'n'. If you're returning that f(0) = 1, then that's incorrect according to either starting point.

Also note, I got your reference code down much faster than before by using bitmasking rather than modulus, maybe you'd like to compare our new version vs the library version?

[Bumber]

Depends which Fibonacci set you're using. There's a 0,1,1,2... one and a 1,1,2... one.

you wrote "2,1,1" in your post though.

http://en.wikipedia.org/wiki/Fibonacci_number
And if you look at wikipedia, you can start at f(0) = 0 or at f(1) = 1, the sequence is the same after that for any value 'n'. If you're returning that f(0) = 1, then that's incorrect according to either starting point.

Also note, I got your reference code down much faster than before by using bitmasking rather than modulus, maybe you'd like to compare our new version vs the library version?

f(0) wasn't supposed to be called in my version. It was part of the invalid input I mentioned. Since 1%3==1, the buffer needed to start at index 1 to avoid using an (n-1).

Edit: Bitmask version runs in about 530ms. It's on par with the 'dumb' method, at least for my samples. Need to crank up the intensity.
The tests look something like this:

Code: [Select]

chrono::steady_clock::time_point begin = chrono::steady_clock::now();
for (int j = 0; j < 100; j++)
{
fibonacci(10000000);
}
chrono::steady_clock::time_point end = chrono::steady_clock::now();

cout << "Time difference = " << chrono::duration_cast<chrono::milliseconds>(end - begin).count() << endl;
Results for 100 runs of f(10 million):
31481ms Modular
5336ms Dumb
5287ms Bitmask

There's some variance each time I run it (Firefox is definitely contributing,) but bitmask method seems consistently slightly better than dumb method.

[Reelya]

changing your original version to {0,1,1} and the start index to "3" will be correct for all values though, and you get f(0) correct as a bonus.

[miauw62]

Why not just use the formula when you're computing really big numbers, it's probably O(1), assuming that powers are O(1).
Not entirely sure if you'll run into issues with rounding errors, though.

[Putnam]

Not entirely sure if you'll run into issues with rounding errors, though.

It's likely that any rounding errors can be solved by rounding the result.

[Orange Wizard]

Just glancing at it, the rounding error gets bigger as n increases. Although the integer overflows long before it approaches anything that round() or equivalent can't solve.

[Reelya]

Why not just use the formula when you're computing really big numbers, it's probably O(1), assuming that powers are O(1).
Not entirely sure if you'll run into issues with rounding errors, though.

Optimizing a given algorithm is a challenge / learning exercise.

[Spehss _]

Getting a compile bug.

Code: [Select]

C:\Users\~blahblahblah~\programs\slime mold simulator\main.cpp|14|warning: non-static data member initializers only available with -std=c++11 or -std=gnu++11 [enabled by default]|
Don't know what to do.

[Orange Wizard]

[enabled by default]

[Spehss _]

Enable C++11 for your compiler. What IDE are you using?

Codeblocks. Specifically Codeblocks-13.12mingw. So it's using Mingw32-g++ for compiling, as far as I can tell. It was set to that when I first downloaded it.

[Gentlefish]

you might have to enter it in yourself, as well. There'll be a text box there to do that.