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.4 required=5.0 tests=SPF_NEUTRAL autolearn=disabled version=3.1.3 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id EE368BC69 for ; Wed, 5 Dec 2007 00:49:56 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAP91VUfRVca8kmdsb2JhbACPUAIBAQcCBik X-IronPort-AV: E=Sophos;i="4.23,251,1194217200"; d="scan'208";a="5267406" Received: from discorde.inria.fr ([192.93.2.38]) by mail1-smtp-roc.national.inria.fr with ESMTP; 05 Dec 2007 00:49:56 +0100 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id lB4NnuC1002382 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Wed, 5 Dec 2007 00:49:56 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAP91VUfRVca8kmdsb2JhbACPUAIBAQcCBik X-IronPort-AV: E=Sophos;i="4.23,251,1194217200"; d="scan'208";a="5267403" Received: from rv-out-0910.google.com ([209.85.198.188]) by mail1-smtp-roc.national.inria.fr with ESMTP; 05 Dec 2007 00:49:54 +0100 Received: by rv-out-0910.google.com with SMTP id f5so3101772rvb for ; Tue, 04 Dec 2007 15:49:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:from:reply-to:to:subject:date:user-agent:cc:references:in-reply-to:content-type:content-transfer-encoding:content-disposition:message-id; bh=xrEgA0uUuUiBVtESOdPKz6+SDwoO52rzm00NVy/nTH4=; b=f9Ecy7Yw1r/YKLCtiFByYAe5GGPKf7MatoFeUI75ObLnbId2ef8A6UmNlIhT/yDFa+7CHrSzzkjO3ynFss/uRD6uMLpCT4WYkS/qZMFJcwndW9YfVGWJR0J7YrXIG2pYAlsXgULSevnAc5yb5iKmT3EpniKzhFHsa2yb7/pkdfE= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=received:from:reply-to:to:subject:date:user-agent:cc:references:in-reply-to:content-type:content-transfer-encoding:content-disposition:message-id; b=WvJY704sqo3CPIUuX8QvMcIMz+985zWh7Dk8aX8VbNW68n2+geeaF1GBut1TypdpKBYrtEjOTXhNDE46Mmstt0887aGLE7f8w5u3wJgqUgAgxjuKFE1o9ONOeK0nzbzcqHZpBcm4bzO2e0k9PJDCYNsM5TbArA5zOEc5jX+U1O4= Received: by 10.141.161.6 with SMTP id n6mr723907rvo.1196812193210; Tue, 04 Dec 2007 15:49:53 -0800 (PST) Received: from ?10.71.0.226? ( [207.81.158.245]) by mx.google.com with ESMTPS id 3sm535638rvi.2007.12.04.15.49.39 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 04 Dec 2007 15:49:51 -0800 (PST) From: Peng Zang Reply-To: peng.zang@gmail.com To: "Evan Klitzke" Subject: Re: [Caml-list] Help with simple ocaml memoization problem Date: Tue, 4 Dec 2007 18:49:24 -0500 User-Agent: KMail/1.9.7 Cc: caml-list@inria.fr References: <200711290053.15443.peng.zang@gmail.com> In-Reply-To: Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200712041849.29780.peng.zang@gmail.com> X-Miltered: at discorde with ID 4755E7A4.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 memoization:01 hash:01 recursive:01 recursive:01 memoize:01 recursion:01 hashtbl:01 hashtbl:01 recursion:01 compiler:01 ocaml:01 syntax:01 bigints:01 camlp:01 -----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 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-----