pablisco
01/24/2022, 9:31 AMAlexander Chori
01/24/2022, 10:04 AMpablisco
01/24/2022, 10:33 AMDominaezzz
01/24/2022, 12:34 PMpablisco
01/24/2022, 1:07 PMDominaezzz
01/24/2022, 2:28 PMephemient
01/24/2022, 10:19 PMprivate val fibs = mutableMapOf(0 to 0L, 1 to 1L)
val fib = DeepRecursiveFunction<Int, Long> {
fibs.getOrPut(it) {
Math.addExact(callRecursive(it - 2), callRecursive(it - 1))
}
}
pablisco
01/25/2022, 10:07 AMephemient
01/26/2022, 2:44 AMRoukanken
01/26/2022, 2:51 PMfib(n)
?
... tho I guess that would still be O(log n)
since it has pow(x, n)
iircephemient
01/26/2022, 2:57 PMval φ = (1 + sqrt(5)) / 2
fun fib(n) = (pow(φ, n) - pow(1 - φ, n)) / sqrt(5)
but try doing that with exact arithmetic (it's possible but no faster)Roukanken
01/26/2022, 2:57 PMephemient
01/26/2022, 3:06 PMAlexander Chori
01/26/2022, 3:18 PMa + sqrt(5)*b
by its coefficients (a, b)
. It removes the necessity to compute the irrational numbers
Take a look (the article is on Russian): https://habr.com/ru/post/645829/Roukanken
01/26/2022, 3:26 PM