F
hallo
ich implementiere dem spass und der übung wegen adler32. hier der wikipedia-artikel dazu. die A und die B komponente sind wiefolgt definiert:
Wikipedia.org schrieb:
A = 1 + D1 + D2 + ... + Dn (mod 65521)
B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
= n×D1 + (n−1)×D2 + (n−2)×D3 + ... + Dn + n (mod 65521)
die naive implementierung wäre trivial. ich möchte jedoch unnötige modulo-operationen weglassen (auf den hinweis unter der beispiel-implementierung auf wikipeda hin).
angenommen, ich habe einen byteblock der einzig aus 2^8-1 besteht, wie hoch ist dann der intervall in welchem die modulo-operation mit A und mit B durchgeführt werden muss, damit A und B nicht overflowen (ausgehend von einem wertbereich bis 2^32-1)? man muss auch berücksichtigen, dass nach der modulo-operation mit 65521 immer noch bis zu 65520 in A und B zurückbleiben kann, das ist mir bewusst. ich habe jedoch keine ahnung wie konkret ich das ausrechnen soll. kann mir da jemand helfen?
gruss
ps.: kann auch sein, dass der thread eher in "rund um die programmierung" gehört, ich hab ihn aber mal hier rein getan weil es lediglich um die berechnung dieses intervalls geht, die implementierung ist dann simpel.
pps.: ist es von der rechenleistung her wirklich günstiger, nach xy additionen mod zu rechnen (und währenddessen immer wieder einen zähler zu inkrementieren und auf ungleichheit zu prüfen) statt nach jeder addition einen vergleich (grösser-gleich der primzahl 65521) und eine bedingte subtraktion zu machen?