https://kotlinlang.org logo
#feed
Title
p

pablisco

01/24/2022, 9:31 AM
I made a thread with some fun ways to implement fibonacci in Kotlin. How you all enjoy it 🙂 https://twitter.com/pablisc0/status/1485544573921280002
👍 4
a

Alexander Chori

01/24/2022, 10:04 AM
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
p

pablisco

01/24/2022, 10:33 AM
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.
👍 1
And here is a stack safe implementation with support up to 8 mill fib numbers 😅
d

Dominaezzz

01/24/2022, 12:34 PM
p

pablisco

01/24/2022, 1:07 PM
Yeah, someone mentioned it. Although, I think the last one I posted is also stack free, with the internal tailrec, right?
d

Dominaezzz

01/24/2022, 2:28 PM
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.
👍 1
e

ephemient

01/24/2022, 10:19 PM
Copy code
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))
    }
}
👌 2
(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…)
💯 1
you can get finite results up to fib(1477) with Double, although of course it's no longer accurate past fib(79)
p

pablisco

01/25/2022, 10:07 AM
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

01/26/2022, 2:44 AM
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

01/26/2022, 2:51 PM
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

01/26/2022, 2:57 PM
there is an closed-form
Copy code
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

01/26/2022, 2:57 PM
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

01/26/2022, 3:06 PM
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
a

Alexander Chori

01/26/2022, 3:18 PM
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

01/26/2022, 3:26 PM
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
👍 1
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)
5 Views