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

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

>>61085128
true

>>61085014
https://stackoverflow.com/a/23624061/1781026

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

>>61085014
dumb frogposter

File: 1458202037.jpg (187KB, 1280x800px) Image search: [Google]

187KB, 1280x800px

>>61085128
>>61085486
>>61085628

File: stop_posting.jpg (300KB, 751x558px) Image search: [Google]

300KB, 751x558px

>>61085014

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.

>>61085014
Your computer sucks, time to upgrade.

stop using recursion it's slow and sucks

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

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

>>61087934
When you're programming in Haskell.

tail recursion

>>61087946
javascript on node is jited. so is C#

File: Screenshot.png (165KB, 1920x1080px) Image search: [Google]

165KB, 1920x1080px

>>61085014
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

File: Screenshot.png (137KB, 1920x1080px) Image search: [Google]

137KB, 1920x1080px

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

File: Screenshot from 2017-06-26 11-35-48.png (32KB, 734x489px) Image search: [Google]

32KB, 734x489px

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

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

>>61085014
I like frogposters

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

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

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

File: 1480745330811.png (222KB, 800x800px) Image search: [Google]

222KB, 800x800px

>>61088493
>>61088550
Impressive

https://www.youtube.com/watch?v=eao0Y4SJQjo

File: 1488869296301.png (228KB, 3316x1896px) Image search: [Google]

228KB, 3316x1896px

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)))

>>61087946
>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?

>>61085014
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.

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

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

>>61088721
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].

>>61087986
the meme haskell way:

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

>>61089260
(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.

>>61088493
>>61088550
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.

>>61089564
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.

>>61086651
My man. I love to see OPM memes from /a/.

>>61087916
Now write the Ackermann function in basic

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

File: 12.jpg (817KB, 1247x916px) Image search: [Google]

817KB, 1247x916px

>>61085014
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)

>>61085014

it ain't haskell

probably doesn't optimize for tail recursion

>>61086491
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.

File: Capture.png (13KB, 782x237px) Image search: [Google]

13KB, 782x237px

>>61085014

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

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

>>61093359
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.

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

>>61093946
Lets see you sum the primes under 2 billion.