Subject: Re: [boost] [xint] Boost.XInt formal review
From: Jeffrey Lee Hellrung, Jr. (jhellrung_at_[hidden])
Date: 2011-03-02 16:46:33
On 3/2/2011 2:58 AM, Vladimir Prus wrote:
> Boosters,
>
> the formal review of the Boost.XInt library, by Chad Nelson, starts now and will
> run through March 11.
>
> The documentation for the current version is available at:
>
> http://www.oakcircle.com/xint_docs/
>
> The source code is available via Subversion at:
>
> http://svn.boost.org/svn/boost/sandbox/xint
[...]
This (like Mathias) is not a review, but rather a random list of
comments upon a first pass through the documentation (and a little
through the implementation, but only because the documentation proved
insufficient to answer some questions).
I have two general and major comments.
1) I was hoping the bignum algorithms would be factored out and allowed
to operate on, e.g., ranges of digits, rather than being coupled to the
xint::integer_t data structure. I know this had been mentioned before.
Chad, what are your thoughts on this? I know the purpose of this
library is to provide out-of-the-box bignum functionality with minimal
hassle, but, to me, the algorithms should be part of the interface as
well and decoupled from the xint::integer_t data structure.
2) In a similar vein, I would like to see the cryptographic
functionality decoupled from the xint::integer_t data structure as well,
and released separately.
Also, good things: I like the policy-based design, and I think it's the
right direction. The Boost.Parameter arity thing may get onerous (see
comment below), and one thing you could do to work around it is to just
accept a mpl::map of tags, since I'm guessing your not using
Boost.Parameter's deduction functionality (awesome and powerful, but
unnecessary in this case, I think).
On to more specific comments...
Documentation Comments
----------------------
* http://www.oakcircle.com/xint_docs/
"Why would I use it? ... Because it's fast."
Do you have any benchmarks to back this up? Fast relative to...?
"Why would I use it? ... Because it has the features you need."
Included in here is "[c]ryptographically-secure prime number
generation". This seems a little too domain-specific to be included in
this library. Is there any reason the prime number generation couldn't
be factored out and, further, be bignum-implementation agnostic?
Boost.Prime, for example?
* http://www.oakcircle.com/xint_docs/namespaceboost_1_1xint.html
integer_t<...> square (const integer_t<...> n)
The complexity is just O(n^2). If you want to more precise, don't use
O(...), just state the number of additions/subtractions and multiplications.
integer_t<...> pow (const integer_t<...> n, const integer_t<...> e)
I suspect this complexity is, really, O( # of bits in the result ), as
the last one or two multiplies are what dominate.
I was also thinking about adding an overload where the power is
specified as an unsigned long, but I don't know if it would actually be
worth it...
integer_t<...> square_root (const integer_t<...> n)
You should mention that the algorithm is just Newton iteration with
initial guess 2^floor(log2(n)/2) (where n is the input value). Also,
your complexity claim implies a bounded number of Newton iterations,
independent of the inputs, as each loop through the while loop is O(n^2)
(where n is the # of bits) due to the division...that may be the case,
and if so, you might want to back that up with a reference or something,
but I suspect you should have maybe a log(n) in there (where n is the #
of bits), as Newton has "only" quadratic convergence.
I believe there is an O(n) square_root algorithm that would be
asymptotically faster, but...I'd have to look it up...
int is_prime (const integer_t<...> n, callback_t callback=no_callback)
Given the documentation, I think a more descriptive name, such as
is_probably_prime_rabin_miller, would be better. Also, I'm not sure how
small "infinitesimally" small is...it seems the wikipedia page only
guarantees at most a 1/4^5 chance of a false positive (given the current
implementation), but in practice it states the chance is much much less.
Perhaps you should allow the iteration count (the "k" from the
wikipedia article) to be passed as a parameter as well (possibly
defaulted), for those that want more control on their primality test.
But, similar to a comment above, I'm not sure any cryptographic or
number theoretic features outside of basic bignum arithmetic and
operations should be included in this library; I would like to see them
factored out and independent of xint.
*
http://www.oakcircle.com/xint_docs/structboost_1_1xint_1_1options_1_1threadsafe.html
"Note that even with this option, it is still your responsibility to
ensure that only one thread accesses a particular integer object at a time."
You seem to imply that it is not thread safe under any circumstances for
multiple threads to even have *read* access to an xint::integer_t
object. Is that the case, and if so, why?
* http://www.oakcircle.com/xint_docs/classboost_1_1xint_1_1integer__t.html
template<...> class boost::xint::integer_t<>
"You can specify several template parameters for the type. Most of these
parameters must be specified via helper classes defined in the
boost::xint::options namespace. See the list and descriptions there."
So that covers "most" of the template parameters...what about the rest?
Also, it would be helpful to document here what the default settings are.
integer_t<...> & operator+= (const integer_t<...> b)
integer_t<...> & operator-= (const integer_t<...> b)
Why are these parameters passed by value?
int sign (bool signed_zero=false) const
I think you should separate the 2 different meanings of signedness into
2 separate functions. There are performance considerations, of course,
but it's also difficult to the casual reader to infer what x.sign(true)
is suppose to mean without looking it up. A second function called
sign_with_signed_zero might be more appropriate.
* http://www.oakcircle.com/xint_docs/threadsafe.html
"When using copy_on_write, identical integer objects are allowed to
share storage, which is more efficient for both CPU power and memory..."
I'm (still) not sold that copy-on-write gives any noticeable performance
benefits in this library over move semantics except in contrived
examples, so I think some kind of justification of the above claim would
be justified.
I'm also not a fan of the integer_t::integer_t(const integer_t& b, bool
force_thread_safety) constructor; isn't there already an "ensure_unique"
member function already there (in the implementation) that ensures an
integer_t object has sole ownership of its storage? Indeed, looking
more at some source files, I would guess this is _make_unique. I would
consider such a member function preferable to this constructor overload,
especially given how the mysterious boolean parameter looks in client
code (see integer_t::sign comment above).
* http://www.oakcircle.com/xint_docs/basic__types__and__includes_8hpp.html
"#define BOOST_PARAMETER_MAX_ARITY 6"
This is not guaranteed to actually have any effect. Think about if
Boost.Parameter gets included before any xint header does. Better (and,
yes, more onerous) to document that xint::integer_t uses Boost.Parameter
and hence the user must set this macro to at least 6.
Miscellaneous Comments
----------------------
Why is digit_t in the xint::detail namespace, when it is expected to be
part of the interface for purposes of supplying an allocator?
How did you create your documentation? Your documentation generator may
appreciate an acknowledgment in your documentation.
Also, regarding the complexity notation, it would probably be best to
state the complexity in terms of some other letter than n, so as not to
confuse n with the input value. I know I did *not* do this in my
comments above, as I was trying to follow your notation, but it easily
gets confusing. Or just use log(n) instead of n to mean the # of bits
or digits.
That's it for now,
- Jeff