Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk