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

[Thomas Okken]

(01-19-2018 07:39 PM)Joe Horn Wrote:  

(01-19-2018 02:40 PM)Thomas Okken Wrote:  I think Joe meant "slow."

Yes, plus the fact that it's the obvious brute-force way of doing it. It doesn't use any number theory tricks, or clever shortcuts, or anything which represents thinking outside the box...

You're using a rather more exalted version of "elegant" than I do. I think the repeated division is more elegant than FACTORS because it doesn't do all the unnecessary work of finding all those other factors that you aren't even interested in.

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 (*)).

To really cut down on the divisions, you should divide by high powers of the desired factors, and back off toward lower factors when the higher ones don't divide the number evenly any more. That would be fast; whether it would be elegant is a matter of taste. Also it might not even be beneficial: a lot of complexity analysis ignores how the cost of doing arithmetic becomes higher when you're realing with larger numbers. Dividing by 512 is harder than dividing by 2.

(*) 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.