Re: [boost] Big Int

From: Richard Peters (r.a.peters_at_[hidden])
Date: 2005-03-05 08:31:59

From: "Christoph Ludwig" <cludwig_at_[hidden]>
> I only superficially looked through the documentation and the headers of
your
> library. And as much as I liked to, I cannot invest much time in the
> evaluation of your work. Nevertheless, here are some random notes in no
> particular order:

Thank you for going through my library :)

>  * The documentation is obviously unfinished. What I'd like to see besides
the
>    missing parts of the reference are some statements that clarify
>     - what sets your library apart from other bigint libraries (The
maintained
>       ones that I am aware of are GnuMP / cln, NTL, Piologie, MIRACL. I am
>       sure there are more.)
>     - how your library relates to the proposal for a bigint type for the
C++
>       standard library (papers N1692 and N1744).

Yes, the documentation is not finished. I would like to use boostbook for
documentation, but I haven't been able to set it up right.
This library is written purely in portable c++, and is therefore platform
independent. An assembly implementation is probably a lot faster, but my
library has the option to plug in other libraries. At the moment, cln and
GnuMP can be used as back-end. My library will be released under the boost
license.
The bigint type proposed for the C++ standard library does not permit the
use of expression templates. Using expression templates has a positive and a
negative aspect: A significant speedup can be gained using expression
templates. The downside is that templates cannot deduce the correct type of
expressions, for example:
template<class T> void f(T a, T b) will not work when invoked as f(x + y,
x - y), because x + y returns an object of type different from x - y.
Because the C++ standard library proposal specifies the result type of the
operators to be of type const integer, a library implementing that proposal
cannot use expression templates.

>  * Specification of div_and_mod(): The formal input parameters are named x
and
>    y, but the effect section refers to e and f.
>
>  * You always refer to the parameter types as "IntegerType", but some
>    parameters need obviously to be references. What can IntegerType
actually
>    be? Only big_integer and types resulting from the expression template
>    machinery built around big_integer? Or also int, long etc.? If the
latter,
>    what happens if there is an overflow?

The idea is to allow big_integer, types resulting from expression templates
and int, long, etc. There's still some work in specifying all of this.

>  * I am glad you defined conversions to bit-strings in little / big endian
>    format. That's something I missed from time to time in other libraries.

I use these functions very much in my cryptography-related software. I
wouldn't know what to do without them :)

>  * Did I miss the functions that convert big_integer to long, double etc.?
And
>    the other way around, how can I convert a double to a big_integer?
(Such
>    conversion functions are essential in my area of interest, lattice
basis
>    reduction.)

I don't have functions converting to/from floating point types. Actually, I
have never had the need for floating point values, and I'm wouldn't know how
to implement them. If you'd like, I can contact you when I resume work on
this library, so that we can work something out.

>  * The function names group_divide and group_inverse are too generic, IMO.
>    They don't convey that you are referring to the prime residue group mod
>    m. As soon as you start implementing, e.g., EC arithmetic or the
arithmetic
>    in GF(p^n), the names become confusing because there are several groups
>    involved. I'd prefer something along the lines of divide_mod,
inverse_mod.

Good point.

>  * There are some functions in NTL I found convenient and that I didn't
see
>    in your library: E.g., bit-wise operators, Hamming-weight, CRT,
>    logarithm with result type double. Do you plan to support these? (There
are
>    even more functions in NTL, like Jacobi symbol, primality tests etc.
that
>    are required in any library for computational number theory. Do you
have a
>    clear policy what belongs in your big_integer library and what you
consider
>    to be too specialized?)

Well... I try to aim at core operations only. At the moment, I support
jacobi symbol and primality testing, but I will almost certainly remove
them. Bit-wise operators should probably be available. The other operations
that you mentioned are without doubt useful, but I think they belong in a
separate library.

> Again, this is after a superficial look only, so it's likely I missed
> something.
>
> Regards
>
> Christoph

best regards,

Richard Peters