canapa ha scritto:
Interessante
discussione sulla programmazione del codice di Collatz.
Da quello che ho capito (da ignarante) l'applicazione non fà dei semplici calcoli matematici ma usa la tecnica del "bit shifting" che è più complesso ma molto più veloce.
E' innovazione pure questo no?
mi spiace perché quel gamer11200 è stato messo subito in difficoltà dal'admin del progetto... d'altra parte ha voluto provare a suggerire del codice scritto in modo assolutamente non ottimizzato a gente che lo fa per mestiere!
Comunque, la congettura collatz si basa sul principio 3n+1 (lo dico perché serve per il resto del discorso). Fare moltiplicazioni e divisioni con un processore è molto complesso, cioè le eseguono lentamente rispetto ad altre operazioni. Ad un primo approccio, la congettura collatz sembrerebbe basata su queste operazioni (dividi per 2 finché puoi, poi moltiplica per 3 e aggiungi 1).
Se invece la guardiamo in binario, ovvero sia con i numeri rappresentati solo da 0 e 1 (non da 0 a 9), le operazioni diventano:
1. attacca un 1 in fondo al numero binario n (così facendo esso diventa 2n+1);
2. aggiungi quest'ultimo al numero originario per somma binaria (dando 3n+1);
3. rimuovi tutti gli 0 che ci sono alla destra del numero (così facendo è come dividere per 2 in base decimale)
Si può notare come non vengano più eseguite divisioni o moltipicazioni: esse sono state trasformate in semplicissimi spostamenti di bit, operazioni che i processori eseguono alla massima velocità.
L'ottimizzazione del codice è basato su questo e mille altri trucchetti.