prestazioni della funzione log10 che restituiscono un

Question

int. Oggi avevo bisogno di una funzione log10 economica, di cui ho usato solo la parte int. Supponendo che il risultato sia floored, quindi log10 di 999 sarebbe 2. Sarebbe utile scrivere una funzione da solo? E se è così, quale sarebbe il migliore per andare. Supponendo che il codice non sarebbe ottimizzato.

Le alternative a log10 Ive though of;

• utilizzare un ciclo for che divide o moltiplica per 10;
• utilizzare un parser di stringa (probabilmente estremamente costoso);
• utilizzando una funzione intero log2() moltiplicata per una costante.

Grazie in anticipo :)

Answer 1

L'operazione può essere eseguita in (veloce) tempo costante su qualsiasi architettura che abbia zeri iniziali del conteggio o istruzioni simili (che è la maggior parte delle architetture). Ecco un frammento C ho seduti intorno per calcolare il numero di cifre in base dieci, che è essenzialmente lo stesso compito (assume una gcc come compilatore e 32 bit int):

unsigned int baseTwoDigits(unsigned int x) { 
    return x ? 32 - __builtin_clz(x) : 0; 
} 

unsigned int tenToThe[] = { 
    1, 
    10, 
    100, 
    1000, 
    10000, 
    100000, 
    1000000, 
    10000000, 
    100000000, 
    1000000000, 
}; 

unsigned int baseTenDigits(unsigned int x) { 
    unsigned int guess[33] = { 
     0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 
     3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 
     6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 
     9, 9, 9 
    }; 
    unsigned int digits = guess[baseTwoDigits(x)]; 
    return digits + (x >= tenToThe[digits]); 
} 

GCC e clang compilare questo fino a ~ 10 istruzioni su x86. Con cura, è possibile renderlo più veloce ancora in fase di montaggio.

L'intuizione chiave consiste nell'utilizzare il logaritmo di base-due (estremamente economico) per ottenere una stima rapida del logaritmo di base-dieci; a quel punto abbiamo solo bisogno di confrontarci con una singola potenza di dieci per decidere se dobbiamo aggiustare l'ipotesi. Questo è molto più efficiente della ricerca attraverso più poteri di dieci per trovare quello giusto.

Se gli ingressi sono in modo preponderante polarizzato su numeri a una e due cifre, una scansione lineare a volte è più veloce; per tutte le altre distribuzioni di input, questa implementazione tende a vincere abbastanza facilmente.

Answer 2

Se si vuole avere una funzione di log più veloce è necessario approssimare il loro risultato. Per esempio. la funzione exp può essere approssimata usando un'approssimazione taylor 'corta'. Si possono trovare esempi di approssimazioni per exp, log, radice e il potere here

edit: potete trovare una breve comparsion prestazioni here

Answer 3

Beh, c'è il vecchio standby - la "funzione di registrazione dei poveri". (Se si desidera gestire più di 63 cifre intere, cambiare la prima "se" ad un "po '".)

n = 1; 
if (v >= 1e32){n += 32; v /= 1e32;} 
if (v >= 1e16){n += 16; v /= 1e16;} 
if (v >= 1e8){n += 8; v /= 1e8;} 
if (v >= 1e4){n += 4; v /= 1e4;} 
if (v >= 1e2){n += 2; v /= 1e2;} 
if (v >= 1e1){n += 1; v /= 1e1;} 

quindi se alimentate a 123.456,7, ecco come va:

n = 1; 
if (v >= 1e32) no 
if (v >= 1e16) no 
if (v >= 1e8) no 
if (v >= 1e4) yes, so n = 5, v = 12.34567 
if (v >= 1e2) no 
if (v >= 1e1) yes, so n = 6, v = 1.234567 
    so result is n = 6 

---

Ecco una variante che utilizza moltiplicazione, anziché divisione:

int n = 1; 
double d = 1, temp; 
temp = d * 1e32; if (v >= temp){n += 32; d = temp;} 
temp = d * 1e16; if (v >= temp){n += 16; d = temp;} 
temp = d * 1e8; if (v >= temp){n += 8; d = temp;} 
temp = d * 1e4; if (v >= temp){n += 4; d = temp;} 
temp = d * 1e2; if (v >= temp){n += 2; d = temp;} 
temp = d * 1e1; if (v >= temp){n += 1; d = temp;} 

e un look esecuzione come questo senso

v = 123456.7 
n = 1 
d = 1 
temp = 1e32, if (v >= 1e32) no 
temp = 1e16, if (v >= 1e16) no 
temp = 1e8, if (v >= 1e8) no 
temp = 1e4, if (v >= 1e4) yes, so n = 5, d = 1e4; 
temp = 1e6, if (v >= 1e6) no 
temp = 1e5, if (v >= 1e5) yes, so n = 6, d = 1e5; 

Answer 4

Soltanto per farlo sarebbe ciclo con sottraendo potenze di 10. This poteri possono essere calcolate e memorizzate nella tabella. Qui ad esempio in python:

table = [10**i for i in range(1, 10)] 
# [10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000] 

def fast_log10(n): 
    for i, k in enumerate(table): 
     if n - k < 0: 
      return i 

Esempio di utilizzo:

>>> fast_log10(1) 
0 
>>> fast_log10(10) 
1 
>>> fast_log10(100) 
2 
>>> fast_log10(999) 
2 
fast_log10(1000) 
3 

Inoltre è possibile usare la ricerca binaria con questa tabella. Quindi la complessità dell'algoritmo sarebbe solo O (lg (n)), dove n è il numero di cifre. Qui ad esempio con la ricerca binaria in C:

long int table[] = {10, 100, 1000, 10000, 1000000}; 
#define TABLE_LENGHT sizeof(table)/sizeof(long int) 

int bisect_log10(long int n, int s, int e) { 
    int a = (e - s)/2 + s; 
    if(s >= e) 
     return s; 
    if((table[a] - n) <= 0) 
     return bisect_log10(n, a + 1, e); 
    else 
     return bisect_log10(n, s, a); 
} 

int fast_log10(long int n){ 
    return bisect_log10(n, 0, TABLE_LENGHT); 
} 

Nota per i piccoli numeri questo metodo sarebbe più lento allora il metodo superiore. Codice completo here.

Answer 5

senza specifiche, mi limiterò a dare una risposta generale:

La funzione di registro sarà abbastanza efficace nella maggior parte delle lingue in quanto è una funzione tale base.

Il fatto che siate interessati solo ai numeri interi potrebbe darvi qualche vantaggio, ma probabilmente questo non è sufficiente per battere facilmente le soluzioni standard integrate.

Una delle poche cose che posso pensare di essere più veloce di una funzione incorporata è una ricerca di tabelle, quindi se sei interessato solo ai numeri fino a 10000, ad esempio, potresti semplicemente creare una tabella che potresti usare per cercare uno di questi valori quando ne hai bisogno.

Ovviamente questa soluzione non si ridimensionerà bene, ma potrebbe essere proprio quello che ti serve.

---

Nota a margine: Se si importano i dati, ad esempio, si può effettivamente essere più veloce di guardare la lunghezza della stringa diecty (piuttosto che prima convertire la stringa in un numero e che guardare il valore della stringa) . Ovviamente questo richiederà che l'input sia memorizzato nel formato giusto, altrimenti non ti darà nulla.