# Splitting a multiplication into multiple smaller steps, reaching the same result

Suppose I have a number, x, which should be doubled every second.

If one had a function which is called exactly once every second, the solution would be simple: All you would have to do was multiplying x by 2.

What, however, can you do to achieve the same results when working not in one-second but very tiny steps?

The target function should, given a small delta time value, still multiply x by 2 every second.

An example:

1. x == 3

2. Apply the function every millisecond for one second, therefore passing 1/1000 as parameter to it

3. Now x == 6

• How can I solve this problem?
-
The function should multiply by $2^{1/1000}$ (the 1000th root of 2). – Florian Jul 25 '11 at 12:42
@Florian, that's certainly the right answer from the point of view of pure mathematics, but I suspect that if you tried to implement it in floating point, it wouldn't do what you want it to do. – Gerry Myerson Jul 25 '11 at 12:47
Perhaps this isn't quite what you want, but... have the function store an internal counter. If the counter is less than 1000, the function returns its input. If the counter equals 1000, then the function sets the counter to 0 and returns twice its input. – Chris Taylor Jul 25 '11 at 12:59

You want a function of time that multiplies by a fixed coefficient every $\delta$ time step, and which doubles every second. In other words, $x(t+\delta) = a x(t)$. Assuming $\delta = 1/n \text{ sec}$ for some integer $n$, you get $x(t+1)=x(t+n\delta) = a^nx(t)$, and hence you have to solve $a^n=2$, which results in $a=2^{1/n}$.

The only problem is that the smaller you make $\delta = 1/n$, the faster this procedure will accumulate error from what you would get just multiplying by $2$ every second, though I can't say off the top of my head whether or not the deviation is negligible for your purposes. (You wouldn't have to worry at all though if you didn't bother with successive iteration and simply calculated the value of $x(t)$ explicitly as $2^tx(0)$ - accurate and much less resource-intensive.)

-

The mathematically correct answer has been given a couple of times, so allow me to suggest another method that produces similar results without accumulating error.

Create an array $A$ whose indexes range from $A[0]$ to some big number—preferably, a power of two, like $A[1024]$. Set $A[0] = 1$ and $A[1024] = 2$. Now, to calculate the values in between, find the midpoint of this array ($A[512]$) and set it to the geometric mean of $A[0]$ and $A[1024]$; that is, $\sqrt{A[0] \cdot A[1024]} = \sqrt{2}$. Again, find the midpoint of two numbers and take their geometric mean, so that, for example:

$$\begin{array}\\A[256] = \sqrt{A[0] \cdot A[512]}\\ A[384] = \sqrt{A[256] \cdot A[512]}\\ A[448] = \sqrt{A[384] \cdot A[512]}\\ A[416] = \sqrt{A[384] \cdot A[448]}\end{array}$$

And so on. After you've calculated this array, your "slow doubling" function can grab successive values out of this array, since those values gradually increase from 1 to 2.

-
You need an internal counter to implement this. On the other hand, if you can use an internal counter, you actually do not need this array: just double the number once in 1000 times, and do nothing for the rest. – Tsuyoshi Ito Jul 25 '11 at 15:27

You do not say if the the function can use an internal counter, nor the desired intermediate results. Moreover you did not even specify which set x belongs to: integers? rationals? complex numbers?

If x is a real number and you want a linear function xi+1 <- f(xi), of course the answer is: use A radix of 2. (There can be two of them if the number of steps is even, or plenty of them if you work on complex numbers, or ...)

On the other side, if you do not necessarily need a linear function, there are lots of awful tricks to obtain function giving random-looking results but ensuring fn(x) = 2x.

A simple example working with small integers (but this is linear in the GF) is the following:

x <- (x*11) % 2601127

i.e. multiply by 11 modulo 2601127. Iterate the function above 1000 times and it will double the initial (integer and smaller than 1300000) value.

-