2009-04-20 14 views
5

Qualcuno può spiegarmi come la divisione in MIX (da TAOCP di Knuth) funziona su base byte-byte?Come funziona la divisione in MIX?

rA = |-| . . . .0| 

rX = |+|1235|0|3|1| 

La posizione di memoria 1000 contiene |-|0|0|0|2|0|.

Quando si esegue l'operazione

DIV 1000 

registri diventano

rA = |+|0|617|?|?| 

rX = |-|0|0|0|?|1| 

Ora capisco i segni sulla rA e rX, ma in quale ordine sono i byte di rAX riempiti e che le divisioni sono fatto?

Se DIV 1000 porta ad ogni bit diviso 2, allora ci si aspetterebbe

rAX = |+|617|0|1|0|-|0|1|0|1|1| 

in cui rA contiene i risultati di divisione e rX i restanti (riempiti dal lato destro).

Probabilmente mi manca qualcosa qui, e Knuth sembra pensare che dovrei essere in grado di capirlo da solo (da qui le domande di livello 10 a riguardo, che anch'io non ottengo), ma qualcuno potrebbe aiutarmi Qui?

risposta

3

Quindi l'ho capito da solo.

Se si esegue la divisione manualmente, convertendo i byte in un numero singolo si otterrà -210,501,825 (se si utilizza il più piccolo tipo di byte, ovvero 6 bit (!) Nel libro di Knuths). Dividi questo per -128, che è il valore in posizione 1000 usando lo stesso byte.

Il quoziente è 1644545, il resto 65, il segno sarà postivo poiché entrambi i numeri sono negativi. Se si memorizzano 1.644.545 nel rA e 65 in Rx, si otterrà

|+|0|6|17|32|01| 
|-|0|0|0|1|1| 

utilizzando il più piccolo bytesize (che detiene 64 numeri). Poiché Knuth non assume mai un particolare byte nei suoi esempi, rX ha un certo numero di punti interrogativi. Il segno di rX è sempre il segno precedente di rA.

Modifica: Ho utilizzato il pratico strumento di utilità MixEmul per giocare con i registri di MIX. Questa è una bella implementazione MIX fatta in .NET