Re: What's a formula for the maximum modulo iteration delay for Adler-32?

"Daryle Walker" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> I'm not sure which one of these groups is more appropiate.
>
> I'm working on an object-oriented variant of the Adler-32 algorithm
> (described at the end of Internet RFC 1950).  The routine involves
> additions that are modulo to 65521 (the largest prime < 2^16).  Remember
> that in doing modulo arithmetic, you can do the modulo reduction after
> each sum, or do all the adding and then reduce the result.  The
> canonical texts for the algorithm assume 32-bit registers and say that
> the modulo reduction can be delayed for 5552 steps (after that, the
> register overflows).
>
> For my version of the routine, I want to allow registers larger than 32
> bits.  On bigger computers, the 64-bit registers work faster.  For even
> more efficency, I should increase the 5552 iteration limit.
>
> My question: what should I increase it to?

On modern computers, calculating modulo with a 32 bit modulus is relatively
fast. I would stick to adding together 5552 numbers for each modulo
operation. You should find that the five thousand additions will be taking
the majority of the time. Even if you could theoreticaly descrease the
number of modulo operations on a 64-bit architecture, the performance gain
would be minimal. It is simply not worth the added complexity.

> Supplemental material in some example code gives where Adler got 5552
> from:
>
> Find the maximum natural number, n, for
>     255(n)(n + 1)/2 + (n + 1)(BASE - 1) <= MAX_INT
>
> where BASE is 65521.  For 32-bit registers, MAX_INT is (2^32 - 1),
> giving 5552 for n.
>
> While I was looking through my _Numerical Recipies_ book for the
> quadratic formula, I saw a section about "linear programming" (finding
> the best solution with less-than restraints).  That can't help me here,
> but that section ended with discussion of related subjects.  Two of
> those subjects, "quadratic programming" and "integer programming", is
> what I want to use, right?
>
> Separately, I don't want to hard code the 32-bit (5552) or 64-bit
> (unknown) solutions, I want to compute them in case my program runs on a
> computer with a different register size.  Is that fesible, or should I
> just hard-code 5552?

Yes, it is feasible, but complexity leads to obscurity, and you most likely
don't want that.

Remember KISS: Keep It Simple, (Stupid)!

-Michael.