Re: [boost] Algebraic abstractions related to (big) integers in C++

Subject: Re: [boost] Algebraic abstractions related to (big) integers in C++
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2011-03-31 14:53:37

pavel wrote:
>  Phil wrote on Thursday, March 31, 2011 at 4:51:18:
> > I came to the conclusion that it is better to write multi-word
> addition
> > code (like the above) in assembler for each platform.
> 
> > I believe that the issues are similar on other architectures that
> have
> > a flag register, but maybe others can confirm or deny that.
> 
> > Any thoughts anyone?
> 
> taking into account luke's message about adc_pi, i think that it's a
> perfect opportunity to abstract multiword addition (with carry) like
> this:
> 
>   unsigned add_with_carry(unsigned *dest, const unsigned *src, size_t
> size);
> 
> the returned value is intended to be an overflow flag (read: carry of
> the result of the most significant word addition)
> 
> that is the returned value is 0 or 1 (or even 2)
> 
> obviously, inside the function one may implement any incredible (asm?)
> code (possibly involving sse/avx/altivec/etc.)

So you actually tried to "start" a C-interface for a bigint library. It's actually an interesting idea to think about a pure C interface for such bigint functionality, because the best case scenario would be that compiler vendors provide efficient implementations of such an interface. However, coming up with a good C interface here might be a similar challenge than designing a complete bigint library, possibly even more difficult.

The answer Phil gave you to quite surprised me:

Phil Endecott wrote:
> What you describe is the sort of thing I (and I presume others)
> had in mind when we suggested that arithmetic algorithms
> be decoupled from data structures"

It is indeed a good idea, but I had interpreted this suggestion always the other way round. I thought that the main application of this was to implement more algorithms (for example different versions of multiplication), but reusing the existing algorithms definitively also makes sense. But for Phil's use case scenario, restricting the integer types accepted by the algorithms might be important (only unsigned for example, but maybe even more restrictive).

Regards,
Thomas