07/03/2024, 23:53
apatriarca ha scritto:Molto probabilmente fa semplicemente una divisione intera invece che usare il prodotto e uno shift. In effetti qui puoi vedere che fa quello che dico.
#define n_B 32
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 D = (uint64_t)1 << n_Z;
uint64_t k_max;
uint64_t D_max;
if(d)
{
for(; !(d & D); --n_Z, D >>= 1);
if(D != d)
{
Q = (D <<= n_B) / d + 1;
k_max = Q / ((uint64_t)Q * d - D);
D_max = (k_max + 1) * (double)D / Q;
}
}
return (d_data_t){Q, n_Z, Q ? D_max : (uint64_t)-1};
}
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.
27/03/2024, 19:21
utente__medio ha scritto:Per il calcolo dik_max
riesco a cavarmela con una divisione intera, ma perD_max
, dal momento che quel prodotto può generare un overflow, ho pensato di utilizzare il tipodouble
. A tal proposito è possibile calcolareD_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 didouble
in questa circostanza potesse riservare qualche "sorpresa" inaspettata.
D_max
ho lasciato perdere i double
e ho pensato ad una soluzione con gli interi. 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 \).uint32_t
: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} \) ):#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.
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.
Powered by phpBB © phpBB Group - Privacy policy - Cookie privacy
phpBB Mobile / SEO by Artodia.