The fastest ways to calculate Fibonacci sequence

Question

I have code which created using Python. My problem is time. When the index number is greater than 1000 everything crashed, but I solved this problem. Now, I want to ask you about your answer to this problem

Answer 1

I am not sure if this is the fastest way, but it works with Fibonacci(1000)

https://code.sololearn.com/ca7dpI3umG7y/?ref=app

Answer 2

https://code.sololearn.com/coRxH5i17Moz/?ref=app

I think using dynamic programming will be faster than any normal recursive function..So I think this might be fastest way..

PS: Range for 1000 is very long and I guess c++ doesn't have data type to express these long numbers..

Answer 3

For some reason, I asked myself this same question one night and I decided to tackle the question... and here is what I came up with:

https://code.sololearn.com/c8T4QQnuxep7

Note:
The script starts off asking the user how many fibonacci numbers to print out.

also,

I've seen a few different versions of how to start the fibonacci sequence. I've seen some people start off with a 0 & 1, some start off with a 1 & 1, and some with a 1 & 2.

I went at the problem assuming the first number in the sequence is 0, and the second number is 1, and thats where I ran into problems.

I calculated the next number by adding the previous two numbers in the sequence, but you can't really do that with the first 2 numbers.

Because of this, I just printed a string when displaying the first three numbers and then I started calculating numbers from the fourth number.

You'll see that I assigned NUMA to 1 (the value of the second number), and NUMB to 1 (the value of the third number). This allowed me to make NUMC the sum of NUMB + NUMA.

After I print NUMC on screen, I reassign NUMA to NUMB's value, NUMB to NUMC's value, recalculate NUMC's value, and loop the whole process x amount of times.

I would love to hear thoughts on how I attacked the problem

Answer 4

Jason Bourne your code has a little flaw, this is not the fibonacci series but the powers of 2.
You are not really doing anything with x, you just keep doubling the last value.

But the code itself is quite efficient, you are only using 3 numbers, that does not take a lot of memory. Compared to my code yours is still 50% more, because I only use 2 variables and make 2 assignments in each loop, instead of 3. That's why it might be slightly slower. The walrus does not affect it very much, it only applies to the first two elements anyway.

a = 0
yield a

These two lines can be combined by the walrus like this

yield (a:=0)

So it is just syntax simplification.

Answer 5

Tibor Santa ugh my dumb typo, I had initially used x1 x2 and x3 as variables and when I changed them to x y z I wrote z+=y rather than z+=x, I fixed it now and it works fine. Anyway, I tried running the code for 300,000 for each using time module to measure how long it takes and on average they were pretty similar so i guess that was latency issues before. I'm guessing mine is a bit slower because at high numbers writing x to a 1000+ digit number each iteration wastes a decent amount of time. Also thanks for explaining walrus, I spent 10 minutes searching it on Google and didn't understand a thing, much appreciated.

Answer 6

num = int(input())

def calculate_number(number):
if number <= 1:
return number
else:
return(calculate_number(number-1) + calculate_number(number-2))

for number in range(num):
print(calculate_number(number))

The use of recursive is viable when we tackle this problem.

You can change my for loop to only print the results, which would free a hell of a lot more memory and also would make it faster.

Cheers m8!

Answer 7

@AnonymousGuy

for some reason, your script can only calculate up to the 47th number. Higher, and it screws up.

For example, this is the result if I enter 48:
-1323752223

Answer 8

D. Booey 📜

Range of integer data type is less in c++, it can be extended to some extent by using long or double data type..but I don't think c++ have data type to store very large values like fibbonnaci of 1000...

That's the reason it is not printing values above 47 as you said..

Answer 9

Tibor Santa I saw your code on this post and it worked very well. I made this very simple one https://code.sololearn.com/ch0GbVerg4qe/?ref=app which is essentially 3 assignments and one addition per iteration. But it's still considerably slower than yours (for example mine can't run n=400,000 in Sololearn). I'm very new to coding so I don't know much about code efficiency, is it because of the walrus operation?