My Golden Class

My Golden Class

Repasando un problema de @diegorattaggi y #mathiratti sobre φ el número áureo, el cual intenté mediante artificios matemáticos aprovechando las propiedades de las potencias del número aúreo sin llegar a resolverlo, se me ocurrió hacerlo por fuerza bruta, es decir iterando cada uno de los términos hasta conseguir resultados. En vano, solo obtuve un resultado para m=7 y n=5 y además no podía prosperar en cuanto las cifras crecían en número de dígitos. (El problema es bello, pero para resolverlo matemáticamente.)

Luego me acordé de este otro problema y me propuse mejorar la clase que desarrollé para ejecutar la fuerza bruta del problema anterior.

Aprovechando que es una clase nueva, he eliminado cualquier rastro de fuerza bruta y le he incluido algunas mejoras como por ejemplo :

  1. Número infinito de decimales de φ
  2. Cálculo de potencias de φ en función de los elementos de la sucesión de Fibonacci, más rápido y más preciso
  3. Cálculo de raices cuadradas para el tipo BigDecimal, para obtener infinitos decimales de φ.
  4. Obtención de la sucesión de Fibonacci n, como no. (Hasta Fib (315.000) y creo que haciendo algunos ajustes en el compilador de Intellij, alguno más caerá). Le he incluido una versión secursiva y otra iterativa, la función recursiva es mucho más eficiente gracias a la palabra clave modificadora de función tailrec de kotlin,el cual al incluirlo delante de una función recursiva, el compilador la trata como si fuera iterativa convirtiendo la función en un ciclo rápido y muy eficiente, alucinante.
  5. Obtención de un elemento concreto de la sucesión

Y ahora estamos preparados para atacar el problema con software, aunque a mi me gusta más hacerlo con matemáticas. Lo primero la clase con Kotlin

import java.math.BigDecimal
import java.math.BigInteger
import java.math.RoundingMode

class Phi {
    var decimals = 10
    val  TWO= 2.toBigDecimal()
    val  FIVE= 5.toBigDecimal()
    val  SQRTFIVE= sqrt(FIVE)

    val value: BigDecimal
        get() = (BigDecimal.ONE + SQRTFIVE).divide(TWO, decimals, RoundingMode.HALF_DOWN)
    private val fibonacci = mutableListOf()

    init {
        fibonacci.clear()
    }

    private fun calculateFibonacci(n: Int) {
        fibonacci.clear()
        fibonacciRecursive(n.toBigDecimal())
    }

    private fun sqrt(value: BigDecimal, scale: Int=decimals): BigDecimal {
        var x0 = BigDecimal("0")
        var x1 = BigDecimal(kotlin.math.sqrt(value.toDouble()))
        while (x0 != x1) {
            x0 = x1
            x1 = value.divide(x0, scale, RoundingMode.HALF_UP)
            x1 = x1.add(x0)
            x1 = x1.divide(TWO, scale, RoundingMode.HALF_UP)
        }
        return x1
    }

    private tailrec fun fibonacciRecursive(n: BigDecimal, a: BigDecimal = BigDecimal.ZERO, b: BigDecimal = BigDecimal.ONE) {
        fibonacci.add(b)
        when (n) {
            BigDecimal.ZERO -> a
            BigDecimal.ONE -> b
            else -> fibonacciRecursive(n - BigDecimal.ONE, b, a.add(b))
        }
    }

    private fun checkSucession(n:Int) { if (fibonacci.size < n) calculateFibonacci(n)}

    fun fibonacciIterator(n: Int): BigDecimal{
        var l = BigDecimal.ONE
        var lm1 = BigDecimal.ONE
        for (i in 3..n){
            var tmp = l
            l += lm1
            lm1 = tmp
        }
        return l
    }

    fun pow(n: Int) : BigDecimal {
        checkSucession(n)
        return fibonacci[n - 1] * value + fibonacci[n - 2]
    }

    fun fibonacciExplicitItem(n: Int): BigInteger = (getPhi(decimals).pow(n) - (BigDecimal.ONE - value).pow(n)).divide(sqrt(FIVE), decimals, RoundingMode.HALF_DOWN).toBigInteger()

    fun fibonacciItem(n: Int): BigDecimal {
        checkSucession(n)
        return fibonacci[n-1]
    }


    fun fibonacci(n: Int): List {
        checkSucession(n)
        return fibonacci;
    }

    fun sumInverse(n: Int): BigDecimal{
        val pn = value.pow(n)
        return when (n % 2){
            0 -> pn.toBigInteger().toBigDecimal() + BigDecimal.ONE
            1 -> pn.toBigInteger().toBigDecimal()
            else -> BigDecimal.ZERO
        }
    }

    override fun toString(): String {
        return value.toString()
    }

    fun getPhi(decimals:Int): BigDecimal = (BigDecimal.ONE + sqrt(FIVE, decimals )).divide(TWO)

    fun getPhiToString(decimals:Int): String {
        val phi = getPhi(decimals).toString()
        val text : StringBuilder= StringBuilder()
        text.append("1.\n")
        val phi2 = phi.removePrefix("1.")
        phi2.forEachIndexed { index, c ->
            when {
                index % 100 == 0 && index > 0 -> text.append("\t$index:\n$c")
                index % 10 == 0  && index > 0 -> text.append(" $c")
                else -> text.append(c)
            }
        }
        text.append("\t$decimals:")
        return text.toString()
    }
}

Y para iniciar, vamos a ver como funciona

import java.math.BigDecimal
import kotlin.system.measureTimeMillis

fun main(args: Array){
val n = 100000
val power = 1500
val phi = Phi()

val t1 = measureTimeMillis { println("phi: ${phi.getPhi(100000)}") }
println("$n decimals of Phi. Duration: $t1")
val t2 = measureTimeMillis { "Fibonacci($n): ${phi.fibonacci(n)}" }
println("Fibonacci($n). Duration: $t2")
val t3 = measureTimeMillis { println("Fibonacci($n): ${phi.fibonacciItem(n)}") }
println("FibonacciItem($n). Duration: $t3")
val t4 = measureTimeMillis { println("Phi^$power: ${phi.pow(power)}") }
println("Phi^$power. Duration: $t4")
}
  1. Instancia de la clase
  2. Obtenemos el número φ con 100.000 decimales
  3. Obtenemos la sucesión de Fibonacci para n=100.000
  4. Obtenemos el elemento 100.000 de la sucesión de Fibonacci
  5. Elevamos φ a la potencia 1500

Resultado

Phi: 1.618033988... 100.000 decimals ...8836739749559326107
100000 decimals of Phi. Duration: 2601ms
Fibonacci(100000). Duration: 143044ms
Fibonacci(100000): 259740693472217 ... 20.900 digits ... 5699780289236362349895374653428746875
FibonacciItem(100000). Duration: 1ms
Phi^1500: 30301238166550805786929189390145575626423967452224056329446235918567465318942832927313669458439880439962733393211656583769182495024464042800878040985094292794417098116786924311826550387756605278028834211153418987752560366539982408518048936164775701203049457214716895381907861202507701229899701575192565697255980968.78939750000
Phi^1500. Duration: 1ms

Pues para el montón de dígitos, sin paralelismo y lo que conseguimos, Kotlin vuelve a conquistarme.

Para terminar resolvamos el segundo problema

val t1 = measureTimeMillis {
val phi3 = phi.pow(3)
val phi5 = phi.pow(5)
val phi6 = phi.pow(6)
val phi8 = phi.pow(8)

val result =
(phi3 + ((phi3 + ((phi3 + phi5) / (BigDecimal.ONE - phi8))) / (BigDecimal.ONE - ((phi6 + phi8) / (BigDecimal.ONE - phi8))))) /
(((phi6 + ((phi6 + phi8) / (BigDecimal.ONE - phi8))) / (BigDecimal.ONE - ((phi6 + phi8) / (BigDecimal.ONE - phi8)))) - BigDecimal.ONE)
println("Result: $result")
}
println("Result. Duration: $t1")

20200723_155641.jpg

El resultado rápido y preciso y sobretodo, bello en sí. Las matemáticas lo son.

Result: 1.00000000000
Result. Duration: 3ms

Saludos y gracias @diegorattaggi

Pd: El post de Arithmos sobre la cantidad de dígitos de los elementos de la sucesión de Fibonacci, está implementada con esta clase y con buena nota

Las imágenes han sido descargadas del perfil de @diegorattaggi.

Sucesión de Fibonacci

Sucesión de Fibonacci
Publiqué en mi otro blog sobre mates, física y otros temas un post acerca de la sucesión y la espiral de Fibonacci y gustándome como me gustan las funciones recursivas, no podía quedar atrás una implementación en C# de esta sucesión.
Para ellos, en este artículo expondré diversos métodos para calcular la sucesión de Fibonacci a los cuales se les pasará como argumento el valor de n de la función y que a continuación os muestro:
El primero de ellos será mediante la función recursiva. Este es el método natural de cálculo de la sucesión
espiral01.png

        public double GetRecursiveFunction(int n)
        {
            if ((n == 0) || (n == 1)) return 1;
            else return GetRecursiveFunction(n -1) + GetRecursiveFunction(n - 2);
        }

Este método tiene el inconveniente de la complejidad recurrente que se aplica sobre su cálculo, es decir que si solicitamos el valor del elemento 39, haríamos una llamada a GetRecursiveFunction(39) , la cual una vez dentro de esta, llamará a los elementos GetRecursiveFunction(38) y GetRecursiveFunction(37) de la misma función para sumarlos, y estos a su vez a sus dos anteriores hasta llegar a GetRecursiveFunction(0) o GetRecursiveFunction(1) devolviendo el valor de 1 a partir de entonces comenzará a sumar. Esto significa que para cada cálculo se realiza la suma de las iteraciones de los dos elementos anteriores más 1. Si para n igual a 6 se llama a la función 15 veces y para n igual a 7, 25 veces, para n igual a 8 se llamaría a la función 15 más 25 y más 1 de la primera llamada. Esto supone un gasto de recursos enorme ya que para n igual a 40 el número de iteraciones se elevaría a la suma de 78.176.337, 126.491.971 y 1, un total de 204.668.309 iteraciones para obtener el elemento 40 de la sucesión; en tiempo, aproximadamente unos 8 segundos en un dual core con SSD. A todos los efectos, no es eficiente.El siguiente método de cálculo de la sucesión de Fibonacci, será el de la función general extraída mediante la ecuación de recurrencia y sus raíces.espiral14.png

Esta función tiene como inconveniente la precisión y muestro el por qué. En primero lugar creo una propiedad de solo lectura para calcular ϕ (Phi) o el número áureo, el cual es igual a
Espiral04.png
provocando una falta de precisión; por otra parte el uso de la exponenciación a n, lo que a su vez provoca que un número excesivamente grande, sea tratado exponencialmente. Todo esto unido para un n grande, nos hace obtener un número extremadamente aproximado a cualquier elemento de la sucesión, pero sin llegar a serlo, por lo que debemos auxiliarnos de la función de redondeo para obtener unos resultados satisfactorios. A pesar de los complejos cálculos, es muy rápida.

        public double Phi
        {
            get
            {
                return (1 + Math.Sqrt(5)) / 2;
            }
        }

        public double GetGeneralFuncion(int n)
        {
            double result = (double)((Math.Pow(Phi, n) - Math.Pow((1 - Phi), n)) / Math.Sqrt(5));
            return Math.Round(result);
        }

La siguiente función es la iterativa. Esta parte de los dos primeros valores 0 y 1 y va obteniendo el siguiente en cada iteración, sencilla y muy rápida. No tiene problemas de redondeo. El inconveniente que tiene es que no almacena los valores anteriores, sino que simplemente los calcula.

        public double GetIterativeFunction(int n)
        {
            double f0 = 0;
            double f1 = 1;
            for (int i = 1; i < n; i++)
            {
                f1 = f0 + f1;
                f0 = f1 - f0;
            }

            return f1;
        }

Por último, una función parecida a la iterativa pero en la cual quedan almacenados los elementos de la sucesión mediante un objeto List, de este modo se asignan los dos primeros valores y se van generando los siguientes añadiéndolos a la lista según se van calculando.

        public List numbers = new List();
        public void GetArrayListFunction(int n)
        {
            numbers.Clear();
            numbers.Add(0);
            numbers.Add(1);
            for (int i = 2; i < n; i++)
            {
                numbers.Add(numbers[i - 1] + numbers[i - 2]);
            }
        }

Una vez que hemos visto las funciones para obtener los elementos de la sucesión de Fibonacci, vamos a calcular la espiral de Fibonacci mediante dos métodos, XAML y código puro y duro.
Si lo hacemos con XAML, creamos un objeto Path y dentro de Path.Data con el siguiente código:

        <Path Stroke="Red" StrokeThickness="2" >
        <Path.Data>
            <PathGeometry>
                <PathGeometry.Figures>
                    <PathFigureCollection>
                            <PathFigure StartPoint="610,610">
                                <PathFigure.Segments>
                                <PathSegmentCollection>
                                        <ArcSegment Point="600, 600" Size="10 10" />
                                        <ArcSegment Point="590, 610" Size="10 10" />
                                        <ArcSegment Point="610, 630" Size="20 20" />
                                        <ArcSegment Point="640, 600" Size="30 30" />
                                        <ArcSegment Point="590, 550" Size="50 50" />
                                        <ArcSegment Point="510, 630" Size="80 80" />
                                        <ArcSegment Point="640, 760" Size="130 130" />
                                        <ArcSegment Point="850, 550" Size="210 210" />
                                        <ArcSegment Point="510, 210" Size="340 340" />
                                        <ArcSegment Point="-40, 760" Size="550 550" />
                                        <ArcSegment Point="850, 1650" Size="890 890" />
                                        <ArcSegment Point="2290, 210" Size="1440 1440" />
                                    </PathSegmentCollection>
                            </PathFigure.Segments>
                        </PathFigure>
                    </PathFigureCollection>
                </PathGeometry.Figures>
            </PathGeometry>
        </Path.Data>
        </Path>

Lo que hacemos es crear objetos ArcSegment como tantos elementos de la sucesión queramos incluir, pero su límite es evidente, por lo que podríamos crear un método genérico que creara una espiral en base al argumento n, de modo que llamamos por ejemplo a la función iterativa basada en List y con los datos almacenados en esta lista, usarlos para crear tanto objetos ArcSegment como elementos tenga la sucesión. El problema es que la sucesión de Fibonacci tiene un crecimiento alto y la espiral desaparecerá rápidamente de nuestra ventana, pero calcular, calcula correctamente la espiral.
He creado dos propiedades para el centro de la espiral, x e y un ángulo como variable angular. (También podríamos haber usado la función polar de la espiral, pero he escogido esta para mostrar cada arco de segmento).
Para seleccionar el centro de cada arco, he ingeniado un método que mediante el seno y coseno del ángulo de la función, sume o reste los valores de la sucesión y asigne correctamente el centro.
Una vez creados los arcos, los añadimos al objeto Figure y como en XAML vamos añadiendo a la colección.

        public double CenterX { get; set; } = 512;
        public double CenterY { get; set; } = 384;
        public double Angle { get; set; } = Math.PI;

        void create(int n)
        {

            Fibonacci fib = new Fibonacci();
            fib.GetArrayListFunction(n);

            PathGeometry pathGeometry = new PathGeometry();

            PathFigure figure = new PathFigure();
            figure.StartPoint = new Point(CenterX, CenterY);

            for (int i =0; i < fib.numbers.Count; i++)
            {
                double sign = (i % 2 == 0 ? 1 : -1);
                double x = sign==1? Math.Round(Math.Cos(Angle)) : Math.Round(Math.Sin(Angle));
                double y = sign == 1 ? Math.Round(Math.Sin(Angle - Math.PI / 2)) : Math.Round(Math.Cos(Angle-Math.PI/2));
                double a = Math.Round(fib.numbers[i] * sign * x);
                double b = Math.Round(fib.numbers[i] * sign * y);

                CenterX = CenterX + a;
                CenterY = CenterY + b;

                ArcSegment arcSegment = new ArcSegment(new Point(CenterX, CenterY),
                    new Size(fib.numbers[i], fib.numbers[i]),
                    0,false,SweepDirection.Counterclockwise,true);

                figure.Segments.Add(arcSegment);
                Angle += Math.PI/2;

            }

            pathGeometry.Figures.Add(figure);
            path.Data = pathGeometry;
            path.Stroke = Brushes.Green;
        }

el resultado en ambos casos

fib02.png
y esto es todo,
saludos!