We all enjoy showing off how elegant our implementation of the Fibonacci sequence is in Haskell or Scheme or whatever. But, frankly, they suck. Even if you're using tail recursion to avoid fucking up the stack it's still terribly inefficient.
Here is the correct way to implement the Fibonacci sequence (in Scheme): (define (fibonacci x)
(let ((phi (/ (+ 1 (sqrt 5)) 2)))
(+ (/ (+ (expt phi x) (expt (- 1 phi) (- x 2))) (+ (expt phi 2) 1)) (/ (- (expt phi (- x 1)) (* phi (expt (- 1 phi) (- x 2)))) (+ (expt phi 2) 1)))))
Name:
Anonymous2008-04-17 14:01
＿＿＿＿＿＿＿＿＿＿＿＿＿
∧ ∧ ｜ Hello, my name is longcat.
（・∀・） ＜ Please help me get long !!
｜ ｜ ｜＿＿＿＿＿＿＿＿＿＿＿＿＿
⊂ ⊃
｜ ｜
｜ ｜
｜ ｜
｜ ｜
｜ ｜
｜ ｜
｜ ｜
｜ ｜
｜ ｜
｜ ｜
*** - floating point underflow
The following restarts are available:
ABORT :R1 ABORT
Break 1 [8]>
Oh, my. Here's how I would implement a function with identical output and range in C: float fibonacci(int n) {
return fibonacci_table[n];
}
Name:
Anonymous2008-04-17 14:37
>>11 *Main> f 1474
4.992254605478015e307
*Main> f 1475
Infinity
>>14
In guile the results were much more accurate (but it says that large fibonacci numbers are infinite), differing implementations i guess.
The math is right, and you can port that whereever for a O(1) algorithm without a lookup table.
Name:
Anonymous2008-04-17 16:24
I want to see fibs in Croma LISP.
Name:
Anonymous2008-04-17 18:23
>>18
it's only O(1) if you use a lookup table for sqrt and expt.
Name:
Anonymous2008-04-17 20:23
>>18
You can port that whereever you have floating point maths, at least. What's wrong with lookup tables anyway? Given the limited valid input range, the memory use is neglible, and even if you generate it dynamically, the difference between O(1) vs. O(n) neglible.
>>22,23
An bog-standard iterative fibonacci function written in Python gives accurate results instantly on my machine for n up to about 20000. (After that it still gives accurate results, but there is a noticable delay before printing the answer, probably because of terminal scrolling.)
Given a "O(1)" implementation that only works up to n = 1474 (as tested with guile), I'd say the difference between O(1) and O(n) is pretty darn negligible.
using System;
using System.Collections.Generic;
using RedCorona.Utils;
class Fibonacci{
public static LargeInteger GetFib(long n){
if(n < -4294967295 || n > 4294967295) throw(new System.OverflowException());
double p = Math.Sqrt(5);
bool negative = n < 0;
if(negative) n = -n;
uint e = (uint)n;
LargeInteger res = (1 / Math.Sqrt(5)) * (((LargeInteger)((p + 1) / 2)).Power(e) - ((LargeInteger)(2 / (p + 1))).Power(e) * (2 * -(e % 2)) / 2);
if(negative && n % 2 == 0) res = -res;
string t = res.ToLongString();
int i = t.IndexOf(".");
char r = t[i + 1];
t = t.Substring(0, i).Replace(",", null);
res = LargeInteger.Parse(t);
if(r > '4') res += 1;
return res;
}
public static double GetFibDouble(double n){
double p = Math.Sqrt(5);
bool round = n == Math.Round(n);
double res = (1 / p) * (Math.Pow((p + 1) / 2, n) - Math.Pow(2 / (p + 1), n) * Math.Cos(n * Math.PI));
if(round) res = Math.Round(res);
return res;
}
}
Name:
Anonymous2008-04-18 8:24
def fib():
a,b=0,1
while True:
print a,b,
a,b=a+b,b*2+a
FORCED INDENTATION OF CODE
Name:
Anonymous2008-04-18 10:29
>>32
Enterprise code, ready for deployment any time.
Name:
Anonymous2008-04-18 22:55
Greetings /prog/, here is my FIBONACCI ENTERPRISE EDITION (Fib2EE). It uses the power of [o][b]PARALLEL PROCESSING[/o][/b] to build its lookup table with threads. This will increase the performance by as much as a factor of 4 on the latest desktop machines.
I timed it and it can calculate fib(0)..fib(4500) in 2.918 seconds on my quad core processors.
import java.math.BigInteger;
public class Fibonacci implements javax.ejb.EJBObject {
private static final int TABLE_SIZE = 1024;
private static final BigInteger[] TABLE;
static {
TABLE = new BigInteger[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++) {
final int final_i = i;
new Thread(new Runnable() {
public void run() {
TABLE[final_i] = basefib(final_i);
}
}).run();
}
}
private static BigInteger basefib(int n) {
if (n == 0)
return BigInteger.ZERO;
else if (n == 1)
return BigInteger.ONE;
else {
BigInteger a = BigInteger.ZERO,
b = BigInteger.ONE,
f = BigInteger.ZERO;
for (int i = 0; i < n - 1; i++) {
f = a.add(b);
a = b;
b = f;
}
return f;
}
}
public static BigInteger fib(int n) {
if (0 <= n && n < TABLE_SIZE)
return TABLE[n];
else
return basefib(n);
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
for (int i = 1; i < 4500; i++) {
BigInteger s = fib(i);
}
long delta = System.currentTimeMillis() - start;
System.out.println(delta / 1000.0);
}
}
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy