TAOCP 5.4.6 Exercise 1

Section 5.4.6: Practical Considerations for Tape Merging

Exercise 1. [18] [18] Give a formula for the exact number of characters per tape, when every block on the tape contains n characters. Assume that the tape could hold exactly 23000000 characters if there were no interblock gaps.

Verified: no
Solve time: 1m54s

Let $L = 23{,}000{,}000$. This is the number of character positions on the tape if there were no interblock gaps.

Assume the tape is partitioned into $K$ blocks, each block containing exactly $n$ characters. Between any two consecutive blocks there is one interblock gap, and each gap occupies one character position on the tape.

Counting occupied positions

With $K$ blocks, the number of data characters is

$$ Kn. $$

The number of interblock gaps is $K - 1$, so the number of positions consumed by gaps is

$$ K - 1. $$

Hence the total number of tape positions used is

$$ Kn + (K - 1). $$

This must fit within the available tape length $L$, so

$$ Kn + (K - 1) \le L. $$

Solving for $K$

Rewriting,

$$ Kn + K - 1 \le L, $$

$$ K(n+1) \le L + 1. $$

Thus the maximum possible number of blocks is

$$ K = \left\lfloor \frac{L+1}{n+1} \right\rfloor. $$

Characters per tape

The number of actual data characters per tape is $Kn$. Substituting the value of $K$,

$$ \text{characters per tape} = n \left\lfloor \frac{L+1}{n+1} \right\rfloor. $$

Final formula

With $L = 23{,}000{,}000$,

$$ \boxed{\text{characters per tape} = n \left\lfloor \frac{23{,}000{,}000 + 1}{n+1} \right\rfloor }. $$