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 EAA31092; Sat, 15 May 2004 04:53:38 +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 EAA30095 for ; Sat, 15 May 2004 04:53:37 +0200 (MET DST) Received: from mproxy.gmail.com (rproxy.gmail.com [64.233.170.197]) by concorde.inria.fr (8.12.10/8.12.10) with SMTP id i4F2rZSH023146 for ; Sat, 15 May 2004 04:53:36 +0200 Received: by mproxy.gmail.com with SMTP id 61so11016rnd for ; Fri, 14 May 2004 19:53:34 -0700 (PDT) Received: by 10.11.119.15 with SMTP id r15mr8914cwc; Fri, 14 May 2004 19:53:34 -0700 (PDT) Message-ID: <891bd3390405141953628db08a@mail.gmail.com> Date: Fri, 14 May 2004 22:53:34 -0400 From: Yaron Minsky Reply-To: yminsky@cs.cornell.edu To: Jean-Christophe Filliatre , Caml Mailing List Subject: Re: [Caml-list] Counting bits in a big_int In-Reply-To: <16547.27869.60461.270873@gargle.gargle.HOWL> Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit References: <891bd3390405112022194630a8@mail.gmail.com> <16547.8441.559944.112854@gargle.gargle.HOWL> <891bd3390405130427180c36d6@mail.gmail.com> <16547.27869.60461.270873@gargle.gargle.HOWL> X-Miltered: at concorde with ID 40A5862F.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; yaron:01 minsky:01 yminsky:01 caml-list:01 mult:01 2004:99 filliatre:01 filliatre:01 lri:01 yaron:01 minsky:01 mult:01 int:01 int:01 rec:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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. let ( *! ) = mult_big_int let ( +! ) = add_big_int let ( -! ) = sub_big_int let ( %! ) = mod_big_int let ( /! ) = div_big_int let ( **! ) = power_big_int_positive_int let ( <>! ) x y = not (eq_big_int x y) let ( =! ) = eq_big_int let ( ! ) = gt_big_int let ( <=! ) = le_big_int let ( >=! ) = ge_big_int let nbits_slow x = let rec loop i two_to_i = if two_to_i >! x then i else loop (succ i) (two *! two_to_i) in if x =! zero then 1 else loop 1 two let nbits x = let nwords = num_digits_big_int x in let wsize = Sys.word_size in let lowbits = (nwords - 1) * wsize in let lastword = x /! two **! lowbits in nbits_slow lastword + (nwords - 1) * wsize On Thu, 13 May 2004 14:41:01 +0200, Jean-Christophe Filliatre wrote: > > > Yaron Minsky writes: > > What I'm actually interested in is finding the index of the rightmost > > set bit. So, for the int: > > 1000110, I'd want the answer to be 7, not 3. > > Ok; then Michael's suggestion should work, as follows: > > ====================================================================== > let count_bits b = > let rec loop i two_to_i = (* inv 2^(i-1) <= b *) > if gt_big_int two_to_i b then i > else loop (succ i) (mult_int_big_int 2 two_to_i) > in > if eq_big_int b zero_big_int then 1 else loop 1 (big_int_of_int 2) > ====================================================================== > > -- > Jean-Christophe > > ------------------- 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