El punto flotante actual (flotante ANSI C, doble) permite representar una aproximación de un número real.
¿Hay alguna forma de representar números reales sin errores ?
Aquí hay una idea que tuve, que es todo menos perfecta.
Por ejemplo, 1/3 es 0.33333333 ... (base 10) u o.01010101 ... (base 2), pero también 0.1 (base 3)
¿Es una buena idea implementar esta "estructura":
base, mantissa, exponent
entonces 1/3 podría ser 3 ^ -1
{[11] = base 3, [1.0] mantissa, [-1] exponent}
¿Alguna otra idea?
Respuestas:
Todo depende de lo que quieras hacer.
Por ejemplo, lo que muestra es una excelente manera de representar números racionales. Sin embargo, todavía no puede representar algo así como o correo a la perfección.π mi
De hecho, muchos lenguajes como Haskell y Esquema han construido en el soporte para los números racionales, almacenándolos en la forma dondea,bson enteros.unsi a , b
La razón principal por la que estos no son ampliamente utilizados es el rendimiento. Los números de coma flotante son un poco imprecisos, pero sus operaciones se implementan en hardware. Su sistema propuesto permite una mayor precisión, pero requiere varios pasos para implementar, en lugar de una sola operación que se puede realizar en hardware.
Se sabe que algunos números reales son incomputable, tales como los números de acampada . No hay ningún algoritmo de enumeración de sus dígitos, a diferencia de , donde podemos calcular el n º dígitos, siempre y cuando esperamos lo suficiente.π norte
Si desea una precisión real para cosas irracionales o números trascendentales, es probable que necesite usar algún tipo de sistema de álgebra simbólica, luego obtenga una respuesta final en forma simbólica, que podría aproximar a cualquier número de dígitos. Sin embargo, debido a los problemas de indecidibilidad descritos anteriormente, este enfoque es necesariamente limitado. Todavía es bueno para cosas como integrales aproximadas o series infinitas.
fuente
No hay forma de representar todos los números reales sin errores si cada número debe tener una representación finita. Hay innumerables números reales, pero solo innumerables cadenas finitas de 1 y 0 que podría usar para representarlos.
fuente
Su idea no funciona porque un número representado en la base con mantisa my exponente e es el número racional b ⋅ m - e , por lo tanto, su representación funciona precisamente para números racionales y no para otros. No puedes representar √si metro mi b ⋅ m- e por ejemplo.2-√
Hay toda una rama de las matemáticas computables que se ocupa de la aritmética real exacta. Se han propuesto muchas estructuras de datos para representar números reales exactos : flujos de dígitos, flujos de contracciones afines, secuencias de Cauchy de racionales, secuencias de Cauchy de racionales diádicos, cortes de Dedekind, secuencias de intervalos shkrinking, etc. Existen implementaciones de bases aritméticas reales exactas. sobre estas ideas, por ejemplo:
De estos, iRRAM es el más maduro y eficiente. Marshall en un proyecto experimental, mientras que el tercero es un proyecto estudiantil, pero también el más accesible. Tiene una introducción muy agradable que explica los problemas relacionados con el cálculo de números reales, le recomiendo que lo mire.
Déjame hacer un comentario. Alguien objetará que un objeto infinito no puede ser representado por una computadora. En cierto sentido, esto es cierto, pero en otro no lo es. Nunca tenemos que representar un número real completo , solo necesitamos una aproximación finitaen cada etapa de la computación. Por lo tanto, solo necesitamos una representación que pueda representar una precisión real hasta cualquier precisión dada. Por supuesto, una vez que se nos acaba la memoria de la computadora, se nos acaba la memoria de la computadora, pero eso es una limitación de la computadora, no la representación en sí. Esta situación no es diferente a muchas otras en programación. Por ejemplo, las personas usan números enteros en Python y piensan en ellos como "arbitrariamente grandes" aunque, por supuesto, no pueden exceder el tamaño de la memoria disponible. A veces, el infinito es una aproximación útil para un número finito muy grande.
Además, a menudo escucho la afirmación de que las computadoras solo pueden manejar números reales computables . Esto pierde dos puntos importantes. Primero, las computadoras tienen acceso a los datos del mundo externo, por lo que también tendríamos que suponer (no verificable) que el mundo externo también es computable. En segundo lugar, necesitamos distinguir entre los reales que una computadora puede calcular y los reales que puede representar. Por ejemplo, si elegimos flujos de dígitos como representación de reales, entonces es perfectamente posible representar un real no computable: si alguien nos lo diera, sabríamos cómo representarlo. Pero si elegimos representar reales como piezas de código fuente que computan dígitos, entonces no podríamos representar reales no computables, obviamente.
En cualquier caso, este tema se aborda mejor con algunas lecturas adicionales.
fuente
Hay muchas implementaciones efectivas de números racionales , pero una que se ha propuesto muchas veces y que incluso puede manejar algunos irracionales bastante bien es las fracciones continuas .
Cita de las fracciones continuas de Darren C. Collins :
Cita de Mathworld - Fracciones continuas periódicas
es decir, todas las raíces se pueden expresar como fracciones continuas periódicas.
También hay una fracción continua exacta para π que me sorprendió hasta que @AndrejBauer señaló que en realidad no lo es.
fuente
Hay una serie de sugerencias "reales reales" en los comentarios (por ejemplo, fracciones continuas, transformaciones fraccionales lineales, etc.). El problema típico es que, si bien puedes calcular las respuestas a una fórmula, la igualdad a menudo es indecidible.
Sin embargo, si solo está interesado en los números algebraicos, entonces tiene suerte: la teoría de los campos cerrados reales es completa, mínima y decidible. Esto fue probado por Tarski en 1948.
Pero hay una trampa. No desea utilizar el algoritmo de Tarski, ya que se encuentra en la clase de complejidad NONELEMENTARY, que es tan poco práctico como los algoritmos poco prácticos pueden ser. Hay métodos más recientes que reducen la complejidad a DEXP, que es lo mejor que conocemos actualmente.
Tenga en cuenta que el problema es NP-hard porque incluye SAT. Sin embargo, no se sabe (ni se cree) que esté en NP.
EDITAR Voy a tratar de explicar esto un poco más.
El marco para comprender todo esto es un problema de decisión conocido como Teorías del módulo de satisfacción, o SMT para abreviar. Básicamente, queremos resolver SAT para una teoría construida sobre la lógica clásica.
Entonces comenzamos con la lógica clásica de primer orden con una prueba de igualdad. Qué símbolos de función queremos incluir y cuáles son sus axiomas determinan si la teoría es o no decidible.
Hay muchas teorías interesantes expresadas en el marco SMT. Por ejemplo, existen teorías de estructuras de datos (por ejemplo, listas, árboles binarios, etc.) que se utilizan para ayudar a probar que los programas son correctos, y la teoría de la geometría euclidiana. Pero para nuestro propósito, estamos viendo teorías de diferentes tipos de números.
La aritmética previa a la hamburguesa es la teoría de los números naturales con suma. Esta teoría es decidible.
La aritmética de peano es la teoría de los números naturales con suma y multiplicación. Esta teoría no es decidible, como lo demostró Gödel.
La aritmética de Tarski es la teoría de los números reales con todas las operaciones de campo (suma, resta, multiplicación y división). Curiosamente, esta teoría es decidible. Este fue un resultado altamente contra-intuitivo en ese momento. Puede suponer que porque es un "superconjunto" de los números naturales es "más difícil", pero este no es el caso; compare la programación lineal sobre los racionales con la programación lineal sobre los enteros, por ejemplo.
Puede que no parezca obvio que la satisfacción es todo lo que necesita, pero lo es. Por ejemplo, si desea probar si la raíz cuadrada positiva de 2 es igual o no a la raíz cúbica real de 3, puede expresar esto como el problema de la satisfacción:
Alfred Tarski (1948), Un método de decisión para álgebra y geometría elementales .
fuente
Es posible representar una clase muy grande de números llamados números algebraicos exactamente, tratándolos como raíces de polinomios.
fuente
fuente
No puede representar todos los números reales en una computadora, pero puede representar muchos. Podrías usar fracciones que representarían más números que flotantes. También podría hacer cosas más sofisticadas como representar números como raíz de algún polinomio con una aproximación que según el método de newtons convergerá al número.
fuente
Es posible representar cualquier número con precisión donde las entradas son representables almacenándolas como una cadena de operaciones, por ejemplo, almacenando
1/3
como1 divided by 3
, al manejar la cancelación de operaciones puede simplificar la siguiente operación para dar una respuesta exacta(1/3) * 3
. Esto también puede manejar situaciones en las que ha conocido irracionales, comoπ
retenerlo en sus cálculos.Sin embargo, requiere una cantidad creciente de memoria para cada número y, suponiendo que su simplificador no sea perfecto, probablemente requerirá una cantidad cada vez mayor para los valores en los que está trabajando mucho.
fuente