Okay you fucking neets, it's time for a programming challenge

Okay you fucking neets, it's time for a programming challenge.

Write a program to output the 100,000th fibonacci number in under 10 seconds.

Other urls found in this thread:

play.rust-lang.org/?gist=dd1c3b00d0e52b905d2a36cde7aebc0f&version=stable&mode=release
play.rust-lang.org/?gist=90a878d5f01c8faf33b9490b812ca63f
twitter.com/SFWRedditImages

>int main() {
> return [insert 100,000th fib number]
> }

fine I'll start

-module(fibonacci_memo).
-export([fib/1]).

fib(N) ->
case ets:info(fib_memo) of
undefined ->
ets:new(fib_memo, [named_table]),
ets:insert_new(fib_memo, {0,0}),
ets:insert_new(fib_memo, {1,1});
_ -> ok
end,
fibonacci(N).

fibonacci(N) ->
case ets:lookup(fib_memo, N) of
[] ->
FibNum = fibonacci(N-1) + fibonacci(N-2),
ets:insert_new(fib_memo, {N, FibNum}),
FibNum;
[{_, Value}] ->
Value
end.

Ah, I see you are a man of culture as well

best by test

You motherf..

Here is my Scheme solution, it gives you fib(23000) almost instantly, but can't calculate fib(25000) because the number is too large.

Still I found fib(23000) to be quite a big number..
>pic related

(define (fibonacci nr)
(define (fib counter nr1 nr2)
(if (= 0 counter)
nr2
(fib (- counter 1) nr2 (+ nr1 nr2))))
(fib nr 0 1))

>can't even get up to 25k

I know you're meming, but it still pisses me off.

It's not like the machine crashes, but the result is simply "+Inf".
Would be intersting to compare the result of Erlang, Haskell or CommonLisp here..

so basically you failed the challenge

rethink your algorithm and why it takes so long to compute, or look at my erlang solution above.

>rethink your algorithm and why it takes so long to compute, or look at my erlang solution above.

I think you should re-read my previous post.
As I wrote before my algorithm gives you the result almost instantly (< 1 second).
It's tail recursive and gets optimized to a simple addition.


It's more an issue of the highest displayable value.

f i = snd $ iterate (\(x,y) -> (y, x+y)) (0,1) !! i


'f 100000' calculates the 100,000th fibonacci number.

(cont.)

OK, from what I wrote before it's not clear that the problem is not about computing time, but about the size of the number itself.

I also don't think CL has this problems, maybe it's just my scheme compiler..

But how long does it take?

I can also write a ruby solution one-liner that takes 200 years to finish..

On my Dell Optiplex 7040 with an Intel 6400 and no optimizations enabled during the compilation.

real 0m0.318s
user 0m0.292s
sys 0m0.008s

but im a neet... i dont understand any of this.

Please show me that ruby one-line though.

I'm wondering if matrix in c++ would do a job
Probably yeah, but I'm too lazy to write it

shiiet even binets formula hardly works

extern crate num_bigint;
extern crate num_traits;

use num_bigint::BigUint;
use num_traits::{Zero, One};

fn main() {
let instant = std::time::Instant::now();
let mut a = BigUint::zero();
let mut b = BigUint::one();

for _ in 1..100_000 {
let tmp = a + &b;
a = std::mem::replace(&mut b, tmp);
}

println!("{}\n{:?} ms", b, (instant.elapsed() * 1000).as_secs());
}
play.rust-lang.org/?gist=dd1c3b00d0e52b905d2a36cde7aebc0f&version=stable&mode=release
115 ms

Runtime is under 10 seconds, or development?

>100_000
For what purpose? Why not just a 100000?

Not the rusty but you can write _ inside numbers to make the numbers easier to read, you can't really write a comma there or it would fuck up.
Personally I have a hard time differentiating 100000 and 1000000 just by a glance.

I knew there was some kind of formula for this but forgot the name

yeah the floating point multiplication looks like it would kill the answer

>ITT retards doing a retard's homework

If OP wanted his homework done he could just google it though. This is one of the things with a billion solutions readily available on Google already.

>ets:info(fib_memo)

>using a global variable

pass around the memo results you fucking pleb

>implying I didn't already post my solution above

here's a (you) for you

>those hipsters with built-in "big integer" types
back in time we had only arrays of digits

Agreed.
fn main() {
let instant = std::time::Instant::now();

let mut a = vec!(0);
let mut b = vec!(1);

for _ in 2..100_000 {
let tmp = add(&b, &a);
a = b;
b = tmp;
}

println!("{:?}\n{} ms", b, (instant.elapsed() * 1000).as_secs());
}

fn add(a: &[u32], b: &[u32]) -> Vec {
debug_assert!(a.len() >= b.len());

let mut vec = vec!(0; a.len() + 1);
let mut i = 0;
let mut carry = 0;

while i < b.len() {
carry += a[i] as u64 + b[i] as u64;
vec[i] = carry as u32;
carry >>= 32;
i += 1;
}

while carry != 0 {
carry += *a.get(i).unwrap_or(&0) as u64;
vec[i] = carry as u32;
carry >>= 32;
i += 1;
}

if vec[vec.len() - 1] == 0 {
vec.pop();
}

vec
}
play.rust-lang.org/?gist=90a878d5f01c8faf33b9490b812ca63f
165 ms

get out

Triggered anti Rust shill detected

>these results

You need to specify what a Fibonacci number is.

It is quite different to say
F(0) = 0, F(1) = 1, and F(2) = 1
versus
F(1) = 0, F(2) = 1, and F(3) = 1

It is obviously the first. The second is retarded. Learn to math.

I fail to see the connection between any of those tans and their assigned languages
Haskell is holding an art sketchpad for fucks sake

Looks good to me, I don't expect Haskell to get any work done.

Fpbp

Pajeetech 9000
public static BigInteger fib(long n) {
BigInteger f1 = BigInteger.ZERO;
BigInteger f2 = BigInteger.ONE;

for(long i = 2; i < n; i++) {
BigInteger temp = f2;
f2 = f2.add(f1);
f1 = temp;
}

return f1.add(f2);
}

236ms

#include
int main()
{
int i, n;
double fib[3] = {0., 1., 0.};

for (n = 0; n < 100000; ++n)
{
i = (i + 1) % 3;
fib[i] = fib[(i + 1) % 3] + fib[(i + 2) % 3];
}

printf("%f\n", fib[i]);
}

Oops, forgot to initialize i to 1 and n is off by one or two.

pajeet my son, for not using recursion, you are going to the designated shitting street in hell

in J:
fib=: 3 : 0
2&{@((],+/)@(1&{,2&{)^:y) 0 0x 1x
)


Avg time taken for fib 100000x on my iPhone: 3.0767

doesnt this depend on your computer? how is this a challenge?

Most interpreters don't account for tail recursive optimization, the stack would blow up.

how do you format code?

Fibonacci isn't tail recursive

This might work for this particular example, but keep in mind double cannot precisely represent integers over 10^52 (which is why node.js sucks ass) so you're playing with fire. Proper implementation would use some sort of bigint.

I have an implementation in Clojure

(defn fib [n]
(loop [ret 1M prevret 0M i 0]
(if (= i n)
ret
(if (< i 2)
(recur (inc prevret) 1M (inc i))
(recur (+ ret prevret) ret (inc i))))))


206ms, which compare to rust's 165 isnt even half bad.

>This might work for this particular example,
That's what OP asked for. Anything else is just overengineering, which is an antipattern you should try to avoid.

First of all, representing large integer number in the proper format isn't overengineering you smug C weenie.
And secondly I checked. It doesn't even work. I get a NaN. It's far larger than double can represent.

Implementation details.

Doesn't matter if it isn't, interpreters can make pretty much any recursive function tail recursive.

Are you retarded?

If you don't know Fibonacci then you're a brainlet but if you are to retarded to google it if you don't know this you truly should just kill yourself, or go back to

What esoteric programming language is this?

Look at all these imperativelets.

fibo :: Integer -> Integer
fibo 0 = 0
fibo 1 = 1
fibo n = fibo (n-1) + fibo (n-2)

100,000 is low enough that the naive way gives a result in a fraction of a second, this isn't even a challenge.
def fib(n):
p = 0
q = 1
for x in xrange(n):
p,q = q,p+q
return p

print(fib(100000))