FPGA Central

Can anyone explain me how the following algorithm is working?

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 entire
computation took less time than division.

[email protected] wrote:
> Can anyone explain me how the following algorithm is working?
>
> 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 entire
> computation took less time than division.

How does shifting and subtracting determine if 255/256 is a factor of
1.08925? Tell me that, and I'll be able to answer your question.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

[email protected]:
> Can anyone explain me how the following algorithm is working?

I suppose looking at an implementation might be helpful:

http://www.jjj.de/fxt/demo/arith/shiftadd-log-demo.cc