Aritmética de punto fijo

Para mayor eficiencia, los factores de escala suelen elegirse como potencias (positivas o negativas) de la base b utilizada para representar internamente los números enteros. Sin embargo, a menudo el factor de escala óptimo viene determinado por la aplicación. Por lo tanto, se suelen utilizar factores de escala que son potencias de 10 (por ejemplo, 1/100 para valores en dólares) por conveniencia, incluso cuando los números enteros se representan internamente en binario. Los factores de escala decimales también se integran bien con el sistema métrico (SI) , ya que la elección del factor de escala de punto fijo suele ser equivalente a la elección de una unidad de medida (como el centímetro o la micra en relación con el metro ).

Sin embargo, ocasionalmente se pueden utilizar otros factores de escala; por ejemplo, una cantidad fraccionaria de horas puede representarse como un número entero de segundos; es decir, como un número de punto fijo con un factor de escala de 1/3600.

Incluso con el redondeo más preciso, los valores de punto fijo representados con un factor de escala S pueden tener un error de hasta ±0,5 × S en el valor entero almacenado. Por lo tanto, los factores de escala más pequeños generalmente producen resultados más precisos.

Por otro lado, un factor de escala menor implica un rango menor de valores que se pueden almacenar en una variable de programa determinada. El valor máximo de punto fijo que se puede almacenar en una variable es el mayor valor entero que se puede almacenar en ella, multiplicado por el factor de escala, y lo mismo ocurre con el valor mínimo. Por ejemplo, la tabla siguiente muestra el factor de escala implícito S , los valores mínimo y máximo representables V _min y V _max , y la precisión δ  = S /2 de los valores que se podrían representar en formato binario de punto fijo con signo de 16 bits, según el número f de bits fraccionarios implícitos.

Se ha dicho que los formatos de punto fijo con factores de escala de la forma 2 ⁿ −1 (es decir, 1, 3, 7, 15, 31, etc.) son apropiados para el procesamiento de imágenes y otras tareas de procesamiento de señales digitales. Proporcionan conversiones más consistentes entre valores de punto fijo y de punto flotante que la escala de 2 ⁿ . El lenguaje de programación Julia implementa ambas versiones. ^{[ 2 ]}

Cualquier fracción binaria a / ^2m , como 1/16 o 17/32, puede representarse con exactitud en punto fijo, con un factor de escala de potencia de dos 1/ ^2n, donde n  ≥ m . Sin embargo, la mayoría de las fracciones decimales, como 0,1 o 0,123, son fracciones periódicas infinitas en base 2 y, por lo tanto, no pueden representarse de esa manera.

De manera similar, cualquier fracción decimal a /10 ^m , como 1/100 o 37/1000, puede representarse exactamente en punto fijo con un factor de escala de potencia de diez 1/10 ⁿ , donde n  ≥ m . Este formato decimal también puede representar cualquier fracción binaria a /2 ^m , como 1/8 (0,125) o 17/32 (0,53125).

En términos más generales, un número racional a / b , con a y b primos entre sí y b positivo, puede representarse exactamente en punto fijo binario solo si b es una potencia de 2; y en punto fijo decimal solo si b no tiene factores primos distintos de 2 o 5.

Los cálculos de punto fijo pueden ser más rápidos o usar menos hardware que los de punto flotante. Si el rango de los valores a representar se conoce de antemano y está suficientemente limitado, el punto fijo puede hacer un mejor uso de los bits disponibles. Por ejemplo, si hay 32 bits disponibles para representar un número decimal entre 0 y 1, una representación de punto fijo puede tener un error menor que1,2 × 10 ⁻¹⁰ , mientras que la representación de punto flotante estándar IEEE 754 puede tener un error de hasta596 × 10 ⁻¹⁰ porque 9 de los bits se asignan al signo y exponente del factor de escala dinámica que no se utiliza en este rango limitado de valores. Para una grabación de audio digital que requiere menos de Con un margen dinámico de 40 dB , un sistema de punto fijo de 32 bits tiene una relación señal/ruido superior a la de un sistema de punto flotante.

Los programas que utilizan cálculos de punto fijo suelen ser más portátiles que los que utilizan punto flotante, ya que no dependen de la disponibilidad de una unidad de punto flotante (FPU). Esta ventaja era especialmente significativa antes de la adopción generalizada del estándar de punto flotante IEEE , cuando los cálculos de punto flotante con los mismos datos arrojaban resultados diferentes según el fabricante y, a menudo, según el modelo de ordenador.

Muchos procesadores integrados carecen de una unidad de punto flotante (FPU), ya que las unidades aritméticas de enteros requieren muchas menos puertas lógicas y ocupan una superficie de chip considerablemente menor que una FPU; además, la emulación por software de punto flotante en dispositivos de baja velocidad sería demasiado lenta para la mayoría de las aplicaciones. Los chips de CPU de los primeros ordenadores personales y consolas de videojuegos , como el Intel 386 y el 486SX , también carecían de una FPU.

La resolución absoluta (diferencia entre valores sucesivos) de cualquier formato de punto fijo es constante en todo su rango, es decir, el factor de escala S. En cambio, la resolución relativa de un formato de punto flotante es aproximadamente constante en todo su rango, variando dentro de un factor de la base b ; mientras que su resolución absoluta varía en muchos órdenes de magnitud, al igual que los propios valores.

En muchos casos, los errores de redondeo y truncamiento de los cálculos de punto fijo son más fáciles de analizar que los de los cálculos equivalentes de punto flotante. Aplicar técnicas de linealización al truncamiento, como el tramado o la conformación de ruido, es más sencillo dentro de la aritmética de punto fijo. Por otro lado, el uso de punto fijo requiere mayor cuidado por parte del programador. Evitar el desbordamiento requiere estimaciones mucho más precisas para los rangos de las variables y todos los valores intermedios en el cálculo, y a menudo también código adicional para ajustar sus factores de escala. La programación de punto fijo normalmente requiere el uso de tipos enteros de diferentes anchos . Las aplicaciones de punto fijo pueden utilizar punto flotante por bloques , que es un entorno de punto fijo donde cada matriz (bloque) de datos de punto fijo se escala con un exponente común en una sola palabra.

Para sumar o restar dos valores con el mismo factor de escala implícito, basta con sumar o restar los enteros subyacentes; el resultado tendrá su factor de escala implícito común y, por lo tanto, puede almacenarse en las mismas variables de programa que los operandos. Estas operaciones producen el resultado matemático exacto, siempre que no se produzca un desbordamiento , es decir, siempre que el entero resultante pueda almacenarse en la variable de programa receptora . Si se produce un desbordamiento, ocurre como con los enteros ordinarios del mismo signo. En los casos sin signo y con signo mediante complemento a dos, el comportamiento de desbordamiento es bien conocido como un grupo finito .

Si los operandos tienen factores de escala diferentes, deberán convertirse a un factor de escala común antes de la operación.

Para multiplicar dos números de punto fijo, basta con multiplicar los dos números enteros subyacentes y suponer que el factor de escala del resultado es el producto de sus factores de escala.

(p/q) * (r/s) = pr/qs

El resultado será exacto, sin redondeo, siempre que no exceda el límite de la variable receptora. (En concreto, en la multiplicación de enteros, el producto puede tener hasta el doble de la suma de los dos factores).

Por ejemplo, al multiplicar los números 123 escalado por 1/1000 (0,123) y 25 escalado por 1/10 (2,5) se obtiene el entero 123×25 = 3075 escalado por (1/1000)×(1/10) = 1/10000, es decir, 3075/10000 = 0,3075. Como otro ejemplo, al multiplicar el primer número por 155 escalado implícitamente por 1/32 (155/32 = 4,84375) se obtiene el entero 123×155 = 19065 con un factor de escala implícito (1/1000)×(1/32) = 1/32000, es decir, 19065/32000 = 0,59578125.

En binario, es común usar un factor de escala que sea una potencia de dos. Después de la multiplicación, este factor de escala se puede eliminar mediante un desplazamiento a la derecha. Este desplazamiento es sencillo y rápido en la mayoría de las computadoras.

Cuando se utiliza el desplazamiento a la derecha o una instrucción típica de división entera (como la división entera en C y la instrucción idiv de x86), el resultado es equivalente a una división con redondeo hacia abajo (floor(x/y)). Se puede utilizar un método con redondeo para reducir el error introducido. Son posibles tres variantes según la elección del criterio de desempate:

• El redondeo al alza es posible añadiendo un sumando de redondeo equivalente a la mitad del factor de escala antes del desplazamiento. La prueba: redondeo(x/y) = piso(x/y + 0,5) = piso((x + y/2)/y). Si y = 2^n, esto es equivalente a (x + 2^(n−1)) >> n (donde >> representa un desplazamiento a la derecha).
• Redondear hacia abajo a la mitad es, por analogía, floor((x - y/2)/y) o (x - 2^(n-1)) >> n.
• El redondeo a la mitad más cercano implica básicamente tomar una decisión adicional además del redondeo a la mitad más cercano. Es un poco más complicado, pero aún así no requiere bifurcaciones en una CPU. ^{[ 4 ]}

Estos métodos de redondeo se pueden utilizar en cualquier escalado mediante división entera. Por ejemplo, también son aplicables al análisis del reescalado.

La división de números de punto fijo puede entenderse como la división de dos fracciones con denominadores potencialmente diferentes (factores de escala). Con p / q y r / s (donde p, q y rs son todos enteros), el enfoque ingenuo consiste en reorganizar la fracción para formar un nuevo factor de escala (s/q):

(p/q) / (r/s) = (p÷r) / (s÷q)

Por ejemplo, la división de 3456 escalado por 1/100 (34,56) y 1234 escalado por 1/1000 (1,234) produce el entero 3456÷1234 = 3 (redondeado) con factor de escala (1/100)/(1/1000) = 10, es decir, 30. Como otro ejemplo, la división del primer número por 155 escalado implícitamente por 1/32 (155/32 = 4,84375) produce el entero 3456÷155 = 22 (redondeado) con factor de escala implícito (1/100)/(1/32) = 32/100 = 8/25, es decir, 22×32/100 = 7,04.

Con valores de s y q muy similares, el algoritmo anterior da como resultado un factor de escala demasiado grueso. Esto se puede mejorar convirtiendo primero el dividendo a un factor de escala menor. Digamos que reducimos el factor de escala n veces; entonces, en su lugar, calculamos:

(p/q) / (r/s) = (np/nq) / (r/s) = (np÷r) / (s÷nq)

Por ejemplo, si a = 1,23 se representa como 123 con un factor de escala de 1/100, y b = 6,25 se representa como 6250 con un factor de escala de 1/1000, entonces la división simple de los enteros produce 123÷6250 = 0 (redondeado) con un factor de escala de (1/100)/(1/1000) = 10. Si a se convierte primero a 1.230.000 con un factor de escala de 1/1000000, el resultado será 1.230.000÷6250 = 197 (redondeado) con un factor de escala de 1/1000 (0,197). El valor exacto de 1,23/6,25 es 0,1968.

Otra forma de entender la escala es considerar la división, la operación inversa de la multiplicación. Si la multiplicación produce un factor de escala más fino, es lógico que el dividendo también deba tener un factor de escala más fino para recuperar el valor original.

En la computación de punto fijo, a menudo es necesario convertir un valor a un factor de escala diferente. Esta operación es necesaria, por ejemplo:

• Para almacenar un valor en una variable de programa que tiene un factor de escala implícito diferente;
• Para convertir dos valores al mismo factor de escala, de modo que puedan sumarse o restarse;
• Para restaurar el factor de escala original de un valor después de multiplicarlo o dividirlo por otro;
• Para mejorar la exactitud del resultado de una división;
• Para asegurar que el factor de escala de un producto o cociente sea una potencia simple como 10 ⁿ o 2 ⁿ ;
• Para garantizar que el resultado de una operación pueda almacenarse en una variable de programa sin desbordamiento;
• Para reducir el coste del hardware que procesa datos de punto fijo.

Para convertir un número de un tipo de punto fijo con factor de escala R a otro tipo con factor de escala S , el entero subyacente debe multiplicarse por la razón R / S. Así, por ejemplo, para convertir el valor 1,23 = 123/100 de un factor de escala R = 1/100 a uno con factor de escala S = 1/1000, el entero 123 debe multiplicarse por (1/100)/(1/1000) = 10, lo que da como resultado la representación 1230/1000.

Si el factor de escala es una potencia de la base utilizada internamente para representar el número entero, cambiarlo solo requiere eliminar los dígitos de menor orden o añadir ceros. Sin embargo, esta operación debe conservar el signo. En la representación en complemento a dos, esto implica extender el bit de signo, como en las operaciones de desplazamiento aritmético .

Si S no divide a R (en particular, si el nuevo factor de escala S es mayor que el R original ), es posible que haya que redondear el nuevo número entero .

En particular, si r y s son variables de punto fijo con factores de escala implícitos R y S , la operación r ← r × s requiere multiplicar los enteros correspondientes y dividir explícitamente el resultado por S. Es posible que el resultado deba redondearse y que se produzca un desbordamiento.

Por ejemplo, si el factor de escala común es 1/100, multiplicar 1,23 por 0,25 implica multiplicar 123 por 25 para obtener 3075 con un factor de escala intermedio de 1/10000. Para volver al factor de escala original de 1/100, el número entero 3075 debe multiplicarse por 1/100, es decir, dividirse por 100, para obtener 31 (0,31) o 30 (0,30), según la política de redondeo utilizada.

De manera similar, la operación r ← r / s requerirá dividir los números enteros y multiplicar explícitamente el cociente por S. Aquí también pueden producirse redondeos y/o desbordamientos.

Para convertir un número de coma flotante a coma fija, se puede multiplicar por el factor de escala S y redondear el resultado al entero más cercano. Es importante asegurarse de que el resultado quepa en la variable o registro de destino. Dependiendo del factor de escala, el tamaño de almacenamiento y el rango de números de entrada, la conversión podría no requerir redondeo.

Para convertir un número de punto fijo a punto flotante, se puede convertir el entero a punto flotante y luego dividirlo por el factor de escala S. Esta conversión puede implicar redondeo si el valor absoluto del entero es mayor que 2²⁴ ⁽ para punto flotante IEEE de precisión simple binaria) o de 2⁵³ ⁽ para precisión doble). Puede producirse un desbordamiento o un subdesbordamiento si | S | es muy grande o muy pequeño, respectivamente.

Los procesadores típicos no ofrecen soporte específico para la aritmética de punto fijo. Sin embargo, la mayoría de las computadoras con aritmética binaria cuentan con instrucciones de desplazamiento de bits rápidas que permiten multiplicar o dividir un número entero por cualquier potencia de 2; en particular, una instrucción de desplazamiento aritmético . Estas instrucciones se pueden usar para cambiar rápidamente factores de escala que sean potencias de 2, conservando el signo del número.

Las primeras computadoras, como la IBM 1620 y la Burroughs B3500, utilizaban una representación decimal codificada en binario (BCD) para los números enteros, concretamente en base 10, donde cada dígito decimal se codificaba de forma independiente con 4 bits. Algunos procesadores, como los microcontroladores, aún pueden utilizarla. En estas máquinas, la conversión de los factores de escala decimal se puede realizar mediante desplazamientos de bits o manipulación de direcciones de memoria.

Algunas arquitecturas DSP ofrecen soporte nativo para formatos de punto fijo específicos, por ejemplo, números de n bits con signo y n −1 bits fraccionarios (cuyos valores pueden oscilar entre −1 y casi +1). Este soporte puede incluir una instrucción de multiplicación con renormalización: la conversión de escala del producto de 2 n −2 a n −1 bits fraccionarios. Si la CPU no ofrece esta función, el programador debe guardar el producto en un registro o variable temporal de tamaño suficiente e implementar la renormalización explícitamente.

El desbordamiento se produce cuando el resultado de una operación aritmética es demasiado grande para almacenarse en el área de destino designada. En la suma y la resta, el resultado puede requerir un bit más que los operandos. En la multiplicación de dos enteros sin signo de m y n bits, el resultado puede tener m + n bits.

En caso de desbordamiento, los bits de orden superior suelen perderse, ya que el entero sin escalar se reduce módulo 2ⁿ ^, donde n es el tamaño del área de almacenamiento. En particular, se pierde el bit de signo, lo que puede alterar radicalmente el signo y la magnitud del valor.

Algunos procesadores pueden activar un indicador de desbordamiento de hardware o generar una excepción cuando se produce un desbordamiento. Otros, en cambio, utilizan aritmética de saturación : si el resultado de una suma o resta se desborda, almacenan el valor de mayor magnitud que cabe en el área de almacenamiento y que tiene el signo correcto.

Sin embargo, estas características no son muy útiles en la práctica; por lo general, es más fácil y seguro seleccionar factores de escala y tamaños de palabra para excluir la posibilidad de desbordamiento, o comprobar si los operandos tienen valores excesivos antes de ejecutar la operación.

Supongamos que existe la siguiente multiplicación con dos números de punto fijo de 3 cifras decimales.

${\displaystyle {\begin{aligned}(10.500)(1.050)&=1\times 10.500+0.050\times 10.500\\&=10.500+0.525000=11.025000\end{aligned}}}$

Nótese cómo, dado que hay 3 decimales, mostramos los ceros finales. Para volver a caracterizar esto como una multiplicación entera, primero debemos multiplicar por${\displaystyle 1000\ (=10^{3})}$, moviendo todos los decimales a posiciones enteras, luego multiplicaremos por${\displaystyle 1/1000\ (=10^{-3})}$para volver a colocarlos. La ecuación ahora se ve así:

${\displaystyle {\begin{aligned}(10.500)(10^{3})(1.050)(10^{3})(10^{-3})(10^{-3})&=(10500)(1050)(10^{-6})\\&=11\,025\,000(10^{-6})\\&=11.025000\end{aligned}}}$

Esto funciona de forma equivalente si elegimos una base diferente, concretamente la base 2 para computación, ya que un desplazamiento de bits es lo mismo que una multiplicación o división por un factor de 2. Tres dígitos decimales equivalen a unos 10 dígitos binarios, por lo que deberíamos redondear 0,05 a 10 bits después del punto binario. La aproximación más cercana es entonces 0,0000110011.

${\displaystyle {\begin{aligned}10&=8+2=2^{3}+2^{1}\\1&=2^{0}\\0.5&=2^{-1}\\0.05&=0.0000110011_{2}\end{aligned}}}$

Así, nuestra multiplicación se convierte en

${\displaystyle {\begin{aligned}(1010.100)(2^{3})(1.0000110011)(2^{10})(2^{-13})&=(1010100)(10000110011)(2^{-13})\\&=(10110000010111100)(2^{-13})\\&=1011.0000010111100\end{aligned}}}$

Esto se redondea a 11,023 con tres dígitos después del punto decimal.

Consideremos la tarea de calcular el producto de 1.2 y 5.6 con punto fijo binario usando 16 bits de fracción. Para representar los dos números, se multiplican por 2¹⁶ ^, obteniendo 78 643.2 y 367 001.6 ; y se redondean estos valores al entero más cercano, obteniendo 78 643 y 367 002. Estos números caben cómodamente en una palabra de 32 bits con formato de complemento a dos con signo.

Al multiplicar estos enteros, se obtiene el entero de 35 bits 28 862 138 286 con 32 bits de fracción, sin redondeo. Cabe destacar que almacenar este valor directamente en una variable entera de 32 bits provocaría un desbordamiento y la pérdida de los bits más significativos. En la práctica, probablemente se almacenaría en una variable o registro entero con signo de 64 bits .

Si el resultado se va a almacenar en el mismo formato que los datos, con 16 bits de fracción, ese entero debe dividirse por 2 ¹⁶ , lo que da aproximadamente 440 401 .28, y luego redondearse al entero más cercano. Este efecto se puede lograr sumando 2 ¹⁵ y luego desplazando el resultado 16 bits. El resultado es 440 401 , que representa el valor 6. 719 985 961 914 062 5 . Teniendo en cuenta la precisión del formato, ese valor se expresa mejor como 6. 719 986 ± 0. 000 008 (sin contar el error que proviene de las aproximaciones de los operandos). El resultado correcto sería 1.2 × 5.6 = 6.72.

Para un ejemplo más complejo, supongamos que los números 1.2 y 5.6 se representan en formato de punto fijo de 32 bits con 30 y 20 bits de fracción, respectivamente. Al escalarlos por 2³⁰ y 2²⁰ se obtienen 1²⁸⁸⁴⁰¹⁸⁸ y 5 872 025,6, que se redondean a 1²⁸⁸⁴⁰¹⁸⁹ y 5 872 ⁰²⁶ , ^{respectivamente} . Ambos números aún caben en una variable entera con signo de 32 bits y representan las fracciones .

1. 200 000 000 186 264 514 923 095 703 125 y

5. 600 000 381 469 726 562 50

Su producto es (exactamente) el entero de 53 bits 7 566 047 890 552 914 , que tiene 30+20 = 50 bits de fracción implícitos y, por lo tanto, representa la fracción.

6. 720 000 458 806 753 229 623 609 513 510

Si elegimos representar este valor en formato fijo de 16 bits con signo y 8 bits de fracción, debemos dividir el producto entero por 2 ⁵⁰⁻⁸ = 2 ⁴² y redondear el resultado; lo cual se puede lograr sumando 2 ⁴¹ y desplazando 42 bits. El resultado es 1720, que representa el valor 1720/2 ⁸ = 6,718 75 , o más bien el intervalo entre 3439/2 ⁹ y 3441/2 ⁹ (aproximadamente 6,719 ± 0,002).