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