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")

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.