Hvor svær kan en checksum være at regne ud ?
Taget i betragtning hvor gammel en idé en checksum er, elsker jeg at der stadig kan gøres store fremskridt med små modifikationer af simple algoritmer.
Philip Koopman har i mange år forsket i CRC algoritmer og fundet ud af at mange af dem vi har brugt er meget langt fra at være optimale til det vi bruger dem til.
Men han har også kigget på almindelige checksums algoritmer og nogle, f.eks "Fletcher" klarer sig egentlig ret godt, mens andre ikke gør.
Undervejs fandt han en lille bitte forbedring, som gør en stor forskel.
Her er en klassisk primtals-modulus checksum:
sum = 0
for x in i:
sum = (sum + x) % 65371
return sum
Her er den kraftigt forbedrede "koopman16" version:
sum = 0
for x in i:
sum = ((sum << 16) + x) % 65371
return (sum << 16) % 65371
Og her er hvilken forskel de to 16 bit shifts gør:
Illustration: Philip Koopman.
...ca. 1000 gange mindre risiko for uopdaget fejl, i forhold til Fletcher16, helt op til 4kByte blockstørrelse.
Han har også lavet 8 og 32 bit versioner, der sammen med den matematiske forklaring på forbedringen kan læses i hans glimrende artikel.
Tip med hatten herfra!
/phk
...men det er dyrt at lave god journalistik. Derfor beder vi dig overveje at tegne abonnement på Version2.
Digitaliseringen buldrer derudaf, og it-folkene tegner fremtidens Danmark. Derfor er det vigtigere end nogensinde med et kvalificeret bud på, hvordan it bedst kan være med til at udvikle det danske samfund og erhvervsliv.
Og der har aldrig været mere akut brug for en kritisk vagthund, der råber op, når der tages forkerte it-beslutninger.
Den rolle har Version2 indtaget siden 2006 - og det bliver vi ved med.
