|
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.
|
|
|
|
|
Does the result of the XOR have to be stored in a register/accumulator before being stored in the result?
|
|
|
|
|
No, not necessarily, the `xor mem, reg` form could be used. I don't see how that would help though.
|
|
|
|
|
harold aptroot wrote: how that would help
Contrarywise, I'd expect it to make things worse.
But it depends on the CPU.
|
|
|
|
|
|
Max Holder wrote: Only up to n=200; n=201 result is bigger than ulong
Are you sure about that? If I change the code to use a checked context for the addition:
checked { b += a; }
I get an overflow at n = 94.
Using the original code, I see:
n = 92: 7540113804746346429n = 93: 12200160415121876738n = 94: 1293530146158671551
That's clearly wrong; the result for 94 is less than the result for 92!
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
|
Can you explain what you actually are doing with the XOR's, what is the mathematics behind it? Im really curios about it.
modified 18-Apr-13 13:05pm.
|
|
|
|
|
|
Or you can combine two iterations so there is no swap:
private static ulong GetFib3(int n)
{
ulong a = 0;
ulong b = 1;
if (n == 0) return a;
if (n <= 2) return b;
if ((n & 1) == 0)
{
a = 1;
n--;
}
int i = n - 1;
do
{
a += b;
b += a;
i -= 2;
} while (i != 0);
return b;
}
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
