Re: [boost] [xint] Some preliminary review notes

Subject: Re: [boost] [xint] Some preliminary review notes
From: Chad Nelson (chad.thecomfychair_at_[hidden])
Date: 2011-03-25 10:01:15

On Fri, 25 Mar 2011 12:06:35 +0300
Vladimir Prus <vladimir_at_[hidden]> wrote:

> I've promised to post initial summary of Boost.Xint this Monday, but
> real life has interferred. I apologise.

Amazing how that happens, eh? ;-)

> [...] At the same time, Chad, I'd appreciate some input from you.
>
> - Could you express your current world view of those issues. Whether
> they are real, important, and what plan do you have about them, if
> any. Note that you are not required by any means to address every
> raised concern, but some coherent plan of action will be very
> important both for further development of your library and for review
> result.

Certainly. I've rearranged the quoted message to address them in a
logical order:

> - Whether it would be better to separate algorithms and data
> represetation

It would, and I intend to redesign the internals to accommodate this,
as outlined in this message:
<http://permalink.gmane.org/gmane.comp.lib.boost.devel/215984>. (I'll
refer to this as "the redesign" below, as it directly affects several
later answers.)

> - Whether COW is good idea or not,

It's not a good idea in general, and quite possibly not a good idea for
XInt either. I can't prove it either way as yet.

However, I believe the point will become moot. The redesign mentioned
above will allow for different data structures, and since I'll need to
write one with and one without CoW to see whether it's truly an
improvement, I'll provide both if it proves that it is.

> and whether current COW is truly thread-safe.

Steven Watanabe discovered an implementation bug in the copy
constructor, which I've since corrected. (Steven, you looked at the
"postreview1" version for my CoW timings, I assume that correction looks
okay?) No one else has mentioned any specific problem with it, or
provided any scenario where my design wouldn't be thread-safe when used
as I outlined.

> - Whether ET should be used

I'm not sure whether it would be worthwhile or not. I'd like to explore
it in the future, but I believe it is not the way to go at present.

> - Whether it's possible to optimize specific cases (addition of
> 128-bit integers, ln+gamma, etc), by some template specializations, or
> other mechanism.

It would probably be possible with ET. I don't yet see a way to provide
many of them without it. In any case, I would prefer to concentrate on
optimizing the general case before worrying about specific cases.

> - Whether data copy in "a + b + c" should be eliminated

If I recall the specific code that prompted that comment, there was at
least one unnecessary copy there, which I will eliminate.

> - Whether the library is "fast", in particular:
>   - Do algorithms have best big-O complexity?

Two specific algorithms (multiplication of larger numbers, and likely
the square-root algorithm) can be improved, and I will do so. No other
algorithms were mentioned, so I assume that they are at least sufficient
for the first version. I'll be happy to improve the speed of any
algorithm as I find ways to do so.

>   - Are fixed-size integers fast enough

Fast enough for...? :-) They obviously aren't as fast as they could be
at present. The redesign mentioned earlier may allow for a
stack-allocated structure for fixed-size integers, which could
presumably provide a large speed increase for smaller numbers. At
present, that's all I can promise, as fixed-size integers are not the
primary purpose of the library.

> - Do you keep track of technical issues raised? Could you share that
> list?

The ones in my issue-tracker that I haven't yet addressed are, in
(very roughly) descending order of priority:

* Add CRTP
* Redesign storage system
* Improve efficiency of addition
* Eliminate on_exception, use BOOST_THROW_EXCEPTION instead
* Move or typedef xint::detail::digit_t to the xint namespace
* Fix 'secure' operation
* Improve policy-based design
* Improve multiplication algorithm
* Simplify SFINAE code for operators
* Fix Linux strong_random_generator
* Rename integer_t to basic_integer
* Rename "secure" option
* Add a sign_with_signed_zero function
* Conversions to/from floating-point types
* Convenience function for creating bit-masks
* Add more tests
* Move the random generator types to the xint namespace
* Eliminate base_random_generator
* Split up include files
* Change pow2, factorial, nan to free functions with template parameters
* Separate the random generators, let client code include them if
  desired
* Move is_even, is_odd, and hex_digits out of the class; maybe sign too
* Improve square-root efficiency
* New functions or examples requested
* Conversion to/from dynamic_bitset
* Conversion to/from bitset
* Add a throw-on-overflow option for fixed-size integers
* Add is_definitely_prime

I've removed documentation-only improvements from the list.

Note that these are the titles of the issues only, and were intended
solely as reminders to myself, so they may be cryptic. If you want more
details on any particular item, please ask.
-- 
Chad Nelson
Oak Circle Software, Inc.
*
*
*