tipos pseudocodigo programacion informatica funciones estructura ejemplos caracteristicas algoritmos algoritmo algorithm math reference d standard-library

algorithm - pseudocodigo - ¿Dónde encontrar algoritmos para las funciones matemáticas estándar?



tipos de algoritmos (8)

Consulte Código autónomo para computación numérica para enlaces a códigos para algunas funciones especiales y para generación de números aleatorios. Todo el código allí es de dominio público. El código se implementa en C ++ y Python, pero es fácil de traducir a cualquier otro idioma.

Estoy buscando enviar un parche a la biblioteca estándar de lenguaje de programación D que permitirá que gran parte de std.math se evalúe en tiempo de compilación utilizando las funciones de evaluación de la función de tiempo de compilación del lenguaje. La evaluación de la función de tiempo de compilación tiene varias limitaciones, las más importantes son:

  1. No puedes usar el lenguaje ensamblador.
  2. No puede llamar al código C o al código cuya fuente no está disponible.

Varias funciones estándar violan estas y las versiones en tiempo de compilación deben escribirse. ¿Dónde puedo obtener información sobre buenos algoritmos para calcular cosas como logaritmos, exponentes, poderes y funciones trigonométricas? Prefiero solo descripciones de alto nivel de algoritmos para el código real, por dos razones:

  1. Para evitar la ambigüedad legal y la necesidad de hacer que mi código se vea "lo suficientemente diferente" de la fuente para asegurarme de que soy el propietario de los derechos de autor.

  2. Quiero algoritmos simples y portátiles. No me importa la micro-optimización siempre que sean al menos tan eficientemente asintóticamente.

Editar: el modelo de evaluación de función de tiempo de D''D permite que los resultados flotantes computados en tiempo de compilación difieran de los computados en tiempo de ejecución de todos modos, así que no me importa si mis algoritmos en tiempo de compilación no dan exactamente el mismo resultado que la versión en tiempo de ejecución siempre y cuando no sean menos precisos en un grado prácticamente significativo.

El libro de Jean-Michel Muller es una excelente recomendación, al igual que Hart.

¿Es realmente necesario que tengas los derechos de autor? Por lo general, es una mala idea entrar en el negocio de escribir funciones de biblioteca matemática si puede evitarlo (y lo digo como alguien que lo hace profesionalmente). No sé si D puede tomar el código con licencia BSD, pero hay varias buenas implementaciones de código abierto que pueden ser útiles. Es posible que desee ver el FDLIBM de Sun , por ejemplo. Los Cephes de Stephen Moshier también serían una posibilidad, aunque su situación de licenciamiento es un poco extraña, pero creo que ha estado dispuesto a permitir que la gente redistribuya su código bajo otras licencias en el pasado.

En una nota lateral, a menos que esté apoyando el punto flotante de precisión arbitraria (no creo que D lo haga), no suele haber una noción de "eficiencia asintótica" para las funciones de la libma.

La fuente que recomiendo es Métodos Numéricos para Científicos e Ingenieros por RW Hamming.

Este libro es publicado por Dover Press, y es un libro de bolsillo de bajo costo.

Como era de esperar, surgen problemas similares en otros idiomas:

http://java.sun.com/j2se/1.5.0/docs/api/java/lang/StrictMath.html

Para ayudar a garantizar la portabilidad de los programas Java, las definiciones de algunas de las funciones numéricas en este paquete requieren que produzcan los mismos resultados que ciertos algoritmos publicados. Estos algoritmos están disponibles en la conocida biblioteca de red netlib como paquete "Librería de matemáticas libremente distribuible", fdlibm. Estos algoritmos, que están escritos en el lenguaje de programación C, deben entenderse como ejecutados con todas las operaciones de punto flotante siguiendo las reglas de la aritmética de coma flotante de Java.

No sé cuáles son las reglas de D para el cálculo del tiempo de ejecución de las funciones matemáticas, pero es posible que pueda obtener un truco similar: vuelva a interpretar la fuente C de fdlibm como D. Si D llama a las bibliotecas C específicas de la plataforma, entonces tiene el problema de que puede ser imposible en tiempo de compilación predecir el valor del tiempo de ejecución.

Creo que la licencia de fdlibm es muy permisiva, tendrías que comprobar por ti mismo si es adecuada para la redistribución en D. Una versión que he visto requiere que se conserve un aviso de copyright, y eso es todo.

John Hart Computer Approximations 1968 de John Wiley & Sons.

Los cálculos idealmente deberían coincidir exactamente con lo que harían si se realizaran en tiempo de ejecución. Eso puede ser complicado. Para muchas funciones, ninguna serie converge rápidamente en todo el dominio, por lo que los algoritmos pegan varios métodos.

Además, hay varios formatos de punto flotante. La mayoría de las plataformas (creo) ahora usan IEEE 754. Cuando escribí un compilador ca. 1985, tuve que lidiar con formatos de punto flotante multiplataforma. Fue muy tedioso hacer las cosas bien, porque tienes que unir los números poco a poco, asegurándote de obtener exactamente el valor que se calcularía en la máquina de destino. No sé si tienes que lidiar con eso.