Re: Optimizing numeric SUM() aggregate

On 27 July 2016 at 07:33, Andrew Borodin <borodin(at)octonica(dot)com> wrote:
>>I think we could do carry every 0x7FFFFFF / 10000 accumulation, couldn't we?
>
> I feel that I have to elaborate a bit. Probably my calculations are wrong.
>
> Lets assume we already have accumulated INT_MAX of 9999 digits in
> previous-place accumulator. That's almost overflow, but that's not
> overflow. Carring that accumulator to currents gives us INT_MAX/10000
> carried sum.
> So in current-place accumulator we can accumulate: ( INT_MAX - INT_MAX
> / 10000 ) / 9999, where 9999 is max value dropped in current-place
> accumulator on each addition.
> That is INT_MAX * 9999 / 99990000 or simply INT_MAX / 10000.
>
> If we use unsigned 32-bit integer that is 429496. Which is 43 times
> less frequent carring.
>
> As a bonus, we get rid of 9999 const in the code (:
>
> Please correct me if I'm wrong.
>

This is basically the same problem that has already been solved in
mul_var() and other places in numeric.c, so in this case it could be
coded using something like

accum->maxdig += NBASE - 1;
if (accum->maxdig > (INT_MAX - INT_MAX / NBASE) / (NBASE - 1))
Propagate carries...

I agree that the new code should avoid explicitly referring to
constants like 9999, and I don't think there is any reason for this
new code to assume NBASE=10000.

Regards,
Dean