Summing of field elements. Optimal weighting algorithm.

Weighting algorithm works efficiently until "weights" of slices in processed field are high enough. In this case the width of working area near main diagonal after each iteration decreases in logarithm times (D1=LOG2N, D2=LOG2 LOG2 N etc.). Though when in slices remain two or less set bits this algorithm starts to work inefficiently. This happens because if slice has exactly two set bits, than its weight is 01b, this means that after another cycle one set bit will move to the next slice, which also can have non-zero bits, and that leads to another move of set bit. This effect is similar to movement of carry bit in binary summator and can last during several iterations of main cycle, which significantly decreases algorithm productivity.

In optimal weighting algorithm main cycle stops after slices "weight" reduced to two ( one for non-optimal algorithm ), and then sum is calculated from "weights" by transforming scalar array where they are stored. See program text below.

procedure SUMF3( refer slice outs, inf[ ]; index incap );

const

maxincap = 32; { Slicelen = N - number of filed elements }

index

outcap, flag, i, w[ maxincap + lg2 Slicelen ];

slice

sum[ ];

begin

outcap := incap + lg2 Slicelen;{ Result capacity }

slice sum[ outcap ];

for i := 0 to outcap-1 do{ Initialization of field sum }

begin

if i < incap then COPY( sum[ i ], inf[ i ] ) else CLEAR( sum[ i ] );

end;

while 0 do { Work while weight of each slice will reduce to 2 }

begin

flag := 0;

for i := 0 to outcap-1 do{ Write weights array w }

begin

WEIGHT( sum[ i ], w[ i ] );{ Weight slice }

CLEAR( sum[ i ] );{ Clear }

if w[ i ] > 2 then flag := 1{ Check convergence }

end;

if flag = 0 then break;

for i := 0 to outcap-1 do{ Write weights to field sum }

begin

CLEAR( Y );

MOVSCALAR( Y, w[ i ] );{ Write w in Y }

ROT( Y, Y, i );{ Shift }

SETWORD( sum[ 0 ], Y, i ){ Write with rotation }

end

end;

{

Now we transform array of weights so,

that it containes only ones and zeroes.

}

for i := 0 to outcap-1 do

begin

if w[ i ] = 2 then

begin

w[ i ] := 0;

w[ i+1 ] := w[ i+1 ] + 1;

end

else if w[ i ] = 3 then

begin

w[ i ] := 1;

w[ i+1 ] := w[ i+1 ] + 1;

end

end;

{

Write result to outs.

}

CLEAR( outs );

for i := 0 to outcap-1 do if w[ i ] = 1 then BITON( outs, i, 1 );

end;