Aritmética de punto fijo en C Programación

Question

Estoy tratando de crear una aplicación que almacene precios de acciones con alta precisión. Actualmente estoy usando un doble para hacerlo. Para ahorrar memoria, ¿puedo usar cualquier otro tipo de datos? Sé que esto tiene algo que ver con la aritmética de punto fijo, pero no puedo resolverlo.

Answer 1

La idea detrás de la aritmética de punto fijo es que almacene los valores multiplicados por una cierta cantidad, utilice los valores multiplicados para todo el cálculo y divídalo por la misma cantidad cuando desee el resultado. El propósito de esta técnica es usar aritmética de enteros (int, long ...) mientras se pueden representar fracciones.

La forma más habitual y más eficiente de hacerlo en C es mediante el uso de operadores de desplazamiento de bits (< < y >>).Cambiar bits es una operación bastante simple y rápida para la ALU y al hacerlo tiene la propiedad de multiplicar (< <) y dividir (>>) el valor entero por 2 en cada turno (además, se pueden hacer muchos cambios exactamente igual precio de uno solo). Por supuesto, el inconveniente es que el multiplicador debe ser una potencia de 2 (que generalmente no es un problema en sí mismo ya que realmente no nos importa ese valor multiplicador exacto).

Ahora digamos que queremos usar enteros de 32 bits para almacenar nuestros valores. Debemos elegir un poder de 2 multiplicadores. Dividamos la torta en dos, por ejemplo, 65536 (este es el caso más común, pero puedes usar cualquier potencia de 2 según tus necesidades en precisión). Esto es 2 y el 16 aquí significa que utilizaremos los 16 bits menos significativos (LSB) para la parte fraccionaria. El resto (32 - 16 = 16) es para los bits más significativos (MSB), la parte entera.

 integer (MSB) fraction (LSB) 
      v     v 
    0000000000000000.0000000000000000 

Vamos a poner esto en el código:

#define SHIFT_AMOUNT 16 // 2^16 = 65536 
#define SHIFT_MASK ((1 << SHIFT_AMOUNT) - 1) // 65535 (all LSB set, all MSB clear) 

int price = 500 << SHIFT_AMOUNT; 

Este es el valor que se debe poner en la tienda (estructura, base de datos, lo que sea). Tenga en cuenta que int no es necesariamente 32 bits en C, aunque en la actualidad es mayormente el caso. Además, sin otra declaración, está firmado por defecto. Puede agregar unsigned a la declaración para estar seguro. Mejor que eso, puedes usar uint32_t o uint_least32_t (declarado en stdint.h) si tu código depende en gran medida del tamaño del bit entero (puedes introducir algunos hacks al respecto). En caso de duda, use un typedef para su tipo de punto fijo y estará más seguro.

Cuando desee hacer cálculos con este valor, puede usar los 4 operadores básicos: +, -, * y /. Debe tener en cuenta que al sumar y restar un valor (+ y -), ese valor también debe cambiarse. Digamos que queremos añadir a nuestro precio de 10 500:

price += 10 << SHIFT_AMOUNT; 

Pero para la multiplicación y división (* y /), el multiplicador/divisor no debe desplazarse. Digamos que queremos multiplicar por 3:

price *= 3; 

Ahora vamos a hacer las cosas más interesantes dividiendo el precio de un 4 por lo que hacemos para un no-cero parte fraccionaria:

price /= 4; // now our price is ((500 + 10) * 3)/4 = 382.5 

Eso es todo acerca las normas. Cuando se desea recuperar el precio real en cualquier momento, debe desplazamiento a la derecha:

printf("price integer is %d\n", price >> SHIFT_AMOUNT); 

Si necesita la parte fraccionaria, debe enmascarar hacia fuera:

printf ("price fraction is %d\n", price & SHIFT_MASK); 

Por supuesto, este valor no es lo que podemos llamar una fracción decimal, de hecho es un número entero en el rango [0 - 65535]. Pero se correlaciona exactamente con el rango de fracción decimal [0 - 0,9999 ...]. En otras palabras, el mapeo se ve así: 0 => 0, 32768 => 0.5, 65535 => 0.9999 ...

Una manera fácil de verlo como una fracción decimal es recurrir a C incorporado en la aritmética flotante en este punto:

printf("price fraction in decimal is %f\n", ((double)(price & SHIFT_MASK)/(1 << SHIFT_AMOUNT))); 

Pero si usted no tiene el apoyo FPU (hardware o software) , puede utilizar sus nuevas habilidades como éste por el precio completo:

printf("price is roughly %d.%lld\n", price >> SHIFT_AMOUNT, (long long)(price & SHIFT_MASK) * 100000/(1 << SHIFT_AMOUNT)); 

el número de 0s en la expresión es más o menos el número de dígitos que desea después de la coma decimal. No sobreestimes el número de 0 dada la precisión de tu fracción (no hay una trampa real aquí, eso es bastante obvio). No utilice long simple como sizeof (long) puede ser igual a sizeof (int). Utilice largo largo en caso int es de 32 bits como largo largo está garantizada para ser 64 bits de mínimo (o bien utiliza int64_t, int_least64_t y tal, declarado en stdint.h). En otras palabras, use un tipo dos veces el tamaño de su tipo de punto fijo, eso es suficiente. Finalmente, si no tiene acceso a tipos> = 64 bits, tal vez sea hora de ejercitarlos emulando, al menos para su salida.

Estas son las ideas básicas detrás de la aritmética de punto fijo.

Tenga cuidado con los valores negativos. A veces puede ser difícil, especialmente cuando es el momento de mostrar el valor final. Además, C es una implementación definida sobre enteros con signo (aunque las plataformas donde esto es un problema son muy poco comunes hoy en día). Siempre debe hacer pruebas mínimas en su entorno para asegurarse de que todo salga como se espera. Si no, puedes hackearlo si sabes lo que haces (no voy a desarrollar sobre esto, pero esto tiene algo que ver con el desplazamiento aritmético versus el desplazamiento lógico y la representación del complemento a 2). Sin embargo, con números enteros sin signo, está seguro de todo lo que haga, ya que los comportamientos están bien definidos.

tomar también en cuenta que si un número entero de 32 bits no puede representar los valores más grandes que 2 - 1 usando aritmética de punto fijo con 2 limita el rango de 2 - 1 en el electrónico (y divida todo esto por 2 con enteros con signo, lo que en nuestro ejemplo nos dejaría con un rango disponible de 2 - 1). El objetivo es elegir un SHIFT_AMOUNT adecuado a la situación. Esta es una compensación entre la magnitud de la parte entera y la precisión de la parte fraccionaria.

Ahora, para las advertencias reales: esta técnica definitivamente no es adecuada en áreas donde la precisión es una prioridad (financiera, científica, militar ...). El punto flotante habitual (flotante/doble) a menudo no es lo suficientemente preciso, a pesar de que tienen mejores propiedades que el punto fijo en general. El punto fijo tiene la misma precisión sea cual sea el valor (esto puede ser una ventaja en algunos casos), donde la precisión de los flotadores es inversamente proporcional a la magnitud del valor (es decir, cuanto menor es la magnitud, más precisión obtienes ... bueno, esto es más complejo que eso, pero entiendes el punto). También los flotadores tienen una magnitud mucho mayor que los enteros equivalentes (en número de bits) (punto fijo o no), al costo de una pérdida de precisión con valores altos (incluso puede llegar a un punto de magnitud donde se agrega 1 o incluso los valores mayores no tendrán ningún efecto, algo que no puede suceder con los enteros).

Si trabaja en esas áreas sensibles, que es mejor usar las bibliotecas dedicadas a los fines de precisión arbitraria (ir echar un vistazo a gmplib, es gratis). En la ciencia de la computación, esencialmente, ganar precisión se trata de la cantidad de bits que usa para almacenar sus valores. ¿Quieres alta precisión? Usa bits. Eso es todo.

Answer 2

No te recomendaría hacerlo, si su único propósito es ahorrar memoria. El error en el cálculo del precio puede acumularse y vas a arruinarlo.

Si realmente desea implementar cosas similares, puede que acaba de tomar el intervalo mínimo del precio y luego usar directamente int entero y el funcionamiento de manipular su número? Solo necesita convertirlo al número de punto flotante cuando lo visualice, lo que le hará la vida más fácil.

Answer 3

Veo dos opciones para usted. Si está trabajando en la industria de los servicios financieros, probablemente haya normas que su código debe cumplir con precisión y precisión, por lo que tendrá que aceptarlo, independientemente del costo de la memoria. Entiendo que ese negocio generalmente está bien financiado, por lo que pagar por más memoria no debería ser un problema. :)

Si esto es para uso personal, a continuación, para la máxima precisión le recomiendo que utilice números enteros y multiplicar todos los precios por un factor fijo antes de su almacenamiento. Por ejemplo, si quiere que las cosas sean precisas para el centavo (probablemente no lo suficientemente bueno), multiplique todos los precios por 100 para que su unidad sea efectivamente centavos en lugar de dólares y vaya desde allí. Si quieres más precisión, multiplica por más. Por ejemplo, para tener una precisión de centésimo de centavo (un estándar que he escuchado se aplica comúnmente), multiplique los precios por 10000 (100 * 100).

Ahora con enteros de 32 bits, multiplicando por 10000 deja poco espacio para un gran número de dólares. Un límite práctico de 32 bits de 2 mil millones significa que solo se pueden expresar precios de hasta $ 20000: 2000000000/10000 = 20000. Esto empeora si se multiplica ese valor de 20000 por algo, ya que puede que no haya espacio para mantener el resultado. Por este motivo, recomiendo usar enteros de 64 bits (long long). Incluso si multiplicas todos los precios por 10000, aún hay suficiente margen para mantener grandes valores, incluso en las multiplicaciones.

El truco de punto fijo es que cada vez que haces un cálculo es necesario recordar que cada valor es realmente un valor subyacente multiplicado por una constante. Antes de sumar o restar, necesita multiplicar valores con una constante más pequeña para que coincida con los que tienen una constante mayor. Después de multiplicar, necesita dividir por algo para que el resultado vuelva a multiplicarse por la constante deseada. Si usas un no poder de dos como tu constante, tendrás que dividir el número entero, lo cual es costoso, en el tiempo. Muchas personas usan poderes de dos como sus constantes, por lo que pueden cambiar en lugar de dividirse.

Si todo esto parece complicado, lo es. Creo que la opción más fácil es usar dobles y comprar más RAM si la necesitas. Tienen 53 bits de precisión, que es aproximadamente 9 cuatrillones, o casi 16 dígitos decimales. Sí, aún podrías perder centavos cuando trabajas con miles de millones, pero si te preocupas por eso, no estás siendo multimillonario de la manera correcta. :)