Re: [boost] [xint] Boost.XInt formal review

Subject: Re: [boost] [xint] Boost.XInt formal review
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2011-03-03 15:28:35

On 03/03/2011 17:10, Chad Nelson wrote:

> Not the same case at all. XInt isn't a language, it's a library that's
> explicitly designed for very large numbers. If someone didn't need
> numbers larger than the built-in types can handle, they wouldn't use it.

So you're already limiting the application area of XInt.

The problem is that the application area you're restricting it to 
doesn't seem to be the one that is the most likely to require arithmetic 
with infinite precision.

>> Can your library allow me to choose a memory layout optimal for the
>> application of my choosing?
>> Probably not. How about you let me choose my own layout and let me
>> interface with your algorithms?
>
> If you want that sort of flexibility, you'd probably be better off with
> something like GMP. XInt isn't designed for that, and in my opinion,
> shouldn't be.

GMP doesn't allow what I want at all. It can't really do, it's in C.

>> - So that the library is easily extendable
>
> What would you want to do to the internals of it that it doesn't
> already provide, and that I wouldn't be willing or even eager to add?

There are hundreds of functions that you can use with integers, each 
with their own algorithms documented in various research papers.
Do you really claim that your library can provide all of them?

Say I want to implement the gammaln function (gammaln(x) = ln(gamma(x))).

Assuming you did implement good ln and gamma functions (which you do 
not, all you have is a O(n^3) factorial), it is still interesting to 
compute gammaln directly because it uses less memory.

And before you wonder the point of that function, know that it is 
typically used to compute binomial coefficients (and combinatorics are 
certainly big users of big integers).

Now, cool stuff, if you were using expression templates, you could 
recognize that when doing ln(gamma(x)) you should really call gammaln(x).

Clearly, this is becoming too big of a thing for a monolithic library to 
handle.
That's why you need to be generic and modular, and separate concerns as 
much as possible.

>
>> - So that the algorithms only require a range of digits as input if
>>    that's all they need, allowing them to work with arbitrary types
>>    of my choosing without having to copy or convert to your types
>
> If it exposed the internal details of a number, then I'd never be able
> to change the way it works without breaking existing client code. That
> would be a much worse design.

You need to come up with a concept that can be used to interface the 
data and the algorithms.

Now that you've written the algorithms, it's easy: just look at their 
requirements, and define your concept from then.
See <http://www.generic-programming.org/about/intro/lifting.php>

>
>> [...] If the user provides a SIMD type as a digit, you'll get
>> optimized SIMD code for free, for example, in a completely
>> externalized way. Now *that* would be awesome. [...]
>
> Yes, it would. But it would come at a cost.

The design I am proposing would allow you to "outsource" the low-level 
optimizations and concentrate on the algorithms.

Do you not see the value in this?

> Disabled by default on *external* numbers. It's still used internally,
> where it's completely safe and much faster to do so.

Why would you need to unnecessarily copy around internal temporary numbers?

> Which C++ still is, until C++0x is official and built into almost every
> platform's compilers. Which won't happen for a number of years yet.

Emulation of move semantics in C++03 with Boost.Move is functional. 
Sure, it came a bit late in the project, so I can understand why you 
only did simplistic support without delving too much into it.

Also, using expression templates, you could also obtain speed 
improvements similar to that move semantics can bring.

Speaking of expression templates, I know that an bigint implementation 
made at STMicro (for use in embedded environments) uses expression 
templates to compute the worst-case size needed for an expression so 
that it can preallocate the result buffer accordingly, so this could 
also have other interesting uses.

>> Something else, I went through a code a bit, and I saw virtual
>> inheritance. Just why do you need dynamic dispatch in a design where
>> all information is purely static?
>
> For the policy-based options.

I don't see how that requires virtual inheritance.