7
$\begingroup$

The following quote describes an algorithm invented by Feynman to compute the logarithm of a fractional number (presumably a dyadic one).

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.

Unfortunately, there are many numbers that cannot be represented as advertised above, for example 7/4, 11/8. There must be something wrong with the quote.

What was the algorithm proposed by Feynman ?

|cite|improve this question
$\endgroup$
  • 6
    $\begingroup$ Why do you think that 7/4 can't be represented this way? To me it seems that $7/4 = (1+2^{-1}) \times (1+2^{-3}) \times (1+2^{-5}) \times (1+2^{-8}) \times (1+2^{-10}) \times \ldots$ $\endgroup$ – Jukka Suomela Dec 2 '10 at 11:34
  • $\begingroup$ @Jukka. Thanks, I assumed that there was only a finite number of terms in the expansion. Now it makes sense. But then I don't think you have uniqueness, do you ? Maybe he is restricting to terms of the form (1+2^(-2^k)), this would give a nice algorithm in base 2. Mmh... $\endgroup$ – caroline Dec 2 '10 at 15:34
  • 3
    $\begingroup$ Why isn’t it unique? (Not that I know the proof of uniqueness.) $\endgroup$ – Tsuyoshi Ito Dec 2 '10 at 15:52
6
$\begingroup$

You can multiply $r$ by $(1+2^{-k})$ by adding $r$ to $r$ shifted right by $k$ positions. To find the factors of a number $s$, you can start setting $r:=1$ and for $k=0,1,2,\ldots$, test if $r(1+2^{-k})\leq s$. If the test succeeds, set $r:=r(1+2^{-k})$. Along the way you can calculate $\log s$ by summing $\log 1+2^{-k}$ for every factor found.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ shouldn't the final sum term be $log(1+2^{-k})$, not $log(1+2^{k})$? $\endgroup$ – s8soj3o289 Dec 3 '10 at 8:41
  • $\begingroup$ I realize this answer is quite old, but I'm trying to actually implement this algorithm and can't find much else on it. The part of your answer that confuses me is shouldn't "adding rr to rr shifted right by kk positions" equal $(r + r^{-k})$ not $r(1 + 2^{-k})$? And when using bit-shifting am I correct in thinking the convergent sequence of r are the factors so one must simply map $log$ over them and then sum the results (or vice versa)? $\endgroup$ – Sophia Gold Mar 17 '17 at 21:18
0
$\begingroup$

EDIT: This answer does not in fact seem to reflect the OPs intentions. I moved to delete it, but then read this, Policy on deleting incorrect answers? and decided to bring it back with this notice.

The algorithm below is a correct method for computing the logarithm but in my haste I did not follow through and confirm for myself that it reflected the original request. Tsuyoshi did and noted this issue.

The algorithm is described in detail here:

http://wiki.tcl.tk/15228

The tcl implementation listed on the above page is copied below,


proc logarithm {x} {
    set eps 1e-[set ::tcl_precision]
    if {$x<=-1} {error "logarithm requires a positive argument"}
set log $x
    set pow [expr {-$x*$x}]
    set i 2
    set add [expr {$pow/$i}]
    while {abs($add)>$eps*abs($log)} {
    set log [expr {$log+$add}]
    incr i
    set pow [expr {-$pow*$x}]
    set add [expr {$pow/$i}]
}
incr i -2
#puts "$i iterations"
    return $log
}

proc log {x} {
    set doubles 0
    if {$x<=0} {error "logarithm requires a positive argument"}
if {$x<1} {
    while {$x<=0.5} {
        # iterate : x=x*2 until 1/2<x<1
        incr doubles -1
        set x [expr {$x*2}]
    }
} else  {
    while {$x>=2} {
        # iterate : x=x/2 until 1<x<2
        incr doubles
        set x [expr {$x/2}]
    }
}
set x [expr {double($x-1)}]
global log2
#puts x=$x
    return [expr {[logarithm $x]+$doubles*$log2}]
}

# compute log(2)
set log2 [expr {-[logarithm -0.2]*3-[logarithm [expr {-3./128.}]]}]
# for debugging purpose
proc close {x} {
    set eps 1e-[set ::tcl_precision]
    set my [log $x]
set system [expr {log($x)}]
if {abs($my-$system)>$eps*abs($system)} {
    puts "my log $x : $my"
    puts "system log($x) : $system"
    error "$x runs odd"
}
return $my
}
|cite|improve this answer
$\endgroup$
  • 6
    $\begingroup$ The code simply uses the Taylor series for ln(1+x), and I cannot see its relevance to this question. $\endgroup$ – Tsuyoshi Ito Dec 2 '10 at 15:03
  • 1
    $\begingroup$ Thanks, but I don't think this is what Feynman has in mind. Its algorithm is supposed to benefit from a parallel implementation. I guess he can test directly if the factor (1+2^(-k)) appears in the product, without testing the previous factors. $\endgroup$ – caroline Dec 2 '10 at 15:37
  • $\begingroup$ it claimed feynman as the basis of the implementation which was what lead me to post it. $\endgroup$ – s8soj3o289 Dec 2 '10 at 19:57
  • $\begingroup$ Can you back up the claim? As I said, I cannot see any relevance of this code to Feynman’s method for logarithm (except that the code also calculates logarithm). $\endgroup$ – Tsuyoshi Ito Dec 2 '10 at 20:18
  • $\begingroup$ I wasn't trying to defend it, just explain the initial impetus, which perhaps was rash. I agree you are correct, in that it does not represent the computation described, rather just the more traditional method. $\endgroup$ – s8soj3o289 Dec 3 '10 at 8:39

Your Answer

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