La forma más rápida para convertir binario a decimal?
https://stackoverflow.com/questions/1686004
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Tengo cuatro enteros de 32 bits sin signo que representa un entero de 128 bits, en poco orden endian:
typedef struct {
unsigned int part[4];
} bigint_t;
Me gustaría convertir este número en su representación como cadena decimal y de salida en un archivo.
En este momento, estoy usando una función bigint_divmod10 dividir el número por 10, no perder de vista el resto. Yo llamo a esta función repetidamente, la salida del resto como un dígito, hasta que el número es cero. Es bastante lento. ¿Es esta la forma más rápida de hacerlo? Si es así, ¿hay una forma inteligente para implementar esta función que no estoy viendo? He intentado mirar get_str.c de GMP, pero me resulta bastante impenetrable.
Edit: aquí está el código más rápido que pude para llegar a la función de 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;
}
donde la función de complemento se define 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;
}
}
}
}
Solución
Depende de lo demás que está haciendo con los números. Usted puede operar fuera una ligera pérdida en la eficiencia del espacio y una modesta pérdida de eficiencia de la aritmética multiprecision a cambio de conversión muy eficiente desde y hacia decimal. La clave es hacer aritmética multiprecision con una base que es una potencia de 10 en lugar de una potencia de 2.
Por ejemplo, es posible utilizar la base 10000, en el que empacar un dígito en una palabra de 16 bits y hacer su aritmética de dígitos en números enteros de 32 bits. (Si estás en una máquina de 64 bits se puede doblar y hacer que la base de mil millones.) Este tipo de código es relativamente eficiente en cuanto al tiempo, aunque no tan rápido como el uso de la energía natural de dos, porque no se puede aprovechar el bit de acarreo en el hardware. Y no se puede representar como muchos enteros en el mismo número de bits. Pero es un genio en la conversión hacia y desde decimal, porque se llega a convertir los dígitos individuales sin ninguna división larga.
Si necesita representar la gama completa de los números de cero a ((1 << 128) - 1), todavía se puede hacer esto, pero agregar un dígito adicional, por lo que sus números serán más grandes.
Si resulta que realmente necesita el espacio extra / velocidad (tal vez usted está haciendo una gran cantidad de cálculos de 128 bits de cifrado), entonces el método de simultanous div / mod 10 es el método más rápido que conozco. El único otro truco es que si enteros pequeños son comunes, puede manejarlos de forma especial. (Es decir, si las tres palabras más significativas de 32 bits son todos cero, sólo tiene que utilizar la división nativa para convertir.)
¿Hay una forma inteligente para implementar esta función que no estoy viendo?
Dave Hanson C interfaces e implementaciones tiene un largo capítulo en la aritmética multiprecision. La división de un gran número de un solo dígito es un caso especial que tiene esta aplicación 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 una comprensión completa, lo que realmente ayuda a tener el libro, pero el código fuente es todavía mucho más fácil de entender que el código fuente de GNU. Y se podría adaptar fácilmente para utilizar la base de 10.000 (que actualmente utiliza la base 256).
Resumen: si su cuello de botella es la conversión a decimal, implementar aritmética multiprecision con una base que es una potencia de 10 . Si el tamaño de palabra nativa de la máquina es de 32 y que está utilizando el código C, utilizar 10.000 en una palabra de 16 bits.
Otros consejos
Si sus valores son en su mayoría menos de ULLONG_MAX (18446744073709551615) que iba a tratar de usar para ellos sprintf(buf,"%llu",ullong_val). Apuesto a que esto está bastante bien optimizado en la biblioteca estándar, pero el análisis de formato se llevará a algunos ciclos sin embargo.
De lo contrario me gustaría crear un bigint_divmod1000000000 (o mejor nombre mod10to9) la función y usar eso. Se necesitaría 9 veces menos que divide bigint_divmod10.
tabla de búsqueda de 8 bits. Puede tener 4 tablas de búsqueda de 256 números. En primer lugar es de 0-256 para LSB bytes, segunda tabla es primera tabla multiplica por 256 y así sucesivamente.
Así que cuando usted necesita su número suma los números de tabla de consulta. Cuando la adición se puede añadir al bunary e ir más adelante un paso sobre cada byte para fijar owerflows.
Ejemplo número 0x12345678 En primera tabla de consulta no está bajo addres (0x78 = 120) así 0x010200 es primero número en segundo mesa bajo (0x56 = 87) es 0x0202000106 (0x56 en DEC es 22016) en la tercera tabla que hou tendría 0x03040007080702 y en última lable en 0x12 tiene 0x030001090809080808 (esto no encaja en la aritmética de 32 bits, pero que allredy know)
A continuación, resumir este número (como bumbers binarios) y dar un pase, byte a byte para el desbordamiento código en el bucle for es algo así como
s=carry+val[i];
val[i]=val[i]&10
carry=s/10;
//you can put last two operations in table
Si contamos las operaciones necesarias para ello.
1. (mirando en las tablas y añadiendo) 4 tablas de búsqueda. 16 adiciones (tener en cuenta que cuando no se necesita llevar sobre owerflow, becuase no pueden OCUR)
2. una pasada en cada paso 3 operatins 16 pasos para pasar.
passimistic límite superior 6 * 16 = 100 operaciones.
EDIT:
Este es el código C ++, y es 30% más rápido que la aplicación ingenua.
#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;
}
En el futuro, en lugar de aplicar un tipo uint128, acabo de utilizar los caracteres de la cadena directa. Esto resultó ser mucho más rápido que va de cadena a uint128 y la espalda.
El aumento de velocidad más rápida provendrá de los inlining la conversión en lugar de llamar a las funciones; podría ser tan simple como marcar bigint_divmod10() línea , o el uso de la optimización guiada por perfiles según lo ofrecido por el compilador.
Sé que esta pregunta es viejo, pero yo quiero contribuir, ya que ninguno puso una manera de evitar el ciclo de división. Éste utiliza pow2, no he probado el punto de referencia, pero en teoría debería ser más rápido que cualquier otro, y también podría ser ajustado en la función pow también.
#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;
}
Salida: 36
