Wie viele Ziffern in dieser Basis?

Question

Das Problem besteht darin, eine Formel abzuleiten, um die Anzahl der Stellen zu bestimmen, die eine gegebene Dezimalzahl in einer gegebenen Basis haben könnte. Beispiel: Die Dezimalzahl 100006 kann durch 17,11,9,8,7,6,8 Ziffern in den Basen 2,3,4,5,6,7,8 dargestellt werden.

Well der Formel I bisher abgeleitet ist wie folgt: (log10 (num)/log10 (base)) + 1.

in C/C++ I diese Formel benutzt, um die oben angegebenen Ergebnisse zu berechnen.

long long int size = ((double)log10(num)/(double)log10(base)) + 1.0;

Aber leider ist die Formel nicht richtige Antwort gibt es einige Fälle, wie diese:

Number 8 in base 2 : 1,0,0,0 
Number of digits: 4 
Formula returned: 3 

Number 64 in base 2 : 1,0,0,0,0,0,0 
Number of digits: 7 
Formula returned: 6 

Number 64 in base 4 : 1,0,0,0 
Number of digits: 4 
Formula returned: 3 

Number 125 in base 5 : 1,0,0,0 
Number of digits: 4 
Formula returned: 3 

Number 128 in base 2 : 1,0,0,0,0,0,0,0 
Number of digits: 8 
Formula returned: 7 

Number 216 in base 6 : 1,0,0,0 
Number of digits: 4 
Formula returned: 3 

Number 243 in base 3 : 1,0,0,0,0,0 
Number of digits: 6 
Formula returned: 5 

Number 343 in base 7 : 1,0,0,0 
Number of digits: 4 
Formula returned: 3 

So ist der Fehler von 1 digit.I ist nur mir jemand helfen will, die zu korrigieren Formel so, dass es für alle möglichen Fälle funktioniert.

Bearbeiten: Gemäß der Eingabespezifikation habe ich mit Fällen wie 10000000000, d. H. 10^10, ich glaube nicht, log10() in C/C++ kann solche Fälle behandeln? Daher wird jede andere Prozedur/Formel für dieses Problem sehr geschätzt.

Answer 1

In Ihren Compilereinstellungen gibt es schnelle Gleitoperationen. Sie benötigen präzise Floations-Operationen. Die Sache ist, dass log10 (8)/log10 (2) immer 3 in Mathe ist. Aber vielleicht ist Ihr Ergebnis 2.99999, zum Beispiel. Es ist schlecht. Sie müssen ein kleines Additiv hinzufügen, aber nicht 0,5. Es sollte etwa 0,00001 oder so ähnlich sein.

Fast wahre Formel:

int size = static_cast<int>((log10((double)num)/log10((double)base)) + 1.00000001); 

Wirklich echte Lösung

Sie sollten das Ergebnis Ihrer Formel überprüfen. Compexity ist O(log log n) oder O(log result)!

int fast_power(int base, int s) 
{ 
    int res = 1; 
    while (s) { 
     if (s%2) { 
      res*=base; 
      s--; 
     } else { 
      s/=2; 
      base*=base; 
     } 
    } 
    return res; 
} 

int digits_size(int n, int base) 
{ 
    int s = int(log10(1.0*n)/log10(1.0*base)) + 1; 
    return fast_power(base, s) > n ? s : s+1; 
} 

Diese Kontrolle ist besser als Brute-Force-Test mit base Multiplikationen.

Answer 2

Number of digits of a numeral in a given base

Answer 3

Da die Formel korrekt ist (ich habe gerade versucht), würde ich denken, dass es in Ihrer Abteilung ein Rundungsfehler ist, so dass die Zahl nur geringfügig kleiner sein als der Integer-Wert sollte es sein. Wenn Sie also auf eine ganze Zahl abschneiden, verlieren Sie 1. Versuchen Sie, eine zusätzliche 0,5 zu Ihrem endgültigen Wert hinzuzufügen (so dass das Abschneiden tatsächlich eine runde Operation ist).

Answer 4

Es kann von Vorteil sein, eine Rundungsfunktion (zB + 0,5) irgendwo in den Code einzufügen: es ist sehr wahrscheinlich, dass die Division produziert (zB) 2.99989787, zu der 1.0 hinzugefügt wird, was 3.99989787 ergibt und zu einem konvertiert wird int, gibt es 3.

Answer 5

Eine der folgenden arbeiten:

>>> from math import * 
>>> def digits(n, b=10): 
...  return int(1 + floor(log(n, b))) if n else 1 
... 
>>> def digits(n, b=10): 
...  return int(ceil(log(n + 1, b))) if n else 1 
... 

die erste Version wird bei mathpath.org erläutert. In der zweiten Version ist die + 1 erforderlich, um die richtige Antwort für eine beliebige Zahl zu liefern n das ist die kleinste Zahl mit d Ziffern in der Basis b. Das heißt, diese Zahlen, die geschrieben werden, sind 10 ... 0 in der Basis b. Beachten Sie, dass der Eingang 0 als Sonderfall behandelt werden muss.

Dezimal Beispiele:

>>> digits(1) 
1 
>>> digits(9) 
1 
>>> digits(10) 
2 
>>> digits(99) 
2 
>>> digits(100) 
3 

Binary:

>>> digits(1, 2) 
1 
>>> digits(2, 2) 
2 
>>> digits(3, 2) 
2 
>>> digits(4, 2) 
3 
>>> digits(1027, 2) 
11 

bearbeiten: Die OP stellt fest, dass die log Lösung nicht für große Eingänge arbeiten kann.Ich weiß nicht so recht, aber wenn ja, der folgende Code sollte nicht brechen, weil es nur Integer-Arithmetik verwendet (diesmal in C):

unsigned int 
digits(unsigned long long n, unsigned long long b) 
{ 
    unsigned int d = 0; 
    while (d++, n /= b); 
    return d; 
} 

Dieser Code wahrscheinlich weniger effizient sein wird. Und ja, wurde es für maximale Unklarheiten geschrieben. Es verwendet einfach die Beobachtung, dass jede Zahl mindestens eine Ziffer hat, und dass jede Division durch b, die nicht 0 ergibt, das Vorhandensein einer zusätzlichen Ziffer impliziert. Eine lesbare Version ist die folgende:

unsigned int 
digits(unsigned long long n, unsigned long long b) 
{ 
    unsigned int d = 1; 
    while (n /= b) { 
    d++; 
    } 
    return d; 
} 

Answer 6

Sieht aus wie die Formel richtig für mich ist:

Number 8 in base 2 : 1,0,0,0 
Number of digits: 4 
Formula returned: 3 

log10(8) = 0.903089 
log10(2) = 0.301029 

Division => 3 

+1 => 4 

es ist definitiv Also nur ein Rundungsfehler.

Answer 7

Was Sie wollen, ist Decke (= kleinste ganze Zahl nicht größer als) log _b (n + 1), und nicht als das, was Sie jetzt gerade berechnet wird, Stock (1 + log _b (n)).

Sie könnten versuchen:

int digits = (int) ceil(log((double)(n+1))/log((double)base)); 

Answer 8

Arbeiten mit dem Formel

log(8)/log(2) + 1 = 4 

das Problem ist in der Genauigkeit der Logarithmusberechnung. Mit

ceil(log(n+1)/log(b)) 

sollte dieses Problem beheben. Dies ist nicht ganz dasselbe wie

ceil(log(n)/log(b)) 

, da dies die Antwort 3 für n = 8 ergibt b = 2, noch ist es das gleiche wie

log(n+1)/log(b) + 1 

, da dies die Antwort 4 für n gibt = 7 b = 2 (wenn auf volle Genauigkeit berechnet).

ich tatsächlich einige neugierig resultierende Implementierung und die erste Form mit g Kompilieren ++:

double n = double(atoi(argv[1])); 
double b = double(atoi(argv[2])); 
int i = int(std::log(n)/std::log(b) + 1.0); 

versagt (IE gibt die Antwort 3), während

double v = std::log(n)/std::log(b) + 1.0; 
int i = int(v); 

erfolgreich ist (gibt die Antwort 4). Betrachtet man es einige mehr ich eine dritte Form

ceil(log(n+0.5)/log(b)) 

wäre stabiler sein, weil es den „kritischen“ Fall vermeidet, wenn n (oder n + 1 für die zweite Form) ist eine ganzzahlige Potenz von b (für ganzzahlige Werte von n).

Answer 9

Fließkomma-Rundungsprobleme.

log10(216)/log10(6) = 2.9999999999999996 

Aber Sie können 0 nicht hinzufügen.5, wie vorgeschlagen, weil es würde vermieden, für die folgende

log10(1295) = log10(6) = 3.9995691928566091 // 5, 5, 5, 5 
log10(1296) = log10(6) = 4.0     // 1, 0, 0, 0, 0 

Vielleicht das Protokoll (Wert, Base) Funktion unter Verwendung dieser Rundungsfehler nicht funktionieren würde.

Answer 10

Wie andere gezeigt haben, haben Sie Rundungsfehler, aber die vorgeschlagenen Lösungen verschieben einfach die Gefahrenzone oder machen sie kleiner, sie eliminieren sie nicht. Wenn Ihre Zahlen Ganzzahlen sind, können Sie überprüfen - mit Ganzzahlarithmetik - dass eine Potenz der Basis kleiner oder gleich Ihrer Zahl ist, und die nächste darüber ist (die erste Potenz ist die Anzahl der Stellen). Aber wenn Sie Fließkomma-Arithmetik irgendwo in der Kette verwenden, sind Sie anfällig für Fehler (es sei denn, Ihre Basis ist eine Potenz von Zwei und vielleicht sogar dann).

EDIT:
Hier ist grobe aber effektive Lösung in Ganzzahlarithmetik. Wenn Ihre Integer-Klassen Zahlen enthalten können, die so groß sind wie die Basisanzahl, gibt dies die richtige Antwort.

 
    size = 0, k = 1; 
    while(k<=num) 
    { 
     k *= base; 
     size += 1; 
    } 

Answer 11

Ich denke, dass der einzige Weg, um den Rundungsfehler beseitigt werden, ohne andere Fehler zu erzeugen, zu verwenden oder zu implementieren Integer-Logarithmen.

Answer 12

Hier ist eine Lösung in bash:

% digits() { echo $1 $2 opq | dc | sed 's/ .//g;s/.//' | wc -c; } 


% digits 10000000000 42 
7 

Answer 13

static int numInBase(int num, int theBase) 
{ 
    if(num == 0) return 0; 
    if (num == theBase) return 1; 
    return 1 + numInBase(num/theBase,theBase); 
}