From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id NAA17094; Sat, 15 May 2004 13:14:46 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id NAA16832 for ; Sat, 15 May 2004 13:14:45 +0200 (MET DST) Received: from fichte.ai.univie.ac.at (fichte.ai.univie.ac.at [131.130.174.156]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i4FBEiSH007828 for ; Sat, 15 May 2004 13:14:44 +0200 Received: from fichte.ai.univie.ac.at (markus@localhost [127.0.0.1]) by fichte.ai.univie.ac.at (8.12.3/8.12.3/Debian-6.6) with ESMTP id i4FBEYDu001364; Sat, 15 May 2004 13:14:34 +0200 Received: (from markus@localhost) by fichte.ai.univie.ac.at (8.12.3/8.12.3/Debian-6.6) id i4FBEXhe001363; Sat, 15 May 2004 13:14:33 +0200 Date: Sat, 15 May 2004 13:14:33 +0200 From: Markus Mottl To: yminsky@cs.cornell.edu Cc: Jean-Christophe Filliatre , Caml Mailing List Subject: Re: [Caml-list] Counting bits in a big_int Message-ID: <20040515111433.GA32168@fichte.ai.univie.ac.at> Mail-Followup-To: yminsky@cs.cornell.edu, Jean-Christophe Filliatre , Caml Mailing List References: <891bd3390405112022194630a8@mail.gmail.com> <16547.8441.559944.112854@gargle.gargle.HOWL> <891bd3390405130427180c36d6@mail.gmail.com> <16547.27869.60461.270873@gargle.gargle.HOWL> <891bd3390405141953628db08a@mail.gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <891bd3390405141953628db08a@mail.gmail.com> User-Agent: Mutt/1.4.1i X-Miltered: at concorde with ID 40A5FBA4.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 yaron:01 minsky:01 nat:01 nat:01 shorter:01 int:01 int:01 mottl:02 mottl:02 wrote:03 sys:03 markus:04 markus:04 let:04 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, 14 May 2004, Yaron Minsky wrote: > Here's the fastest bitcounter I've been able to come up with. It's > about an order of magnitude faster than just counting bit by bit. How about this: --------------------------------------------------------------------------- open Big_int open Nat let nbits x = let nat = nat_of_big_int (abs_big_int x) in let nwords = num_digits_nat nat 0 (length_nat nat) in Sys.word_size * nwords - num_leading_zero_bits_in_digit nat (nwords - 1) --------------------------------------------------------------------------- This runs another order of magnitude faster, and it's shorter, too :-) Regards, Markus -- Markus Mottl http://www.oefai.at/~markus markus@oefai.at ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners