[C] Compilatore e divisione

[utente__medio11]

Ciao, personalmente non conosco il linguaggio assembly, ma per caso da una discussione è emerso che il compilatore per effettuare la divisione intera $D/18$ effettuasse il prodotto tra $D$ e il numero $954437177$, per poi eseguire uno shift a destra di $34$ posizioni.

Dal momento che la cosa mi incuriosiva, ho deciso di rifletterci un po' su, e la prima cosa che mi è venuta in mente per "trasformare" una divisione in una moltiplicazione è quella di moltiplicare il dividendo per l'inverso del divisore:

$D/18=1/2(D/9)=1/2(D*1/9)$

Essendo $9=(1001)_2$ ho svolto la divisione $1/9$ in binario



Dal momento che $1/9$ non può essere rappresentato in binario in modo esatto, ho pensato di approssimare la parte dopo la virgola in 32 bit (in modo che, ipotizzando che anche $D$ sia un intero a 32 bit, il loro prodotto possa essere espresso attraverso una variabile intera a 64 bit):

$1/9=1/(1001)_2=(0.bar(000111))_2\approx(0.000|11100011100011100011100011100011|)_2=$

$=(11100011100011100011100011100011)_2/2^(32+3)$

In definitiva quindi ottengo che la parte intera della suddetta divisione può essere calcolata come:

$[D/18]=[1/2(D*(0.bar(000111))_2)]=D*(11100011100011100011100011100011)_2$ \(\gg(32+3+1)\)

E' evidente che i $(11100011100011100011100011100011)_2=(3817748707)_(10)$ e $36$ ottenuti siano diversi dai $954437177$ e $34$ utilizzati dal compilatore, anche se utilizzando per l'approssimazione 30 bit e non 32 i numeri tornano "quasi" del tutto:

$D*((11100011100011100011100011100011)_2$ \(\gg2)\gg34=\)

\(=D*954437176\gg34\)

"Quasi" nel senso che il secondo fattore è più piccolo di un'unità rispetto a quello utilizzato dal compilatore.

-----------------------------------------------------------------------------------------------------------------------

In generale avremo quindi che

$[D/d]=D*q$ \(\gg\) $n$

con $q$ e $n$ che sono funzione di $d$.

Ovviamente affinché questo metodo sia performante i valori di $q$ e $n$ devono essere già noti; nel mio caso ho posto [inline]d_max = 100000[/inline] e ho utilizzato gli array [inline]v_q[/inline] e [inline]v_n[/inline] per contenere rispettivamente i valori di $q$ e $n$ calcolati (dalla funzione [inline]fun()[/inline] ) per valori di $d$ appartenenti all'intervallo $[1;100000]$. Quindi per esempio per accedere ai valori di $q$ e $n$ per $d = 41$ basterà accedere rispettivamente agli elementi [inline]v_q[41][/inline] e [inline]v_n[41][/inline].

Per testare il tutto ho disabilitato le ottimizzazioni del compilatore (affinché non venissero ignorati i cicli) e ho misurato i tempi necessari a calcolare [inline]N[/inline] volte una stessa divisione in diversi scenari:

- NATIVA: si riferisce alla divisione nativa del compilatore;
- OTTIMIZZATA CON ARRAY: si riferisce alla versione da me implementata con i valori di $q$ e $n$ prelevati rispettivamente dagli array [inline]v_q[/inline] e [inline]v_n[/inline]. Inoltre non ho utilizzato la funzione [inline]optimized_division()[/inline] per velocizzare il tutto evitando le varie chiamate a funzione (visto che la parola chiave [inline]inline[/inline] non sembra fare effetto);
- OTTIMIZZATA SENZA ARRAY: come sopra, ma i valori di $q$ e $n$ sono stati estratti dai due array per risparmiare sui tempi di accesso agli array.

Un altro test sulla velocità l'ho fatto misurando i tempi necessari a calcolare [inline]N[/inline] divisioni in cui il divisore è dato da [inline]rand() + 1[/inline] (che nel mio caso va bene essendo [inline]RAND_MAX < d_max[/inline] ).

Infine ho eseguito un test simile al precedente, ma questo volta non per calcolare i tempi, ma per valutare se la divisione nativa e la divisione da me implementata restituissero sempre gli stessi risultati.

Di seguito riporto il codice e l'output che ottengo lanciandolo:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

#define MAX_d 100000

uint32_t v_q[MAX_d + 1];
uint32_t v_n[MAX_d + 1];

void fun(const uint32_t max_d)
{
    for(uint32_t d = 2; d <= max_d; ++d)
    {
        uint32_t D = 1;
        uint32_t d_2 = d;
        uint32_t q = 0;
        uint8_t n = 0;
        for(; !(D & d_2); ++n, d_2 >>= 1);
        if(d == d_2)
        {
            for(; D < d_2; ++n, D <<= 1);
            for(uint8_t i = 0; i < 32; ++i)
            {
                q <<= 1;
                if(D > d_2)
                {
                    q |= 1;
                    D -= d_2;
                }
                D <<= 1;
            }
            v_q[d] = q;
            v_n[d] = n;
        }
        else
        {
            v_q[d] = v_q[d_2];
            v_n[d] = v_n[d_2] + n;
        }
    }
}

uint32_t optimized_division(const uint32_t D, const uint32_t d)
{
    if(d < D)
    {
        return v_q[d] ? (uint64_t)D * v_q[d] >> 31 + v_n[d] : D >> v_n[d];
    }
    return d == D ? 1 : 0;
}

int main()
{
    uint32_t D = 941787252;
    uint32_t d = 36248; // <= MAX_d

    fun(MAX_d);
    printf("OK\n\n");

    uint32_t N = 50000000;
    srand(time(0));
    clock_t begin;
    clock_t end;

    begin = clock();
    for(uint32_t i = 0; i < N; ++i)
    {
        D / d;
    }
    end = clock();
    printf("%ux [ %u / %u = %u ] IN %fs (NATIVA)\n", N, D, d, D / d, (double)(end - begin) / CLOCKS_PER_SEC);

    begin = clock();
    for(uint32_t q = v_q[d], n = v_n[d], i = 0; i < N; ++i)
    {
        d < D ? (q ? (uint64_t)D * q >> 31 + n : D >> n) : (d == D ? 1 : 0);
    }
    end = clock();
    printf("%ux [ %u / %u = %u ] IN %fs (OTTIMIZZATA SENZA ARRAY)\n", N, D, d, d < D ? (v_q[d] ? (uint64_t)D * v_q[d] >> 31 + v_n[d] : D >> v_n[d]) : (d == D ? 1 : 0), (double)(end - begin) / CLOCKS_PER_SEC);

    begin = clock();
    for(uint32_t i = 0; i < N; ++i)
    {
        d < D ? (v_q[d] ? (uint64_t)D * v_q[d] >> 31 + v_n[d] : D >> v_n[d]) : (d == D ? 1 : 0);
    }
    end = clock();
    printf("%ux [ %u / %u = %u ] IN %fs (OTTIMIZZATA CON ARRAY)\n", N, D, d, d < D ? (v_q[d] ? (uint64_t)D * v_q[d] >> 31 + v_n[d] : D >> v_n[d]) : (d == D ? 1 : 0), (double)(end - begin) / CLOCKS_PER_SEC);

    begin = clock();
    for(uint32_t i = 0; i < N; ++i)
    {
        D / (rand() + 1);
    }
    end = clock();
    printf("\n%ux [ %u / (rand() + 1) ] IN %fs (NATIVA)\n", N, D, (double)(end - begin) / CLOCKS_PER_SEC);

    begin = clock();
    for(uint32_t i = 0; i < N; ++i)
    {
        d = rand() + 1;
        d < D ? (v_q[d] ? (uint64_t)D * v_q[d] >> 31 + v_n[d] : D >> v_n[d]) : (d == D ? 1 : 0);
    }
    end = clock();
    printf("%ux [ %u / (rand() + 1) ] IN %fs (OTTIMIZZATA CON ARRAY)\n", N, D, (double)(end - begin) / CLOCKS_PER_SEC);

    printf("\n------");
    for(uint32_t cont = 0, i = 0; i < N && cont < 5; ++i)
    {
        d = rand() + 1;
        if(D / d != optimized_division(D, d))
        {
            ++cont;
            printf("\n%u / %u = %u (NATIVA)", D, d, D / d);
            printf("\n%u / %u = %u (OTTIMIZZATA)\n", D, d, optimized_division(D, d));
        }
    }
    printf("------\n");
}

OK

50000000x [ 941787252 / 36248 = 25981 ] IN 0.123000s (NATIVA)
50000000x [ 941787252 / 36248 = 25981 ] IN 0.119000s (OTTIMIZZATA SENZA ARRAY)
50000000x [ 941787252 / 36248 = 25981 ] IN 0.137000s (OTTIMIZZATA CON ARRAY)

50000000x [ 941787252 / (rand() + 1) ] IN 0.732000s (NATIVA)
50000000x [ 941787252 / (rand() + 1) ] IN 0.766000s (OTTIMIZZATA CON ARRAY)

------
941787252 / 84 = 11211753 (NATIVA)
941787252 / 84 = 11211752 (OTTIMIZZATA)

941787252 / 294 = 3203358 (NATIVA)
941787252 / 294 = 3203357 (OTTIMIZZATA)

941787252 / 252 = 3737251 (NATIVA)
941787252 / 252 = 3737250 (OTTIMIZZATA)

941787252 / 14 = 67270518 (NATIVA)
941787252 / 14 = 67270517 (OTTIMIZZATA)

941787252 / 3 = 313929084 (NATIVA)
941787252 / 3 = 313929083 (OTTIMIZZATA)
------

Process returned 0 (0x0)   execution time : 1.911 s
Press any key to continue.

A questo punto le questioni sono fondamentalmente due:

- ritenete che il compilatore utilizzi per la divisione intera un approccio simile a quello da me implementato?
Dai primi due test si evince relativamente ai tempi che [inline]OTTIMIZZATA CON ARRAY > NATIVA > OTTIMIZZATA SENZA ARRAY[/inline], il che mi fa pensare che il compilatore prelevi comunque i coefficienti da qualche parte, ma che questo prelievo sia più veloce rispetto a quello fatto dagli array globali [inline]v_q[/inline] e [inline]v_n[/inline]. Concordate sul fatto che anche il compilatore deve avere già a disposizione da qualche parte questi valori? E in tal caso dove e come ci accede?

- Dal terzo test si osserva che in alcuni casi (ossia per alcuni valori di $d$), la divisione da me implementata restituisce valori che sono più piccoli di un'unità rispetto al risultato reale. Come già ipotizzato in precedenza deve esserci qualche particolare che mi sfugge e di cui non ho tenuto conto nella fase di approssimazione; infatti se aumento i valori di $q$ di un'unità, i test fatti mi restituiscono sempre il risultato corretto. Come mai?

[utente__medio11]

"utente__medio":Per il calcolo di [inline]k_max[/inline] riesco a cavarmela con una divisione intera, ma per [inline]D_max[/inline], dal momento che quel prodotto può generare un overflow, ho pensato di utilizzare il tipo [inline]double[/inline]. A tal proposito è possibile calcolare [inline]D_max[/inline] senza utilizzare variabili a virgola mobile o soluzioni troppo arzigogolate? E, visto che non ho molta esperienza con l'analisi numerica riguardante i numeri in floating point, mi chiedevo se l'utilizzo di [inline]double[/inline] in questa circostanza potesse riservare qualche "sorpresa" inaspettata.

Alla fine per il calcolo di [inline]D_max[/inline] ho lasciato perdere i [inline]double[/inline] e ho pensato ad una soluzione con gli interi.
Di seguito riprendo e integro il mio precedente post relativamente alla parte più informatica ed implementativa del problema:

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 \( Q \) e \( D \) (e quindi per \( d \)) delle variabili intere senza segno a \(32 \) bit ([inline]uint32_t[/inline]), in modo che il prodotto \( D \cdot Q \) possa essere contenuto in un [inline]uint64_t[/inline]. 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 \).
Dal punto di vista pratico \( Q \) può essere calcolato come

\( Q = q \cdot 2^n = \lceil \frac{1}{d} \rceil _{n, \ 2} \cdot \ 2^n = \lceil \frac{2^n}{d} \rceil _{0, \ 2} \)

e ipotizzando che \( d \) non sia una potenza di \( 2 \), e quindi che \( 2^n \) non sia divisibile per \( d \), si ricava

\( Q = \lceil \frac{2^n}{d} \rceil = \lfloor \frac{2^n}{d} \rfloor + 1 \)

Ponendo \( d = 2^{n_Z} + c \) con \( 0 < c < 2^{n_Z} \), ed essendo \( 0 < n_Z < n_B \), dimostriamo, anche se forse superfluo, che \( Q < 2^{n_B} \):

\( \lfloor \frac{2^n}{d} \rfloor + 1 < 2^{n_B} \ \Rightarrow \ \lfloor \frac{2^n}{d} \rfloor < 2^{n_B} - 1 \ \Rightarrow \ \frac{2^n}{d} < 2^{n_B} - 1 \ \Rightarrow \ \frac{2^{n_Z} \ \cdot \ 2^{n_B}}{2^{n_Z} + c} < 2^{n_B} - 1 \\ \Rightarrow \ 2^{n_Z} \cdot 2^{n_B} < ( 2^{n_B} - 1 ) ( 2^{n_Z} + c ) \ \Rightarrow \ c ( 2^{n_B} - 1 ) > 2^{n_Z} \)

che essendo verificata nel caso peggiore, ossia per \( c = c_{min} = 1 \) e \( n_Z = n_{Z_{max}} = n_B - 1 \), risulterà quindi sempre verificata.
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 \).

Essendo in generale \( \lfloor x \rfloor = x - y \) con \( 0 \leq y < 1 \), è possibile dimostrare che \( d \ Q - 2^n > 0 \) :

\( Q > \frac{2^n}{d} \ \Rightarrow \ \lfloor \frac{2^n}{d} \rfloor + 1 > \frac{2^n}{d} \ \Rightarrow \ \frac{2^n}{d} - y + 1 > \frac{2^n}{d} \ \Rightarrow \ y < 1 \)

A questo punto si può facilmente dimostrare che per \( k_{max} \) è possibile utilizzare un [inline]uint32_t[/inline]:

\( k_{max} < 2^{n_B} \ \Rightarrow \ \lfloor \frac{Q}{d \ Q - 2^n} \rfloor < 2^{n_B} \ \Rightarrow \ \frac{Q}{d \ Q - 2^n} < 2^{n_B} \ \Rightarrow \ Q < 2^{n_B} ( d \ Q - 2^n ) \)

Dimostriamo adesso che \( k_{max} + 1 \leq Q \):

\( k_{max} \leq Q - 1 \ \Rightarrow \ \lfloor \frac{Q}{d \ Q - 2^n} \rfloor \leq Q - 1 \ \Rightarrow \ \frac{Q}{d \ Q - 2^n} < Q - 1 + 1 \ \Rightarrow \ Q < Q ( d \ Q - 2^n ) \)

Si deduce quindi, essendo \( n < 2 \cdot n_B \) e \( \frac{k_{max} + 1}{Q} \leq 1 \) , che \( D_{max} < 2^{2 \ \cdot \ n_B} \), ossia che per \( D_{max} \) può essere utilizzato un [inline]uint64_t[/inline]. Lo stesso non si può dire però per il prodotto \( ( k_{max} + 1 ) \ 2^n \), che in alcuni casi (per esempio per \( d = 199 \)) causerebbe invece un overflow nell'ambito degli [inline]uint64_t[/inline]. Per calcolare \( D_{max} \) si può ricorrere per esempio al seguente metodo finalizzato ad evitare il calcolo diretto del suddetto prodotto (dove per semplicità poniamo \( K = k_{max} + 1 \), mentre \( Q_1 \) e \( R_1 \) rappresentano rispettivamente il quoziente (intero) e il resto della divisione \( \frac{K \ \cdot \ 2^{n_B}}{Q} \) ):

\( \frac{K \ \cdot \ 2^n}{Q} = \frac{K \ \cdot \ 2^{n_B + n_Z}}{Q} = \frac{K \ \cdot \ 2^{n_B} \ \cdot \ 2^{n_Z}}{Q} = ( \frac{K \ \cdot \ 2^{n_B}}{Q} ) \cdot 2^{n_Z} = ( Q_1 + \frac{R_1}{Q}) \cdot 2^{n_Z} = Q_1 \cdot 2^{n_Z} + \frac{R_1 \ \cdot \ 2^{n_Z}}{Q} \)

E quindi in definitiva \( D_{max} \) può essere calcolato come \( Q_1 \cdot 2^{n_Z} + \lfloor \frac{R_1 \ \cdot \ 2^{n_Z}}{Q} \rfloor \).

Questo invece il codice che ne deriva con relativo output che mostra i risultati di alcuni test:

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <time.h>

#define n_B 32
#define d_MAX 100000

typedef struct d_data_t_
{
    uint32_t Q;
    unsigned int n_Z;
    uint64_t D_max;
}   d_data_t;

d_data_t get_d_data_single_value(const uint32_t d)
{
    uint32_t Q = 0;
    unsigned int n_Z = n_B - 1;
    uint64_t k_max_plus_1_to_nB;
    uint64_t pow_2 = (uint64_t)1 << n_Z;
    if(d)
    {
        for(; !(pow_2 & d); --n_Z, pow_2 >>= 1);
        if(pow_2 != d)
        {
            Q = (pow_2 <<= n_B) / d + 1;
            k_max_plus_1_to_nB = Q / ((uint64_t)d * Q - pow_2) + 1 << n_B;
        }
    }
    return (d_data_t){Q, n_Z, Q ? (k_max_plus_1_to_nB / Q << n_Z) + (k_max_plus_1_to_nB % Q << n_Z) / Q : (uint64_t)-1};
}

uint32_t optimized_division_single_value(const uint32_t D, const uint32_t d, const d_data_t dd)
{
    if(d)
    {
        if(D <= d)
        {
            return D == d ? 1 : 0;
        }
        if(!dd.Q)
        {
            return D >> dd.n_Z;
        }
        if(D <= dd.D_max)
        {
            return (uint64_t)D * dd.Q >> dd.n_Z + n_B;
        }
    }
    exit(EXIT_FAILURE);
}

void get_d_data_from_1_to_d_max(const uint32_t d_max, d_data_t *v_dd)
{
    v_dd[1].Q = v_dd[1].n_Z = 0;
    v_dd[1].D_max = (uint64_t)-1;
    uint64_t k_max_plus_1_to_nB;
    for(uint32_t d = 2, d_; d <= d_max; ++d)
    {
        v_dd[d].n_Z = v_dd[d - 1].n_Z + (d == (uint64_t)1 << v_dd[d - 1].n_Z + 1);
        uint64_t pow_2 = (uint64_t)1 << v_dd[d].n_Z + n_B;
        if(1 & d)
        {
            v_dd[d].Q = pow_2 / d + 1;
            k_max_plus_1_to_nB = v_dd[d].Q / ((uint64_t)d * v_dd[d].Q - pow_2) + 1 << n_B;
        }
        else
        {
            for(d_ = d; !(1 & d_); d_ >>= 1);
            if(v_dd[d].Q = v_dd[d_].Q)
            {
                k_max_plus_1_to_nB = v_dd[d].Q / ((uint64_t)d * v_dd[d].Q - pow_2) + 1 << n_B;
            }
        }
        v_dd[d].D_max = v_dd[d].Q ? (k_max_plus_1_to_nB / v_dd[d].Q << v_dd[d].n_Z) + (k_max_plus_1_to_nB % v_dd[d].Q << v_dd[d].n_Z) / v_dd[d].Q : (uint64_t)-1;
    }
}

uint32_t optimized_division_from_1_to_d_max(const uint32_t D, const uint32_t d, const uint32_t d_max, const d_data_t *v_dd)
{
    if(d)
    {
        if(D <= d)
        {
            return D == d ? 1 : 0;
        }
        if(d <= d_max)
        {
            if(!v_dd[d].Q)
            {
                return D >> v_dd[d].n_Z;
            }
            if(D <= v_dd[d].D_max)
            {
                return (uint64_t)D * v_dd[d].Q >> v_dd[d].n_Z + n_B;
            }
        }
    }
    exit(EXIT_FAILURE);
}

int main()
{
    uint32_t D = 941780256;
    uint32_t d = 72538;

    d_data_t dd = get_d_data_single_value(d);

    d_data_t v_dd[d_MAX + 1];
    get_d_data_from_1_to_d_max(d_MAX, v_dd);

    printf("\n Q (d=%"PRIu32") = %"PRIu32" (VALORE SINGOLO)\n", d, dd.Q);
    printf(" Q (d=%"PRIu32") = %"PRIu32" (INTERVALLO)\n\n", d, v_dd[d].Q);
    printf(" n_Z (d=%"PRIu32") = %u (VALORE SINGOLO)\n", d, dd.n_Z);
    printf(" n_Z (d=%"PRIu32") = %u (INTERVALLO)\n\n", d, v_dd[d].n_Z);
    printf(" D_max (d=%"PRIu32") = %"PRIu64" (VALORE SINGOLO)\n", d, dd.D_max);
    printf(" D_max (d=%"PRIu32") = %"PRIu64" (INTERVALLO)\n\n", d, v_dd[d].D_max);

    printf(" %"PRIu32" / %"PRIu32" = %"PRIu32" (DIVISIONE NATIVA)\n", D, d, D / d);
    uint32_t Q_1 = optimized_division_single_value(D, d, dd);
    printf(" %"PRIu32" / %"PRIu32" = %"PRIu32" (VALORE SINGOLO)\n", D, d, Q_1);
    uint32_t Q_2 = optimized_division_from_1_to_d_max(D, d, d_MAX, v_dd);
    printf(" %"PRIu32" / %"PRIu32" = %"PRIu32" (INTERVALLO)\n", D, d, Q_2);


    uint32_t N = 50000000;
    srand(time(0));
    clock_t begin;
    clock_t end;

    begin = clock();
    for(uint32_t i = 0; i < N; ++i)
    {
        D / d;
    }
    end = clock();
    printf("\n %ux [ %u / %u = %u ] IN %fs (DIVISIONE NATIVA)\n", N, D, d, D / d, (double)(end - begin) / CLOCKS_PER_SEC);

    begin = clock();
    for(uint32_t i = 0; i < N; ++i)
    {
        optimized_division_single_value(D, d, dd);
    }
    end = clock();
    printf(" %ux [ %u / %u = %u ] IN %fs (VALORE SINGOLO)\n", N, D, d, optimized_division_single_value(D, d, dd), (double)(end - begin) / CLOCKS_PER_SEC);

    begin = clock();
    for(uint32_t i = 0; i < N; ++i)
    {
        optimized_division_from_1_to_d_max(D, d, d_MAX, v_dd);
    }
    end = clock();
    printf(" %ux [ %u / %u = %u ] IN %fs (INTERVALLO)\n", N, D, d, optimized_division_from_1_to_d_max(D, d, d_MAX, v_dd), (double)(end - begin) / CLOCKS_PER_SEC);

    begin = clock();
    for(uint32_t i = 0; i < N; ++i)
    {
        D / (rand() + 1);
    }
    end = clock();
    printf("\n %ux [ %u / (rand() + 1) ] IN %fs (DIVISIONE NATIVA)\n", N, D, (double)(end - begin) / CLOCKS_PER_SEC);

    begin = clock();
    for(uint32_t i = 0; i < N; ++i)
    {
        optimized_division_from_1_to_d_max(D, rand() + 1, d_MAX, v_dd);
    }
    end = clock();
    printf(" %ux [ %u / (rand() + 1) ] IN %fs (INTERVALLO)\n", N, D, (double)(end - begin) / CLOCKS_PER_SEC);
}

 Q (d=72538) = 3880379618 (VALORE SINGOLO)
 Q (d=72538) = 3880379618 (INTERVALLO)

 n_Z (d=72538) = 16 (VALORE SINGOLO)
 n_Z (d=72538) = 16 (INTERVALLO)

 D_max (d=72538) = 14195904212 (VALORE SINGOLO)
 D_max (d=72538) = 14195904212 (INTERVALLO)

 941780256 / 72538 = 12983 (DIVISIONE NATIVA)
 941780256 / 72538 = 12983 (VALORE SINGOLO)
 941780256 / 72538 = 12983 (INTERVALLO)

 50000000x [ 941780256 / 72538 = 12983 ] IN 0.126000s (DIVISIONE NATIVA)
 50000000x [ 941780256 / 72538 = 12983 ] IN 0.444000s (VALORE SINGOLO)
 50000000x [ 941780256 / 72538 = 12983 ] IN 0.521000s (INTERVALLO)

 50000000x [ 941780256 / (rand() + 1) ] IN 0.787000s (DIVISIONE NATIVA)
 50000000x [ 941780256 / (rand() + 1) ] IN 1.228000s (INTERVALLO)

Process returned 0 (0x0)   execution time : 3.136 s
Press any key to continue.

Eventuali migliorie e/o osservazioni sono ben accette.