Matematicamente.it

La divisione intera \( D \backslash d = \lfloor D / d \rfloor = \lfloor D \cdot \frac{1}{d} \rfloor \) (con \( D > 0 \) variabile intera e \( d > 1 \) costante intera) è una funzione costante a tratti con gradini unitari in corrispondenza dei multipli del divisore, ossia per quei valori di \( D \) esprimibili nella forma \( k \ d \) (con \( k \in N^+ \)).
Detto \( a \) un intero appartenente all'intervallo \( [ 1 \ ; \ d ) \), sarà quidi:

\( f(D) = \lfloor D \cdot \frac{1}{d} \rfloor = \begin{cases} k , \ \ \ \ \ \ \ \ \ \ \ D = k \ d \\ k - 1 , \ \ \ \ D = k \ d - a \end{cases} \)

Sia \( q = \lceil \frac{1}{d} \rceil _{n, \ b} \) un arrotondamento per eccesso di \( \frac{1}{d} \) all'\( n \)-esima cifra frazionaria nella base numerica \( b \) (ovviamente sarà \( \frac{1}{d} \leq q < 1 \)), affinché \( \lfloor D \ q \rfloor \) restituisca gli stessi risultati della divisione intera dovranno quindi essere rispettate le seguenti condizioni:

\( \begin{cases} \lfloor ( k \ d ) \ q \rfloor = k \\ \lfloor ( k \ d - a ) \ q \rfloor = k - 1 \end{cases} \Rightarrow \begin{cases} k \ d \ q \geq k \\ k \ d \ q < k + 1 \\ ( k \ d - a ) \ q \geq k - 1 \\ ( k \ d - a ) \ q < k \end{cases} \)

Introdotta la differenza \( \epsilon = q - \frac{1}{d} \geq 0 \), si evince che la prima e la terza disequazione risultano sempre verificate:

1) \( \ \ k \ d \ q \geq k \ \Rightarrow \ k \ d \ ( \epsilon + \frac{1}{d} ) - k \geq 0 \ \Rightarrow \ k \ d \ \epsilon + k - k \geq 0 \ \Rightarrow \ k \ d \ \epsilon \geq 0 \)

3) \( \ \ ( k \ d - a ) \ q \geq k - 1 \ \Rightarrow \ (k \ d - a ) ( \epsilon + \frac{1}{d} ) - k + 1 \geq 0 \ \Rightarrow \ k \ d \ \epsilon + k - a \ \epsilon - \frac{a}{d} - k + 1 \geq 0 \ \Rightarrow \ \epsilon \ ( k \ d - a ) + ( 1 - \frac{a}{d} ) \geq 0 \)

Restano quindi la seconda e la quarta disequazione:

\( \begin{cases} k \ d \ q < k + 1 \ \ \ \ \Rightarrow \ k \ d \ q - k < 1 \\ ( k \ d - a ) \ q < k \ \Rightarrow \ k \ d \ q - k < a \ q \end{cases} \)

La condizione più restrittiva è data dal minore tra i secondi membri delle due disequazioni, ossia \( q \), che si ottiene da \( a \ q \) per \( a = a_{min} = 1 \), e che risulta minore dell'unità.
Quindi in definitiva:

\( \begin{cases} \lfloor ( k \ d ) \ q \rfloor = k \\ \lfloor ( k \ d - a ) \ q \rfloor = k - 1 \end{cases} \ \Rightarrow \ k \ d \ q - k < q \ \Rightarrow \ k < \frac{q}{d \ q - 1} \ \Rightarrow \ k_{max} = \lfloor \frac{q}{d \ q - 1} \rfloor \)

A questo punto è possibile restringere il campo passando dall'intervallo \( [ k_{max} \ d \ ; \ ( k_{max} + 1 ) \ d ) \) ad un singolo valore esprimibile come \( D_{max} = k_{max} \ d + a \). Per farlo notiamo che dovrà essere:

\( \lfloor D_{max} \ q \rfloor = k_{max} \ \Rightarrow \begin{cases} D_{max} \ q \geq k_{max} \ \Rightarrow \ ( k_{max} \ d + a ) ( \epsilon + \frac{1}{d} ) - k_{max} \geq 0 \ \Rightarrow \ k_{max} \ d \ \epsilon + a \ \epsilon + \frac{a}{d} \geq 0 \\ D_{max} \ q < k_{max} + 1 \ \Rightarrow \ D_{max} < \frac{k_{max} + 1}{q} \end{cases} \)

La prima disequazione è sempre verificata e quindi dalla seconda risulta che \( D_{max} = \lfloor \frac{k_{max} + 1}{q} \rfloor \).

Volendo operare con gli interi, ed essendo in questo caso \( q = \lceil \frac{1}{d} \rceil _{n, \ 2} \), si ricava che

\( \lfloor D \ q \rfloor = \lfloor \frac {D \ ( q \ \cdot \ 2^n )}{2^n} \rfloor = \lfloor \frac {D \ \cdot \ Q}{2^n} \rfloor = D \cdot Q \gg n \)

dove è bene ricordare che l'operatore di moltiplicazione ha la precedenza su quello di right-shift.
Per farla semplice utilizziamo per \( D \) e \( Q \) delle variabili intere senza segno a \(32 \) bit (uint32_t), in modo che il loro prodotto possa essere contenuto in un uint64_t. Sarà quindi \( n = n_B + n_Z \), dove \( n_B = 32 \) è il numero di bit utilizzati per \( Q \) e \( n_Z = \lfloor \log_2(d) \rfloor \) è il numero di zeri frazionari iniziali di \( q \).
Ovviamente per l'applicabilità del metodo bisognerà sempre controllare che \( D \leq D_{max} \), con

\( k_{max} = \lfloor \frac{q}{d \ q - 1} \rfloor = \lfloor \frac{q \ \cdot \ 2^n}{( d \ q - 1 ) \ 2^n} \rfloor = \lfloor \frac{Q}{d \ Q - 2^n} \rfloor \),

\( D_{max} = \lfloor \frac{k_{max} + 1}{q} \rfloor = \lfloor \frac{ ( k_{max} + 1 ) \ 2^n}{q \ \cdot \ 2^n} \rfloor = \lfloor \frac{ ( k_{max} + 1 ) \ 2^n}{Q} \rfloor \).