Convertir un número muy grande a la base de 10 cuerdas

Un entero mide 4 bytes. En mi ejemplo tengo números que miden 1 MB. ¿Cómo puedo convertirlos a un número decimal legible por humanos rápidamente ?

El número está presente en uint[] Array que contiene elementos de Size .

No sé si esto es más rápido, pero aquí hay un ejemplo en Delphi que escribí hace mucho tiempo para manejar grandes intenciones como cadenas (MUY rápidas y sucias): esto fue para uint de 128 bits, pero podría extenderlo indefinidamente.

 Function HexToBinShort(hex:integer):string; begin case hex of 0: result:='0000'; //convert each hex digit to binary string 1: result:='0001'; //could do this with high-nybble and low nybble 2: result:='0010'; //of each sequential byte in the array (mask and bit shift) 3: result:='0011'; //ie: binstring:=binstring + HexToBinShort(nybble[i]) 4: result:='0100'; //but must count DOWN for i (start with MSB!) 5: result:='0101'; 6: result:='0110'; 7: result:='0111'; 8: result:='1000'; 9: result:='1001'; 10: result:='1010'; 11: result:='1011'; 12: result:='1100'; 13: result:='1101'; 14: result:='1110'; 15: result:='1111'; end; end; 

Luego tome la cadena binaria concatenada y agregue poderes de dos cada vez que vea un ‘1’

 Function BinToIntString(binstring:string):string; var i, j : integer; var calcHold, calc2 :string; begin calc2:=binstring[Length(binstring)]; // first bit is easy 0 or 1 for i := (Length(binstring) - 1) downto 1 do begin if binstring[i] = '1' then begin calcHold:=generateCard(Length(binstring)-i); calc2 := AddDecimalStrings(calcHold, calc2); end; end; result:=calc2; end; 

generateCard se utiliza para crear una representación de cadena decimal de 2 ^ i (para i> 0)

 Function generateCard(i:integer):string; var j : integer; var outVal : string; begin outVal := '2'; if i > 1 then begin for j := 2 to i do begin outVal:= MulByTwo(outVal); end; end; result := outVal; end; 

y MulByTwo multiplica una cadena decimal por dos

 Function MulByTwo(val:string):string; var i : integer; var carry, hold : integer; var outHold : string; var outString :string; var outString2 : string; begin outString:= StringOfChar('0', Length(val) + 1); outString2:= StringOfChar('0', Length(val)); carry :=0; for i := Length(val) downto 1 do begin hold := StrToInt(val[i]) * 2 + carry; if hold >= 10 then begin carry := 1; hold := hold - 10; end else begin carry := 0; end; outHold := IntToStr(hold); outString[i+1] := outHold[1]; end; if carry = 1 then begin outString[1] := '1'; result := outString; end else begin for i := 1 to length(outString2) do outString2[i]:=outString[i+1]; result := outString2; end; end; 

Y finalmente, AddDecimalStrings … bueno, agrega dos cadenas decimales:

 Function AddDecimalStrings(val1, val2:string):string; var i,j :integer; var carry, hold, largest: integer; var outString, outString2, bigVal, smVal, outHold:string; begin if Length(val1) > Length(val2) then begin largest:= Length(val1); bigVal := val1; smVal := StringOfChar('0', largest); j:=1; for i := (largest - length(val2) +1) to largest do begin smVal[i] := val2[j]; j:=j+1; end; end else begin if length(val2) > Length(val1) then begin largest:=Length(val2); bigVal:=val2; smVal := StringOfChar('0', largest); j:=1; for i := (largest - length(val1) +1) to largest do begin smVal[i] := val1[j]; j:=j+1; end; end else begin largest:=length(val1); bigVal:=val1; smVal:=val2; end; end; carry:=0; outString:=StringOfChar('0', largest +1); outString2:=StringOfChar('0', largest); for i := largest downto 1 do begin hold := StrToInt(bigVal[i]) + StrToInt(smVal[i]) + carry; if hold >=10 then begin carry:=1; hold := hold - 10; end else begin carry:=0; end; outHold:= IntToStr(hold); outString[i+1]:=outHold[1]; end; if carry = 1 then begin outString[1] := '1'; result := outString; end else begin for i := 1 to length(outString2) do outString2[i]:=outString[i+1]; result := outString2; end; end; 

Estas funciones le permiten realizar aritmética básica en enteros casi arbitrariamente grandes como cadenas. Usted golpea otra pared cuando el número de dígitos es demasiado grande para indexar una matriz, por supuesto.

Aquí hay una división por dos, por cierto (útil para ir por el otro lado …). No manejo los números impares aquí.

 Function DivByTwo(val:string):string; var i : integer; var hold : integer; var outHold : string; var outString, outString2 :string; begin outString:=StringOfChar('0',Length(val)); for i := Length(val) downto 1 do begin if StrToInt(val[i]) mod 2 = 0 then begin hold:= Math.Floor(StrToInt(val[i]) / 2); outHold:= IntToStr(hold); outString[i]:=outHold[1]; end else begin hold:= Math.Floor((StrToInt(val[i]) - 1) / 2); outHold:=IntToStr(hold); outString[i]:= outHold[1]; if i <> Length(val) then begin hold:= StrToInt(outString[i+1]) + 5; outHold:= IntToStr(hold); outString[i+1] := outHold[1]; end; end; end; outString2:=StringOfChar('0',Length(val)-1); if (outString[1] = '0') and (length(outString) > 1) then begin for i := 1 to length(outString2) do outString2[i]:=outString[i+1]; result:=outString2; end else begin result:=outString; end; end; 

EDITAR: ¡Acabo de intentar esto con una cadena binaria de 9 millones de bits y es ridículamente lento! No es sorprendente, de verdad. Este es un código completamente no optimizado que tiene una gran cantidad de fruta de baja altura para recoger para acelerar las cosas. Aún así, no puedo evitar sentir que este es el tipo (o escala) de problema que probablemente querría escribir, al menos parcialmente, en un ensamblaje totalmente optimizado. Las operaciones individuales son pequeñas, pero deben realizarse muchas veces, lo que significa que piden ensamblaje. El multiproceso sin duda podría ser aprovechado aquí también.

He estado pensando en tu problema. No tengo una solución codificada, pero aquí hay un enfoque:

En primer lugar, supongamos sin pérdida de generalidad que tiene una colección de 2 n bits. (Si tiene menos de exactamente 2 n bits, elimine la matriz de bits con ceros iniciales hasta que lo haga. Obviamente, al hacerlo nunca más que duplica el tamaño de la matriz.) En su caso, dice que tiene un millón de uints, por lo que es 2 25 bits.

Supongamos también que cada colección de 2 k + 1 bits se puede dividir de manera uniforme en dos colecciones de bits, las colecciones izquierda y derecha, cada una con 2 k bits.

Por lo tanto, cada colección de bits, o subcolección, tiene un “tamaño” que es una potencia exacta de dos. La colección más pequeña posible contiene un solo bit y no puede subdividirse más.

En segundo lugar, supongamos que, de manera similar, tiene una representación inmutable de un número en forma decimal, y que nuevamente, sin pérdida de generalidad, hay 2 dígitos decimales en la cadena. Si hay menos de exactamente 2 d , nuevamente, rellene con ceros iniciales. Nuevamente, cada colección decimal de tamaño mayor que uno puede dividirse en dos colecciones, cada una de la mitad del tamaño.

Ahora trazamos un algoritmo recursivo:

 DigitCollection Convert(BitCollection bits) { if (bits.Size == 1) return bits[0] ? DigitCollection.SingleOne : DigitCollection.SingleZero; DigitCollection left = Convert(bits.Left); DigitCollection right = Convert(bits.Right); DigitCollection power = MakePowerOfTwo(bits.Right.Size); return Add(Multiply(left, power), right); } 

Ahora necesitamos los métodos Add, Multiply y MakePowerOfTwo. Como veremos en un momento, también necesitaremos Restar, y dos operadores Shift, para multiplicar rápidamente por potencias de diez.

La sum y la resta son fáciles. Claramente, si la colección más larga contiene n dígitos, entonces se pueden implementar métodos de sum y resta para tomar el tiempo O (n).

Los operadores FullShift y HalfShift hacen colecciones de nuevos dígitos a partir de las antiguas para facilitar la multiplicación rápida por potencia de diez. Si una colección de dígitos de tamaño 2 d + 1 consta de subcolecciones (X1, X2), cada una de tamaño 2d , la colección “semicerrada” contiene 2 d + 2 elementos y consta de ((2 d primeros ceros, X1 ), (X2, 2 d ceros finales)). La colección de turno completo consta de ((X1, X2), (2 d + 1 ceros al final)).

Estos son obviamente muy baratos para construir.

La multiplicación es donde nos encontramos con grandes problemas . Supongamos, sin pérdida de generalidad, que estamos multiplicando dos DigitCollections cada una con exactamente 2 dígitos. Podemos usar el algoritmo de Karatsuba:

 DigitCollection Multiply(DigitCollection x, DigitCollection y) { // Assume x and y are the same digit size. if (x and y are both single digits) return the trivial solution; // Assume that z2, z1 and z0 are all the same digit size as x and y. DigitCollection z2 = Multiply(x.Left, y.Left); DigitCollection z0 = Multiply(x.Right, y.Right); DigitCollection z1 = Subtract( Multiply(Add(x.Left, x.Right), Add(y.Left, y.Right)), Add(z2, z0)); return Add(Add(FullShift(z2), HalfShift(z1)), z0); } 

¿Cuál es el orden de este algoritmo? Supongamos que hay n = 2 d dígitos. ¿Qué es O (Multiplicar (n))? Recibimos terapia tres veces, cada una con un problema con la mitad de dígitos. El rest de las operaciones de sum, resta y desplazamiento no son más que O (n). Así que tenemos una recurrencia:

 T(n) = 3 T(n/2) + O(n) 

Lo que tiene una solución fácil a través del Teorema Maestro: este algoritmo es O (n 1 / lg 3 ), que es aproximadamente O (n 1.58 ).

¿Qué hay de MakePowerOfTwo? Eso es fácil dado lo que ya tenemos. Usamos la identidad:

2 2n + 1 = 2 n x 2 n + 2 n x 2 n

y escribe el algoritmo:

 DigitCollection MakePowerOfTwo(int p) { if (p == 0) return DigitCollection.SingleOne; DigitCollection power = MakePowerOfTwo(p / 2); power = Multiply(power, power); if (p % 2 != 0) power = Add(power, power); return power; } 

Está dominado por el cálculo de la multiplicación, y también lo está O (n 1.58 ).

Y ahora podemos ver que la llamada original a Convert también está dominada por la multiplicación.

Entonces, con este algoritmo, si tiene 2 dígitos binarios para convertir, puede esperar que tome alrededor de O (2 1.58 d ) pasos para hacerlo. En su caso, tiene 2 25 bits para convertir, por lo que debería tomar alrededor de 777 mil millones de cálculos.

El hecho clave aquí es que este algoritmo está completamente dominado por el costo de la multiplicación . Si puede reducir el costo de la multiplicación a menos de O (n 1.58 ), obtendrá grandes ganancias. Si yo fuera tú, estaría estudiando mejoras en los algoritmos de multiplicación decimal sobre Karatsuba.

Es posible que pueda ahorrar algo de tiempo haciendo más de un dígito a la vez. si lo haces, digamos, 100,000 a la vez, probablemente irá al menos un poco más rápido que 10 a la vez.

Eso sí, es probable que siga siendo bastante lento, pero le ahorrará algo de tiempo.

Es posible que puedas hacerlo recursivo y acelerarlo mucho más: obtén la raíz cuadrada aproximada del número, redondeando al exponente más cercano de 10. div y mod por ese número, y envía los resultados al mismo función. Tenga en cuenta que no estoy seguro de cómo manejaría un div o mod de ese tamaño de manera eficiente, pero si puede averiguarlo (y no se queda sin memoria), todavía será más eficiente en el tiempo. que dividirlo un dígito a la vez.

Versión alternativa: renunciar a los decimales, ya que el número va a ser demasiado grande para tener sentido para cualquier lector humano real de todos modos, y convertir la cosa en hexadecimal. Todavía es técnicamente legible para los humanos, pero puede convertirlo en un byte a la vez y ahorrarse un montón de angustia.

Gracias a todos ustedes, descubrí una forma basada principalmente en la idea de J …, quien sugirió convertir el número en 10 números basados ​​sumndo la potencia de 2 cada vez que hay un 1 . Pero en lugar de un sistema basado en 10 (sistema decimal humano) utilizo un sistema basado en 1000000000000000000 (10 ^ 18). Por lo tanto, cada dígito tiene no solo 10 posibilidades (0 … 9), sino también 10 ^ 18. Esto se ajusta a un número de 64 bits que luego convertimos .ToString()

Es la forma más eficiente hasta ahora.