pablisco

    pablisco

    8 months ago
    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

    Alexander Chori

    8 months ago
    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

    pablisco

    8 months ago
    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.
    And here is a stack safe implementation with support up to 8 mill fib numbers 😅
    Dominaezzz

    Dominaezzz

    8 months ago
    pablisco

    pablisco

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

    Dominaezzz

    8 months ago
    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.
    e

    ephemient

    8 months ago
    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))
        }
    }
    (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…)
    you can get finite results up to fib(1477) with Double, although of course it's no longer accurate past fib(79)
    pablisco

    pablisco

    7 months ago
    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 🙂
    e

    ephemient

    7 months ago
    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
    r

    Roukanken

    7 months ago
    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
    e

    ephemient

    7 months ago
    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)
    r

    Roukanken

    7 months ago
    yeah I was just reading that, and thinking that yeah, maybe not best idea
    golden ratio is ofc irrational so good luck with exact arithmetic
    e

    ephemient

    7 months ago
    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
    for n: Int ≥ 0, the irrational components cancel out
    Alexander Chori

    Alexander Chori

    7 months ago
    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/
    r

    Roukanken

    7 months ago
    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
    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}
    (and insert nth power there somewhere, probs on the srcond matrix)