2 ms·
I have a gut feeling that there is a faster way to compute logarithms going from least to most significant bit. How would I go about using ML to find it? [Edit
by mikewarot 4y ago
I have a gut feeling that there is a faster way to compute logarithms going from least to most significant bit. How would I go about using ML to find it?
[Edit] I think Feynman's algorithm might do it:
"Consider the problem of finding the logarithm of a
fractional number between 1 and 2. (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 for the presence of each of these factors in
a binary 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 the
Connection Machine especially well because the small
table of the logarithms of 1 + 2^(-k) could be shared by all
the processors. The entire computation took less time
than doing a division."
- xpe 4y agoStart with these questions: 1. How big is the search space? 2. What analysis approaches are likely to bear fruit for the search space? (theoretical analysis? optimization?) 3. If optimization is called for, what kind?
- adgjlsfhk1 4y agonote that this algorithm will no longer be good. for precisions up to roughly 1000 bits small tables combined with minimax polynomials are optimal and for higher precision, you want to use more complicated methods. if you're interested, the ARB library unlikely the currently fastest known methods.
- radford-neal 4y agoSeems similar to the CORDIC algorithm (https://en.wikipedia.org/wiki/CORDIC https://en.wikipedia.org/wiki/CORDIC).