On 9/11/05, Daryle Walker <darylew@hotmail.com> wrote:
Will access to the internals improve the implementation of GCD? If not, we already have GCD and LCM functions in Boost.
Yeah, I knew about those. I hadn't gotten around to checking them out yet. If they use Euclid's algorithm rather than the binary algorithm, then I won't use them.
I think they're all Euclid-based. (They can't assume that the numeric type is binary-based.)
No. The binary gcd algorithm. See Knuth "Semi-numerical algorithms."
Did you think I mistakenly said "binary-based" for "binary gcd"? I didn't; they mean separate things. I have the book; I've read the algorithm. Even though the binary GCD algorithm works for any representation, it's optimal for radix-2 representations, especially in computers with bit-level operations. (If a type matches that, then the algorithm can be done with shifts and masks.) I don't know if the binary GCD algorithm is more efficient if you cannot assume that the numeric type has an optimal representation.
it is possible to devise efficient algorithms resembling the binary GCD for any base with only a few prime factors (if you have access to the ACM digital library: i've recently found an article there discussing the merits of 12-based (GCD) computation, but i don't remember the title or author, so you'll have to search), but i guess for a binary architecture the binary GCD (and representation) is the natural (and optimal) choice br, andras