Re: [boost] [xint] Third release is ready, requesting preliminary review

Subject: Re: [boost] [xint] Third release is ready, requesting preliminary review
From: Jeffrey Lee Hellrung, Jr. (jhellrung_at_[hidden])
Date: 2010-05-02 03:48:39

On 4/29/2010 10:35 PM, Chad Nelson wrote:
> I'm happy to announce that the third release of the Extended Integer
> library is ready, in both the sandbox and the Vault.
[...]

I agree with the design to have the "default" class throw exceptions, 
and also to have a no-throw variant.  Your rationale section is a very 
good section to have, given the differing opinions among "us all" ;)

Also, the support for -0 is about how I'd imagine it, tucked away 
somewhere you'd never notice it except if you really wanted to know.

For now, just a few comments/questions on complexity.  It appears your 
complexities are formulated in terms of "n", but this (I hope!) is not 
the same "n" as the input parameter (e.g., I certainly hope that 
multiplying together integers n and m is not Theta(n*m) complexity!). 
Although one could guess what you really mean (n = # of chunks, or 
whatever), you should be more precise.  You also, to more precise, might 
want to use "Big-Theta" notation rather than "Big-Oh", where you can (it 
might be that, for example, multiplication is optimized to be 
constant-time if either argument is "1", though if that's the case, you 
might want to mention that).

Referring to your "A Note on Algorithmic Complexity":  Which algorithms 
are you making an "educated guess" on their complexity?

I'm curious:  Are you researching, or do you have plans to research, 
more efficient multiplication algorithms (Karatsuba's, FFT-based, etc.)? 
  I believe these only become efficient at large integers, but I'm not 
sure how large...

Okay, some questions regarding the arithmetic functions:  It looks like 
you have named free functions for all the arithmetic operators which 
have identical functionality to the overloaded arithmetic operators. 
This was obviously deliberate.  Can you comment on this decision, i.e., 
why have the named free functions at all?

Do you have free functions that implement the low-level arithmetic 
operations for just pairs of pointers?  E.g., do you have an add 
function that looks like

void add(
     const unsigned int* x_first,
     const unsigned int* x_last,
     const unsigned int* y_first,
     const unsigned int* y_last,
     const unsigned int* result_first);

?  Okay this signature is probably not what you'd want, but more 
fundamentally my question is, have you separated the arithmetic/numeric 
algorithms from the memory management algorithms?  Can one build their 
own, e.g., stack-based integer class as just a wrapper around the 
arithmetic algorithms?

Also, I don't see any allocator template parameters anywhere.  I'm 
guessing any consideration of acceptance into boost is conditional on 
allocator support.

Very nice work on the documentation.  I'll have to continue to troll 
through it at my usually leisurely pace.

- Jeff