Re: [boost] [xint] Utility question, how to implement...

Subject: Re: [boost] [xint] Utility question, how to implement...
From: Chad Nelson (chad.thecomfychair_at_[hidden])
Date: 2011-03-07 12:07:48

On Mon, 7 Mar 2011 10:03:37 -0500
"Stewart, Robert" <Robert.Stewart_at_[hidden]> wrote:

>> [...] For that matter, pretty much everything in the library is
>> implemented in terms of addition, subtraction, multiplication,
>> division, modulus, comparisons, and the occasional bit-manipulation
>> function or is_odd/is_even. All of which are in the public
>> interface. Lower-level access might occasionally allow for a faster
>> implementation, but it's almost never required. (I'd go so far as to
>> say never, but there's an exception to every rule.)
>
> That is, of course, very likely.  The hidden part of the question is
> whether such an algorithm can be implemented efficiently without
> needing access to the internals.

That depends on the algorithm. There are a few (random_by_size springs
to mind) that require access to the internals for maximum efficiency.
However, most algorithms have no need for that. Even relatively complex
ones, like powmod with the Montgomery reduction algorithm, can be
efficiently expressed entirely through the current public interface.

> Note, this is the same thing being asked related to expression
> templates.  The idea there is to reduce a non-trivial sequence of
> operations to some provided public function that does a combination
> of operations in one call taking advantage of the internals. IOW, if
> you provide a function that does "add two numbers and multiply the
> result by a third" implemented in some manner that is more efficient
> than the naive sequence, then you can use ETs to recognize that
> pattern (product of a sum and a third value) and call the special
> function rather than apply the naive sequence of operations. [...]

Yes, I'm starting to realize that. I'm not sure that it will be of much
use to most people, but it could be indispensable to a few. I'm pretty
sure it can be added without changing the existing public interface or
breaking client code that uses it, but I'm still pondering the
possibilities.
-- 
Chad Nelson
Oak Circle Software, Inc.
*
*
*