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

Subject: Re: [boost] [xint] Third release is ready, requesting preliminary review
From: Chad Nelson (chad.thecomfychair_at_[hidden])
Date: 2010-05-02 12:48:48

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 05/02/2010 03:48 AM, Jeffrey Lee Hellrung, Jr. 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" ;)

So I figured. :-)

> 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.

As we discussed.

> 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.

Easy enough... done. That paragraph of the complexity page now reads:
"This documentation includes a time-complexity estimate, in big-O
notation, for each algorithm. The n in the complexity estimates is
roughly the number of bits in the parameter(s). (More accurately, it's
the number of digit_t values needed to hold those bits.)"

> You also, to more precise, might want to use "Big-Theta" notation
> rather than "Big-Oh", where you can

I'm not familiar with Big-Theta. I've just looked it up, but I think I
must be missing some background information because it doesn't make a
lot of sense.

> (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).

I check for zero, but not one. I didn't think it was worth mentioning
details like that... the complexity estimate is just something to give
people some idea how the time will increase based on the size of the
parameters.

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

The ones that gave me the most trouble were the three based on the GCD
algorithm (gcd, lcm, and invmod, I believe). I finally found a research
paper describing the complexity of the binary GCD algorithm, and I based
the other two on that.

> 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...

Yes, I already have a description of the Karatsuba one to work from, for
a later release. It's supposed to be more effective than the traditional
version once you get past a certain size, but I don't know what that
size is yet. Once that's added, I'll look into the others.

> 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?

Originally those were the functions that handled the internals. I had to
move the internals down by another layer of abstraction in order to
efficiently handle the fixed_integer types, and I just never thought to
remove the free functions.

> Do you have free functions that implement the low-level arithmetic
> operations for just pairs of pointers? [...]

Not pairs of pointers, but I do have lower-level functions (the ones in
the detail namespace) that work on base_integer types.

> ?  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?

They're separated, in that the memory management is all done by the
base_integer class, and the math is handled by the higher classes and
free functions.

> Can one build their own, e.g., stack-based integer class as just a
> wrapper around the arithmetic algorithms?

Maybe, if one wants to implement all the free functions for their type.
:-) I hadn't considered that anyone might want to.

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

<sigh> I wish someone had mentioned that before. Not that it makes that
much difference... while trying to add the data-caching stuff to the
fixed_integer types last night, I came to the conclusion that I needed
something like that anyway.

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

Thanks!
- -- 
Chad Nelson
Oak Circle Software, Inc.
*
*
*
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkvdrO0ACgkQp9x9jeZ9/wQr3gCbB9Iw7+KViC6zEbj2MCP5mDOD
enEAn1wXmnAahgJpAZeyZW4YqRbkIaQV
=3d5q
-----END PGP SIGNATURE-----