F# Humor (kinda)

So I was bored, didn’t know what to do, started solving problems on codewars (shut up!).

There was this little problem there, where they are asking you to compute \frac{\sum_{i=1}^n i!}{n!}, for potentially large n’s with 10^{-6} precision.

It’s easy to see that this needs to be refactored (no need to actually compute factorials), and the solution I found most “fsharpy” and beautiful (and not mine) was:

let going n =
    { n .. -1 .. 2 }
    |> Seq.map double
    |> Seq.scan (/) 1.
    |> Seq.sum

This works. Here is my less elegant solution:

let going n =
    let rec sumBack (acc : double) n (cur : double) =
        if n = 0 || cur < 1e-6 then Math.Round(acc, 6)
            sumBack (acc + cur) (n - 1) (cur / double n)
    sumBack  0. n 1.

Kinda ugh, but what I found humorous and instructive (things humorous usually are) was that falling for the language beauty and power is not always conducive to performance. Since we have the 10^{-6} constraint, it’s not necessary to scan the entire sequence {n..2}, we can start backwards and terminate as soon as the constraint is met. Thus, for very large n, we’ll only need to perform 1 division. So as the sum converges to 1, performance of the second solution converges to O(1), and, since it’s tail recursion, we aren’t actually using any stack, our memory usage is always O(1), which is more than we can say for the first solution. But I still love it more than my own for purely aesthetical reasons.

One thought on “F# Humor (kinda)

  1. You can do a functional version that terminates when the constraint is met.

    let going n =
    { n .. -1 .. 2 }
    |> Seq.map double
    |> Seq.scan (/) 1.
    |> Seq.takeWhile (fun x -> x > 1e-6)
    |> Seq.sum
    |> (fun x -> Math.Round(x,6))

    As the sequence is never materialised the memory usage should not be as high as you think.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.