venerdì 7 giugno 2013

Doomsday+1


Apparentemente, dividere per quattro o per sette un numero di taglia moderata non è un'operazione del tutto agevole. Per questo motivo, nel 1973 Conway propose di rimpiazzare la formula$$ y=\left( x + \left\lfloor \frac{x}{4} \right\rfloor \right) \bmod 7 $$ con l'equivalente$$ y=\left( \left\lfloor \frac{x}{12} \right\rfloor + x \bmod 12 + \left\lfloor \frac{x \bmod 12}{4} \right\rfloor \right) \bmod 7 \quad,$$ che richiede la manipolazione di numeri più piccoli. In effetti, i primi due termini della somma sono quoziente e resto della divisione euclidea $x:12$, e il terzo si ricava facilmente dal secondo. Ad esempio (cfr. con il post di ieri), per $x=71=5\cdot12+11$ occorre calcolare $$ \left(5+11+\left\lfloor\frac{11}{4}\right\rfloor\right) \bmod 7 = \underbrace{\left(5+11+2\right) \bmod 7}_{18\,{\rm mod}\,7} =4 $$ e per $x=7=0\cdot12+7$ $$\left(0+7+\left\lfloor\frac{7}{4}\right\rfloor\right) \bmod 7 = \underbrace{(0+7+1)\bmod 7 }_{8\,{\rm mod}\,7}= 1 \;. $$ 

Nessun commento:

Posta un commento