Come contare il numero di cifre in numeri in basi diverse?

Question

Sto lavorando con i numeri in basi diverse (base-10, base-8, base-16, ecc.). Sto cercando di contare il numero di caratteri in ciascun numero.

Esempio

numero: ABCDEF

Numero di cifre:

So del metodo basato sulla logaritmi, ma sto affrontando alcuni problemi.

1. This Python script uscite che non è riuscito a calcolare il numero di cifre correttamente in 3.969 numeri su 1.000.000.

2. credo che il metodo che utilizza logaritmi potrebbe essere piuttosto lento

Links:

• This C program deve essere molto lento (quello che se ho un grandissimo numero?). Inoltre, non può gestire numeri in basi diverse (ad esempio, base 16).

• Non una vittima di this quanto vi PO aveva chiesto solo di base-10

---

Edit: certamente posso calcolare la lunghezza di una stringa, ma quello che mi interessa di più, è se è possibile eseguire il calcolo senza convenzione nella stringa. Vorrei conoscere l'algoritmo che potrebbe aiutare a farlo conoscendo solo la base e la base da convertire in.

Edit2:fonte-base è base 10 e la base per convertire in può essere qualsiasi altra base.

---

Come è possibile calcolare il numero di cifre in numeri in diverse basi?

Se conosco il numero in base-10, come faccio a calcolare il numero di cifre nello stesso numero convertito in base-16 (base-8, ecc.) senza eseguire la conversione?

Nota: un po 'di codice Python o C sarà molto apprezzato

Answer 1

I logaritmi non dovrebbero essere veramente lenti. E puoi facilmente calcolare i logaritmi su qualsiasi base con questa formula: logBaseN(x)=logBaseA(x)/logBaseA(N) - puoi usare ln (Base e = 2.718 ...) o logBase10 o qualunque cosa tu abbia. Quindi non si ha realmente bisogno di un programma, di un formulario deve farlo:

num_digets(N, base) = 1 + floor(log(N)/log(base)) 

dove N è il vostro numero e base la base che si desidera che il numero in

Per ulteriori spiegazioni date un'occhiata qui.: http://www.mathpath.org/concepts/Num/numdigits.htm

Answer 2

io non sono sicuro di aver capito la tua domanda. Quando dici che il tuo numero iniziale è in base b1, significa che hai una rappresentazione di esso come una stringa in base b1? Forse vuoi costruire una tabella che ti dice quale numero in base b1 corrisponde a b2, b2^2, b2^3, ...e poi confronta il tuo numero con questi numeri per vedere dove si adatta.

Altrimenti andrei con l'algoritmo che hai citato, che può essere facilmente adottato su qualsiasi base.

ingresso: il vostro intero x, la base b2 si desidera contare le cifre in

int number_of_digits (int x, int b2) { 
    int n = 0; 
    while (x >0) { 
     x/=b2; 
     n++; 
    } 
    return n; 
} 

Entrambi i metodi sono lineari solo in n..

MODIFICA: Se si desidera essere più veloce, è possibile implementarlo come ricerca binaria. Quindi puoi ottenere O (log (n)).

Answer 3

Nota la funzione NumToStr() nel codice Python è errato a causa di un off-by-one nella vostra base, dovrebbe essere:

def NumToStr(num): 
    str='' 
    while num: 
      str+=alpha[(num)%base] 
      num=(num)/base 
    return ''.join(list(reversed(str))) 

Si noti che il controllo che questa funzione restituisce il risultato corretto avrebbe rilevato l'errore (ad esempio, utilizzare alpha="").

Con questa correzione si ottiene il numero corretto di cifre usando la formula:

nDigits = int(ceil(log(nmb, base))) 

tranne per potenze esatte di base (base**0, base**1, base**2, ecc ...) in cui è esattamente uno in meno di quello che dovrebbe essere. Questo può essere risolto modificando leggermente la forumla a:

nDigits = 1 + floor(log(nmb, base)) 

noti che anche questo sembra sicuro per alcuni input (ad esempio conversione da base 10 a base 10 si dice erroneamente 3 cifre per 1000 e 6 cifre per 1000000). Questo sembra essere dovuto alla inprecision intrinseca di galleggianti, per esempio:

print floor(log(1000, 10)) 

uscite 2 anziché il previsto 3.

Per quanto riguarda la tua segnalazione relativa alle prestazioni, non mi preoccuperei dei problemi di prestazioni per un codice così banale finché non avessi eseguito il profiling/benchmarking che mostra che si tratta di un problema. Ad esempio, il tuo codice C "molto lento" richiederebbe al massimo 38 divisioni per 10 per un numero di 128 bit. Se hai bisogno di prestazioni migliori di questo, ti imbatterai nello stesso problema con qualsiasi metodo banale menzionato qui. La cosa più veloce che riesco a pensare sarebbe una funzione personalizzata log() che utilizza una combinazione di tabelle di ricerca e interpolazione lineare, ma dovresti fare attenzione alla precisione risultante.