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-14 18:22:44

Steven Watanabe wrote:
Thomas Klimpel wrote:
> > OK, that's at least a step forward from "implementation-defined", but
> > the modulo operator ("%") is still awkward to use in practice (for
> > negative numbers).
>
> If you don't like it, then you can always fix up
> the result to be what you want. The cost of
> adjusting the result is going to be a lot less than
> the cost of the division itself.

That's definitively true. My current workaround for

k = modulo(m,n);

in places where I'm unable to work around the missing "modulo" functionality of C/C++ is to write

k = ((m%n)+n)%n

Based on the information from Kim Barrett,

k = m >= 0 ? m%n : (m%n) + n;

should also work (that's a bit longer than the old form, but looks more efficient, and I could write a "modulo" template encapsulating this functionality for my personal use). If I'm not mistaken, this would be the most efficient workaround in case of XInt.

> Not to mention that the existing behaviour is the most natural
> and efficient to implement for the signed-magnitude
> representation that the library uses.

That's definitively true. There are probably also use cases where this definition of division and modulo is the most suitable. It just happens that I regularly encounter use cases where one of the other possible definitions would have been more suitable. 

> > > If XInt follows C99 / C++0x here, does that answer your complaint?
> >
> > Probably not, because this was a complaint about C/C++, not about
> > XInt. This complaint was in response to Steven asking "Are the basic
> > operations that are provided not enough for some algorithm that you
> > care about?". From my experience with C/C++, I could answer this
> > question with a definitive "Yes, the basic operations provided by C/C++
> > for integer numbers are not enough for some algorithms that I care
> > about!". I know that this is a review of XInt, but as I have much more
> > experience with C/C++, it makes sense to answer this question for C/C++
> > instead, which XInt tries to follow for consistency reasons.
> 
> I'm afraid that what you've said doesn't help me at all
> You've mentioned that you don't like the way division
> is defined, and you've mentioned FFT's, but you haven't
> made any attempt to explain how this is a real problem
> for XInt. This isn't about implementability. An FFT can
> be implemented using only basic math operations. It's
> a matter of efficiency. And for this, you can't generalize
> from the builtin types to XInt because the performance
> characteristics are significantly different.

I was delighted that you tried to answer to this. I agree that the use cases of XInt and normal C/C++ integers are hardly comparable, so it's probably not possible to generalize from experiences with the builtin types to XInt.

(Side note: I wasn't talking about implementing an FFT, but simply about working with the data structures that occur in this context. With this I just mean that the "zeroth" spectral order is stored at a[0], the first positive spectral order is stored at a[1], the first negative spectral order is stored at a[n-1], and similarly for the higher orders. In this context, the modulo operation where the "remainder" is always a positive number would allow me to compute the index when I have the spectral order, and the modulo operation where the absolute value of the "remainder" is as small as possible (and negative in the case where this condition is ambiguous) would allow me to compute the spectral order when I have the index.)

The question with respect to XInt was, whether the algorithms should be separated from the data structures, or whether the data structures should be an implementation detail hidden from the public interface. Even so I agree that the algorithms and data structures are not orthogonal to each other for a bigint library, I have my doubts that just saying addition, substraction, multiplication and division are the fundamental operations that a bigint library need to provide, and any other "relevant" algorithm can be ("efficiently"?) implemented in terms of these. This might not be relevant to XInt, because XInt provides more "fundamental operations" than just these "evocative" four. I can quite imagine that XInt indeed has managed to provide all important "fundamental operations", whichever these may be.

Regards,
Thomas