Re: Optimizing numeric SUM() aggregate

> if (accum->maxdig > (INT_MAX - INT_MAX / NBASE) / (NBASE - 1))
Woth noting that (INT_MAX - INT_MAX / NBASE) / (NBASE - 1) == INT_MAX
/ NBASE for any NBASE > 1
>I don't think there is any reason for this new code to assume NBASE=10000
There is a comment on line 64 stating that value 10000 is hardcoded
somewhere else, any other value is not recommended and a bunch of code
is left for historical reasons.

Best regards, Andrey Borodin, Octonica & Ural Federal University.

2016-07-27 13:57 GMT+05:00 Dean Rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com>:
> 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