Infinite Decimals Times a Digit

math# Reducing to Earlier Problem

#
`O`(`n`^{2}) Multiplication

algorithm
# Toward Lower-Space Multiplication

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.

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`.

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`^{2}) space and time
per digit of output produced.

Multiplication

Initialize `g()` = 0;
Repeatedly {
Replace `g` with `a`( `g`, `m`( copy(`x`), `y`() ) );
Call `x`() but ignore the result;
Output `g`()
}

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

To compute the `n`th 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`.

Loading user comment form…

Looking for comments…