From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.3 required=5.0 tests=SPF_FAIL autolearn=disabled version=3.1.3 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 59834BC6B for ; Thu, 29 Nov 2007 07:13:01 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAADrnTUfAXQInh2dsb2JhbACPRQEBAQgKKQ X-IronPort-AV: E=Sophos;i="4.23,227,1194217200"; d="scan'208";a="4721058" Received: from concorde.inria.fr ([192.93.2.39]) by mail2-smtp-roc.national.inria.fr with ESMTP; 29 Nov 2007 07:13:01 +0100 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id lAT6D0YT014221 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Thu, 29 Nov 2007 07:13:01 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAADrnTUdA6bjhkGdsb2JhbACPRQEBAQEHAggiBQ X-IronPort-AV: E=Sophos;i="4.23,227,1194217200"; d="scan'208";a="5047748" Received: from wr-out-0506.google.com ([64.233.184.225]) by mail1-smtp-roc.national.inria.fr with ESMTP; 29 Nov 2007 07:13:00 +0100 Received: by wr-out-0506.google.com with SMTP id c57so1494970wra for ; Wed, 28 Nov 2007 22:12:59 -0800 (PST) Received: by 10.143.9.5 with SMTP id m5mr115605wfi.1196316777791; Wed, 28 Nov 2007 22:12:57 -0800 (PST) Received: by 10.142.226.14 with HTTP; Wed, 28 Nov 2007 22:12:57 -0800 (PST) Message-ID: Date: Wed, 28 Nov 2007 22:12:57 -0800 From: "Evan Klitzke" To: peng.zang@gmail.com Subject: Re: [Caml-list] Help with simple ocaml memoization problem Cc: caml-list@inria.fr In-Reply-To: <200711290053.15443.peng.zang@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <200711290053.15443.peng.zang@gmail.com> X-Miltered: at concorde with ID 474E586C.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 memoization:01 recursion:01 recursive:01 compiler:01 ocaml:01 hashtbl:01 hashtbl:01 recursive:01 syntax:01 bigints:01 camlp:01 peng:98 peng:98 faithful:98 On 11/28/07, Peng Zang 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? -- Evan Klitzke