Chapter 3, Modularity, Objects, and State

Exercise 3.66


First, I shall present the formulae and then try to capture a way to arrive at the formulae.

Let’s say we start from a point (S,T). Then number of steps to arrive at (S+a,T+b) can be given by:

$$ \, steps = \begin{cases} 2^{a+1} - 1 & \text{if $b-a = 0$} \\ 2^{a+1} - 1 + 2^a + 2^{a+1}(b-a-1) & \text{if $b-a \ge 1$} \\ \text{Undefined} & \text{otherwise} \end{cases} \, $$

Let’s first verify it. I generated the following sequence using the code given in book with the starting point (1,1):

index pair index pair
0 (1,1) 16 (2,6)
1 (1,2) 17 (1,10)
2 (2,2) 18 (3,5)
3 (1,3) 19 (1,11)
4 (2,3) 20 (2,7)
5 (1,4) 21 (1,12)
6 (3,3) 22 (4,5)
7 (1,5) 23 (1,13)
8 (2,4) 24 (2,8)
9 (1,6) 25 (1,14)
10 (3,4) 50 (3,9)
11 (1,7) 100 (2,27)
12 (2,5) 157 (1,80)
13 (1,8) 200 (2,52)
14 (4,4) 518 (4,36)
15 (1,9) 1002 (3,128)

Let’s check our formulae on (1,1):

Here a = 0, b = 0, Thus $\, b-a = 0 \,$ , so we apply $\, 2^{a+1}-1 \,$ which gives 1. Since we count from 0, so this is correct(1-1 = 0).

(4,4)

Here, a = 3, b = 3, Thus $\, b-a = 0 \,$ , so we apply $\, 2^{a+1}-1 \,$ which gives 15. Since we count from 0, this is correct(15-1 = 14).

(4,5)

Here, a = 3, b = 4, Thus $\, b-a \ge 1 \,$ , so we apply $\, 2^{a+1} - 1 + 2^a + 2^{a+1}{b-a-1}\,$ which gives 23. Since we count from 0, this is correct(23-1 = 22).

(2,52)

Here, a = 1, b = 51, Thus $\, b-a \ge 1 \,$ , so we apply $\, 2^{a+1} - 1 + 2^a + 2^{a+1}(b-a-1)\,$ which gives 201. Since we count from 0, this is correct(201-1 = 200).

(3,128)

Here, a = 2, b = 127, Thus $\, b-a \ge 1 \,$ , so we apply $\, 2^{a+1} - 1 + 2^a + 2^{a+1}(b-a-1)\,$ which gives 1003. Since we count from 0, this is correct(1003-1 = 1002).


Now, let’s try to construct the farmulae.

There are two ways, one is to generate many pairs and try to check for patterns and come up with farmulae. Another is to start from the algorithm and check how it is generating pairs then come up with the formulae. The former way can not be proved to be correct but the latter way is provably correct.

I first went with first approach and then constructed the formulae with second approach.

Now, let’s start with second approach:

For reference, let’s see the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
(define (interleave s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream (stream-car s1)
                   (interleave s2 (stream-cdr s1)))))

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) (list (stream-car s) x))
                (stream-cdr t))
    (pairs (stream-cdr s) (stream-cdr t)))))

One way to look at it is imagine that every step is a space to be occupied by a pair. Obviously a pair can occupy only one space.

Initially all the spaces are available i.e. (1,2,3 …100, … , …) each space is denoted by a number which represents the number of steps to generate the pair at that step. These spaces are filled in linear order starting from the first space i.e. 1 then next and so on.

Now let’s see the pairs procedure. There are following things that happens when we invoke pairs:

  1. Output a pair containing first element from each stream. This pair occupies the first space available. Let’s call this pair fp(first pair).
  2. Two streams of pairs are created:
    • a stream that combines first element of one stream with every element of other stream. Let’s call this stream sm(stream from map).
    • a stream that combines the rest of the elements(excluding first) of both streams. Let’s call this stream sp(stream from next pairs invocation).
  3. sm and sp are mixed alternatingly with procedure interleave.

Now, we shall see how the spaces are occupied by the streams generated in the above steps.

First let’s assume that at first invocation $\, s_1, s_2, ... s_i, ... \,$ spaces are available.

Then:

  • fp takes the first available space i.e. $\, s_1 \,$.
  • sm and sp takes spaces alternatively. first pair of sm gets $\, s_2 \,$ then first pair of sp gets $\, s_3 \,$ and so on.

Since sp is the stream generated by recursive invocation of pairs, we just need to focus on the spaces which are occupied by sm and sp will be automatically considered because of recursion.

Now, we can see that sm takes $\, s_2, s_4, s_6, .. \,$ or the even spaces from the available spaces.

Let’s take concrete cases:

We start from (S,T), where S is the first element of stream s and T is the first element of stream t(s and t are the streams passed to pairs).

Initially we have the following spaces available: (1,2,3,4,5,….)

First invocation of pairs

  1. fp = (S,T), It occupies space: 1.
  2. First element of sm is (S,T+1) and it occupies the next available space i.e. 2.
  3. Rest of the elements of sm, (S, T+1+x), where x > 1, occupies (4, 6, 8, 10, …**) or 2+2x.

A point to note here is in one invocation first two available spaces go to fp and first element of sm and rest of the spaces which are multiple of 2 will be taken by sm.

Since the second element of sm or the first element in point 3 will be referred later, I am denoting it by lsm2 - second element of sm in previous invocation of pair.

Second invocation of pairs(because of recursive call):

  1. Now fp = (S+1, T+1) and it occupies the first available space. What is the first available space now? 3 it is!

  2. First element of this state sm is (S+1, T+1+1) and it will now occupy the next available space. Clearly this is 5.

    Can we arrive at the above two numbers(3 and 5) algebraically? Sure.

    ( Denoting space(a,b) as the space occupied by pair (a,b). )

    As noted in earlier invocation also, fp and first element of sm or, (S+1, T+1) and (S+1, T+1+1) respectively, will take the next two available spaces from the beginning.

    What are the empty spaces available from the beginning? The spaces left by rest of sm(third point) in previous invocation. We know that in previous invocation, sm left one space empty in every two spaces.

    We can take one empty space on left side of lsm2, or (S, T+1+1), and one on the right side.

    How much we move on the left side or right side to get empty space from the space taken by sm2? Since in last invocation all spaces were contigous, so we need to move only one space left and one space right to get the empty space.

    So, spaces to be taken by fp and first element of sm: lsm2 $\, \pm 1 \,$ = space(S, T+1+1) $\, \pm 1 \,$ = 3 and 5(since lsm2 = 4) respectively.

  3. Rest of the elements of sm, (S+1, T+1+1+x), where x > 1, take the available spaces alternatingly. That is we leave the first available space then occupy the next and then leave the next and occupy the next and so on.

    Since all the multiples of 2 are taken in previous step, how we can leave and occupy alternatingly from the current available spaces? We take even of the even places or every $\, 2+2 = 2^2\,$ place!

    Thus we take space(S+1, T+1+1) + $\, 2^2 x \,$.

    Note, it may seem like 2^2 is also even and we may conflict with the spaces occupied by previous invocation - which wont happen because we are adding space(S+1, T+1+1). For example, we get following spaces occupied: (9, 13, 17, 21, 25, 29, …). Clearly there is no conflict because of our offset.

    Now after this invocation - sm leaves one space empty in every four spaces. In the previous invocation sm left one space empty in every two spaces. It seems we know where it is leading us!

    Again, as in last step lsm2 now denotes the second element of sm which now becomes (S+1, T+1+1+1).

Third invocation of pairs:

  1. fp = (S+2, T+2) and it occupies lsm2 - 2. Why?(answer follows later)
  2. First element of sm = (S+2, T+2+1) takes lsm2 + 2.

    Well, unlike in previous step we added/subtracted 2 instead of 1. The reason is in previous step when lsm2 takes space, the empty space was available after every two space not after every one space!

  3. Rest of elements of sm = (S+2, T+2+1+x) where x > 1. Again we follow the same method, we take available spaces alternatingly. But in last step there is one empty space in every four spaces, so now to leave one and take one alternatingly we need to take spaces in the multiples of $\, 4+4 = 2^3 \,$.

    Thus we take space(S+2, T+2+1) + $\, 2^3 x \,$ .

Fourth invocation

  1. fp=(S+3, T+3) occupies lsm2 - 4.
  2. First element of sm = (S+3, T+3+1) occupies lsm2 + 4.
  3. Rest of elements of sm = (S+3, T+3+1+x) where x>1 occupies (S+3, T+3+1) + $\, 2^3x \,$ .

Can we write it in generic form for (S+a, T+b)?

Yes.

  1. If a = 0 and b = 0, then space(S+a, T+b) = 1.

  2. If a = 0 and b = 1, then space(S+a, T+b) = 2.

  3. If a = b:

    Clearly this is fp and from the above we first need lsm2 which is obviously = (S+a-1, T+a+1).

    Thus space(S+a, T+b) = lsm2 - $\, 2^{a-1} \,$ = space(S+a-1, T+a+1) - $\, 2^{a-1} \,$ .

  4. If b-a = 1:

    Clearly this is first element of sm. Thus the space taken by it is = space(S+a-1, T+a+1) + $\, 2^{a-1} \,$.

  5. If b-a > x:

    This if the rest of elements of sm. Thus the space taken by them is = space(S+a, T+a+1) + $\, 2^{a+1} \,$.

Now we can see that in step 5 we can supply the result of 4. After doing that we will see an expression where we can use step 5. Doing that will lead us to a geometric series.

I am skipping these steps now as this is straight forward. And we get 3 formulaes:

If a = b:

$$ \, 2^{a+1} - 1 \, $$

If b-a = 1:

$\, 2^{a+1} - 1 + 2^a \,$, or $\, 3.2^a - 1 \,$

If b-a > 1:

$\, 2^{a+1} - 1 + 2^a + 2^{a+1}(b-a-1) \,$.

The last two equations can be combined! And we get the same result as shown in the beginning.