Re: [Caml-list] Help with simple ocaml memoization problem

[Peng Zang <peng.zang@gmail.com>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Oops.  I was looking at this code again, and it actually isn't tail recursive.  
Ie. It's still recursing on the stack.  For one, I still add 1 after I make 
the recursive call and two, wrapping it in a lazy means once the value is 
calculated it must go back to memoize it.  But, it turns out it doesn't 
matter as there's not that many levels of recursion anyways.  The value 
837799 has a collatz lenght of 525 which means about that number of recursive 
calls.  I actually think the problem you had before was overflow from using 
ints.  In any event, here's the code without any laziness to confuse the 
issue.

let ( ++ ) = Int64.add;;
let ( ** ) = Int64.mul;;
let ( %% ) = Int64.rem;;
let ( // ) = Int64.div;;
let cache = Hashtbl.create 1000000;;
let cache2 = Hashtbl.create 1000000;;


let collatz = function
  | x when x %% 2L = 1L -> 3L ** x ++ 1L
  | x -> x // 2L
;;

let rec find_collatz_len x = match x with
  | 1L -> 1L
  | x when Hashtbl.mem cache x -> Hashtbl.find cache x
  | x -> let ans = 1L ++ find_collatz_len (collatz x) in
      Hashtbl.add cache x ans;
      ans
;;

let lengths = Array.init 999999
  (fun x -> let x = Int64.of_int (x + 1) in (x, find_collatz_len x));;
Array.sort (fun (a,b) (c,d) -> compare d b) lengths;;
lengths.(0)


Peng




On Thursday 29 November 2007 01:12:57 am Evan Klitzke wrote:
> On 11/28/07, Peng Zang <peng.zang@gmail.com> wrote:
> > I don't know how to increase the stack size off the top of my head, but
> > in general you want to avoid recursion on the stack anyways.  An easy way
> > is to simply make the function tail recursive so the compiler can
> > optimized it into a loop for you.  Here's a pretty faithful replication
> > of your python code. Note I use Int64 instead of BigInt as I'm running
> > OCaml 3.09.3.
> >
> > let ( ++ ) = Int64.add;;
> > let ( ** ) = Int64.mul;;
> > let ( %% ) = Int64.rem;;
> > let ( // ) = Int64.div;;
> > let l1 = Int64.of_int 1;;
> > let l2 = Int64.of_int 2;;
> > let l3 = Int64.of_int 3;;
> > let cache = Hashtbl.create 1000000;;
> >
> > let collatz = function
> >
> >   | x when x %% l2 = l1 -> l3 ** x ++ l1
> >   | x -> x // l2
> >
> > ;;
> > let rec find_collatz_len = function
> >
> >   | x when x = l1 -> l1
> >   | x when Hashtbl.mem cache x -> Lazy.force (Hashtbl.find cache x)
> >   | x -> let ans = lazy (l1 ++ find_collatz_len (collatz x)) in
> >
> >       Hashtbl.add cache x ans;
> >       Lazy.force ans
> > ;;
> > let lengths = Array.init 999999
> >   (fun x -> let x = Int64.of_int (x+1) in (x, find_collatz_len x));;
> > Array.sort (fun (a,b) (c,d) -> compare d b) lengths;;
> > lengths.(0);;
> >
> >
> > The use of laziness here is just so I can put the recursive call in the
> > tail position -- a quick hack because I'm too lazy to spend time making
> > it into a loop myself.
> >
> > There should really be some easy syntax to write BigInts or Int64s
> > directly in the code.  Is there some camlp4 that does this somewhere? 
> > And it would nice if Int64 operators were predefined in the module.
>
> Thanks Peng. This is much easier to grok than the code that I
> originally wrote! One question that I have is what is the difference
> between the Map and Hashtbl modules? From the documentation they look
> very similar -- why did you use Hashtbl here rather than Map?


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFHVeeJfIRcEFL/JewRAv64AKC5xEgXeTibAg0BEPNyrFTIMCPprgCgqEYB
UG8FMXoAWBJBzicGk2z3MB8=
=Gw33
-----END PGP SIGNATURE-----