Don't take life too seriously: it's just a temporary situation

I primi FNV sono i minimi primi della forma p = 256t + 28 + k, dove Formula per al definizione di t, tali che:

  • k < 28;

  • k sia rappresentabile in notazione binaria con 4 o 5 cifre uguali a 1, ossia sia la somma di 4 o 5 diverse potenze di 2;

  • p mod (240 – 224 – 1) > 224 + 28 + 27, ossia p mod 1099494850559 > 16777600.

 

Il loro nome è legato a un algoritmo di hashing ideato da Glenn Fowler e Phong Vo nel 1991 e successivamente migliorato da Landon Curt Noll e per questo chiamato “algoritmo FNV”.

Un algoritmo di hashing serve a calcolare, a partire da una sequenza di dati (caratteri o numeri) un numero da utilizzare come indice in una tabella, per creare strutture di ricerca particolarmente efficienti: in media si può trovare un elemento in una tabella grande a piacere, anche di miliardi di oggetti, con meno di due tentativi.

L’algoritmo FNV consiste nel partire da un intero (che dipende da n), poi per ogni dato nella sequenza moltiplicare il valore precedente per un primo FNV e calcolare l’or esclusivo bit a bit con il dato.

Il primo FNV da usare dipende dalla numero di cifre binarie 2n del valore di hashing desiderato; la forma particolare di tali primi permette di rendere molto veloce la moltiplicazione, anche per n grande, e le altre caratteristiche sperimentalmente permettono ottime prestazioni nelle ricerche nelle tabelle.

 

La tabella seguente mostra i primi FNV noti.

n

2n

t

k

p

5

32

3

147

16777619

6

64

5

179

1099511628211

7

128

11

59

309485009821345068724781371

8

256

21

99

374144419156711147060143317175368453031918731002211

9

512

43

87

35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759

10

1024

85

141

5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573

 

Inizialmente non furono cercati altri primi FNV, perché non vi è necessità di funzioni di hash che producano più di 1024 cifre binarie. Teoricamente la definizione potrebbe essere estesa a qualsiasi valore di n, tuttavia non è detto che per ogni n esista un valore di k che soddisfi le condizioni indicate; in particolare, non esistono valori validi di k, e quindi neppure primi FNV, per n da 11 a 18, neppure rinunciando alle ultime due condizioni e mantenendo solo la prima, k < 28 (M. Fiorentini, 2017); è possibile che esista un numero finito di primi FNV.

Vedi anche

Primi (numeri).

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.