I made a thread with some fun ways to implement fibonacci in

Question

I made a thread with some fun ways to implement fibonacci in Kotlin How you all enjoy it slightly smiling face <https twitter com pablisc0 status 1485544573921280002>

Alexander Chori · Answer

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 · Answer

Yeah after 90 items the resolution of an int is not really good for fib I mean it s more to showcase language features slightly smiling face I ve <https twitter com pablisc0 status 1485560596074569732 s=20|updated> as the flow implementation is also not stack safe scream I should have had some coffee before tweeting

pablisco · Answer

And <https twitter com pablisc0 status 1485567267140210693 s=20|here> is a stack safe implementation with support up to 8 mill fib numbers sweat smile

Dominaezzz · Answer

Have you checked out <https kotlinlang org api latest jvm stdlib kotlin deep recursive function |https kotlinlang org api latest jvm stdlib kotlin deep recursive function >

pablisco · Answer

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

Dominaezzz · Answer

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 · Answer

```private val fibs = mutableMapOf 0 to 0L 1 to 1L val fib = DeepRecursiveFunction lt Int Long gt fibs getOrPut it Math addExact callRecursive it 2 callRecursive it 1 ```

ephemient · Answer

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 · Answer

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

pablisco · Answer

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 slightly smiling face

ephemient · Answer

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 · Answer

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 · Answer

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 · Answer

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

Roukanken · Answer

golden ratio is ofc irrational so good luck with exact arithmetic

ephemient · Answer

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 · Answer

for n Int 0 the irrational components cancel out

Alexander Chori · Answer

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

Roukanken · Answer

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 · Answer

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 · Answer

and insert nth power there somewhere probs on the srcond matrix