¿Existe algún software que pueda autogenerar rutinas C de coma flotante con precisión numérica a partir de fórmulas simbólicas?

25

Dada la función real de las variables reales, ¿existe un software disponible que pueda generar automáticamente un código numérico exacto para calcular la función sobre todas las entradas en una máquina equipada con aritmética IEEE 754?

Por ejemplo, si la función real a evaluar fuera:

f (a, b, c) = \ frac {-b - \ sqrt {b ^ 2 - 4ac}} {2a}

El software consideraría la cancelación catastrófica y posiblemente la búsqueda de tablas de salida para ciertos conjuntos de entradas para evitar una pérdida en la precisión computacional.

Alternativamente, ¿hay algún software que pueda generar una rutina de búsqueda pura basada en tablas para calcular una función dada con alta precisión?

Daniel Trebbien
fuente
55
Problema difícil en general.
dmckee
1
Si el problema hubiera sido específicamente sobre el cálculo raíz (o factorización) de polinomios, existen algunas bibliotecas C (o C ++).
moala
2
Es posible que desee consultar la excelente serie de artículos de Richard Harris en la revista ACCU Overload sobre The Floating Point Blues . Los indicé en Programmers.SX para las personas que podrían estar interesadas.
Mark Booth

Respuestas:

25

La mejor solución que conozco es programar las expresiones simbólicas en Mathematica , Maple o SymPy ; Todos los enlaces van directamente a la documentación de generación de código. Todos los programas anteriores pueden generar código en C o Fortran.

Ninguno de los programas anteriores menciona precisión en aritmética IEEE 754; en general, sería difícil anticipar todas las fuentes de cancelación catastrófica, como señala @dmckee. Es difícil reemplazar la experiencia humana en análisis numérico.

Para proporcionar un ejemplo concreto, considere calcular las funciones trigonométricas con alta precisión para entradas arbitrarias en . Hay muchas estrategias para hacerlo, algunas incluso dependen del hardware, como se ve en el artículo de Wikipedia Trigonometric Tables . Todos los algoritmos requieren ingenio y análisis numérico, incluso los algoritmos que dependen de tablas de búsqueda y series o interpolación de Taylor (consulte el artículo de Wikipedia The Table-Maker's Dilemma ). Para obtener más detalles, consulte la pregunta relacionada sobre el desbordamiento de pila ¿ Cómo funcionan las funciones trigonométricas? .[0,2π]

El software que generó código o rutinas para calcular funciones arbitrarias con alta precisión no solo necesitaría tener en cuenta los errores de cancelación, sino también las aproximaciones de series (Taylor, Padé, Chebyshev, racionales, etc.) para calcular funciones que no están definidas en términos de un número finito de sumas, restas, multiplicaciones, divisiones y cambios de bits. (Ver Teoría de la aproximación ).

Geoff Oxberry
fuente
44
"Es difícil reemplazar la experiencia humana en análisis numérico". - esto solo merece un +1.
JM
"Es difícil" no es lo mismo que "es imposible". Existen "teoremas de pleno empleo" para algunos trabajos (por ejemplo, escritores de compiladores). ¿Hay uno para analistas numéricos?
Seudónimo
Sí. El teorema del arroz .
Geoff Oxberry
14

Si desea tener una idea de cuán lejos estamos de un paquete de software de este tipo, consulte la nota de trabajo LAPACK 2001 sobre computación. Da rotaciones de manera confiable y eficiente . Esperaría que la mayoría de los no especialistas (¡y muchos especialistas!) En análisis numérico se sorprendan de cuánto análisis se llevó a cabo para resolver un problema tan aparentemente simple:

Dado , encuentre y modo que c R s Cf,gCcRsC

R(c,s)[fg]=[css¯c][fg]=[r0]
,

donde es unitario. Equilibrar la confiabilidad con la eficiencia computacional junto con problemas más sutiles como la continuidad es altamente no trivial y es poco probable que se automatice en el futuro previsible.R(c,s)

Jack Poulson
fuente
1
+1 Este es un gran ejemplo, gracias. Supongo que si existiera una solución para los reales, entonces podría adaptarse a números complejos.
Daniel Trebbien
Probablemente debería mencionar que la dificultad fundamental no está en el hecho de que s puede ser complejo, sino en evitar el desbordamiento y / o el desbordamiento innecesario. Está relacionado con la función hipot: en.wikipedia.org/wiki/Hypot
Jack Poulson
11

La generación de código y la precompilación de expresiones matemáticas se está volviendo más popular.

Si bien los paquetes simbólicos como SymPy, Mathematica y Maple pueden incluir generación de código, no estoy seguro de que ninguno de ellos también piense mucho en los números.

Hay un par de otros proyectos en los que uno podría estudiar y que están interesados ​​tanto en simbólicos como en numéricos.

Theano es un proyecto de este tipo centrado en operaciones de matriz. Identifican y reemplazan algunas operaciones que se sabe que están numéricamente mal acondicionadas. No estoy seguro de que esto incluya su caso específico, pero vale la pena analizarlo.

Espiral también puede ser interesante para usted. También precompilan un árbol de sintaxis abstracta y también buscan problemas numéricos. Están más preocupados con las operaciones escalares (como su ejemplo). Sin embargo, también están bastante especializados en un dominio particular.

Sin embargo, el crecimiento en este campo es alentador. Uno puede ser optimista de que su pregunta tendrá una mejor respuesta en unos años.

MRocklin
fuente
2
Convenido; tal vez mi respuesta fue demasiado pesimista, ya que hay muchas soluciones específicas de dominio, pero el problema general es ... difícil.
Jack Poulson
4

No en general, puedo decir con seguridad que el implementador del generador de código en SymPy ni siquiera intentó = P.

Paolo Bientinesi desarrolló un método para generar pruebas de estabilidad de algoritmos de álgebra lineal, que se generan utilizando la notación FLAME de Robert van de Geijn.

Vea este documento , o una versión más larga de notas de trabajo .

aterrel
fuente
1

Sage le permite expresar fórmulas en Cython (una variante de python que genera código C); sin embargo, en respuesta a su pregunta más general: no. Considere el teorema de Rice .

mda
fuente