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

Subject: Re: [boost] [xint] Boost.XInt formal review
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2011-03-12 07:37:45

Steven Watanabe wrote:
> IMHO, trying to make a bigint "just like the STL"
> is simply misguided. Addition, subtraction,
> multiplication, and division aren't algorithms
> that operate on a bigint. They're the basic
> operations that define an integer.

I'm not so sure about whether "division" is a basic operation with respect to an integer. An "efficient" implementation of "division" might be required as a building block for "efficient" implementations of other  algorithms (like GCD or LCM), but I wouldn't say that "division" is required to "define" an integer.

An additional complication with respect to division is the "remainder". At least some algorithms for "division" will compute the "remainder" at the same time as the "quotient". So should the division be defined to yield both "remainder" and "quotient" at the same time? And how should "division" be defined exactly for negative numbers? Should the "remainder" always be a positive number, or should the absolute value of the "remainder" be as small as possible, or should the sign of the numbers be mostly ignored for division (that's what C/C++ try to do)? 

The point I'm trying to convey here is that it's difficult to exactly determine the "fundamental" operations/algorithms ("fundamental" implies here that they work directly with the internally representation of the integer) that must be provided as basic building blocks for other operations/algorithms.

> b) New algorithms: Are the basic operations
> that are provided not enough for some
> algorithm that you care about? Concepts
> should be created by abstracting concrete
> code. If you try to define the interface by
> guessing at what some hypothetical user
> might want, you'll end up with something
> much more complex than it needs to be.

We should be aware that one part of the "big integer" library problem comes from a deficiency of C/C++ with respect to how signed and unsigned integral numbers have been abstracted. From my point of view, this is the underlying reason why GMP is forced to fall back to assembler code, in order to achieve reasonable performance.

But the deficiency of C/C++ in this domain surfaces already much earlier, when working working with negative number and remainders. This typically hits me when working with algorithms using a FFT and related data structures internally, since the nice periodicity features of the FFT data structures are very hard to map to fast and readable C/C++ code.

The point how this all is related to the XInt review is that on the one hand, XInt can't be blamed if it tries to follow the example from C/C++ for consistency reasons, but on the other hand, C/C++ is probably a poor example in this specific domain. Even Ada, which nobody likes for good reasons unrelated to this domain, does a much better job than C/C++ here.

Regards,
Thomas