Re: [boost] Multiprecision vs. xint

Subject: Re: [boost] Multiprecision vs. xint
From: John Maddock (boost.regex_at_[hidden])
Date: 2012-06-15 13:46:07

> Multiprecision addresses many of the problems of xint, and also extends 
> the scope into areas that xint did not address at all.  However it still 
> suffers some of the same problems: if I want an int128_t that is just 128 
> bits of data, it doesn't help me.

Sigh.  There was such a type (it's still in the sandbox somewhere as 
fixed_int.hpp, and uses a 2's complement representation), but I was 
encouraged to move to the current form pre-review - rightly IMO, as it's 
both more flexible and faster *most* of the time (though in some specific 
cases the old fixed_int code wins 'cos it's simpler).

> Furthermore, it doesn't help me to build the int128_t that I want. 
> Although Multiprecision is divided into "front" and "back"-ends, this 
> division is not in the right place to let me substitute my own backend 
> that just provides the 128 bits of storage.  In the xint reviews, we 
> suggested that the algorithms should be decoupled from the data structures 
> and the same applies here.  Similarly, this implementation doesn't provide 
> hooks that would allow me to substitute e.g. assembler implementations of 
> the algorithms.

Point taken.  However there is a difficulty here, lets say we separate out 
some of the low level code from cpp_int and define a routine such as:

template <class Limb>
void some_operator(Limb* presult, const Limb* a, const Limb* b, unsigned 
a_len, unsigned b_len);

This raises a number of questions:

1) What order are the limbs in?  There are two choices, and it's not clear 
to me that there is "right" answer for all situations.  Low order first 
makes the logic easier and is pretty much required for arbitrary precision 
types, but high order first works well for fixed precision types - and is a 
lot easier to for the user to debug - set the debugger display to 
hexadecimal and the value is just right there.
2) We can noticeably simplify the code if a_len and b_len are always the 
same.
3) Further if a_len and b_len are actually constants, then the compiler can 
unroll/optimize the loop more easily (not sure if constexp can help there).
4) 2's complement or sign-magnitude?  It makes a difference for many 
operations.
5) How large is presult?  It's tempting to require that it be large enough 
to hold the result, but that would prohibit use in fixed width types (which 
may overflow).  Or we could add the logic to handle both, as long as you're 
prepared to take the hit in performance when dealing with trivially small 
values.

I other words I'm suggesting that there is an inherent coupling between the 
data structure, and the "optimal" algorithm.

So.... I would be more than happy to separate out a low level customization 
point for cpp_int that would allow substitution of assembly routines - but 
don't imagine that those interfaces would be optimal for your use case - I 
don't believe it's possible to achieve an interface that's achieves that in 
all situations.  Of course I'd be happy to be proved wrong ;-)

I'm sorry if this sounds rather negative, but once you get down to the 
specifics of what such an interface should look like, then IMO it actually 
just gets harder to please everyone (unless there should be a sudden 
outbreak of unanimity!).

Regards, John.