romberg - metodos numericos c++ codigo

Aritmética de punto fijo en programación en C (3)

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

La idea detrás de la aritmética de punto fijo es que almacenes los valores multiplicados por una cierta cantidad, usas los valores multiplicados para todos los cálculos y los divides por la misma cantidad cuando quieres el resultado. El propósito de esta técnica es usar aritmética de enteros (int, long ...) mientras se pueden representar fracciones.

La forma habitual y más eficiente de hacer esto en C es utilizando los operadores de cambio de bits (<< y >>). Desplazar bits es una operación bastante simple y rápida para la ALU y al hacer esto tiene la propiedad de multiplicar (<<) y dividir (>>) el valor entero por 2 en cada cambio (además, se pueden hacer muchos cambios para exactamente lo mismo precio de una sola). Por supuesto, el inconveniente es que el multiplicador debe ser una potencia de 2 (lo que generalmente no es un problema por sí mismo, ya que no nos importa el valor exacto del multiplicador).

Ahora digamos que queremos usar enteros de 32 bits para almacenar nuestros valores. Debemos elegir una potencia de 2 multiplicadores. Vamos a dividir el pastel en dos, así que digamos 65536 (este es el caso más común, pero puedes usar cualquier potencia de 2 dependiendo de tus necesidades en precisión). Esto es 2 ¹⁶ y el 16 aquí significa que usaremos 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 debe poner en la tienda (estructura, base de datos, lo que sea). Tenga en cuenta que int no es necesariamente de 32 bits en C, aunque es el caso en la actualidad. Además, sin más 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 del entero (puedes introducir algunos hacks al respecto). En caso de duda, utilice un typedef para su tipo de punto fijo y estará más seguro.

Cuando quiera 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 10 a nuestro precio de 500:

price += 10 << SHIFT_AMOUNT;

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

price *= 3;

Ahora hagamos las cosas más interesantes dividiendo el precio por 4, de modo que compensemos una parte fraccionaria distinta de cero:

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

Eso es todo sobre las reglas. Cuando quiera recuperar el precio real en cualquier momento, debe hacer un cambio a la derecha:

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

Si necesita la parte fraccionaria, debe enmascararla:

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 asigna exactamente con el rango de fracción decimal [0 - 0.9999 ...]. En otras palabras, la asignación se ve como: 0 => 0, 32768 => 0.5, 65535 => 0.9999 ...

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

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

Pero si no tiene soporte FPU (hardware o software), puede usar sus nuevas habilidades como esta a un 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 0 en la expresión es aproximadamente el número de dígitos que desea después del punto decimal. No sobreestime el número de 0 dado su precisión de fracción (no hay una trampa real aquí, eso es bastante obvio). No use simple mientras que sizeof (long) puede ser igual a sizeof (int). El uso de long long en el caso de que int sea de 32 bits, mientras que el long. Se garantiza como mínimo de 64 bits (o use int64_t, int_least64_t y así, declarado en stdint.h). En otras palabras, use un tipo dos veces más grande que su tipo de punto fijo, eso es lo suficientemente justo. Finalmente, si no tiene acceso a los tipos> = 64 bits, tal vez sea el momento de ejercitarlos emulando, al menos para su salida.

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

Ten cuidado con los valores negativos. Puede volverse complicado a veces, especialmente cuando es hora de mostrar el valor final. Además, C está definido por la implementación para los enteros con signo (aunque las plataformas donde este 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 atacarlo si sabes lo que haces (no desarrollaré esto, pero esto tiene algo que ver con el cambio aritmético frente al cambio lógico y la representación del complemento de 2). Sin embargo, con enteros sin signo, en general estás seguro de lo que hagas, ya que los comportamientos están bien definidos de todos modos.

También tenga en cuenta que si un entero de 32 bits no puede representar valores mayores que 2 ³² - 1, el uso de la aritmética de punto fijo con 2 ¹⁶ limita su rango a 2 ¹⁶ - 1. (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 entonces elegir un SHIFT_AMOUNT adecuado para 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 (flotación / doble) a menudo tampoco es lo suficientemente preciso, aunque 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 sea la magnitud, más precisión obtendrá ... bueno, esto es más complejo que eso, pero te dan el punto). Los flotadores también 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 alcanzar un punto de magnitud donde agregar 1 o incluso los valores mayores no tendrán ningún efecto, algo que no puede ocurrir con los enteros).

Si trabajas en esas áreas sensibles, es mejor que gmplib bibliotecas dedicadas al propósito de la precisión arbitraria (ve a gmplib , es gratis). En la ciencia de la computación, esencialmente, ganar precisión es sobre la cantidad de bits que utiliza para almacenar sus valores. ¿Quieres alta precisión? Utilizar bits. Eso es todo.

No te recomendaría que lo hicieras, si tu único propósito es ahorrar memoria. El error en el cálculo del precio se puede acumular y usted lo va a arruinar.

Si realmente desea implementar cosas similares, ¿puede simplemente tomar el intervalo mínimo del precio y luego usar directamente la operación int e integer para manipular su número? Solo necesita convertirlo al número de punto flotante cuando se muestra, lo que hace su vida más fácil.

Veo dos opciones para ti. Si está trabajando en la industria de servicios financieros, es probable que haya estándares que su código debe cumplir en cuanto a precisión y precisión, por lo que solo tendrá que cumplir con eso, 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 es para uso personal, entonces, para una máxima precisión, le recomiendo que use números enteros y multiplique todos los precios por un factor fijo antes del almacenamiento. Por ejemplo, si quiere cosas precisas al centavo (probablemente no lo suficientemente buenas), multiplique todos los precios por 100 para que su unidad sea efectivamente centavos en lugar de dólares y vaya de allí. Si quieres más precisión, multiplica por más. Por ejemplo, para ser precisos a la centésima de un centavo (un estándar que he escuchado se aplica comúnmente), multiplique los precios por 10000 (100 * 100).

Ahora con enteros de 32 bits, multiplicar por 10000 deja poco espacio para grandes cantidades de dólares. Un práctico límite de 32 bits de 2 mil millones significa que solo se pueden expresar precios tan altos como $ 20000: 2000000000/10000 = 20000. Esto empeora si multiplica ese 20000 por algo, ya que es posible 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, todavía hay mucho margen para mantener valores grandes, incluso en las multiplicaciones.

El truco con el punto fijo es que siempre que realice un cálculo, debe recordar que cada valor es realmente un valor subyacente multiplicado por una constante. Antes de sumar o restar, debe multiplicar los valores con una constante más pequeña para que coincida con los de una constante más grande. Después de multiplicar, necesita dividir por algo para que el resultado vuelva a multiplicarse por la constante deseada. Si usa una no-potencia de dos como su constante, tendrá que hacer una división de enteros, que es costosa, en el tiempo. Muchas personas usan los poderes de dos como sus constantes, por lo que pueden cambiar en lugar de dividir.

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 lo necesitas. Tienen 53 bits de precisión, que es aproximadamente 9 cuatrillones, o casi 16 dígitos decimales. Sí, es posible que aún pierdas centavos cuando trabajas con miles de millones, pero si te importa eso, no estás siendo un multimillonario de la manera correcta. :)