Boost logo

Boost :

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.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk