Re: [boost] Multiprecision vs. xint

Subject: Re: [boost] Multiprecision vs. xint
From: Christopher Kormanyos (e_float_at_[hidden])
Date: 2012-06-16 18:29:37

Thanks for your comments Robert.


>> Although the proposed Boost.Multiprecision provides default
>> implementations of int, rational and float, its main goal is
>> not to compete with the world's best performing implementations
>> thereof.

> Of course it needn't compete with the world-class implementations,
> at least not initially.  However, it must be fast enough to be usable
> in enough use cases to get sufficient experience to determine whether
> the interface is right and whether the customization points are appropriate,
> in order to have a solid foundation for a standard proposal.

Agreed. In my opinion, though, the back-ends already provided in the
review candidate provide sufficient performance to make the library
absolutely usable and simultaneously gain experience with the interface.

>> I would prefer spending review time working on the long-game
>> of boost and C++.

> Yes, given the minimal performance caveat noted above.

>> How will boost or C++ potentially specify extended number
>> types?
>>
>> template<typename back_end_numeric_type,
>>                 typename numeric_traits,
>>                 typename allocator_type,
>>                 typename expression_method>
>> mp_number
>> {
>> };

> That looks ugly, for a numeric type, but typedefs and template
> aliases will be very useful in making nice, user-defined types
> and class templates.

Well, it's just an idea for potential standardization in my dream
of the future. To me it doesn't really seem much uglier than std::basic_string.

But honestly, we are far away from standardizing number representations.
It's just one of my long-term goals.

>> I would prefer to work on the interface, not the performance
>> of the default classes that John and I have provided. If we
>> bicker about these, we will never get to the real matter at
>> hand which is specifying the abstraction for non-built-in
>> types.

> While I agree with your sentiment, note that Phil's concern about
> being able to create a fast, slightly-larger-than-built-in type is important.
> Showing how such a type can be created is an important exercise
> because it will show whether the abstraction and points of customization
> have been properly conceived to permit creating such types.

I also agree. In the past months, I had an opportunity to use multiprecision
with a variety of other types that are in my catalog. So I am convinced that
it works well for the domain of number abstraction. But you are right.
A real example with such a popular type might be beneficial.

John, in your opinion, what might be the best way to include fixed-size
integers of 128 and 256 bits? Would you recommend template specializations
of one of the existing ones or dedicated high-performance back-ends?

I could add a few of these these in the fall, if desired (or if makes sense).
I've got the code and it's in pretty good shape.

> Indeed, given the likelihood of folks wanting to do what Phil did,
> the library could provide a template-based backend implementation
> that does most of the heavy lifting.

>> John's concept takes the first step toward establishing an
>> architecture for extended numeric types.

> It is reasonable to view this as "the first step" and leave the fulfillment of
> some of these other requirements for later.  However, if there is no proof
> of concept for the various use cases, then you can't be sure the abstraction
> and points of customizations are correct.

Well remember, we actually do provide  integer, rational and floating-point
back-ends, right off-the-rack and ready to use.

>> In this way, the previous discussions about default styles
>> of template expression and the proposed name of the
>> abstraction (mp_number or simply number) are more relevant than

> "number" is better. The namespace can always be used, including
> with a namespace alias, to make for a more specific name.
> If "mp_" is in the name, it cannot be removed.

>>> 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.
>>
>> The proposed Boost.Multiprecision says, "You have to write it
>> yourself!" Just like a compiler supplier would. That's the
>> concept of the proposed Boost.Multiprecision.

> That's fine for esoteric things, but not for something that would
> be extremely common.

I guess we need a list of *common* things. I do more with floating-point
and less with integers. Others are focused on cryptographic hash algos
using integers, while others still may use a lot of rational numbers.

Perhaps fixed-size signed and unsigned 128 and 256 bit integers
are so common that we need to support them explicitly.

>> I do, however, have UINT128 and INT128. I wrote them sometime
>> around 2002. If you *really* would like, I could approach
>> John and ask how we could make these boost.ready. I also have
>> UINT24 for embedded systems.

> One of those might be an excellent tutorial for defining a backend,
> though actually including the code, in some form, with the library
> would be ideal.

I can do it, but can't start until sometime in the fall.

<snip>

>> In my opinion, the suggestion was not correct, but
>> understandable. Just because the proposed Boost.Multiprecision
>> provides a template abstraction for arithmetic operations and
>> C99 elementary transcendental functions, does not mean we would
>> like the template itself to be modifiable.

> If the operations are broken down to calls to specific algorithms,
> why not permit customizing those algorithms?  If your concern is
> that doing so exposes implementation details that would thwart
> future improvements, I can certainly understand your reticence.

I personally do not like that level of granularity. Over the years,
I have written quite a few specialized numeric types, both large
and small. In my first designs, I used custom hooks for ugly assembler
stuff, only to notice that my algorithm was less than optimal in the
first place. My preference is to keep the numeric type in and of
itself whole. I do, however, understand user customization.

>> Furthermore, it may be reasonable to see some of what was being
>> requested for xint is what your library provides in its backend.

I am a bit new and came to the board just during the review of xint.
But as far as I remember, it was just the integer type.
Wouldn't xint simply be a big integer back-end for the proposed
multiprecision?

Here's the deal in my opinion. The community needs big integers,
rationals and floats. But there are only a few sources. The proposed
multiprecision provides both an abstraction for these numeric types
as well as reference implementations for integers, rationals and floats.

The proposed multiprecision provides an architecture for the abstraction
of the numeric types. Getting near world-class types would take
a coalition of programmers because it's quite hard to write
very good big number types.

Boost is full of previous attempts to write individual number types, but
no one ever completed any of them. Perhaps it would be good to use the
proposed multiprecision as the abstraction and find out who would like
to contribute to writing the improved back-ends for it.

But this should be done later because it is a long-term project, requiring
more development time, planing and coordination.

>>> Similarly, this implementation doesn't provide hooks that
>>> would allow me to substitute e.g. assembler implementations
>>> of the algorithms.
>>
>> This is correct for Boost.Multiprecision, and it is as it
>> should be. Please don't expect to put hand-written assembler
>> optimizations in the template. If you can do it better than GMP
>> and MPFR, then you must do it in the back-end---an entire
>> back-end.

> Perhaps the documentation needs to be clearer about the role of the
> frontend and backend parts of the library. Specifically, there should
> be information that notes that performance optimizations are, mostly,
> applied to the backend.

Good idea. You are right. There have been other comments along these lines.

In fact, the performance is predominantly determined by that of the back-end.

Thanks again for your comments.

Best regards, Chris.