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.

Pi, Montecarlo y Kotlin

Pi, Montecarlo y Kotlin

Hace unos dias, escribí un artículo sobre el método Montecarlo para calcular la probabilidad de la posición final de un robot en una línea. Luego me acordé del clásico para calcular una aproximación de PI lanzando dardos y al final pensé, ¿que tal se defenderá Kotlin con coroutines en este ambiente?. Bien

fun main (args: Array){

    val averages = mutableListOf()
    val time = measureTimeMillis {
        (0..100000).forEach { _ ->
            runBlocking{
                averages.add(calculate())
            }
        }
        println("PI= ${averages.average()}")
    }
    println("time: $time")
}

fun calculate(): Double{
    val successful = mutableListOf()
    (0..500).forEach { _ ->
        GlobalScope.run {  successful.add((Random.nextDouble().pow(2) + Random.nextDouble().pow(2)) k }.toDouble() / successful.count().toDouble()
}

la verdad que las coroutines van de maravilla, consumen poco y superrápidas.

Funciones estadísticas

Funciones estadísticas

Vamos a ver las funciones estadísticas de varianza, desviación típica y coefeciente de variación con Kotlin. Partiremos de una lista de elementos Double y crearemos extensiones de la lista para calcularlas.

Varianza. La varianza tiene la siguiente formula.

quicklatex.com-d5166eaa9614351e91ec76dec4fc3faf_l3

o lo que es lo mismo

quicklatex.com-220898e23d5d0c3236780d6397b187a2_l3

Equivale al cuadrado de la desviación típica

fun List.variance(): Double {
    val n = this.count()
    val average = this.average()
    return this.map { (it - average).pow(2.0) / n}.sum()
}

Así que si la la desviación al cuadro es la varianza, podemos obtener la desviación obteniendo la raiz de la varianza.

fun List<Double>.stdDeviation() = sqrt(this.variance())

Por último el coeficiente de variación que es igual a la relación entre la desviación típica y el promedio.

cv.png

fun List<Double>.coefficientOfVariation() = stdDeviation() / this.average()

Obtenermos una muestra aleatoria y con pocas líneas de código el resultado:

val list = (0..10).map { n-> Random.nextDouble(5.0,10.0) }
println(list)
println("Average: ${list.average()}")
println("Variance: ${list.variance()}")
println("Std Deviation: ${list.stdDeviation()}")

 

[5.1126146370135555, 7.961926277327813, 6.030297997339725, 7.346200593709344, 6.977298121605789, 6.480337764164781, 9.12926821809771, 9.830048028655337, 7.107841652359342, 7.047870562367113, 8.943727133742051]
Average: 7.451584635125688
Variance: 1.8100002521711398
Std Deviation: 1.3453624984260337
Coefficient: 0.18054716738828816