Subject: Re: [boost] Large Integer Library
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2012-07-02 13:38:14
Michael Tryhorn wrote:
> I have written a Boost-compatible library for the representation and
> manipulation of integers of large or arbitrary size (including 128bit and
> above). I would like to make a preliminary submission of this library for
> your review and input, for potential inclusion into Boost v1.51.0 or later,
> as per the Boost Library Submission Process.
It would have been great if you could have joined the discussion a
couple of weeks ago. Perhaps it is not too late for you to write a
review of the proposed Boost.Multiprecision, since you clearly have
some experience of the subject.
I have had a quick look at your code and my initial thoughts are:
- The storage of these types is just the actual numeric data, so I
should be able to do binary I/O on them etc., which is good. I would
perhaps be a bit more confident of this if it were just an array of
int32s or int64s, rather than the current recursive organisation.
- You're using 2's complement, which I believe is the right choice.
- The simplicity of the code means it could be relatively bug-free, if
- Bitwise multiplication and division is completely inappropriate.
- You have an idiom of working on a temporary and them copying the
result to *this to "commit" it, e.g.
template<class T, class U>
large_int<T, U>& large_int<T, U>::operator++ ()
// Take a copy of *this, to modify
// Perform the increment
if( ret.m_lo == low_part_type(0) )
// Commit the result
return( *this = ret );
I don't see what the benefit of that is; it just makes ++ much slower
than it otherwise would be.
This example, operator++, also illustrates what may be a weakness of
your recursive style. Consider a 256-bit int implemented using 64-bit
built-in ints via intermediate 128-bit ints. The increment does this:
increment the 128-bit m_lo:
increment the 64-bit m_lo (builtin)
test the 64-bit m_lo for zero (builtin) (assume common-case, not zero)
test the 128-bit m_lo for zero (not built-in, impl in traits.hpp)
test the 64-bit m_hi
test the 64-bit m_lo
All of second half of that is redundant once you know that the least
significant 64 bits incremented to a non-zero value, but it is far from
obvious to me that the compiler would successfully optimise it away.
On the other hand, if the implementation were just an array of 4
(u)int64_ts, you would iterate with a for loop and break when non-zero.
- It would be great to see "hooks" where assembler implementations
could be inserted.
- It would be interesting to know if your code could function as a
"back end" to the proposed Boost.Multiprecision, using that library's
expression templates to eliminate temporaries. There are two things
that could be learnt from that: does that help performance, and does
the Multiprecision front/backend split work?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk