Tengo una cadena de longitud arbitraria que representa un valor entero decimal y esta cadena se convierte en un número entero grande en formato binario simple (no BCD, más de 64 bits).Cuantos bytes se requieren para mantener N dígitos decimales
Estoy buscando una buena estimación simple cuántos bytes mantendrán N dígitos decimales con seguridad sin utilizar aritméticos de coma flotante.
Sin utilizar la aritmética de punto flotante: Para N dígitos decimales, es necesario
(98981 * N)/238370 + 1
bytes. 98981/238370 es una buena aproximación racional (desde arriba) a log(10)/log(256) (el 9 º convergente), formas truncadas de la división de enteros, por lo tanto se suman 1. La fórmula es apretado para N < 238370, el número de bytes necesarios para representar 10^N - 1 es exactamente dada por eso, sobreestima para N un múltiplo de 238370 y realmente grandeN. Si no le da demasiado miedo asignar demasiado el byte impar, también puede usar (267 * N)/643 + 1, (49 * N)/118 + 1, (5 * N)/12 + 1 o, desperdiciando alrededor del 10% del espacio, (N + 1)/2.
Como @Henrick Hellström señala, en Delphi habría que utilizar el operador div para la división de número entero (perdido la etiqueta delphi).
Para mayor claridad, el operador/dará como resultado una división de coma flotante. Use el operador div. –
Usted podría estar buscando fixed point arithmetic
El valor máximo de un tipo de punto fijo es simplemente el valor más grande que se puede representar en el tipo entero subyacente, multiplicado por el factor de escala ; y de manera similar para el valor mínimo. Por ejemplo, considere un tipo de punto fijo representado como un binario número entero con b bits en formato de complemento a dos, con un factor de escala de 1/2f (es decir, los últimos bits de F son bits de fracción): el mínimo representable el valor es -2b-1/2f y el valor máximo es (2b-1-1)/2f.
Necesita estos muchos bits: ceil(N/log10(2)). Redondea hasta el próximo múltiplo de 8, es decir, ceil((N/log10(2))/8)+1 bytes.
Agregaría un bit de seguridad para tener en cuenta los errores de redondeo. – CodesInChaos
Sin aritmética de coma flotante: desde log10 (2) = ~ 3.3, puedes calcular 'N * 3.5/8 = (N * 3 + N/2)/8'. @CodeInChaos: se supone que 'ceil' debe redondear. En cualquier caso, la fórmula de entero solo sobreestimará. – zvrba
Creo que una estimación simple se puede basar en el hecho de que 10 bits tienen 3 dígitos decimales con seguridad. – kludg
((size_t)ceil(N/log10(2)) + CHAR_BIT - 1)/CHAR_BIT
Ahora, 1/log10(2) ~ = 3.32 se puede aproximar como 10.0/3 = 3.3(3).
Por lo tanto, sin punto flotante sería como máximo (((size_t)N*10+2)/3 + CHAR_BIT - 1)/CHAR_BIT C bytes.
Mire para desbordamientos cuando N es grande.
1) ¿Su biblioteca de grandes int tiene alguna función 'Length'? 2) ¿Por qué quieres evitar el punto flotante? – CodesInChaos
Dependerá de cómo se almacena. Para la codificación estándar, cada dígito usa 4 bits, por lo que nBytes = (nDigits + 1)/2. También debería considerar usar compresión, incluso compresión en memoria, con algún algoritmo rápido. La relación variará, pero seguramente ahorrará espacio. Consulte también si sus datos pueden tener algunos patrones, como almacenar un delta entre los valores (después del orden, por ejemplo), lo que aumentará aún más la compresión. –