Der schnellste Weg binär zu konvertieren zu dezimal?
https://stackoverflow.com/questions/1686004
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe vier unsigned 32-Bit-Integer eine unsignierte 128-Bit-Ganzzahl, die in Little-Endian-Reihenfolge:
typedef struct {
unsigned int part[4];
} bigint_t;
Ich möchte diese Zahl in ihre Dezimalstring Darstellung konvertieren und zur Ausgabe in eine Datei.
Gerade jetzt, ich bin mit einer bigint_divmod10 Funktion die Anzahl von 10, die Verfolgung des Restes zu teilen. Ich nenne diese Funktion wiederholt, den Rest als eine Ziffer ausgegeben wird, bis die Zahl Null ist. Es ist ziemlich langsam. Ist dies der schnellste Weg, es zu tun? Wenn ja, gibt es einen cleveren Weg, um diese Funktion zu implementieren, die ich sehe, nicht wahr? Ich habe versucht, auf GMP get_str.c suchen, aber ich finde es ziemlich undurchdringlich.
EDIT: Hier ist der schnellste Code ich in der Lage war, mit der divmod10 Funktion zu kommen:
static unsigned uint128_divmod10(uint128 *value)
{
unsigned int a = value->word[3];
unsigned int b = value->word[2];
unsigned int c = value->word[1];
unsigned int d = value->word[0];
unsigned int diva = a / 5;
unsigned int divb = b / 5;
unsigned int divc = c / 5;
unsigned int divd = d / 5;
value->word[3] = diva;
value->word[2] = divb;
value->word[1] = divc;
value->word[0] = divd;
unsigned int moda = a - diva*5;
unsigned int modb = b - divb*5;
unsigned int modc = c - divc*5;
unsigned int modd = d - divd*5;
unsigned int mod = 0;
mod += moda;
unsigned int carryb = mod*858993459;
mod += modb;
if (mod >= 5) {
mod -= 5;
carryb++;
}
unsigned int carryc = mod*858993459;
mod += modc;
if (mod >= 5) {
mod -= 5;
carryc++;
}
unsigned int carryd = mod*858993459;
mod += modd;
if (mod >= 5) {
mod -= 5;
carryd++;
}
uint128_add(value, carryd, 0);
uint128_add(value, carryc, 1);
uint128_add(value, carryb, 2);
if (value->word[0] & 1) {
mod += 5;
}
uint128_shift(value, -1);
return mod;
}
Dabei stand die Add-Funktion ist wie folgt definiert:
static void uint128_add(uint128 *value, unsigned int k, unsigned int pos)
{
unsigned int a = value->word[pos];
value->word[pos] += k;
if (value->word[pos] < a) {
// overflow
for (int i=pos+1; i<4; i++) {
value->word[i]++;
if (value->word[i]) {
break;
}
}
}
}
Lösung
Es hängt davon ab, was Sie sonst noch mit den Zahlen tun. Sie können einen leichten Verlust in Raumeffizienz und ein geringen Effizienzverlust von mehrfacher Arithmetik im Gegenzug für sehr effiziente Umwandlung in und aus Dezimalzahl abwägen. Der Schlüssel ist, mit mehrfacher Arithmetik mit einer Basis zu tun, das eine Leistung von 10 eher als eine Potenz von 2.
Zum Beispiel könnten Sie die Basis 10.000 verwenden, in dem Sie eine Stelle in ein 16-Bit-Wort packen und Sie tun, um Ihre Arithmetik auf Ziffern in 32-Bit-Integer. (Wenn Sie auf einem 64-Bit-Computer sind, können Sie, dass verdoppeln und tun Basis 1000000000). Diese Art von Code relativ effizient zeitlich ist, wenn auch nicht ganz so schnell wie die native Zweierpotenz verwenden, weil Sie nicht ausnutzen können das Übertragsbit auf der Hardware. Und Sie können nicht so viele Zahlen in der gleichen Anzahl von Bits repräsentieren. Aber es ist ein Senkrechtstarter auf bei der Umwandlung und aus Dezimalzahl, weil Sie die einzelnen Ziffern ohne lange Teilung erhalten zu konvertieren.
Wenn Sie das gesamte Spektrum der Zahlen von null bis repräsentieren müssen ((1 << 128) - 1), können Sie dies noch tun, aber fügen Sie eine zusätzliche Ziffer, so dass Ihre Zahlen größer sein wird.
Wenn es sich herausstellt, was Sie wirklich brauchen die zusätzlichen Platz / Geschwindigkeit (vielleicht sind Sie eine Menge Verschlüsselungs 128-Bit-Berechnungen zu tun), dann die Methode der simultanen div / mod von 10 ist die schnellste Methode, die ich kenne. Der einzige andere Trick ist, dass, wenn kleine ganze Zahlen sind häufig, können Sie sie speziell behandeln können. (Das heißt, wenn die drei wichtigsten 32-Bit-Wörter alle Null sind, verwenden Sie einfach die native Teilung zu konvertieren.)
Gibt es einen cleveren Weg, um diese Funktion zu implementieren, die ich sehe nicht?
Dave Hanson C Schnittstellen und Realisierungen ein langes Kapitel über mehrfach Arithmetik hat. Aufteilen eine große Zahl von einer einzigen Stelle ist ein Sonderfall, der diese effiziente Implementierung hat:
int XP_quotient(int n, T z, T x, int y) {
int i;
unsigned carry = 0;
for (i = n - 1; i >= 0; i--) {
carry = carry*BASE + x[i];
z[i] = carry/y;
carry %= y;
}
return carry;
}
Für volles Verständnis, es hilft wirklich, das Buch zu haben, aber die Quellcode ist noch viel einfacher, die GNU-Quellcode zu verstehen, als. Und man konnte es leicht anpassen Basis nutzen 10.000 (derzeit verwendet Basis 256).
Zusammenfassung: Wenn Ihre Leistungsengpass Umwandlung in Dezimalzahlen ist, implementieren mehrfach Arithmetik mit einer Basis, die eine Leistung von 10 ist. Wenn Ihre Maschine native Wortgröße 32 und C-Code verwenden, verwenden 10.000 in einem 16-Bit-Wort.
Andere Tipps
Wenn Sie Ihre Werte sind meist weniger als ULLONG_MAX (18446744073709551615) Ich würde versuchen, für sie sprintf(buf,"%llu",ullong_val) zu verwenden. Ich wette, das ist ziemlich gut in Standardbibliothek optimiert, sondern von Format parsen wird einige Zyklen dauert aber.
Ansonsten würde ich einen bigint_divmod1000000000 erstellen (oder besser Name mod10to9) Funktion und verwenden. Es müßte 9-mal weniger als dividieren bigint_divmod10.
Lookup-Tabelle von 8 Bit. Sie können 4-Lookup-Tabellen von 256 Nummern. Zunächst ist 0-256 für LSB Bytes, zweite Tabelle ist die erste Tabelle mit 256 multipliziert und so weiter.
SO, wenn Sie Ihre Zahl Summe müssen bis Zahlen von Lookup-Tabelle. Wenn Sie das Hinzufügen Sie als bunary hinzufügen und später einen Durchlauf über jedes Byte gehen owerflows zu beheben.
Beispiel Zahl 0x12345678 In der ersten Tabelle ist es unter addres (0x78 = 120) so ist 0x010200 erste Zahl in der zweiten Tabelle unter (0x56 = 87) ist 0x0202000106 (0x56 in dec 22016) in Sie dritten Tabelle würde hou haben 0x03040007080702 und unter dem letzten Label bei 0x12 Sie 0x030001090809080808 (dies paßt nicht in 32-Bit-Arithmetik, sondern dass Sie allredy Know)
Dann ist diese Zahlen summieren (als binärer bumbers) und einen Durchgang gehen, Byte für Byte für Überlauf Code in for-Schleife ist so etwas wie
s=carry+val[i];
val[i]=val[i]&10
carry=s/10;
//you can put last two operations in table
Wenn wir zählen Operationen für diese benötigt werden.
1. (Suche in Tabellen und Hinzufügen) 4-Lookup-Tabellen. 16 Zugänge (denken Sie daran, dass, wenn Sie nicht über owerflow tragen müssen, becuase sie nicht OCUR können)
2. ein Durchgang in jedem Schritt 3 operatins 16 Stufen zu übergeben.
passimistic obere Schranke 6 * 16 = 100 Operationen.
EDIT:
Hier ist c ++ Code und ist 30% schneller als naive Umsetzung.
#include <iostream>
#include <stdint.h>
#include <array>
static uint64_t lu[4][256];
constexpr uint64_t lookup_value(uint64_t n) {
uint64_t r = 0;
uint64_t t = 1;
while (n) {
uint64_t rem = n % 10;
n /= 10;
r += rem * t;
t *= 256;
}
return r;
}
void make_lu() {
uint64_t step = 1;
for (int j = 0; j < 4; ++j) {
uint64_t n = 0;
for (int i = 0; i < 256; ++i) {
lu[j][i] = lookup_value(n);
n += step;
}
step *= 256;
}
}
struct DivMod {
uint8_t div;
uint8_t rem;
};
static DivMod dm[256];
void make_dm() {
for (int i = 0; i < 256; ++i) {
dm[i].div = i / 10;
dm[i].rem = i % 10;
}
}
void init() {
make_lu();
make_dm();
}
uint64_t b2d(uint64_t n) {
uint64_t r = 0;
for (int i = 0; i < 4; ++i) {
r += lu[i][(n >> (i * 8)) & 0xff];
}
uint64_t r2 = 0;
uint64_t of = 0;
for (int i = 0; i < 8; ++i) {
uint64_t v = ((r >> (i * 8)) & 0xff) + of;
DivMod &x = dm[v];
of = x.div;
r2 += uint64_t(x.rem) << (i * 8);
}
return r2;
}
int main() {
init();
uint64_t n;
std::cin >> n;
std::cout << std::hex << b2d(n) << "\n";
return 0;
}
Für die Zukunft, anstatt eine uint128 Art der Umsetzung, habe ich nur die Zeichen der Zeichenfolge direkt. Dies erwies sich als viel schneller als von String gehen zu uint128 und zurück.
Die unmittelbarste Speedup wird aus inlining die Umwandlung anstatt Aufruf von Funktionen; es könnte so einfach sein bigint_divmod10() als Markierung Inline oder mit Profil-geführte Optimierung, wie von Ihrem Compiler angeboten.
Ich weiß, diese Frage ist alt, aber ich möchte dazu beitragen, da keiner eine Möglichkeit, den Teilungszyklus zu vermeiden setzen. Dieses verwendet POW2, ich habe die Benchmark nicht getestet, aber in der Theorie sollte als jede andere schneller sein und könnte sich auch in der Funktion pow gezwickt werden.
#include <iostream>
#include <cmath>
using namespace std;
#define MathBintodec(arr,len)({int dec=0;int ci_;for(ci_=len;ci_--;)dec+=arr[ci_]*pow(2,len-ci_-1);dec;})
int main(){
int r[]={1,0,0,1,0,0};
cout<<MathBintodec(r,6)<<endl;
}
Ausgabe: 36
