Mini-challenge: MAX(factors of 2 or 5)

[Claudio L.]

(01-19-2018 08:15 PM)Thomas Okken Wrote:  Also, the GCD trick isn't that much better, because calculating a GCD still requires repeated division, though admittedly not as many (I think it is usually better, and never worse (*)).

Not really, the algorithm can be done by subtraction only, which works quite well when the numbers are of similar magnitude happens to be this case.

(01-19-2018 08:15 PM)Thomas Okken Wrote:  (*) For example, finding the factors of 2 in 1e9 by taking its GCD with 2^16, using Euclid's algorithm, takes 6 divisions, while basic repeated division takes 10 divisions. How to quickly determine that that GCD, 512, equals 2^9 is left as an exercise to the reader.

Why 2^16? It doesn't guarantee you'll find the maximum if you don't know that the result is 9. You would in this case use 2^32 which is > 1e9 and therefore is guaranteed to have more 2's than needed.
Doing the GCD of 2^32 with 1e9 requires 56 subtractions (more or less, I might have messed up the count at some point). In a CPU without hardware division, this is faster than doing the divisions.

I cooked up a quick factor extractor:

Code:


«
  → 
    'X' 'FCTR' 
   « FCTR WHILE DUP X < REPEAT SQ END
    X GCD X OVER / 
  »
»

It takes a number and the prime factor you want to extract, returns the prime factor extracted with its exponent, and what's left of the number, in your example:
1e9 2 ====> 512 1953125
where it's easy to see multiplying the 2 values you have to get the original 1e9.
The first part looks for a power that is guaranteed to have enough times the factor, so the GCD can extract all of them in one shot. It uses SQ so it reaches a value relatively fast, but can overshoot, causing more delay in the GCD.
The only caveat is that if the given factor is not prime, the GCD will not necessarily be a power of the given factor, but some mix of powers of its prime factors.

EDIT: The code above uses only 1 GCD (many subtractions), 1 division and log2(N) multiplications.