# Feynman's Algorithm for computing a logarithm of a number in [1,2]

I came upon the following quote concerning Feynman (the entire essay this is from can be found here):

Consider the problem of finding the logarithm of a fractional number between 1.0 and 2.0 (the algorithm can be generalized without too much difficulty). Feynman observed that any such number can be uniquely represented as a product of numbers of the form $1 + 2^{-k}$, where $k$ is an integer. Testing each of these factors in a binary number representation is simply a matter of a shift and a subtraction. Once the factors are determined, the logarithm can be computed by adding together the precomputed logarithms of the factors. The algorithm fit especially well on the Connection Machine, since the small table of the logarithms of $1 + 2^{-k}$ could be shared by all the processors. The entire computation took less time than division.

I've given this half a thought and searched a little online, and by basically doing a "binary search" algorithm, one can determine what a set of factors are. See this question on another SE site. However, I am not convinced the factorization is unique since I can't think of an argument. (As an aside, the binary search method doesn't seem the most elegant way to compute the factors.)

So my question is more precisely the following. For ${\bf a} = (a_1, a_2, \dots ) \in \{0,1\}^{{\bf N}}$, show that each number $x \in (1,2]$ is uniquely represented by a certain $\bf{a}$ such that $$x = \prod_{k=1}^\infty (1+a_k 2^{-k}).$$

I know $$\prod_{k=1}^\infty (1+a_k 2^{-k}) = 1 + \sum_{k=1}^\infty \left(a_k + \sum_{1\leq i<j,i+j=k} a_i a_j \right) 2^{-k} = 1 + \sum_{k=1}^\infty b_k 2^{-k}$$ where $b_k$ are the binary digits of $x$, but this doesn't give me much insight.

• @littleO, see the link to the essay for all the context I know. It was related to a startup company trying to do parallel computing. In that case it'd be convenient to compute $\log(1+a_k 2^{-k})$ and then multiply together. – abnry Jul 27 '14 at 3:22
• This feels like the sort of thing someone engineering a slide rule would know. – Semiclassical Jul 27 '14 at 3:37
• Clarification: Does 'uniquely represented' require that the number have a finite number of 'digits'? If not, then I think I see an easy counterexample. – Semiclassical Jul 27 '14 at 3:53
• @semiclassical A finite number of digits is not a requirement. At any rate, whatever makes it work, if possible, is what is meant. – abnry Jul 27 '14 at 3:56
• Feynman is god? – ClassicStyle Jul 27 '14 at 4:39

The representation cannot be unique as stated. Consider $1+\dfrac{1}{2}$, which has the obvious representation $(1,0,0,\ldots)$. But $(1+\dfrac{1}{2})/(1+\dfrac{1}{4})=1.2<1+\dfrac{1}{4}$, and so will have a representation of the form $(0,0,1,\ldots)$. So $1+\dfrac{1}{2}$ will also have a representation $$(1+\dfrac{1}{4})\cdot (0,0,1,\ldots)=(0,1,1,\ldots)$$
The point is similar to the familiar observation that $1.=0.\overline{9}$ in decimal. Consequently no real number representation can be unique unless additional restrictions are imposed (indeed, that's an important technical point in Cantor's diagonal argument). So I think the more interesting question is what conditions must be imposed to get a unique Feynman representation...
• @nayrb: Well, presumably you can get a unique representation for some $a$ by always using as large of factors as possible at each step. That'd prevent using the factor of $1+\frac{1}{4}$ being used instead of $1+\frac{1}{2}$ (which is again similar to agreeing not to use infinite strings of 9's while doing the diagonal argument.) – Semiclassical Jul 27 '14 at 17:52