I want to like python, I really do, but this shit fucking pisses me off:

I want to like python, I really do, but this shit fucking pisses me off:
def fib(n):
return 1 if n < 2 else fib(n - 1) + fib(n - 2)

fib(50)


LITERALLY NOT DONE AFTER 5 MINUTES

Other urls found in this thread:

stackoverflow.com/a/23624061/1781026
youtube.com/watch?v=eao0Y4SJQjo
twitter.com/SFWRedditVideos

>I want to like python, but It cant run my unoptimized piece of shit recursive code
ok.

...

true

stackoverflow.com/a/23624061/1781026

Epic bait
Keep track of your previous answers so you're not constantly recalculating the same thing

dumb frogposter

...

...

I know op wrote shitty code but slow languages are real. I once rewrote a nodeJS script that took over two minutes in c#. I now need .7 seconds for it.

Your computer sucks, time to upgrade.

stop using recursion it's slow and sucks

But there are times when recursion is necessary, aren't there.

> nodeJS script that took over two minutes in c#
> Interpreted vs. compiled langiages
Are you for real right now?

When you're programming in Haskell.

tail recursion

javascript on node is jited. so is C#

Maybe you should consider a non shit language, OP. Here is D, computing the sum of the first 1000th Fibonacci numbers in O(1) time

Sum of the first 1 Millionth Fib sequence.
That took a lot of time.

B-But user, this code that I made runs in two seconds!

Do it in pypy. with OP's function and calculate the sum of first 1000 items

I like frogposters

js is jited almost on every platform. node uses v8 and so does chrome based browsers.

Not him, but doing this.
It's slow, I'm compiling stuff in the meantime though

I'm currently using my implementation to do what this user did. It's been going for over 5 minutes.

Impressive

youtube.com/watch?v=eao0Y4SJQjo

D fag out

Do it properly, for example like here. port to python yourself
let φ=(1 + Math.sqrt(5))/2
new Array(50).fill().map((a,b) => Math.floor((Math.pow(φ, b) - Math.pow(1 - φ, b))/Math.sqrt(5)))

>Are you for real right now?
I'm saying that interpreted langs are slow shit (at least relative to compiled/ good JIT), anything wrong with that?

what kind of dumbass uses double recursion?
just use a doubling method, like the 2x2 matrix formulation of the Fibonacci numbers, so that the algorithm runs in linear time.

You should not be allowed near a compiler nor an interpreter.

>CTRL+F memoization
>no results
Bunch of plebs.

just make a tail recursion system that uses the variables o, e and n. You want to find the nth fibonacci number, so, you can create some if statements, where, if n is 1, then you take the current value of e, and add it to o. If n is bigger than one, then you check if n is even or odd. If n is odd, then, you tail recurse, but, with o replaced with o+e, e replaced with e, n replaced with n-1. When n is even, then, you tail recurse with the arguments with o replaced with o, e replaced with e*e, n replaced with n/2. Because you are looking for fibonacci numbers, you will put the initial value of o to be [0,0;0,0], and the initial value of e to be [1,1;1,0].

the meme haskell way:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

(the n = 1 case gets you the 2x2 matrix containing the fibonacci number you want)
This algorithm works because it creates a correspondence between the binary representation of n, and the doubling method for the fibonacci numbers. You are looking for [1,1;1,0]^n, but, by the addition to multiplication property of exponents, that is just the product of several 2x2 matricies, each of which is [1,1;1,0] to the power of a power of 2. When you check if n is even, or odd for the first time, you are checking to see if you need 1 copy of [1,1;1,0] in the product, or 0 copies. If the result was yes, then the next recursion just steps e up. If the answer was no, then you immediately step e up. When e gets stepped up, n gets divided by 2, so, the next time you ask if n is even or odd, you are not checking the number of copies of [1,1;1,0] in the product, you are checking the number of copies of [1,1;1,0]^2 in the product.

how is it O(1) if its runtime is affected greatly by n?

specifically you can solve for a fibonacci number in close to O(1) time if you have a type that can handle the floating point precision by multiplying out the golden ratio.

v=[1,1,2]
for _ in range(50-2): v[2] = v[0]+v[1]; v[0]=v[1]; v[1]=v[2];
print(v[2])

I don't know. Seems pretty fast for me.

CTFE

Honest question OP.
Why don't you just use a clever(er) definition of the fibonacci sequence using the golden ratio, square root of 5 and exponent of n (and rounding down the result)?

It's always gonna be faster for big n.

My man. I love to see OPM memes from Sup Forums.

Now write the Ackermann function in basic

>50 levels of recursion
this has nothing to do with python, you're just sucky

Just playing around. It's pretty fast though.
#!/usr/bin/env ruby
def fibo(n)
fs=[1,1,2]
(n-2).times do
fs.rotate!
fs[2]=fs[0]+fs[1]
end
return fs[[2,n].min]
end
puts fibo(ARGV[0].to_i)

it ain't haskell

probably doesn't optimize for tail recursion

They don't ask you for fries after you already have food on your tray.

Myth busted.

If you read your SICP you would know how to optimize it.

def cached(f):
f.cache = {}
def wrapped(*args):
k = repr(args)
if k not in f.cache:
f.cache[k] = f(*args)
return f.cache[k]
return wrapped

@cached
def fib(n):
return 1 if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(50))


it doesn't take much to make even your shitty recursive version return instantly

Python is a fucking meme language for hipsters. Even I know that.

I keep trying not to like Python, but stuff like this makes it hard.

I really don't understand this meme.
I study physics and use Python for all of my computation. I can whip out working code very quickly and it runs fast enough to not become a problem. Computation time really isn't an issue as long as i dont need to spend a lot of time writing the code.

try writing something more than 100 lines of code. and with multiple people. in different time zones. etc.

Lets see you sum the primes under 2 billion.