Algunos algoritmos famosos, reprogramados según la programación funcional (lenguaje scala)
Se incluye la función time para cálculo de tiempos de ejecución para poder comparar la eficiencia de los distintos algoritmos. Se usa creando un bloque de ejecución:
time {
algoritmo()
}
package primes - Secuencia infinita (Stream) de números primos:
package primes.sieve - Criba de Eratóstenes:
package binarySearch - Búsqueda en listas ordenadas de números. La complejidad algorítmica se reduce a O(log n), por lo que se emplea en numerosos algoritmos que tienen de entrada una lista ordenada.
package threesum - Búsqueda dentro de una lista de tres números cuya suma sea cero. Es un algoritmo que reduce la complejidad algoritmica de O(n^3) a O(n^2 log n).
package ackermann - Esta función recursiva es conocida por crecer muy rápidamente y desbordar la pila de cálculo, incluso con valores pequeños.
- ackermann: Alias a la mejor implementación conseguida (=ackermannMemo)
- ackermannRec: Definición recursiva
- ackermannPart: Definición recursiva con algunos términos desarrollados de valores pequeños
- ackermannMemo: Definición con memonización para evitar calcular términos ya calculados
package pi.bbm - Implementación del cálculo recursivo para calcular el número PI dígito a dígito. Para ello se utiliza la fórmula de Bailey–Borwein–Plouffe
\begin{equation*} x_n = \left{ 16x_{n-1} + \frac{120n^2 - 89n + 16}{512n^4-1024n^3+712n^2-206n+21}\right} \end{equation*}
El dígito-n hexadecimal de "pi-3" es dado por \begin{align} \lfloor 16 x_n \rfloor \end{align}