Channels

#feed

Title

p

pablisco

01/24/2022, 9:31 AMI 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 AMNice 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 AMYeah, 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 PMHave you checked out https://kotlinlang.org/api/latest/jvm/stdlib/kotlin/-deep-recursive-function/ ?

p

pablisco

01/24/2022, 1:07 PMYeah, 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 PMI'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 AMYeah, 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 AMof 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 PMisn't there an exact equation for

`fib(n)`

?
... tho I guess that would still be `O(log n)`

since it has `pow(x, n)`

iirce

ephemient

01/26/2022, 2:57 PMthere 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 PMyeah 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 PMyou **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 PMI 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 PMYeah, 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