Forum libero

Aspe' qual'era?
M'e` passato di mente ma ce l'avevo 5 secondi fa...
AH! Le divisioni.
Si`, le divisioni invarianti per moltiplicazione.
O divisioni per moltiplicazioni invarianti.
O come cacchio le chiamano.

Concettualmente sono semplici: si approssima la divisione pre-moltiplicando tutto per 2^N (N = wordsize, 32 bit su IA-32), e poi si ri-divide per 2^N, cioe` ci si limita a prendere la word alta di una moltiplicazione a 2<sup>(2*N)</sup> bits. A seconda della dimensione in bits del denominatore, serve quel tot di bits in piu` per evitare errori di troncamento.

Pero` qui:

https://gmplib.org/~tege/divcnst-pldi94.pdf

La spiegazione della figura 4.1, paragrafo "CAUTION", dice che la formula di base e` quella (appunto, quoziente = shift right logico della somma della costante di approssimazione e del numeratore), ma che servono degli shift di aggiustamento per evitare che ci sia un overflow sull'addizione e sullo shift.

Pero`.
Non considera, mi pare, che x86 in particolare ha un'istruzione ADC (add with carry) per fare somme a 64-bit, e siccome li` l'overflow e` sempre al massimo 1 bit, basterebbe aggiungere il carry al risultato, con "ADC qh, 0" dove qh e` l'operando che contiene la word alta del quoziente), inoltre sempre x86 ha la double-precision shift right che "importa" i bits in eccesso dalla word alta. Sicche` non vorrei che considerando tutto questo in effetti si POSSA calcolare q senza preoccuparsi degli shift di aggiustamento.

Non capisco se non l'hanno considerato perche` non tenevano presenti queste istruzioni specifiche di quell'architettura, visto che hanno implementato quest'ottimizzazione in modo generico nel compilatore, oppure se non hanno tenuto presente il caso perche` anche su x86 ADC e SHRD sarebbero piu` lente.

Tanto per dire quali sono i miei "argomenti informatici" del momento.
Ma penso che la risposta dovrebbe essere "si` vabbe' ma in fondo chissenefrega".