El problema es contar la suma de la serie finita $$\sum_{k=0}^{k_0} \frac{a_k}{b_k}$$ Necesito contar en esta serie en binario con cierta precisión, que sería la salida de $n$ binario correcto de dígitos después del punto decimal. Solo puedo utilizar la división entera y además y es garantizado que $\frac{a_k}{b_k}>0$ Con el fin de hacer que yo había tratado de contar esa serie: $$\sum_{k=0}^{k_0} \frac{2^na_k}{b_k}$$ Pero yo no lo había notado que tal situación puede ocurrir: $$\sum_{k=0}^{k_0} \{\frac{2^na_k}{b_k}\} > 1$$ * $\{\bullet\}$ Denota la parte después del punto decimal. Así que supongo que $$\sum_{k=0}^{k_0} \frac{2^n 2^{k_0+1} a_k}{b_k}$$ te dar n precisa binario de dígitos después del punto decimal, si utilizamos la división de enteros. El problema es que tengo que demostrar que. Y yo realmente no sé cómo hacer eso. Gracias
Respuesta
¿Demasiados anuncios?
Si usted toma el coeficiente de todos los términos a ser $2^n2^m$ para suficientemente grande $m$, entonces usted será capaz de extraer con éxito la primera $n$ bits después del punto decimal. $m = k_0 + 1$ sin duda el trabajo sino $m = O(\log k_0)$ también debería funcionar. El punto es que en la mayoría de los perderá 1 bit de contribución adicional al $(n + m)$º lugar después de la coma decimal, debido a la división de enteros, y por lo que incluso si usted consigue esta pérdida máxima para todos los $k_0$ términos, el que más pierde es $k_0 2^{-n-m}$ de la suma real. Así que mientras a $k_0 < 2^m$, usted no obtendrá una perdida contribución capaz de cambiar el primer $n$ bits después del punto decimal por más de $1$. La única pregunta es si usted desea redondear a la unidad más cercana a $n$ bits después del punto decimal, o truncar. Si desea redondear, sólo tiene que utilizar $n+1$ en lugar de $n$ y, a continuación, utilizar el valor de la inferirse $(n+1)$th poco para decidir si la vuelta de la primera $n$ bits para el valor siguiente.
