Lazy Fibonacci Sequence in Ruby

Question

Coming from Python if I wanted to create an iterative lazy Fibonacci sequence, I could do something like this:

def fib():
    a = 1
    b = 2
    yield a
    yield b
    while True:
        yield a + b
        tmp = a
        a = b
        b = tmp + b

Grabbing next(fib) will give me the next element in the sequence by simply adding the previous two elements, so if I want to get the first 1000 Fibonacci elements, I can do that quickly:

fib = fib()
for i in range(0,1000):
    print(next(fib))

If I try to reproduce that in Ruby with an Enumerator, it quickly chokes, recalculating the entire sequence each time we call fib.next():

def fib()
    Enumerator.new do |yielder|
        yielder << 1 << 2
        fib.lazy.zip(fib.lazy.drop(1)).each do |a,b|
            yielder << a + b
        end
    end
end

I found another SO post on how to fix a recursive fibonacci with memoization in Ruby, but I am curious, are lazy sequences and generators a thing in Ruby?

The documentation for Enumerator.new shows how to create an enumerator for Fibonacci numbers. — Stefan
– Stefan, Commented Jan 29, 2018 at 8:08

Stefan Pochmann · Accepted Answer · 2018-01-28 23:42:37Z

4

Don't use recursive enumerators but do it like in Python? With a loop?

def fib()
  Enumerator.new do |yielder|
    a, b = 1, 2
    yielder << a << b
    loop do
      a, b = b, a + b
      yielder << b
    end
  end
end

What you did there in Ruby looks in Python like this:

def fib():
    yield from (1, 2)
    for a, b in zip(fib(), islice(fib(), 1, None)):
        yield a + b

That's slow as well.

Btw, worse than the exponential time is the exponential amount of memory. That recursive Python version crashes for me when trying to compute the 32nd Fibonacci number. At that point I already have almost 4 million generators running. And your Ruby version crashes for me when trying to compute the 20th Fibonacci number, with error can't create fiber (FiberError). At that point I have almost 12000 fibers running.

edited Jan 28, 2018 at 23:42

answered Jan 28, 2018 at 22:56

Stefan Pochmann

29k9 gold badges48 silver badges117 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Chris Over a year ago

Thanks, thats what I get for not understanding Ruby!

Cary Swoveland Over a year ago

In case it's not evident,

enum = fib #=> #<Enumerator: #<Enumerator::Generator:0x000000011dd4f8>:each>; enum.next #=> 1; enum.next #=> 2; enum.next #=> 3; enum.next #=> 5; enum.next #=> 8

and so on.

Collectives™ on Stack Overflow

Lazy Fibonacci Sequence in Ruby

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related