|
Hello,
me and a coworker had thought about optimzing the fibonacci calculation.
This is what we have ended up and is pretty fast. (It is fast enough, for our product, but we want to know what is possible)
private static ulong GetFib3(int n)
{
ulong a = 0;
ulong b = 1;
if (n == 0) return a;
if (n == 1) return b;
for (int i = 2; i <= n ; i++)
{
a ^= b;
b ^= a;
a ^= b;
b += a;
}
return b;
}
The method has following restrictions: Only up to n=200; n=201 result is bigger than ulong and no negative fibonaccis.
This method is actually pretty fast (20x faster than our first approach) and (as I think) it is well optimized.
My main question is: Is it possible to improve the execution speed even more? (I dont mean precalculating the values and then just access the values)
Regards,
Max
modified 18-Apr-13 8:58am.
|
|
|
|
|
Yes.
Precalculate the values. Since you are only working with 200 items, run your existing code to output the list of values into a text file, then add those values as an array:
private static ulong[] fibValues = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...};Then your routine is just a limit test and an array access.
The universe is composed of electrons, neutrons, protons and......morons. (ThePhantomUpvoter)
|
|
|
|
|
Ofcourse precalculating the values and then just accessing the array is fastest.
But I want to calculate it the fastest way...
|
|
|
|
|
That wasn't what you asked! 
The universe is composed of electrons, neutrons, protons and......morons. (ThePhantomUpvoter)
|
|
|
|
|
Thought it will be understood correctly. I edited the inital post.
But thanks for your efforts answering my question 
|
|
|
|
|
There is a formula:
Private Function Fibonacci(ByVal n As Integer) As Double
Return (1 / Math.Sqrt(5)) * ((1 + Math.Sqrt(5)) / 2) ^ n - (1 / Math.Sqrt(5)) * ((1 - Math.Sqrt(5)) / 2) ^ n
End Function
And it seems to do the trick, mening no tables
http://en.wikipedia.org/wiki/Fibonacci_number[^]
|
|
|
|
|
Yes, this implementation works great, BUT it is actually slower on my machine than my code I initially posted.
|
|
|
|
|
Whats the slowdown? if it is Sqrt that could be fixed, and if its the power function you could make that better too.
|
|
|
|
|
This is faster on my computer:
Private Function Fibonacci2(ByVal n As Integer) As Double
Dim gold As Double = 1.6180339887498949
Dim gold2 As Double = 0.6180339887498949
Dim sqrt1over5 As Double = 0.44721359549995793
Return sqrt1over5 * ((gold) ^ n - (gold2) ^ n)
End Function
|
|
|
|
|
My Results so far:
Link to screenshot
Last one is your Goldratio implementation (second fast), second from bottom is my last implementation (and fastest I found)...
I ran it one time (n=50), speed is always a bit different, but differences are accurate.
|
|
|
|
|
The one you posted in your question is that v1 or v2 in your picture? The version you posted in the question I cant run with when n = 60 or above.
|
|
|
|
|
It is the v2.
I can run it fine till 200, 201 would be too big for the ulong.
I see you code in vb.net, maybe there is a problem with datatypes?
|
|
|
|
|
The code looks like this:
Private Function GetFib3(ByVal n As Integer) As ULong
Dim a As Int64 = 0
Dim b As Int64 = 1
If (n = 0) Then Return a
If (n = 1) Then Return b
For i As UInt64 = 2 To n
a = a Xor b
b = b Xor a
a = a Xor b
b += a
Next
Return b
End Function
And it always gives me trouble with aretmetic overflow on the add part.
|
|
|
|
|
Kenneth Haugland wrote: Dim a As Int64 = 0
Dim b As Int64 = 1
Shouldn't those be ULong?
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
They should, but I get the same error anyways...
|
|
|
|
|
I've just tried this in LinqPad, and it works up to n = 93:
Private Function GetFib3(ByVal n As Integer) As ULong
Dim a As ULong = 0
Dim b As ULong = 1
If (n = 0) Then Return a
If (n = 1) Then Return b
For i As ULong = 2 To Convert.ToUInt64(n)
a = a Xor b
b = b Xor a
a = a Xor b
b += a
Next
Return b
End Function
The C# version is only working on higher numbers because it's using an unchecked context by default; the results for n = 94 or higher are wrong.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
None of my implementations work above n=70 regardless of what I do so I went for Numerics.BigInteger:
Private Function GetFib2(ByVal n As Integer) As Numerics.BigInteger
Dim a As New Numerics.BigInteger
a = 0
Dim b As New Numerics.BigInteger
b = 1
If (n = 0) Then Return a
If (n = 1) Then Return b
For i As UInt64 = 2 To n
a = a Xor b
b = b Xor a
a = a Xor b
b += a
Next
Return b
End Function
This is always correct, however it might be a little slower...
|
|
|
|
|
define a and b as uint64 too
|
|
|
|
|
Only for small N... the formula is faster for larger numbers. You won't see any advantage until you get to the larger numbers, and the point where it crosses over (formula becomes faster) will vary on different machines.
|
|
|
|
|
Here is the matrix-power version, it's asymptotically faster but probably not real-life faster because `n` is always low. Worth a try though
static ulong Fibonacci(uint n)
{
ulong m00 = 1, m01 = 1, m10 = 1, m11 = 0;
ulong x00 = 1, x01 = 1, x10 = 1, x11 = 0;
while (n != 0)
{
if ((n & 1) != 0)
{
ulong t00 = m00 * x00 + m01 * x10;
ulong t01 = m00 * x01 + m01 * x11;
ulong t10 = m10 * x00 + m11 * x10;
ulong t11 = m10 * x01 + m11 * x11;
x00 = t00;
x01 = t01;
x10 = t10;
x11 = t11;
}
ulong y00 = m00 * m00 + m01 * m10;
ulong y01 = m00 * m01 + m01 * m11;
ulong y10 = m10 * m00 + m11 * m10;
ulong y11 = m10 * m01 + m11 * m11;
m00 = y00;
m01 = y01;
m10 = y10;
m11 = y11;
n >>= 1;
}
return x01;
}
By the way, is that XOR-swap really faster than a normal swap?
|
|
|
|
|
Thanks for the implementation. Later this day i will compare the results.
I tested the swap with a temp ulong too, it was a bit slower than the XOR swap.
|
|
|
|
|
Max Holder wrote: I tested the swap with a temp ulong too, it was a bit slower than the XOR swap.
Interesting, good to know.
|
|
|
|
|
|
harold aptroot wrote: is that XOR-swap really faster than a normal swap?
How could it be? The XOR swap is to save space, not time.
|
|
|
|
|
PIEBALDconsult wrote: How could it be?
Oh you want conjecture, do you? Ok: the extra temporary could have made it spill something to the stack, and doing the swap through memory is obviously slower than a XOR swap. Memory dependence misprediction penalties and forwarding delays and whatnot.
That only makes sense on 32bit, on 64bit there would obviously be plenty registers.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
