Re: [Caml-list] Counting bits in a big_int

[Markus Mottl <markus@oefai.at>]

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