From: Andras Erdei (aerdei_at_[hidden])
Date: 2005-09-11 05:14:06
On 9/11/05, Daryle Walker <darylew_at_[hidden]> 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