Re: [OT] fastest fibbonacci
On Tuesday, 25 October 2016 at 07:05:20 UTC, Era Scarecrow wrote: Hmm as an experiment I changed from doubles to reals, and got a slightly higher result, up to 85 giving us a 58/64 Of course floating precision is not unlimited :)
Re: [OT] fastest fibbonacci
On Monday, 24 October 2016 at 19:03:51 UTC, Era Scarecrow wrote: It's only good through 71 iterations (longs) then it starts having errors. Also for some odd reason the input is one off, so I had to add a -1 to the input for it to align. This makes it accurate to 41/64 bit results. 71: 308061521170129 308061521170129 true 72: 498454011879264 498454011879265 false Hmm as an experiment I changed from doubles to reals, and got a slightly higher result, up to 85 giving us a 58/64 83: 99194853094755497 99194853094755497 true 84: 160500643816367088 160500643816367088 true 85: 259695496911122585 259695496911122585 true 86: 420196140727489673 420196140727489674 false 87: 679891637638612258 679891637638612259 false 88: 1100087778366101931 1100087778366101933 false
Re: [OT] fastest fibbonacci
On Monday, 24 October 2016 at 08:54:38 UTC, Andrea Fontana wrote: You can simply write it as: round(phi^n/sqrt(5)); Check my example above :) Ran your example and it's perfect for 32bit code. But 64bit, not so much. It's only good through 71 iterations (longs) then it starts having errors. Also for some odd reason the input is one off, so i had to add a -1 to the input for it to align. This makes it accurate to 41/64 bit results. for(int i = 1; i < 100; ++i) { auto cf = computeFib(i); auto cfm = computeFibMagic(i-1); //with magic numbers exampled writeln(i, ": ", cf, "\t", cfm, "\t", cf == cfm); } 64: 10610209857723 10610209857723 true 65: 17167680177565 17167680177565 true 66: 2890035288 2890035288 true 67: 44945570212853 44945570212853 true 68: 72723460248141 72723460248141 true 69: 117669030460994 117669030460994 true 70: 190392490709135 190392490709135 true 71: 308061521170129 308061521170129 true 72: 498454011879264 498454011879265 false 73: 806515533049393 806515533049395 false 74: 13049695449286571304969544928660false 75: 21114850779780502111485077978055false 76: 34164546229067073416454622906715false 77: 55279397008847575527939700884771false 78: 89443943237914648944394323791487false 79: 14472334024676221 14472334024676258 false 80: 23416728348467685 23416728348467746 false
Re: [OT] fastest fibbonacci
On Monday, 24 October 2016 at 08:20:26 UTC, Matthias Bentrup wrote: PS: the exact formula is fib(n) = 1/sqrt(5) * (0.5 + 0.5sqrt(5))^n - 1/sqrt(5) * (0.5 - 0.5sqrt(5))^n. If you round to integer anyway, the second term can be ignored as it is always <= 0.5. You can simply write it as: round(phi^n/sqrt(5)); Check my example above :)
Re: [OT] fastest fibbonacci
On Sunday, 23 October 2016 at 23:17:28 UTC, Stefam Koch wrote: On Sunday, 23 October 2016 at 19:59:16 UTC, Minas Mina wrote: On Sunday, 23 October 2016 at 13:04:30 UTC, Stefam Koch wrote: Hi Guys, while brushing up on my C and algorithm skills, accidently created a version of fibbonaci which I deem to be faster then the other ones floating around. It's also more concise the code is : int computeFib(int n) { int t = 1; int result = 0; while(n--) { result = t - result; t = t + result; } return result; } You can even calculate Fibonacci in O(1). An approximation of it. The fibonacci sequence can be represented exactly as a linear combination of two exponential functions, but the two bases of the exponentials and the linear multipliers of them are irrational numbers, which cannot be represented exactly on a computer. However the rounding error is so small, that rounding to int will give you always the correct answer as long as you stay within the precision limit of the floating point type you use, e.g. a real should give you 64-bit fibonacci in O(1), if the exponential function is O(1). PS: the exact formula is fib(n) = 1/sqrt(5) * (0.5 + 0.5sqrt(5))^n - 1/sqrt(5) * (0.5 - 0.5sqrt(5))^n. If you round to integer anyway, the second term can be ignored as it is always <= 0.5.
Re: [OT] fastest fibbonacci
On Sunday, 23 October 2016 at 13:04:30 UTC, Stefam Koch wrote: Hi Guys, while brushing up on my C and algorithm skills, accidently created a version of fibbonaci which I deem to be faster then the other ones floating around. It's also more concise the code is : int computeFib(int n) { int t = 1; int result = 0; while(n--) { result = t - result; t = t + result; } return result; } import std.stdio; import std.math: pow; int computeFib(int n) { if (n==0) return 1; // Magic :) enum magic_1 = 1.61803398874989484820458683436563811772030917980576286213544862270526046281890244970720720418939113748475; enum magic_2 = 2.23606797749978969640917366873127623544061835961152572427089724541052092563780489941441440837878227; return cast(int)((0.5+pow(magic_1,n+1))/magic_2); } void main() { for(int i = 0; i < 10; ++i) writeln(computeFib(i)); }
Re: [OT] fastest fibbonacci
On 23.10.2016 21:59, Minas Mina wrote: On Sunday, 23 October 2016 at 13:04:30 UTC, Stefam Koch wrote: Hi Guys, while brushing up on my C and algorithm skills, accidently created a version of fibbonaci which I deem to be faster then the other ones floating around. It's also more concise the code is : int computeFib(int n) { int t = 1; int result = 0; while(n--) { result = t - result; t = t + result; } return result; } You can even calculate Fibonacci in O(1). The closed form does not give you an O(1) procedure that computes the same as the above code (with the same wrap-around-behaviour). If arbitrary precision is used, the result grows linearly, so the calculation cannot be better than linear. I don't think the closed form gives you a procedure that is faster than Θ(n·log n) in that case.
Re: [OT] fastest fibbonacci
On Sunday, 23 October 2016 at 19:59:16 UTC, Minas Mina wrote: On Sunday, 23 October 2016 at 13:04:30 UTC, Stefam Koch wrote: Hi Guys, while brushing up on my C and algorithm skills, accidently created a version of fibbonaci which I deem to be faster then the other ones floating around. It's also more concise the code is : int computeFib(int n) { int t = 1; int result = 0; while(n--) { result = t - result; t = t + result; } return result; } You can even calculate Fibonacci in O(1). An approximation of it.
Re: [OT] fastest fibbonacci
On Sunday, 23 October 2016 at 13:04:30 UTC, Stefam Koch wrote: Hi Guys, while brushing up on my C and algorithm skills, accidently created a version of fibbonaci which I deem to be faster then the other ones floating around. It's also more concise the code is : int computeFib(int n) { int t = 1; int result = 0; while(n--) { result = t - result; t = t + result; } return result; } You can even calculate Fibonacci in O(1).
Re: [OT] fastest fibbonacci
On Sunday, 23 October 2016 at 13:04:30 UTC, Stefam Koch wrote: created a version of fibbonaci which I deem to be faster then the other ones floating around. Rosettacode is a good place to check for "floating around" implementations of common practice exercises e.g.: http://rosettacode.org/wiki/Fibonacci_sequence#Matrix_Exponentiation_Version
Re: [OT] fastest fibbonacci
On 10/23/16 12:32 PM, Timon Gehr wrote: It uses a general technique to speed up computation of linear recurrences Would be awesome to factor this out of the particular algorithm. I recall SICP famously does that with a convergence accelerating technique for series. -- Andrei
Re: [OT] fastest fibbonacci
On 23.10.2016 17:42, Stefam Koch wrote: On Sunday, 23 October 2016 at 15:12:37 UTC, Timon Gehr wrote: On 23.10.2016 15:04, Stefam Koch wrote: Hi Guys, while brushing up on my C and algorithm skills, accidently created a version of fibbonaci which I deem to be faster then the other ones floating around. It's also more concise the code is : int computeFib(int n) { int t = 1; int result = 0; while(n--) { result = t - result; t = t + result; } return result; } int computeFib(int n){ int[2] a=[0,1],b=[1,2],c=[1,-1]; for(;n;n>>=1){ foreach(i;1-n&1..2){ auto d=a[i]*a[1]; a[i]=a[i]*b[1]+c[i]*a[1]; b[i]=b[i]*b[1]-d; c[i]=c[i]*c[1]-d; } } return a[0]; } (Also: you might want to use BigInt.) Wow, that looks intresting. Can you explain how it computes fibbonacci ? It uses a general technique to speed up computation of linear recurrences, with a few additional optimizations. One iteration of your while loop multiplies the vector (result,t) by a matrix. I exponentiate this matrix using a logarithmic instead of a linear number of operations.
Re: [OT] fastest fibbonacci
On Sunday, 23 October 2016 at 15:12:37 UTC, Timon Gehr wrote: On 23.10.2016 15:04, Stefam Koch wrote: Hi Guys, while brushing up on my C and algorithm skills, accidently created a version of fibbonaci which I deem to be faster then the other ones floating around. It's also more concise the code is : int computeFib(int n) { int t = 1; int result = 0; while(n--) { result = t - result; t = t + result; } return result; } int computeFib(int n){ int[2] a=[0,1],b=[1,2],c=[1,-1]; for(;n;n>>=1){ foreach(i;1-n&1..2){ auto d=a[i]*a[1]; a[i]=a[i]*b[1]+c[i]*a[1]; b[i]=b[i]*b[1]-d; c[i]=c[i]*c[1]-d; } } return a[0]; } (Also: you might want to use BigInt.) Wow, that looks intresting. Can you explain how it computes fibbonacci ?
Re: [OT] fastest fibbonacci
On 23.10.2016 15:04, Stefam Koch wrote: Hi Guys, while brushing up on my C and algorithm skills, accidently created a version of fibbonaci which I deem to be faster then the other ones floating around. It's also more concise the code is : int computeFib(int n) { int t = 1; int result = 0; while(n--) { result = t - result; t = t + result; } return result; } int computeFib(int n){ int[2] a=[0,1],b=[1,2],c=[1,-1]; for(;n;n>>=1){ foreach(i;1-n&1..2){ auto d=a[i]*a[1]; a[i]=a[i]*b[1]+c[i]*a[1]; b[i]=b[i]*b[1]-d; c[i]=c[i]*c[1]-d; } } return a[0]; } (Also: you might want to use BigInt.)
[OT] fastest fibbonacci
Hi Guys, while brushing up on my C and algorithm skills, accidently created a version of fibbonaci which I deem to be faster then the other ones floating around. It's also more concise the code is : int computeFib(int n) { int t = 1; int result = 0; while(n--) { result = t - result; t = t + result; } return result; }