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

Subject: Re: [boost] Algebraic abstractions related to (big) integers in C++
From: pavel (paul.cpprules_at_[hidden])
Date: 2011-03-31 13:14:18

 Phil wrote on Thursday, March 31, 2011 at 20:41:08:
> 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...

not exactly the thing

here i propose a concrete function (to be part of the runtime library)

>  i.e. you would have
> template <typename ITER, typename CONST_ITER>
> carry_type add_with_carry(ITER dest_begin, ITER dest_end,
>                            CONST_ITER src_begin, CONST_ITER src_end);

> with a general-purpose implementation, and then specialise it:

> carry_type add_with_carry(uint32_t* dest_begin, uint32_t* dest_end,
>                            const uint32_t* src_begin, const uint32_t* src_end);

> and provide an asm implementation for the specialisation.

what is the reason for template function? what is the semantics of the
function (what does it do)? requirements for iterators? underlying
types? containers? 

> However, this doesn't suit the SIMD instruction that Luke described.  
> That does multiple adds in parallel, and has carry-in and carry-out to
> each, but those carries are NOT propagated from one adder to its 
> neighbour in that same instruction.  So to use that instruction 
> efficiently, say you are adding 4 multi-word numbers together:

>      R = A + B + C + D;

> You would do

>      (tmp1, carries1) = A + B;
>      (tmp2, carries2) = tmp1 + C + carries1;
>      (tmp3, carries3) = tmp2 + D + carries2;
>      R = tmp3 + carries3;

> Note that the +s in the first 3 lines use the SIMD instruction Luke 
> described, and the temporaries are incomplete.  In the last line, the 
> carries are added in (with the carry potentially propagating across the
> whole width); this may need one instruction per word.

> In hardware this is called a "carry save adder"; I'm not sure if the 
> SIMD people use the same terminology.

i figured out myself that this simd instruction operates "vertically"
rather than "horizontally"

but thanks for explanation anyway

> Anyway, the point is that even a multi-word addition abstraction is not
> specialisable in a way that fully exploits SIMD instructions.  Doing 
> that probably needs expression templates.

for the "a + b + c" case -- possibly

the question here is: is it practical?

but i guess this is far from the original "nice to have
add_with_carry abstraction" discussion

-- 
Pavel
P.S.
if you notice a grammar mistake or weird phrasing in my message
please point it out