[Caml-list] Counting bits in a big_int

[Caml-list] Counting bits in a big_int

[Yaron Minsky]

Any thoughts on what would be a reasonably efficient way to count the
number of bits in a big_int?  There's no method that directly does it.
 There is the "num_digits_big_int" call, but that returns the number
of machine words.

y

-------------------
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

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

[Michael Hoisie]

If you have any arbitrary big_int, n, wouldn't the number of bits be equal to 2^x, where x is the number such that 2^x >= n?

So, if you have 100 (1100100), then the number of bits would be 7, because 2^7>=100. 

Is this what you mean?

-Michael Hoisie

-------------------
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

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

[Yaron Minsky]

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 ( <! ) = lt_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
<jean-christophe.filliatre@lri.fr> 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

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

[Markus Mottl]

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

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

[Yaron Minsky]

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 <markus@oefai.at> 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

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

[skaller]

On Sun, 2004-05-16 at 06:19, Yaron Minsky wrote:
> 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? 

Yes, the Ocaml people care about that.

>  For instance, does Xavier's reimplementation have the same
> Num module with the same interface as the previous one?

Yes. I've been using Nat for ages and had no problems
with upgrades.

> I guess my real question is: why is Nat undocumented?

Documentation requires work, its fairly easy to guess
what Nat does from the function names .. :)

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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

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

[Xavier Leroy]

> 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?

The Nat interface hasn't changed since the beginning of OCaml, and my
recent reimplementation of the low-level primitives preserved its interface.

> I guess my real question is: why is Nat undocumented?

Nat is a very low-level API, based on in-place modification of
sub-numbers of big integers.  Consequently, it's hard to use directly,
and it's also hard to document.  The lack of documentation is both an
encouragement not to use it, and an evidence that we are lazy :-)

If you really want to know what Nat does, the following tech rep is useful:
"The CAML Numbers Reference Manual" by Valerie Menissier-Morain,
technical report 141, INRIA, july 1992, available at
ftp://ftp.inria.fr/INRIA/publication/RT/RT-0141.ps.gz.  It documents
the Caml V3.1 API for exact-precision arithmetic, but the part of it
that deals with the "nat" abstraction still applies to the Nat module
of OCaml.

- Xavier Leroy

-------------------
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