patternpythonModerate
The dwindling Fibonacci
Viewed 0 times
thefibonaccidwindling
Problem
I've recently taken a renewed interest in non-standard languages like Brainfuck and TIS-100. I'm currently writing a Fibonacci generator in Brainfuck which differs a bit in approach from the usual generators already around.
Since my current understanding of the language is very limited, the limited debugging capabilities in the average Brainfuck IDE and the fact that I've never written a Fibonacci generator before, I decided to write one in Python first.
The usual Fibonacci generator seems to be recursive. If I understand correctly, mine isn't. Since the goal was to produce a generator which would serve as a blueprint for it's Brainfuck equivalent, I tried writing it as straight-forward as possible.
The straight-forwardness means no fancy stuff. Exception handling is for the weak and it's too short to warrant a function just for the sake of defining a function. If this is to be re-used, the whole thing will turn into a function.
Again, it's a blueprint for an implementation in a language where such constructs don't exist.
It's speed surprised me.
I think this is about as simple and as clear as it gets, but let's see if there is room for improvement anyway.
Since my current understanding of the language is very limited, the limited debugging capabilities in the average Brainfuck IDE and the fact that I've never written a Fibonacci generator before, I decided to write one in Python first.
The usual Fibonacci generator seems to be recursive. If I understand correctly, mine isn't. Since the goal was to produce a generator which would serve as a blueprint for it's Brainfuck equivalent, I tried writing it as straight-forward as possible.
The straight-forwardness means no fancy stuff. Exception handling is for the weak and it's too short to warrant a function just for the sake of defining a function. If this is to be re-used, the whole thing will turn into a function.
Again, it's a blueprint for an implementation in a language where such constructs don't exist.
import sys
HIGHEST_FIBO = int(sys.argv[1])
Fibo = [1, 1, 2]
for i in Fibo:
print i
for i in xrange(HIGHEST_FIBO-len(Fibo)):
Fibo[0] = Fibo[1]
Fibo[1] = Fibo[2]
Fibo[2] = Fibo[0] + Fibo[1]
print Fibo[2]It's speed surprised me.
2000 under 2 seconds, where print is likely the most expensive operation. It should be very memory efficient as well.I think this is about as simple and as clear as it gets, but let's see if there is room for improvement anyway.
Solution
There is indeed room for improvement, however slim it may be.
Get rid of the list
If you want to make it even simpler, there is even a function to compute fibonacci numbers and if you are interested, I leave it up to you to find it.
Before I go, I think I should explain this part which may seem confusing:
This takes advantage of tuple assignment in python. The process begins by creating a tuple of both the left hand side and the right hand side of the expression. Then the right hand side of the expression is evaluated. Then the process of tuple unpacking begins where in each value on the left hand side is assigned to the one on the right.
This simple python trick allows for us to write a one line swap
Get rid of the list
import sys
highest_fibo = int(sys.argv[1])
f1 = 0
f2 = 1
for _ in xrange(highest_fibo):
f1, f2 = f2, f1 + f2
print f2,If you want to make it even simpler, there is even a function to compute fibonacci numbers and if you are interested, I leave it up to you to find it.
Before I go, I think I should explain this part which may seem confusing:
f1, f2 = f2, f1 + f2This takes advantage of tuple assignment in python. The process begins by creating a tuple of both the left hand side and the right hand side of the expression. Then the right hand side of the expression is evaluated. Then the process of tuple unpacking begins where in each value on the left hand side is assigned to the one on the right.
This simple python trick allows for us to write a one line swap
Code Snippets
import sys
highest_fibo = int(sys.argv[1])
f1 = 0
f2 = 1
for _ in xrange(highest_fibo):
f1, f2 = f2, f1 + f2
print f2,f1, f2 = f2, f1 + f2Context
StackExchange Code Review Q#100376, answer score: 11
Revisions (0)
No revisions yet.