Boost logo

Boost :

Subject: Re: [boost] Large Integer Library
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2012-07-02 13:38:14

Hi Michael,

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
we're lucky.

- 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
     this_type ret(*this);

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

Regards, Phil.

Boost list run by bdawes at, gregod at, cpdaniel at, john at