Ho provato a ricapitolare il tutto riformulando alcune cose:
Testo nascosto, fai click qui per vederlo
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 \).
In questo modo viene anche meno la questione di distinguere tra
floor e troncamento, in quanto non avendo a che fare con numeri negativi le due funzioni risultano del tutto equivalenti.
Passiamo ora dalla parte più "matematica" a quella più "informatica":
Testo nascosto, fai click qui per vederlo
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 \).
Quello che ho scritto è corretto o ho commesso qualche errore?