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 WAA07493; Sat, 15 May 2004 22:19:09 +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 WAA06473 for ; Sat, 15 May 2004 22:19:07 +0200 (MET DST) Received: from mproxy.gmail.com (rproxy.gmail.com [64.233.170.203]) by concorde.inria.fr (8.12.10/8.12.10) with SMTP id i4FKJ6SH031443 for ; Sat, 15 May 2004 22:19:06 +0200 Received: by mproxy.gmail.com with SMTP id 61so17320rnd for ; Sat, 15 May 2004 13:19:05 -0700 (PDT) Received: by 10.11.117.62 with SMTP id p62mr14270cwc; Sat, 15 May 2004 13:19:04 -0700 (PDT) Message-ID: <891bd339040515131939afd837@mail.gmail.com> Date: Sat, 15 May 2004 16:19:04 -0400 From: Yaron Minsky Reply-To: yminsky@cs.cornell.edu To: Markus Mottl Subject: Re: [Caml-list] Counting bits in a big_int Cc: Jean-Christophe Filliatre , Caml Mailing List In-Reply-To: <20040515111433.GA32168@fichte.ai.univie.ac.at> 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> <891bd3390405141953628db08a@mail.gmail.com> <20040515111433.GA32168@fichte.ai.univie.ac.at> X-Miltered: at concorde with ID 40A67B3A.000 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 nat:01 undocumented:01 nat:01 undocumented:01 2004:99 yaron:01 minsky:01 shorter:01 int:01 int:01 0200,:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Nice. The weird thing about the Nat module is that it's completely undocumented. Is there any reason to think it wil be stable between revisions? For instance, does Xavier's reimplementation have the same Num module with the same interface as the previous one? I guess my real question is: why is Nat undocumented? y On Sat, 15 May 2004 13:14:33 +0200, Markus Mottl wrote: > > 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