Aproximación de un decimal con una fracción (punto fijo de 32 bits a dos números de 23 bits). Piensa en binario, facilidad de cálculo.

Question

Tengo un número decimal de 32 bits de ancho fijo entre 0 y 1,0 (en realidad se garantiza que está entre 0,001 y 0,02, por lo que la pérdida de rango es aceptable en la aproximación). La representación binaria se define como que el bit más significativo representa 1/2, el bit siguiente 1/4, y así sucesivamente hasta los 32 bits.

Debo representar este número como un cociente de dos números de 23 bits (en realidad, uno de ellos es de 23 y otro de 18 bits, pero simplifiquemos por el bien de la discusión). No importa cuáles sean los dos números mientras cada uno de ellos quepa en 23 bits.

Otra forma de pensar en este problema es que tengo una fracción con un numerador de 32 bits y un denominador constante conocido de 2^32. Debo aproximar esta fracción como otra fracción con numerador de 23 bits y denominador de 23 bits, de manera que un error de no más de 1/(2^32) sea aceptable.

¿Existe algún algoritmo razonablemente eficiente que me permita hacer esto sin tener que adivinar y comprobar por la fuerza bruta? Lo ideal sería algún tipo de truco de "manipulación de bits", ya que esto debe hacerse en un microcontrolador bastante pequeño. Si no es así, lo siguiente mejor sería la aritmética de enteros.

Entiendo que como estoy reempaquetando 32 bits de información en un total de 46 bits de información, teóricamente es posible. Una solución de fuerza bruta de adivinar y comprobar hasta que algún par de números funcione es bastante trivial. Lo que estoy buscando es algún algoritmo más eficiente o al menos una forma de averiguar un buen punto de partida para adivinar y comprobar. Lo ideal sería que hubiera un límite de tiempo definido para la ejecución de este algoritmo.

Por ejemplo, mi entrada (A) es 0,005777551792562008. Si tomamos la representación binaria de esto

0b 0000 0001 0111 1010 1010 0011 0011 1100

se puede reinterpretar como el entero sin signo de 32 bits 24.814.396.

Este número puede representarse como la relación (N/D) $$0.005777551792562008 = \frac{24814396}{2^{32}} \approx \frac{41572}{7195435} = 0.005777552017355449$$ .

En este caso, el error de la aproximación es de 2,248e-10 que es menor que 1/(2^32)=2,328e-10 .

La situación descrita en esta pregunta es bastante específica porque se basa en un escenario del mundo real. Sin embargo, siéntase libre de generalizar, incluso si su generalización hace que la respuesta no se ajuste a la situación específica que describo.

El objetivo de esta pregunta es obtener algunas ideas sobre por dónde empezar y, con suerte, dejar algo que sea aplicable en más situaciones. Calcular una aproximación fraccionaria "suficientemente cercana" a un decimal es un problema bastante general, pero que no he visto que se haya abordado específicamente en el contexto de los ordenadores y la representación binaria.

Answer 1

Encontrar aproximaciones racionales a un número es un campo conocido como Aproximación diofantina . En tu caso, estás tratando de encontrar la aproximación más exacta dentro de unos límites en los valores del numerador y el denominador. Resulta que puedes encontrar la mejor aproximación racional a un número utilizando su Fracción continua representación.

Algoritmo

1. Toma la parte entera del número y escríbela.
2. Dividir $1$ por la parte fraccionaria del número.
3. Repita los pasos $1$ y $2$ hasta alcanzar la precisión necesaria.

Voy a dar un ejemplo rápido de cómo encontrar la fracción continua para $\pi$ .

$$\begin{align} \pi&=3+0.14159...\\ &=3+\frac1{7+0.06251...}\\ &=3+\frac1{7+\frac1{15+0.99659}}\\ \pi&\approx3+\frac1{7+\frac1{15+\frac11}}\\ &\approx\frac{355}{113} \end{align}$$

$\frac{355}{113}$ es la mejor aproximación racional de $\pi$ con un denominador inferior a $113$ . Es preciso hasta quince dígitos. Generalmente, el error entre la aproximación y el número es $$\left|n-\frac pq\right|<\frac1{q^2}$$

Esto significa que siempre que se pueda obtener un denominador mayor que $2^{16}=65536$ se garantiza la obtención de un resultado dentro de los límites indicados anteriormente.

Notas

Las fracciones continuas se escriben a menudo con la notación $$\pi\approx[3;7,15,1]= 3+\frac1{7+\frac1{15+\frac11}}$$ donde la parte entera es el primer número y todos los demás números van en el denominador.

En su ejemplo concreto de $0.005777551792562008$ la fracción continua de su aproximación es como

mientras que la aproximación de la fracción continua es como

Fíjate en lo similares que son las dos fracciones continuas, ya que los cinco primeros términos son idénticos. Sin embargo, la aproximación de la fracción continuada dentro del rango que has utilizado es todavía más precisa, teniendo tu aproximación un error mayor que el de la fracción continuada por $2.247823\cdot10^{-10}$ .

Answer 2

Ejemplo elaborado con fracciones continuas :

La fracción $24814396/2^{32}$ se simplifica a $6203599/1073741824$ cuya fracción continua se calcula como sigue:

$$\begin{align} 1073741824 &= \mathbf{173} \cdot 6203599 + 519197\\ 6203599 &= \mathbf{11} \cdot 519197 + 492432 \\ 519197 &= \mathbf{1} \cdot 492432 + 26765 \\ 492432 &= \mathbf{18} \cdot 26765 + 10662 \\ 26765 &= \mathbf{2} \cdot 10662 + 5441 \\ 10662 &= \mathbf{1} \cdot 5441 + 5221 \\ 5441 &= \mathbf{1} \cdot 5221 + 220 \\ 5221 &= \mathbf{23} \cdot 220 + 161 \\ 220 &= \mathbf{1} \cdot 161 + 59 \\ 161 &= \mathbf{2} \cdot 59 + 43 \\ 59 &= \mathbf{1} \cdot 43 + 16 \\ 43 &= \mathbf{2} \cdot 16 + 11 \\ 16 &= \mathbf{1} \cdot 11 + 5 \\ 11 &= \mathbf{2} \cdot 5 + 1 \\ 5 &= \mathbf{5} \cdot 1. \end{align}$$

Así que la fracción continua (finita) en este caso es $[0;173,11,1,18,2,1,1,23,1,2,1,2,1,2,5]$ .

Calculando los convergentes de esta fracción continua (hay una recursión muy sencilla para este cálculo) se obtiene la secuencia de aproximaciones

173: 1/173 = 0.005780346820809248
 11: 11/1904 = 0.005777310924369748
  1: 12/2077 = 0.005777563793933558
 18: 227/39290 = 0.005777551539832018
  2: 466/80657 = 0.005777551855387629
  1: 693/119947 = 0.00577755175202381
  1: 1159/200604 = 0.005777551793583378
 23: 27350/4733839 = 0.005777551792530334
  1: 28509/4934443 = 0.005777551792573143
  2: 84368/14602725 = 0.005777551792559265
  1: 112877/19537168 = 0.00577755179256277
  2: 310122/53677061 = 0.005777551792561817
  1: 422999/73214229 = 0.005777551792562071
  2: 1156120/200105519 = 0.005777551792562004
  5: 6203599/1073741824 = 0.005777551792562008

Podemos ver que el denominador 4934443 es lo suficientemente pequeño para un entero de 23 bits, pero 14602725 es demasiado grande. Así que una respuesta sería cortarlo en $28509/4934443$ por un error de 1.113e-14 . Esto es probablemente óptimo porque $4934443$ está bastante cerca del límite superior, pero si el límite fuera sólo un poco más alto podríamos bajar el coeficiente $2$ en la siguiente fila para $1$ y obtener $55859/9668282$ que tiene un error ligeramente mejor que 1e-14 .