Moyen le plus rapide pour convertir binaire en décimal?
https://stackoverflow.com/questions/1686004
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai quatre non signés entiers de 32 bits représentant un nombre entier de 128 bits non signé, dans peu d'ordre endian:
typedef struct {
unsigned int part[4];
} bigint_t;
Je voudrais convertir ce nombre en sa représentation chaîne décimale et la sortie dans un fichier.
En ce moment, je suis en utilisant une fonction de bigint_divmod10 de diviser le nombre par 10, garder la trace du reste. J'appelle cette fonction de façon répétée, délivrer en sortie le reste sous forme d'un chiffre, jusqu'à ce que le nombre est égal à zéro. Il est assez lent. Est-ce le meilleur moyen de le faire? Si oui, est-il un moyen intelligent pour mettre en œuvre cette fonction que je ne vois pas? J'ai essayé de regarder la get_str.c de GMP, mais je trouve assez impénétrable.
EDIT: voici le code plus rapide que j'ai pu trouver pour la fonction divmod10:
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;
}
où la fonction d'ajout est défini comme suit:
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;
}
}
}
}
La solution
Cela dépend de ce que vous faites avec les chiffres. Vous pouvez troquer une légère perte d'efficacité de l'espace et une perte modeste efficacité de l'arithmétique Multiprécision en échange de conversion très efficace et de décimales. La clé consiste à effectuer des opérations arithmétiques de multiprécision avec une base qui est une puissance de 10 plutôt que d'une puissance de 2.
Par exemple, vous pouvez utiliser la base 10 000, où vous emballez un chiffre en un mot de 16 bits et que vous faites vos opérations arithmétiques sur chiffres entiers de 32 bits. (Si vous êtes sur une machine 64 bits, vous pouvez doubler et que faire la base 1.000.000.000.) Ce type de code est TimeWise relativement efficace, mais pas tout à fait aussi rapide que la puissance native de deux parce que vous ne pouvez pas profiter de le bit de report sur le matériel. Et vous ne pouvez pas représenter autant de nombres entiers dans le même nombre de bits. Mais il est un whiz à la conversion et à partir de décimales, parce que vous pouvez convertir les chiffres individuels sans division.
Si vous avez besoin de représenter la gamme complète des numéros de zéro à ((1 << 128) - 1), vous pouvez toujours le faire, mais ajouter un chiffre supplémentaire, afin que vos chiffres seront plus grands.
S'il se trouve que vous avez vraiment besoin de l'espace supplémentaire / vitesse (peut-être que vous faites beaucoup de calculs cryptographiques 128 bits), la méthode de simultanous div / mod 10 est la méthode la plus rapide que je connaisse. La seule autre astuce est que si petits entiers sont communs, vous pouvez les gérer spécialement. (C'est, si les trois mots de 32 bits les plus significatifs sont tous nuls, il suffit d'utiliser la division native pour convertir.)
Y at-il une façon intelligente de mettre en œuvre cette fonction que je ne vois pas?
Dave Hanson C Interfaces et Implémentations un chapitre assez long sur l'arithmétique multiprécision. La division d'un grand nombre par un seul chiffre est un cas particulier qui a cette mise en œuvre efficace:
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;
}
Pour une compréhension complète, il aide vraiment d'avoir le livre, mais le code source est toujours beaucoup plus facile à comprendre que le code source GNU. Et vous pouvez facilement l'adapter à utiliser la base 10 000 (il utilise actuellement la base 256).
Résumé: si votre goulot d'étranglement est la conversion en décimal, mettre en œuvre arithmétique Multiprécision avec une base qui est une puissance de 10 . Si la taille de votre mot de machine natif est de 32 et que vous utilisez le code C, utiliser 10 000 en un mot de 16 bits.
Autres conseils
Si vos valeurs sont pour la plupart moins de ULLONG_MAX (18446744073709551615) Je vais essayer d'utiliser pour les sprintf(buf,"%llu",ullong_val). Je parie que cela est plutôt bien optimisé dans la bibliothèque standard, mais l'analyse syntaxique format prendra des cycles bien.
Sinon, je créerais une fonction bigint_divmod1000000000 (ou meilleur nom mod10to9) et l'utiliser. Il aurait besoin de 9 fois moins que bigint_divmod10 divise.
Tableau de consultation de 8 bits. Vous pouvez avoir 4 tables de consultation de 256 numéros. Tout d'abord est 0-256 pour les octets LSB, table deuxième est le premier tableau multiplié par 256 et ainsi de suite.
lorsque vous avez besoin de votre somme nombre de numéros de table de consultation. Lorsque vous vous pouvez ajouter ajouter bunary et aller plus tard une passe sur chaque octet pour fixer owerflows.
Exemple numéro 0x12345678 Dans la première table de consultation, il est sous addres (0x78 = 120) si 0x010200 premier nombre est dans le deuxième tableau sous (0x56 = 87) est 0x0202000106 (0x56 en décembre est 22016) à la troisième table que vous hou aurait 0x03040007080702 et en dernier lable à 0x12 vous avez 0x030001090809080808 (cela ne correspond pas à 32 bits arithmétique, mais que vous allredy savoir)
résumer ensuite ce nombre (comme bumbers binaires) et passez un passage, octet par octet pour trop-plein code dans la boucle for est quelque chose comme
s=carry+val[i];
val[i]=val[i]&10
carry=s/10;
//you can put last two operations in table
Si l'on compte les opérations nécessaires à cet effet.
1. (en regardant dans les tables et en ajoutant) 4 tables de consultation. 16 ajouts (garder à l'esprit que lorsque vous n'avez pas besoin de transporter environ owerflow, becuase ils ne peuvent pas OCUR)
2. une passe dans chaque étape 3 operatins 16 pas de passer.
limite supérieure passimistic 6 * 16 = 100 opérations.
EDIT:
Voici le code C ++, et est 30% plus rapide que la mise en œuvre naïve.
#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;
}
Pour référence ultérieure, au lieu de mettre en œuvre un type de uint128, je viens d'utiliser les caractères de la chaîne directement. Cela se est avéré être beaucoup plus rapide que d'aller de chaîne à uint128 et le dos.
Le plus immédiat speedup viendra de inline la conversion plutôt que d'appeler des fonctions; il pourrait être aussi simple que le marquage bigint_divmod10() en ligne , ou en utilisant l'optimisation guidée profil, comme offert par votre compilateur.
Je sais que cette question est vieux, mais je veux contribuer comme aucun mettre un moyen d'éviter le cycle de division. Celui-ci utilise pow2, je ne l'ai pas testé l'indice de référence, mais en théorie devrait être plus rapide que tout autre, et pourrait également être modifié dans la fonction pow ainsi.
#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;
}
Sortie: 36
