2
$\begingroup$

You'll find in the wikipedia Logarithm article a section called Feynman's algorithm.

The paragraph makes claims about uniqueness that, when interpreted mathematically, is incorrect; see this math.stackexchange post,

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

But there can be little doubt that the algorithm work:

We define for $n \ge 1$

$$\tag 1 H_n = \frac{1}{2^n}$$

Let $x$ be a real number between $1$ and $2$ and set $P_0 = 1$

Let $P_n$ be recursively defined. If $P_n * (1 + H_{n+1}) \gt x$ set

$\tag 2 P_{n+1} = P_n$

Else set

$\tag 3 P_{n+1} = P_n * (1 + H_{n+1})$

Claim; The monotone increasing sequence $P_n$ converges to $x$.

Provide a proof that this is true.

My Work

We know that the bounded sequence converges, and by construction it looks like it is doing everything it can to 'get to $x$', but this is not the usual binary subdivision of intervals that is easy to work with.

When an update occurs at $n+1$ we get $P_{n+1} = P_n + H_{n+1} * P_n$. So we 'add in' the new term $H_{n+1}$ and then $H_{n+1}$ applied to other terms 'shifts them down' into lower order terms. It might be a matter of solving equations along with each step of the algorithm, but it isn't easy to see how we are guaranteed to build $x$ that has the form,

$\tag 4 x = 1 + \sum_{k=1}^\infty b_k H_k \; \text{ with } b_k \in \{0,1\}$

Also, I searched for a proof of this but couldn't find one. So any comments with links would be much appreciated.

$\endgroup$
1
$\begingroup$

Let $y$ be the limit of the $P_n$ and suppose for a contradiction that $y<x$. There is a minimal $m$ such that $y(1+H_m)<x$.

Then $1+H_m$ must be one of the terms in the product defining $y$, for the sequence of $P_n$ is increasing and so $P_{m-1}(1+H_m) \leq y(1+H_m) < x$. Similarly every $1+H_{m+k}$ for $k\geq 0$ is a factor in $y$, and $$ y = (1+a_1 2^{-1})(1+a_2 2^{-2})\cdots (1+a_{m-1}2^{-(m-1)}) (1+2^{-m})(1+2^{-m-1})(1+2^{-m-2})\cdots$$ where each $a_i$ is 0 or 1. Now $a_{m-1}$ might not be zero, but there is a biggest $r$ such that $a_{r-1}=0$ (at least one must be zero since $\prod_{k=1}^\infty (1+2^{-k}) >2 \geq x$) and we have $$y = P_{r-2} (1+2^{-r})(1+2^{-r-1})\cdots$$ Note that $$ 1+2^{-r+1} < (1+2^{-r})(1+2^{-r-1})\cdots$$ since the rhs is greater than $1+ 2^{-r}+2^{-r-1}+2^{-r-2}+\cdots = 1+2^{-r+1}$. That means $P_{r-2} (1+H_{r-1}) < y < x$, contradicting $a_{r-1}=0$

$\endgroup$
  • $\begingroup$ Really cool that $\prod_{k=1}^\infty (1+2^{-k}) >2$. Too bad it is not equal to $e$. Hmm, kinda makes you think that looking at $\lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{n}$ might be fun! $\endgroup$ – CopyPasteIt Dec 14 '18 at 14:46
  • $\begingroup$ To solve this it appears necessary to have two hats on - one looking at the sequence and the other the 'limit of algebraic expressions'. $\endgroup$ – CopyPasteIt Dec 14 '18 at 14:55
  • 1
    $\begingroup$ @CopyPasteIt I guess so! The value of that infinite product (which is 2.384231029031371724149899288678397238771619516508433457692...) is related to a q-Pochhammer symbol, you can read about it here mathworld.wolfram.com/q-PochhammerSymbol.html $\endgroup$ – Matthew Towers Dec 14 '18 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.