How to compute an endless repeating decimal times a single-digit constant in any base.

This is related to my earlier post I began talking about most-significant-digit first arithmetic on infinite decimal expansions of real numbers. As a step toward multiplication I now consider multiplying a number by a single digit.

Reducing to Earlier Problem

I’ll still assume base b, a functions x which returns digits in decreasing order, a single digit y, and that all that is needed is to output digits in decreasing order. I’ll also assume a pair of single-digit multiplication functions: “‍high‍” gives the 10s digit and “‍low‍” the 1s digit.

Define two new functions, h() = high( x(), y ) and l() = low( x(), y ) except that l returns a 0 the first time it is called. Then the single-digit multiplication is the same as adding h and l.

O(n²) Multiplication

Let’s suppose we’ve encapsulated the outline from the previous section as a first-order function m : ((∅ → D) × D) → (∅ → D), where D = {0, 1, …, b – 1}. Assume we also have addition as a first-order function, a : ((∅ → D) × (∅ → D)) → (∅ → D). Then the following process implements multiplication at the expense of O(n²) space and time per digit of output produced.

This approach is as efficient in time as traditional long multiplication, but requires more space.

Toward Lower-Space Multiplication

To compute the nth output bit depends on the sum of the 1s digits of n single-digit multiplications. The carry created there can thus reach as high as (n – 1) n.