Re: [boost] Interest in an arbitrary precision library?

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