Anno bisestile: sfida epica per verificarlo in 3 istruzioni CPU

Nei nostri articoli parliamo spesso di ottimizzazione software e delle buone prassi nello sviluppo dei programmi informatici. Determinare se un anno è bisestile può sembrare un problema banale, ma rappresenta in realtà un perfetto esempio di ottimizzazione nell’ambito della programmazione. Dietro una semplice regola matematica si nasconde l’opportunità di migliorare la velocità, la leggibilità e persino la portabilità del codice.

Citando lo scenario quasi distopico dello Z-Day, recentemente portato in auge da John Carmack, stella polare della storica id Software, abbiamo parlato dell’importanza di ottimizzare il software, pratica che troppo spesso viene oggi messa da parte. Soprattutto per via delle scarse limitazioni imposte dall’hardware e dell’ampia disponibilità di framework e librerie esterne.

Ancora oggi si dovrebbe invece puntare a migliorare il software facendo di più a fronte di un impegno di risorse inferiore. Piccole ottimizzazioni possono avere un impatto significativo, come nei sistemi embedded, nel calcolo ad alte prestazioni o nella verifica automatica del codice.

Impresa epica: calcolo dell’anno bisestile con 3 istruzioni CPU

Per istruzione CPU si intende un’operazione elementare che il processore può eseguire direttamente. Ogni istruzione è parte del linguaggio macchina e rappresenta un’azione specifica come sommare o sottrarre due numeri, confrontare due valori, saltare a un’altra istruzione se una condizione è vera, caricare o salvare dati in memoria.

Nel caso di un processore, difficile non significa impossibile, ma piuttosto costoso in termini di tempo e risorse. L’operazione di divisione è, ad esempio, un’operazione costosa per la CPU. Rispetto ad altre operazioni aritmetiche, come somma o moltiplicazione, la divisione richiede infatti più cicli di clock, una logica più complessa e una gestione interna più estesa.

Determinazione dell’anno bisestile: una soluzione elegante e performante

Falk Hüffner, ingegnere senior presso TomTom, ha pubblicato un post molto tecnico che ci ha immediatamente conquistati. Hüffner spiega che per calcolare istantaneamente l’anno bisestile, con circa 3 istruzioni CPU, basta usare il seguente codice C:

bool is_leap_year_fast(uint32_t y) {
    return ((y * 1073750999) & 3221352463) <= 126976;
}

Direte voi: ma è totalmente illeggibile! Cosa significano quei numeri?

In realtà, Hüffner ha messo a punto una soluzione davvero ultra-compatta, efficace ed efficiente, che usa solo tre operazioni a livello di bit.

La regola degli anni bisestili

Nel calendario gregoriano un anno è bisestile se:

• è divisibile per 4,
• ma non è divisibile per 100,
• a meno che non sia anche divisibile per 400.

Per fare qualche esempio, 2024 è divisibile per 4 e non per 100 quindi è anno bisestile; 1900 è divisibile per 4 e per 100 ma non per 400 perciò non è bisestile; 2000 è divisibile per 4, per 100 e per 400 quindi è bisestile.

Raccogliendo tutto quanto, è possibile scrivere il seguente codice C:

bool is_leap_year(uint32_t y) {
    return (y % 4 == 0) && ((y % 100 != 0) || (y % 400 == 0));
}

Prima ottimizzazione: usare operazioni più veloci

Poiché l’obiettivo è di ottimizzare al massimo il codice sviluppato, il fine è quello di rimuovere le divisioni.

Come abbiamo raccontato in precedenza, infatti, le divisioni (simbolo % nel codice C) sono lente, mentre le operazioni bit a bit sono molto più rapide. La funzione può quindi essere riscritta nel seguente modo:

bool is_leap_year_fast1(uint32_t y) {
    if ((y & 3) != 0) return false;      // y % 4 != 0
    if (y % 25 != 0) return true;        // y % 100 != 0
    return (y & 15) == 0;                // y % 400 == 0
}

L’operatore & corrisponde a un AND bit a bit. Di conseguenza, (y & 3) equivale alla precedente y % 4 ma è decisamente più veloce.

In breve, 3 in codice binario è 000...0011: y & 3 estrae gli ultimi 2 bit di y. Se y non è divisibile per 4, uno degli ultimi due bit sarà 1. Se y non è divisibile per 4, l’anno y non è bisestile.

Una tattica molto simile è utilizzata per y & 15, che sostituisce la divisione y % 400.

y % 100 != 0 è riscritto usando y % 25 != 0 perché, dato che y è già divisibile per 4, controllare y % 25 equivale a controllare y % 100.

Ottimizzazione estrema: niente più divisioni

A questo punto ci si chiede: è possibile eliminare anche y % 25? La risposta è affermativa ed è possibile farlo ricorrendo a una tecnica chiamata “divisione tramite moltiplicazione e confronto”.

Hüffner ha utilizzato Z3 (SMT Solver), un risolutore automatico sviluppato da Microsoft Research capace di verificare se esiste una soluzione che soddisfa un insieme di vincoli logici complessi, che possono includere aritmetica, array, bit-vettori, funzioni non interpretate e altro ancora.

Nell’esempio, l’ingegnere software ha usato Z3 per trovare una “moltiplicazione magica”, seguita da una maschera binaria e da un confronto che restituiscono true per gli anni bisestili, false per tutti gli altri.

Z3 ha prodotto la funzione citata in apertura:

• Moltiplicazione: y * 1073750999u – crea un numero che codifica le proprietà divisorie di y.
• Maschera bit a bit: & 3221352463u – isola i bit “interessanti” dell’output.
• Confronto: <= 126976u – se i bit isolati sono entro questa soglia, l’anno è considerato bisestile.

Il risolutore software ha individuato questi numeri sperimentando migliaia di combinazioni fino a ottenere una condizione che si comporta esattamente come la regola gregoriana per gli anni da 0 a 102499 (in pratica, ogni sistema informatico si ferma ben prima, spesso all’anno 9999). La “u” finale nei numeri indica che sono unsigned int, ovvero interi senza segno.

Il codice funziona anche con PowerShell e con altri linguaggi di programmazione

Il codice scritto in C da Hüffner usa una sintassi ottimizzata per prestazioni a basso livello. È tuttavia possibile fare qualcosa di simile in PowerShell o in altri linguaggi di alto livello come Python, JavaScript e così via, con alcune differenze importanti:

• I linguaggi ad alto livello non offrono un controllo preciso delle istruzioni CPU come il C.
• È possibile replicare la logica dell’algoritmo e ottenere un risultato molto veloce, anche se non necessariamente in “3 istruzioni CPU”.

In Windows, ad esempio, si può premere Windows+X, scegliere Windows PowerShell oppure Terminale quindi incollare quanto segue:

function Is-LeapYearFast {
    param([uint32]$y)
    return (($y * 1073750999) -band 3221352463) -le 126976
}

Come si vede, i valori sono gli stessi riportati da Hüffner. Scrivendo quindi Is-LeapYearFast seguito dall’anno (ad esempio Is-LeapYearFast 2024), si ottiene come risposta True o False, a seconda che l’anno indicato sia bisestile o meno.

Conclusioni

Controllare se un anno è bisestile sembra un’operazione semplice, ma dietro le quinte può nascondere un vero esercizio di ottimizzazione.

Nel nostro articolo abbiamo volutamente semplificato le cose e saltato alcuni passaggi intermedi per non rendere la trattazione eccessivamente pesante. L’approccio insolitamente veloce (e un po’ magico) descritto da Hüffner per calcolare se un anno è bisestile usando solo tre istruzioni della CPU è davvero affascinante. Per approfondire, è possibile fare riferimento all’approfondimento sul sito ufficiale dello sviluppatore.

Credit immagine in apertura: iStock.com – BlackJack3D