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 :
- Número infinito de decimales de φ
- 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
- Cálculo de raices cuadradas para el tipo BigDecimal, para obtener infinitos decimales de φ.
- 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
tailrecde 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. - 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")
}
- Instancia de la clase
- Obtenemos el número φ con 100.000 decimales
- Obtenemos la sucesión de Fibonacci para n=100.000
- Obtenemos el elemento 100.000 de la sucesión de Fibonacci
- 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.
wakicode 