11/02/2024, 19:51
d_max = 100000
e ho utilizzato gli array v_q
e v_n
per contenere rispettivamente i valori di $q$ e $n$ calcolati (dalla funzione fun()
) 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 v_q[41]
e v_n[41]
.N
volte una stessa divisione in diversi scenari:v_q
e v_n
. Inoltre non ho utilizzato la funzione optimized_division()
per velocizzare il tutto evitando le varie chiamate a funzione (visto che la parola chiave inline
non sembra fare effetto);N
divisioni in cui il divisore è dato da rand() + 1
(che nel mio caso va bene essendo RAND_MAX < d_max
).#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.
OTTIMIZZATA CON ARRAY > NATIVA > OTTIMIZZATA SENZA ARRAY
, 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 v_q
e v_n
. 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?12/02/2024, 16:24
12/02/2024, 17:09
utente__medio ha scritto: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 OTTIMIZZATA CON ARRAY > NATIVA > OTTIMIZZATA SENZA ARRAY, 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 v_q e v_n. 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?
apatriarca ha scritto:Nota che se avessi avuto una potenza di 2 si poteva convertire tutto in uno shift che era ancora più veloce.
return v_q[d] ? (uint64_t)D * v_q[d] >> 31 + v_n[d] : D >> v_n[d];
13/02/2024, 12:28
13/02/2024, 16:54
apatriarca ha scritto:A questo punto ci rimane solo da scegliere una approssimazione abbastanza vicina per cui, se \( d \) è il nostro divisore e \( \delta \) la nostra approssimazione, allora
\[ \forall k. \; \lfloor (k\,d-1)\,\delta \rfloor = k-1. \]
Sappiamo che \( k\,d\,\delta = k + k\,\epsilon \) dove l'errore \( \epsilon < 2^{1-n} \)*. \( k \) è un intero e quindi lo possiamo estrarre ed eliminare con il corrispondente valore dall'altro lato ottenendo \( \lfloor k\epsilon - \delta \rfloor = -1 \). Dobbiamo quindi mostrare che \( 0 > k\,\epsilon - \delta > -1 \implies k\,\epsilon < \delta \) per ogni \( k \). Ogni dividendo che prendiamo in considerazione sarà minore di \( 2^{32} \) per cui scegliamo \( n \) tale che
\[ k\,\epsilon < 2^{32+1-n}/d < 1/d < \delta \implies 33 < n. \]
Abbiamo quindi ottenuto il valore e il numero di bit usato dal compilatore.
* Qui avevo inizialmente scritto \( 2^n \), ma in base ai miei esperimenti sembra che l'errore sia quello che ho scritto in seguito. Fa anche tornare i conti. La differenza credo sia dovuta al fatto che ci sono due fonti di errore: l'approssimazione di \( 2^n/d \) (con errore minore di \( 1 \) e poi lo shift \( \gg n \).
ceil()
, ossia se la parte decimale è nulla restituisce la parte intera e in caso contrario restituisce la parte intera incrementata di 1. Giusto?14/02/2024, 11:32
15/02/2024, 00:04
15/02/2024, 12:03
15/02/2024, 13:27
apatriarca ha scritto:Usando l'equazione sopra ottengo infatti che è assicurato che funzioni fino a $292$ che è ovviamente molto più piccolo del tuo valore.
15/02/2024, 21:23
δ(d, n) = ceil(1/d, digits=n, base=2)
ϵ(d, n) = δ(d, n) - 1/d
log₂ϵ(d, n) = log2(ϵ(d, n))
log₂M(d, n) = - log₂ϵ(d, n) - log2(d)
M(d, n) = exp2(log₂M(d, n))
M(7, 11)
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.