Created
April 2, 2022 16:32
-
-
Save djuber/1d2fb541537d98f813a088dff365f300 to your computer and use it in GitHub Desktop.
implement fibonacci numbers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# this is constant space, linear time, no memoization. | |
def fib(n) | |
counter, current, previous = 0, 0, 1 | |
while counter < n | |
counter, current, previous = counter + 1, current + previous, current | |
end | |
current | |
end | |
# linear time the first time (for fib(n)) and constant time for subsequent access. | |
# linear heap space (storing all the fib(n) up to a value) for the memoization | |
# but - because it's recursive still, you have linear stack space as well during computation | |
@fibs = [0, 1] | |
def fibm(n) | |
unless @fibs.size > n | |
@fibs.push(fibm(n-1) + fibm(n-2)) | |
end | |
@fibs[n] | |
end | |
# can we merge these? | |
# 1: redefine our linear fib method to build from given position and return the next n - counter values | |
def fibb(n, counter=0, current=0, previous=1) | |
# fib builder - generate an array of fibonacci numbers using the same process, but from given position | |
fibs = [] | |
while counter <= n | |
counter, current, previous = counter + 1, current + previous, current | |
fibs.push(current) | |
end | |
fibs | |
end | |
# leverage that to merge them - build an array of missing values from the array of known values rather than ab initio | |
def fibc(n) | |
# @fibs.size should be at 1 greater than n before reading @fibs[n] | |
if n >= @fibs.size | |
# append new numbers to existing array | |
@fibs = @fibs + fibb(n, @fibs.size, @fibs[-1], @fibs[-2]) | |
end | |
@fibs[n] | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
of course, there's the version that's not linear time, used as a straw man in freshman computer courses to discuss recursion and memoization and programming techniques to avoid this problem. It has the benefit of looking just like the definition given:
but lets assume we're past that. This answers badfib(10) fine, don't call badfib(100) if you're in an hurry. On my machine badfib(30) is visibly delayed (Benchmark.measure gives is 200ms time), badfib(40) takes 17s, badfib(41) takes 27s, badfib(42) takes 45s, badfib(43) takes 72s, and it continues growing, effectively in line with the size of the result, since the same process is unfolding: time to compute badfib(n+1) is time to compute badfib(n) + time to compute badfib(n-1), as we recalculate completely all prior vales.
Using a smaller range to illustrate the additive nature of the time: