How to combine two generators in a non-trivial way

Question

I have a generator which produces all positive integers that are powers of 2, and another which produces all integers that are powers of 3. I now need to use those to produce integers of the form 2^i*3^j where i,j >=0,0 in the increasing order.

The point of using generators is to reduce memory consumption, I think. I have been trying to do this for a while now to no avail. Please help out.

Answer 1

Using a self-reading stream

You can solve this using a self-read stream:

   -----------        -----------
   |  pow 2  |------->|         |
   -----------        |         |
                      |  merge  |-------+------------>
   -----------        |         |       |
.->|   x 3   |------->|         |       |
|  -----------        -----------       |
\_______________________________________/

The first stream produces the powers of two, while the second one ensures all the generated numbers are multiplied by 3 and reinjected into the output. The merge operator ensures that the output is sorted.

Note that we must "seed" the output stream with 1, or the first element will try to produce itself when evaluated.

Here is the code:

(require srfi/41)

(define (merge s1 s2)
  (stream-match s1 ((x . xs)
    (stream-match s2 ((y . ys)
      (if (< x y)
        (stream-cons x (merge xs s2))
        (stream-cons y (merge ys s1))))))))

(define (the-stream)
  (letrec ((s
    (stream-cons 1 (merge (stream-map     (lambda (x) (* 3 x)) s)
                          (stream-iterate (lambda (x) (* 2 x)) 2)))))
  s))

It's quite simple and fast compared to my other proposal, because it uses arithmetic properties of the problem besides monotonicity. I'm wrong, it can be generalized just as well (upcoming)

$ mzscheme -f feedback.scm -e '(display (stream->list (stream-take 20 (the-stream))))'
(1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96)

$ time mzscheme -f feedback.scm -e '(display (stream-ref (the-stream) 10000))'
161968247347450370721577384417107686788864605658546176
real    0m1.746s
user    0m1.344s
sys     0m0.156s

Using generators and a queue

We can also implement this with python's generators, but we need to use a queue to store the numbers waiting in the feedback loop:

# Merge the output of two generators
def merge(g1, g2):
    v1 = g1.next()
    v2 = g2.next()
    while 1:
        if v1 < v2:
            yield v1
            v1 = g1.next()
        else:
            yield v2
            v2 = g2.next()

# Generates the powers of 2, starting with n
def pow2(n):
    while 1: yield n; n *= 2

# Generates values shifted from the given 'q' and multiplied by 3
def mul3(q):
    while 1: yield q.pop(0) * 3

# The generator we want
def pow23():
    q = []
    v = 1
    g = merge(pow2(2), mul3(q))
    while 1:
        yield v
        q.append(v)
        v = g.next()

g23 = pow23()
for i in range(10000): g23.next()
print g23.next()

This is somewhat less elegant (IMHO), but the generators are much more lightweight:

$ time python feedback.py 
161968247347450370721577384417107686788864605658546176
real    0m0.150s
user    0m0.112s
sys     0m0.012s

For what is worth, I have done a scheme implementation (using closures as generators) which shows roughly the same performance.