Calcolo del numero di cifre nel cambiamento di base
Ciao, mi servirebbe calcolare il numero di cifre $d_1$ del numero $n$ nella base $b_1$ (o quantomeno una sua stima per eccesso), sapendo che lo stesso numero nella base $b_2$ presenta $d_2$ cifre.
Mi sono reso conto che
$d_1~~d_2/log_(b_2)(b_1)$
ma non saprei come ricavare una formula corretta del tipo $d_1<=...$
Ho provato ad applicare la formula $d=[log_b(n)]+1$ a $d_1$ e $d_2$, facendo sostituzioni, minorazioni e calcoli vari, ma non sono riuscito ad ottenere nulla di definitivo.
Mi sono reso conto che
$d_1~~d_2/log_(b_2)(b_1)$
ma non saprei come ricavare una formula corretta del tipo $d_1<=...$
Ho provato ad applicare la formula $d=[log_b(n)]+1$ a $d_1$ e $d_2$, facendo sostituzioni, minorazioni e calcoli vari, ma non sono riuscito ad ottenere nulla di definitivo.
Risposte
Forse ho avuto un'idea:
$d_1=[log_(b_1)(n)]+1=[log_(b_2)(n)/log_(b_2)(b_1)]+1>=[[[log_(b_2)(n)]]/log_(b_2)(b_1)]+1=[(d_2-1)/log_(b_2)(b_1)]+1$
E' corretta?
Però mi sembra che in questo modo $d_1$ risulti sottostimato...
$d_1=[log_(b_1)(n)]+1=[log_(b_2)(n)/log_(b_2)(b_1)]+1>=[[[log_(b_2)(n)]]/log_(b_2)(b_1)]+1=[(d_2-1)/log_(b_2)(b_1)]+1$
E' corretta?
Però mi sembra che in questo modo $d_1$ risulti sottostimato...
TEOREMA. Il numero di cifre $d$ per rappresentare un numero $n$ in base $b$ è uguale a
\[ d = \lfloor \log_b n \rfloor + 1 = \lceil \log_b (n + 1) \rceil. \]
DIMOSTRAZIONE. Se la rappresentazione di $n$ in base $b$ ha bisogno di $d$ cifre vuol dire che la $d$-esima cifra è diversa da zero, ma che ogni cifra successiva è nulla. Abbiamo quindi ottenuto che
\[ n = \sum_{i=0}^{d-1} n_i\,b^i = (n_{d-1} + \epsilon)b^{d - 1} \]
dove $1 \leq n_{d - 1} < b \in \mathbb N$ e $\epsilon \in [0, 1 - 1/b^{d-1}] \in \mathbb R$. Facendone il logaritmo otteniamo
\[ \log_b\bigl((n_{d-1} + \epsilon)\,b^{d - 1}\bigr) = \log_b(n_{d-1} + \epsilon) + (d - 1) = d - 1 + \delta \]
dove $\delta \in [0, 1)$ perché $0 \leq n_{d-1} + \epsilon < b$. Abbiamo quindi dimostrato che la parte intera di $n$ è uguale a $d - 1$ (equazione a sinistra).
Per dimostrare la parte a destra è sufficiente osservare che $n + 1$ può avere due casi. Nel primo caso $b^{d-1} < n + 1 < b^d$ e quindi il suo logaritmo è uguale a $d - 1 + \gamma$ dove $\gamma \in (0, 1)$. La parte intera superiore sarà quindi uguale a $d$. Abbiamo poi invece il caso in cui $n + 1 = b^d$ e quindi il logaritmo è $d$ e la parte intera superiore ci fornisce di nuovo $d$.
OSSERVAZIONE. Se hai bisogno di $d_2$ cifre nella base $b_2$, il numero sarà inferiore o uguale a $b_2^{d_2} - 1$ e quindi puoi calcolare
\[ d_1 = \lceil \log_{b_1}(n + 1) \rceil \leq \lceil \log_{b_1}(b_2^{d_2} - 1 + 1) \rceil = \lceil d_2\,\log_{b_1}b_2 \rceil \]
\[ d = \lfloor \log_b n \rfloor + 1 = \lceil \log_b (n + 1) \rceil. \]
DIMOSTRAZIONE. Se la rappresentazione di $n$ in base $b$ ha bisogno di $d$ cifre vuol dire che la $d$-esima cifra è diversa da zero, ma che ogni cifra successiva è nulla. Abbiamo quindi ottenuto che
\[ n = \sum_{i=0}^{d-1} n_i\,b^i = (n_{d-1} + \epsilon)b^{d - 1} \]
dove $1 \leq n_{d - 1} < b \in \mathbb N$ e $\epsilon \in [0, 1 - 1/b^{d-1}] \in \mathbb R$. Facendone il logaritmo otteniamo
\[ \log_b\bigl((n_{d-1} + \epsilon)\,b^{d - 1}\bigr) = \log_b(n_{d-1} + \epsilon) + (d - 1) = d - 1 + \delta \]
dove $\delta \in [0, 1)$ perché $0 \leq n_{d-1} + \epsilon < b$. Abbiamo quindi dimostrato che la parte intera di $n$ è uguale a $d - 1$ (equazione a sinistra).
Per dimostrare la parte a destra è sufficiente osservare che $n + 1$ può avere due casi. Nel primo caso $b^{d-1} < n + 1 < b^d$ e quindi il suo logaritmo è uguale a $d - 1 + \gamma$ dove $\gamma \in (0, 1)$. La parte intera superiore sarà quindi uguale a $d$. Abbiamo poi invece il caso in cui $n + 1 = b^d$ e quindi il logaritmo è $d$ e la parte intera superiore ci fornisce di nuovo $d$.
OSSERVAZIONE. Se hai bisogno di $d_2$ cifre nella base $b_2$, il numero sarà inferiore o uguale a $b_2^{d_2} - 1$ e quindi puoi calcolare
\[ d_1 = \lceil \log_{b_1}(n + 1) \rceil \leq \lceil \log_{b_1}(b_2^{d_2} - 1 + 1) \rceil = \lceil d_2\,\log_{b_1}b_2 \rceil \]
Come verifica è comodo fare i calcoli con potenze di $2$. Per esempio, se hai bisogno di $3$ byte (base $2^8$), di quanti bit hai bisogno? Nella mia formula otteniamo $3*8 = 24$. Nella tua $[2/(1/8)] + 1 = 17$ che è effettivamente inferiore. Il problema è che invece di cercare una maggiorazione del logaritmo e usando $d_2$, hai preso una minorazione ottenendo un risultato meno utile.
"apatriarca":
Il problema è che invece di cercare una maggiorazione del logaritmo e usando $d_2$, hai preso una minorazione ottenendo un risultato meno utile.
Giusto, non so perché ho utilizzato una minorazione... ci riprovo:
[size=125]\( d_1 = \lfloor \log_{b_1}(n) \rfloor + 1 = \lfloor \frac {\log_{b_2}(n)}{\log_{b_2}(b_1)} \rfloor + 1 \leq \lfloor \frac {\lfloor \log_{b_2}(n) \rfloor+1}{\log_{b_2}(b_1)} \rfloor +1=\lfloor \frac {d_2}{\log_{b_2}(b_1)} \rfloor +1 = \lfloor d_2 \cdot \log_{b_1}(b_2) \rfloor + 1 \)[/size]
Che è quasi equivalente alla tua formula (\( \lceil d_2 \cdot \log_{b_1}(b_2) \rceil \)), tranne quando il logaritmo restituisce un intero, nel qual caso la mia formula ritorna un valore più grande di un'unità. Più o meno siamo lì, ma sarei curioso di sapere se seguendo il mio approccio sia possibile "limare" quell'unità.
Relativamente poi alla tua precedente spiegazione, devo leggermela con calma.
Detto ciò, quello che mi interessa praticamente è ricavare $d$ passando per le due basi $10^9$ e $2^32$.
Qualcosa del genere può andare?
#include <iostream>
#include <cmath>
using namespace std;
const uint32_t _10to9 = 1'000'000'000;
const uint64_t _2to32 = (uint64_t)1 << 32;
const double to_2to32 = log(_10to9) / log(_2to32);
const double to_10to9 = 1 / to_2to32;
uint64_t fun(const uint64_t d, const bool flag_to_2to32)
{
return uint64_t(d * (flag_to_2to32 ? to_2to32 : to_10to9)) + 1;
}
int main()
{
uint64_t d = 2000;
cout << (d = fun(d, true)) << "\n";
cout << fun(d, false) << "\n";
}O i numeri in virgola mobile potrebbero riservare qualche strana sorpresa?
Vale la pena ingegnarsi limitandosi all'utilizzo di sole variabili intere? E in tal caso quante cifre decimali sarebbero necessarie per assicurare un risultato "corretto"?
EDIT: Nel caso sarebbe possibile fare una stima per eccesso anche meno accurata per passare dal numero di cifre in base $10^9$ a quello in base $2^32$ e viceversa?
Puoi ovviamente spostare il $d_2$ al di fuori della parte intera superiore ottenendo:
\[ d_{2^{32}} \leq d_{10^9} \left\lceil \frac{9}{32} \log_2 10 \right\rceil = d_{10^9} \]
e viceversa
\[ d_{10^9} \leq d_{2^{32}} \left\lceil \frac{32}{9} \log_{10} 2 \right\rceil = 2\,d_{2^{32}}. \]
La seconda non è molto vicina ovviamente. Puoi alternativamente prendere delle approssimazioni per eccesso dei due logaritmi e quindi usare qualcosa come
\[ d_{2^{32}} \leq \lceil 0.94\,d_{10^9} \rceil \quad d_{10^9} \leq \lceil 1.08\,d_{2^{32}} \rceil. \]
\[ d_{2^{32}} \leq d_{10^9} \left\lceil \frac{9}{32} \log_2 10 \right\rceil = d_{10^9} \]
e viceversa
\[ d_{10^9} \leq d_{2^{32}} \left\lceil \frac{32}{9} \log_{10} 2 \right\rceil = 2\,d_{2^{32}}. \]
La seconda non è molto vicina ovviamente. Puoi alternativamente prendere delle approssimazioni per eccesso dei due logaritmi e quindi usare qualcosa come
\[ d_{2^{32}} \leq \lceil 0.94\,d_{10^9} \rceil \quad d_{10^9} \leq \lceil 1.08\,d_{2^{32}} \rceil. \]
Nota che nella prima approssimazione, sbagli di circa una unità ogni 16. Per cui qualcosa come
\[ d_{10^9} - \lfloor d_{10^9}/16 \rfloor \]
funzionerebbe molto bene e può essere calcolando usando solo i numeri interi (la seconda parte è semplicemente uno shift destro). Su $1000$ cifre in base $2^{32}$ ottieni $938$ usando questa formula e $935$ usando l'approssimazione più precisa. Un errore di $3$ ogni $1000$ mi sembra più che accettabile. Ovviamente puoi volendo aggiungere anche un fattore $3/1024$ per migliorare ulteriormente l'approssimazione.
Per la seconda non ho trovato una formula ugualmente elegante.
\[ d_{10^9} - \lfloor d_{10^9}/16 \rfloor \]
funzionerebbe molto bene e può essere calcolando usando solo i numeri interi (la seconda parte è semplicemente uno shift destro). Su $1000$ cifre in base $2^{32}$ ottieni $938$ usando questa formula e $935$ usando l'approssimazione più precisa. Un errore di $3$ ogni $1000$ mi sembra più che accettabile. Ovviamente puoi volendo aggiungere anche un fattore $3/1024$ per migliorare ulteriormente l'approssimazione.
Per la seconda non ho trovato una formula ugualmente elegante.
"apatriarca":
Puoi alternativamente prendere delle approssimazioni per eccesso dei due logaritmi e quindi usare qualcosa come
\[ d_{2^{32}} \leq \lceil 0.94\,d_{10^9} \rceil \quad d_{10^9} \leq \lceil 1.08\,d_{2^{32}} \rceil. \]
Ci avevo pensato, e in particolare riflettevo su come farlo usando solo gli interi.
"apatriarca":
Nota che nella prima approssimazione, sbagli di circa una unità ogni 16. Per cui qualcosa come
\[ d_{10^9} - \lfloor d_{10^9}/16 \rfloor \]
funzionerebbe molto bene
Ho provato a sviluppare i calcoli, ma mi sembra che la maggiorazione tra le due seguenti righe non regga:
[size=120]\( d_{2^{32}} \leq \lceil 0.94 \cdot d_{10^9} \rceil = \lceil (1-0.06) \cdot d_{10^9} \rceil = d_{10^9} - \lceil 0.06 \cdot d_{10^9} \rceil \)[/size]
[size=120]\( d_{10^9} - \lfloor 0,0625 \cdot d_{10^9} \rfloor = d_{10^9} - \lfloor \frac{d_{10^9}}{16} \rfloor \)[/size]
Mi sono perso qualcosa?
Ne approfitto per chiedere anche un'altra cosa.
Consideriamo il seguente codice:
Premesso che come già detto altre volte non ho molta confidenza con i numeri in virgola mobile, mi chiedevo se un arrotondamento per eccesso ad una certa cifra decimale di $a$ costituisca effettivamente una maggiorazione rispetto al valore "corretto", ossia se la seguente relazione (dove per esempio ho arrotondato $a$ alla quarta cifra decimale) sia vera:
$0.9343>=log_(2^32)(10^9)$
E in tal caso resterà vera fino a quale cifra decimale?
Il mio dubbio nasce dal fatto che presumo che i due logaritmi e la divisione effettuati per il calcolo di $a$ abbiano già comportato una perdita di precisione, o sbaglio? E se mi sbagliassi allora anche
andrà bene per qualsiasi valore di $d_2$, che sia esso un [inline]uint32_t[/inline] o un [inline]uint64_t[/inline]?
Consideriamo il seguente codice:
#include <iostream>
#include <cmath>
using namespace std;
const uint32_t _10to9 = 1'000'000'000;
const uint64_t _2to32 = (uint64_t)1 << 32;
int main()
{
double a = log(_10to9) / log(_2to32);
cout << a << "\n";
}0.934292 Process returned 0 (0x0) execution time : 0.011 s
Premesso che come già detto altre volte non ho molta confidenza con i numeri in virgola mobile, mi chiedevo se un arrotondamento per eccesso ad una certa cifra decimale di $a$ costituisca effettivamente una maggiorazione rispetto al valore "corretto", ossia se la seguente relazione (dove per esempio ho arrotondato $a$ alla quarta cifra decimale) sia vera:
$0.9343>=log_(2^32)(10^9)$
E in tal caso resterà vera fino a quale cifra decimale?
Il mio dubbio nasce dal fatto che presumo che i due logaritmi e la divisione effettuati per il calcolo di $a$ abbiano già comportato una perdita di precisione, o sbaglio? E se mi sbagliassi allora anche
uint64_t d_1 = ceil((double)d_2 * 0.9343);
andrà bene per qualsiasi valore di $d_2$, che sia esso un [inline]uint32_t[/inline] o un [inline]uint64_t[/inline]?
Siccome \(1/16 = 0.0625\) mentre \(\log_{2^{32}}(10^9) < 0.9343\) abbiamo che
\[ 1 - 1/16 = 0.9375 > 0.9343 > \log_{2^{32}}(10^9). \]
Abbiamo quindi
\[ d_{2^{32}} = \lceil d_{10^9}\,\log_{2^{32}}(10^9) \rceil \leq \lceil d_{10^9}\,(1 - 1/16) \rceil \leq \lceil d_{10^9} - \lfloor d_{10^9}/16 \rfloor \rceil = d_{10^9} - \lfloor d_{10^9}/16 \rfloor. \]
Il terzo passaggio fa uso del fatto che la parte intera è sempre inferiore al numero e quindi quando sottrai tale numero ottieni un valore uguale o maggiore. L'ultimo passaggio fa invece uso del fatto che a quel punto il numero è intero e quindi la sua parte intera superiore è uguale al numero.
\[ 1 - 1/16 = 0.9375 > 0.9343 > \log_{2^{32}}(10^9). \]
Abbiamo quindi
\[ d_{2^{32}} = \lceil d_{10^9}\,\log_{2^{32}}(10^9) \rceil \leq \lceil d_{10^9}\,(1 - 1/16) \rceil \leq \lceil d_{10^9} - \lfloor d_{10^9}/16 \rfloor \rceil = d_{10^9} - \lfloor d_{10^9}/16 \rfloor. \]
Il terzo passaggio fa uso del fatto che la parte intera è sempre inferiore al numero e quindi quando sottrai tale numero ottieni un valore uguale o maggiore. L'ultimo passaggio fa invece uso del fatto che a quel punto il numero è intero e quindi la sua parte intera superiore è uguale al numero.
Non c'è alcuna garanzia che il numero da te calcolando usando il logaritmo in virgola mobile fornisca una maggiorazione in quanto il valore viene arrotondato (potenzialmente anche per difetto quindi). Non ti saprei tuttavia dire se e quando fallirà.
Se fai un arrotondamento per eccesso hai invece la sicurezza sarà sempre maggiore ma potrebbe fornire valori più grandi del necessario. Non è difficile capire a che ordine di grandezza avrai valori sempre sbagliati (ci saranno anche singoli valori sbagliati prima ma sono casi isolati). È sufficiente guardare quando l'errore diventerà più grande di una unità. Nel tuo caso (\(0.9343\)) hai un errore di circa $7.7 \times 10^{-6}$ e devi moltiplicarlo per circa \(1.3 \times 10^5\) perché la differenza nel numero dentro la parte intera sia maggiore di uno. Nel caso della mia formula intera hai invece che ne sono sufficienti \(300\).
Se fai un arrotondamento per eccesso hai invece la sicurezza sarà sempre maggiore ma potrebbe fornire valori più grandi del necessario. Non è difficile capire a che ordine di grandezza avrai valori sempre sbagliati (ci saranno anche singoli valori sbagliati prima ma sono casi isolati). È sufficiente guardare quando l'errore diventerà più grande di una unità. Nel tuo caso (\(0.9343\)) hai un errore di circa $7.7 \times 10^{-6}$ e devi moltiplicarlo per circa \(1.3 \times 10^5\) perché la differenza nel numero dentro la parte intera sia maggiore di uno. Nel caso della mia formula intera hai invece che ne sono sufficienti \(300\).
Per avere la stessa precisione dell'approssimazione $0.9343$ dovresti usare qualcosa come [tt]d - (d >> 4) - (d >> 9) - (d >> 10) - (d >> 12) - (d >> 15)[/tt]. Ho scritto il calcolo in questo modo assumendo di avere a che fare con ogni possibile valore in un intero a [tt]64[/tt] bit. Se il range è più basso puoi anche semplicemente calcolare un'approssimazione razionale del valore e usare quella.
"apatriarca":
Siccome \( 1/16 = 0.0625 \) mentre \( \log_{2^{32}}(10^9) < 0.9343 \) abbiamo che
\[ 1 - 1/16 = 0.9375 > 0.9343 > \log_{2^{32}}(10^9). \]
Abbiamo quindi
\[ d_{2^{32}} = \lceil d_{10^9}\,\log_{2^{32}}(10^9) \rceil \leq \lceil d_{10^9}\,(1 - 1/16) \rceil \leq \lceil d_{10^9} - \lfloor d_{10^9}/16 \rfloor \rceil = d_{10^9} - \lfloor d_{10^9}/16 \rfloor. \]
Il terzo passaggio fa uso del fatto che la parte intera è sempre inferiore al numero e quindi quando sottrai tale numero ottieni un valore uguale o maggiore. L'ultimo passaggio fa invece uso del fatto che a quel punto il numero è intero e quindi la sua parte intera superiore è uguale al numero.
Chiaro, grazie!
"apatriarca":
Se fai un arrotondamento per eccesso hai invece la sicurezza sarà sempre maggiore
Ovviamente
\( \lceil \log_{2^{32}}(10^9) \rceil _{n, \ b} \geq \log_{2^{32}}(10^9) \)
ora, per $n=4$ e base $b=10$, dall'output del codice qui postato si deduce che dovrebbe essere
\( \lceil \log_{2^{32}}(10^9) \rceil _{4, \ 10} = 0.9343 \)
Il punto è come calcolare correttamente in C++ il valore \( \lceil \log_{2^{32}}(10^9) \rceil _{n, \ b} \) e fino a quale valore di $n$ è possibile farlo. Io avrei pensato a
ceil(log(_10to9) / log(_2to32) * pow(b, n)) / pow(b, n)
con $n_(max)(b=2)=53$ (che sono i bit della mantissa di un double) e \( n_{max}(b=10)= \lfloor \log_{10}(2^{53}) \rfloor = 15 \)
E' corretto? Ho la sicurezza che fino a $n_(max)$ la suddetta riga di codice restituirà esattamente il valore \( \lceil \log_{2^{32}}(10^9) \rceil _{n, \ b} \) ?
Devi calcolarlo durante l'esecuzione o è qualcosa che ti serve solo per valori specifici conosciuti durante la compilazione? Se è il secondo caso allora credo sia meglio scrivere direttamente il valore.
"apatriarca":
Devi calcolarlo durante l'esecuzione o è qualcosa che ti serve solo per valori specifici conosciuti durante la compilazione? Se è il secondo caso allora credo sia meglio scrivere direttamente il valore.
Come già detto, quello che mi serve è calcolare il numero di cifre (o una sua stima per eccesso) necessarie per convertire uno stesso numero dalla base $10^9$ alla base $2^32$ e viceversa.
Poi l'idea di scrivere direttamente un valore non mi piace più di tanto, preferirei inserire il calcolo di tale costante.
Provo a tirare le somme e mostrare quello che praticamente avrei pensato di fare.
Considerando
"utente__medio":
[size=125]\( d_1 = \lfloor \log_{b_1}(n) \rfloor + 1 = \lfloor \frac {\log_{b_2}(n)}{\log_{b_2}(b_1)} \rfloor + 1 \leq \lfloor \frac {\lfloor \log_{b_2}(n) \rfloor+1}{\log_{b_2}(b_1)} \rfloor +1=\lfloor \frac {d_2}{\log_{b_2}(b_1)} \rfloor +1 = \lfloor d_2 \cdot \log_{b_1}(b_2) \rfloor + 1 \)[/size]
e indicando con [size=120]\( \lceil ... \rceil_{n , \ b} \)[/size] un'arrotondamento per eccesso all $n$-esima cifra frazionaria nella base $b$, si ricava che:
[size=125]\( d_1 \leq \lfloor d_2 \cdot \log_{b_1}(b_2) \rfloor + 1 \leq \lfloor d_2 \cdot \lceil \log_{b_1}(b_2) \rceil_{n , \ b} \rfloor + 1 = \lfloor \frac {d_2 \ \cdot \ ( \lceil \log_{b_1}(b_2) \rceil_{n , \ b} \cdot \ b^n)}{b^n} \rfloor + 1 = \lfloor \frac{d_2 \ \cdot \ k_1}{b^n} \rfloor + 1 \)[/size]
Che nei due casi di mio interesse diventerebbe:
- [size=125]\( \ \ d_{2^{32}} \leq \lfloor \frac{d_{10^9} \ \cdot \ k_{2^{32}}}{2^n} \rfloor + 1\)[/size] con [size=105]\( k_{2^{32}} = \lceil \log_{2^{32}}(10^9) \rceil_{n, \ 2} \cdot 2^n \)[/size] e $n=32$ ;
- [size=125]\( \ \ d_{10^9} \leq \lfloor \frac{d_{2^{32}} \ \cdot \ k_{10^9}}{2^n} \rfloor + 1\)[/size] con [size=105]\( k_{10^9} = \lceil \log_{10^9}(2^{32}) \rceil_{n, \ 2} \cdot 2^n \)[/size] e $n=31$ .
Con $n$ che nei due casi è stato scelto in modo che $k_{2^{32}}$ e $k_{10^9}$ fossero compresi nell'intervallo $[2^31 \ ; 2^32)$ . Quindi $n$ dipende dal numero di cifre intere di $log_(b_1)(b_2)$ in binario e dal numero di zeri frazionari iniziali.
Di seguito il mio tentativo di implementazione:
#include <iostream>
#include <cmath>
using namespace std;
const uint64_t _10to9 = 1'000'000'000;
const uint64_t _2to32 = (uint64_t)1 << 32;
const double log_2to32_10to9 = log(_10to9) / log(_2to32);
const uint32_t k_2to32 = ceil(log_2to32_10to9 * _2to32);
const uint32_t k_10to9 = ceil(1 / log_2to32_10to9 * (_2to32 >> 1));
uint64_t digit_number_approximation(const uint64_t d, const bool flag_to_2to32)
{
if(flag_to_2to32)
{
return ((uint64_t)(uint32_t)d * k_2to32 >> 32) + (d >> 32) * k_2to32 + 1;
}
uint64_t a = (uint64_t)(uint32_t)d * k_10to9;
return ((a >> 32) + (d >> 32) * k_10to9 << 1 | (uint32_t)a >> 31) + 1;
}
int main()
{
uint64_t d_10to9 = 52'840'937'621;
cout << "d_10to9 = " << d_10to9 << "\n";
uint64_t d_2to32 = digit_number_approximation(d_10to9, true);
d_10to9 = digit_number_approximation(d_2to32, false);
cout << "d_2to32 = " << d_2to32 << "\n";
cout << "d_10to9 = " << d_10to9 << "\n";
}d_10to9 = 52840937621 d_2to32 = 49368879922 d_10to9 = 52840937637 Process returned 0 (0x0) execution time : 0.012 s Press any key to continue.
Detto ciò, i miei dubbi sono i seguenti:
1) Vista la perdita di precisione dovuta ai calcoli in virgola mobile, ho la certezza che le seguenti righe di codice
(uint32_t)ceil(log(_10to9) / log(_2to32) * _2to32)
(uint32_t)ceil(log(_2to32) / log(_10to9) * (_2to32 >> 1))
restituiscano rispettivamente i valori \( \lceil \log_{2^{32}}(10^9) \rceil _{32, \ 2} \cdot 2^{32} \) e \( \lceil \log_{10^9}(2^{32}) \rceil _{31, \ 2} \cdot 2^{31} \) ?
2) Complessivamente quello che ho scritto, sia dal punto di vista matematico che informatico, è corretto? O ho commesso qualche errore?
Voglio precisare che il calcolo di [inline]d_10to9[/inline] potrebbe provocare un "overflow" (nel senso di "riavvolgimento") dell'[inline]uint64_t[/inline], ma non me ne preoccuperei più di tanto visto che mi sembra poco realistico pensare che [inline]d_2to32[/inline] possa assumere valori tanto grandi, e inoltre nel caso posso sempre identificare l'overflow a valle della funzione [inline]digit_number_approximation()[/inline].
3) Ho fissato gli $n$ nei due casi a $32$ e $31$ notando rispettivamente che in binario $log_(2^(32))(10^9)=0.1...$ e $log_(10^9)(2^(32))=1.0...$ . Sarebbe possibile invece automatizzarne il calcolo? Magari estraendo informazioni dalla mantissa e dall'esponente del [inline]double[/inline]?
Up
Non hai alcuna certezza che quel numero calcolato in virgola mobile sia corretto. Credo valga tuttavia la pena di usare[tt]log2[/tt] invece di [tt]log[/tt] in quanto molto più efficiente e immediato per le potenze di [tt]2[/tt]. Infatti l'esponente del tuo numero è già in pratica un'approssimazione del valore corretto che vuoi calcolare. In alternativa puoi anche usare [tt]log1p[/tt] che è più efficiente di [tt]log[/tt]. Ma lavorare con i logaritmi in base [tt]2[/tt] sembra ottimale nel tuo caso.
"utente__medio":
Vista la perdita di precisione dovuta ai calcoli in virgola mobile, ho la certezza che le seguenti righe di codice
(uint32_t)ceil(log(_10to9) / log(_2to32) * _2to32)
(uint32_t)ceil(log(_2to32) / log(_10to9) * (_2to32 >> 1))
restituiscano rispettivamente i valori \( \lceil \log_{2^{32}}(10^9) \rceil _{32, \ 2} \cdot 2^{32} \) e \( \lceil \log_{10^9}(2^{32}) \rceil _{31, \ 2} \cdot 2^{31} \) ?
"apatriarca":
Non hai alcuna certezza che quel numero calcolato in virgola mobile sia corretto.
C'è perdita di precisione anche restando nel range della mantissa?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo