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-05 09:53:30

On 04/03/2011 08:39, Chad Nelson wrote:
> On Thu, 03 Mar 2011 21:28:35 +0100
> Mathias Gaunard<mathias.gaunard_at_[hidden]>  wrote:
>
>> 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.
>
> That makes no sense. It's a large-integer library. How does designing it
> specifically for large integers make it unsuitable for its purpose?

It's not tailored to particularly large integers (well, in truth, using 
it with very large integers would be catastrophic, because the 
algorithms don't have good complexities).

So it's a library for general-purpose integers that can be large up to a 
point.

If you're already alienating the cases where the integers are often 
small and rarely big, there is not much of an applicability range left 
for your library.

Shall it be renamed to "the monolithic thread-safe COW library for 
integers between 100 and 1000 digits"?
What's the applicability range of that?

>> 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?
>
> Do they require specialized bit-twiddling?

They're often defined in terms of digits, yes.

> Or are they arithmetic
> operations that can be described in terms of functions that the library
> already provides?

Well, in a discrete world, you can implement everything on top of the 
basic arithmetic operations.
But that wouldn't be efficient. I've already given you a very simple 
example that demonstrates how it can be best to implement a composition 
of two functions on its own rather than evaluate the functions one after 
the other.

Even for multiplication, there are a lot of different algorithms. The 
best algorithm to use depends on the situation, a fast fourier transform 
is probably the best when dealing with large values for example.

It seems however that you library is stuck with the naive O(n^2) 
implementation. A new multiplication algorithm was created fairly 
recently in 2007, so you could want to add new algorithms to your 
library at any time.
Extension is important. Take a look at Boost.Graph; several contributors 
add new algorithms to it every so often. But if it's not extensible, it 
cannot happen.

On a side note, every algorithm that depends on multiplication should 
take a functor that specifies which multiplication algorithm to use 
(with a suitable default).
This way, I can provide my multiplication that uses an optimized FFT 
routine to your algorithms, without requiring your library to contain 
all possible optimized implementations of multiplication.

> Certainly, but it doesn't outweigh the cost.

What cost? The cost of reorganizing your library entirely?
I thought we agreed you'd have to do that anyway.

>>>> 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.
>
> Yes, it's always much easier to attack something than to build it in
> the first place.

This is a review, not a personal attack.
I'm asking you why you need to do a specific thing, since I see no 
reason to, and you reply with that kind of comment?
Am I to understand you don't wish to continue a discussion with someone 
that is obviously going to give you a "no" vote?

I have built libraries that used so-called policy-based designs, and 
never required virtual inheritance.
So I honestly see no reason why you are doing that, and would welcome to 
be enlightened or to explain to you how you can circumvent the problems 
that required you to use this if possible.

Likewise, I would also warmly welcome answers to several questions I 
have asked you that you have ignored. What are the advantages of your 
library over the myriad of existing ones?
The reason I'm asking you that is because, from my possibly narrow view, 
you do not compare favourably to them. I would gladly be corrected on 
this topic.