A modest proposal: eliminate template code bloat

[Dmitry Olshansky]

On 08.04.2012 22:49, Dmitry Olshansky wrote:
>
> The refinement is merging prefixes and suffixes of course.
> And for that one needs to calculate hashes for all of prefixes and all
> of suffixes. I will define _all_ later on.
>
> First observation is that if you calculated partial checksums for
> prefixes you have sums for all suffixes and vise-versa.
> Namely:
> //prefix ends on i, suffix start on i
> sum_prefix[i] = total - sum_suffix[i];
>
> that is derived from the fact that:
> total = sum_prefix[i] + sum_suffix[i];
> (taking into account the properties of +/- in the finite field)
>

Mm btw there is one step from here to use it on arbitrary common slices 
(i, j) where i < j:
slice_sum(i, j) = sum_prefix[j] - sum_prefix[i]

P.S. (Goes for walk citing a dynamic programming maxim)

-- 
Dmitry Olshansky