maneira mais rápida para converter binário para decimal?
https://stackoverflow.com/questions/1686004
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho quatro inteiros de 32 bits não assinados representam um número inteiro de 128 bits não assinado, em pouco de ordem endian:
typedef struct {
unsigned int part[4];
} bigint_t;
Eu gostaria de converter esse número em sua representação de seqüência decimal e saída para um arquivo.
Agora, eu estou usando uma função bigint_divmod10 dividir o número por 10, mantendo o controle do restante. Eu chamo esta função repetidamente, emitir o restante como um dígito, até que o número é zero. É muito lento. É esta a maneira mais rápida de fazê-lo? Se assim for, há uma maneira inteligente para implementar essa função que eu não estou vendo? Eu tentei olhar para get_str.c de GMP, mas acho que é bastante impenetrável.
EDIT: aqui está o código mais rápido eu era capaz de chegar a para a função 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;
}
onde a função add é definido como:
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;
}
}
}
}
Solução
Depende o que mais você está fazendo com os números. Você pode trocar uma ligeira perda de eficiência de espaço e uma perda modesta na eficiência da aritmética multiprecision em troca de conversão muito eficiente de e para decimal. A chave é fazer multiprecision aritmética com uma base que é uma potência de 10, em vez de uma potência de 2.
Por exemplo, você pode usar base de 10.000, onde você arrumar um dígito em uma palavra de 16 bits e você faz sua aritmética em dígitos em números inteiros de 32 bits. (Se você estiver em uma máquina de 64 bits você pode dobrar isso e fazer base de 1.000.000.000.) Este tipo de código é timewise relativamente eficiente, embora não tão rápido quanto usando o poder nativo de dois, porque você não pode tirar proveito de o carry pouco sobre o hardware. E você não pode representar o maior número de inteiros no mesmo número de bits. Mas é um génio na conversão de e para decimal, porque você começa a converter os dígitos individuais sem qualquer divisão longa.
Se você precisa para representar toda a gama de números de zero a ((1 << 128) - 1), você ainda pode fazer isso, mas acrescentar um dígito extra, para que seus números serão maiores.
Se se verificar que você realmente precisa do espaço extra / velocidade (talvez você está fazendo um monte de cálculos de 128 bits de criptografia), então o método de simultanous div / mod 10 é o método mais rápido que eu conheço. O único outro truque é que se inteiros pequenos são comuns, você pode lidar com eles de forma especial. (Isto é, se as três palavras mais importantes de 32 bits são todos zero, basta usar a divisão nativa para converter.)
Existe uma maneira inteligente para implementar essa função que eu não estou vendo?
O Dave Hanson C Interfaces e Implementações tem um longo capítulo na aritmética multiprecision. Dividindo um grande número de um único dígito é um caso especial que tem essa implementação eficiente:
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;
}
Para plena compreensão, ele realmente ajuda a ter o livro, mas o código fonte ainda é muito mais fácil de entender do que o código fonte GNU. E você pode facilmente adaptá-lo para a base de uso 10.000 (que atualmente usa a base 256).
Resumo: se o seu gargalo de desempenho é a conversão para decimal, implementar aritmética multiprecision com uma base que é uma potência de 10 . Se o tamanho da palavra nativa da sua máquina é de 32 e você estiver usando código C, o uso 10.000 em uma palavra de 16 bits.
Outras dicas
Se os seus valores são quase sempre inferior a ULLONG_MAX (18446744073709551615) eu tentaria uso para eles sprintf(buf,"%llu",ullong_val). Aposto que isso é muito bem otimizado na biblioteca padrão, mas a análise de formato vai demorar alguns ciclos embora.
Caso contrário, eu iria criar um bigint_divmod1000000000 (ou nome melhor mod10to9) função e uso isso. Seria necessário 9 vezes menos do que divide bigint_divmod10.
Lookup mesa de 8 bits. Você pode ter 4 tabelas de pesquisa de 256 números. Primeiro é 0-256 para LSB bytes, segunda tabela é primeira tabela multiplicado por 256 e assim por diante.
Assim, quando você precisar do seu número soma-se os números de tabela de pesquisa. Quando a adição você pode adicionar como bunary e ir mais tarde uma passagem sobre cada byte para owerflows correção.
Exemplo número 0x12345678 Na primeira tabela de consulta existe sob addres (0x78 = 120) assim 0x010200 é primeiro número na segunda debaixo da mesa (0x56 = 87) é 0x0202000106 (0x56 em dec é 22016) na terceira tabela que hou teria 0x03040007080702 e sob última lable em 0x12 você tem 0x030001090809080808 (isso não se encaixa em 32 bits aritmética, mas que você allredy saber)
Em seguida, resumir este números (como bumbers binários) e ir um passo, byte por byte para transbordo código no loop for é algo como
s=carry+val[i];
val[i]=val[i]&10
carry=s/10;
//you can put last two operations in table
Se contarmos operações necessárias para isso.
1. (olhando em tabelas e adicionando) 4 tabelas de pesquisa. (Não ter em mente que quando você não precisa carregar sobre Owerflow, becuase eles podem OCUR) 16 adições
2. uma passagem em cada passo 3 operatins 16 passos de passar.
passimistic limite superior de 6 * 16 = 100 operações.
EDIT:
Aqui é código C ++, e é 30% mais rápido do que implementação ingênua.
#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;
}
Para referência futura, em vez de implementar um tipo uint128, eu usei apenas os caracteres da cadeia diretamente. Este acabou por ser muito mais rápido do que ir de string para uint128 e volta.
A aceleração mais imediato virá de inlining a conversão ao invés de chamar funções; poderia ser tão simples como marcação bigint_divmod10() em linha , ou usando otimização guiada por perfil oferecida pelo seu compilador.
Eu sei que esta questão é antiga, mas eu quero contribuir como nenhum colocar uma maneira evitando o ciclo de divisão. Este usa pow2, eu não testei o ponto de referência, mas, em teoria, deve ser mais rápido do que qualquer outro, e também pode ser ajustado na função pow também.
#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;
}
Saída: 36
