Feynman and the logarithm

Question

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 ?

Answer 1

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.

Answer 2

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
}