|
Boost : |
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk