utente__medio ha scritto:Per il calcolo di k_max riesco a cavarmela con una divisione intera, ma per D_max, dal momento che quel prodotto può generare un overflow, ho pensato di utilizzare il tipo double. A tal proposito è possibile calcolare D_max 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 double in questa circostanza potesse riservare qualche "sorpresa" inaspettata.
Alla fine per il calcolo di
D_max ho lasciato perdere i
double 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:
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 \( Q \) e \( D \) (e quindi per \( d \)) delle variabili intere senza segno a \(32 \) bit (uint32_t), in modo che il prodotto \( D \cdot Q \) 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 \).
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 uint32_t:
\( 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 uint64_t. 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 uint64_t. 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:
Testo nascosto, fai click qui per vederlo
- Codice:
#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);
}
- Codice:
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.
