I made a thread with some fun ways to implement fi...

# feed

[pablisco]

I made a thread with some fun ways to implement fibonacci in Kotlin. How you all enjoy it 🙂
https://twitter.com/pablisc0/status/1485544573921280002

[Alexander Chori]

Nice usage of value class in [3/4]! However, the fibonacci numbers are growing so quickly, so this solution will have troubles with overflow very quickly. In all other solutions, for example, we could utilize arbitrary precision arithmetics

[pablisco]

Yeah, after 90 items, the resolution of an int is not really good for fib.
I mean, it’s more to showcase language features 🙂
I’ve updated as the flow implementation is also not stack safe 😱 I should have had some coffee before tweeting.

[pablisco]

And here is a stack safe implementation with support up to 8 mill fib numbers 😅

[Dominaezzz]

Have you checked out https://kotlinlang.org/api/latest/jvm/stdlib/kotlin/-deep-recursive-function/ ?

[pablisco]

Yeah, someone mentioned it. Although, I think the last one I posted is also stack free, with the internal tailrec, right?

[Dominaezzz]

I'm not sure. It probably is but I feel it's relying on implementation details to achieve stackless execution. Not that it matters, it's not the point of the post. I just thought that would make a nice addition to the list of fun ways to do deep recursion.

[ephemient]

private 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))
    }
}

[ephemient]

(just for the record, I just put addExact there to throw an exception instead of wrapping fib(93) from the accurate 12200160415121876738 to the Long-sized -6246583658587674878. exponential functions grow fast…)

[ephemient]

you can get finite results up to fib(1477) with Double, although of course it's no longer accurate past fib(79)

[pablisco]

Yeah, it’s more of a showcase of Kotlin features… Very few people would use fib in prod (hopefully) but these are very valid points that people should take into account 🙂

[ephemient]

of course. if you wanted to have a "production" fibonacci function, you'd probably go for the fast algorithm with O(log n) operations instead of the O(n) or O(2^n) operations required for the recurrence, memoized or not. (it's not really O(log n) because big integer operations are not O(1), though) https://pl.kotl.in/FBhQCxfOs

[Roukanken]

isn't there an exact equation for fib(n) ?
... tho I guess that would still be O(log n) since it has pow(x, n) iirc

[ephemient]

there is an closed-form

val φ = (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]

yeah I was just reading that, and thinking that yeah, maybe not best idea

[Roukanken]

golden ratio is ofc irrational so good luck with exact arithmetic

[ephemient]

you can do it - just think of the binomial expansion, along with pow(sqrt(5), 2 * n) = pow(5, n). but it's not worth it

[ephemient]

for n: Int ≥ 0, the irrational components cancel out

[Alexander Chori]

I recently saw an article about computing the Fibonacci numbers by Bine’s formulae as show @ephemient. In the article it was proposed to represent numbers in form a + 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]

Yeah, I thought of such solution, but I realized, when you take it a step further, you'll arrive exactly at what matrix form is doing

[Roukanken]

I havent looked at the code emph shared, but basically you would need 2x2 matrix of {last fib, current fib} x { whole part, root of 5 part}

And then just multiply it with a matrix that produces {fib, next fib}

[Roukanken]

(and insert nth power there somewhere, probs on the srcond matrix)