Back to Questions
1.5k
views1
comment
Collatz conjecture, memoization, and continuations
f#

So I was attempting to solve a problem with a solution that was simple enough as long as you memoized the results. I was looking for a particular number whos Collatz length has a specific property. Solving this problem recursively would be very unkind to you stack, unless you use continuations.

1
2
3
4
5
6
7
8
9
10
11
12

open System.Collections.Generic

let cache = new Dictionary<_,_>()

let CollatzLength n =
  if cache.ContainsKey n then cache.(n) else
  let rec collatzUtil n cont =
    if cache.ContainsKey n then cont(cache.(n))
    elif n = 1UL then cont 1
    else collatzUtil (if n%2UL = 0UL then (n/2UL) else (3UL*n+1UL)) (cont >> (+) 1)
  cache.(n) <- collatzUtil n id
  cache.(n)

This is a sufficently fast solution for the problem at hand, but could be a little faster. I would like it to be able to cache the values in the Util loop. Currently, inputing 8 would work out 8, 4, 2, 1, and then cache 8 with 4, but not any of the others it worked out. The caching would also have to be apart of the continuation. I'm fairly new to continuations, and just figuring out this one was a little mind bending as it was. The fact that the continuations unwind themselves in reverse meant that I couldn't pair it with the paricular "n" the was passed in to the Util function, though I might be missing something. How would one go about adding caching in the continuation to get all the values calculated in this loop?

.

Actually, Collatz sequences are short enough that you don't really need to worry about blowing the stack, so you don't need to bother with tail recursion or continuation passing style and can just write the function naively (note that I've used bigints here instead of uint64s):

1
2
3
4
5
6

let rec collatz = function
| n when n = 1I -> 1
| n -> 1 + collatz (if n%2I = 0I then n/2I else 3I*n+1I)

let count = collatz 2361198062777205778683I

Then, you can use the standard trick for memoizing a recursive function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

open System.Collections.Generic

let memo_rec f =
  let cache = Dictionary<_,_>()
  let rec fn x =
    if not (cache.ContainsKey x) then
      cache.[x] <- f fn x
    cache.[x]
  fn

let collatz = memo_rec (fun cltz -> 
  function
  | n when n = 1I -> 1
  | n -> 1 + cltz (if n%2I = 0I then n/2I else 3I*n+1I))

However, if you want to go ahead and do things the "right way", see Brian's answer to this StackOverflow question.

By on 1/6/2011 2:47 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper