Re: [boost] Large Integer Library

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
     ++ret.m_lo;
     if( ret.m_lo == low_part_type(0) )
     {
         ++ret.m_hi;
     }

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