[Ocaml-lib-devel] Extending big_int

[Richard J. <ri...@an...>]

A suggestion for ExtBig_int interface below.  I'm about 3/4 way
through the implementation, which will follow.

Comments welcome.

Some comments of my own:

* Big_int is implemented on top of Nat.  I got halfway through the
implementation before realising this, but it looks like I might have
tackled this at the wrong level.  OTOH, Big_int itself provides no way
to access the underlying Nat; also I suspect that most people will be
using Big_int directly, even for number theoretical / crypto work,
because Nat (natural numbers) can be too limiting.

* Some of the functions overlap with work done by Numerix / Cryptokit
/ GMP.  My intention wasn't to make this be a competitor to these -
just to make Big_ints a bit more useful out of the box.

* I added lsl, lsr, land, lor and lxor operators.  These are useful
but unfortunately the implementation is very slow because the basic
Big_int module doesn't really provide any bit-oriented methods.  We
could get around this by using Obj.magic to break encapsulation, but
the implementation would then be both complex and fragile.

* My current implementation of Big_int <-> binary representations is
slow, also because of the previous point.

* Factorization would be nice, but I'm not confident that I can
implement a suitable algorithm.  Perhaps this area is just too
specialised for extlib.

Rich.

----------------------------------------------------------------------
(*
 * ExtBig_int - Additional functions for handling big_ints.
 * Copyright (C) 2005 Richard W.M. Jones
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version,
 * with the special exception on linking described in file LICENSE.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *)

(** Additional functions for handing [big_int]s. *)

module Big_int :
sig
  type big_int (** The type of big integers. *)

  (** {6 New Functions} *)

  val one_big_int : big_int
  val two_big_int : big_int
  val three_big_int : big_int
  val four_big_int : big_int
  val five_big_int : big_int
  val six_big_int : big_int
  val seven_big_int : big_int
  val eight_big_int : big_int
  val nine_big_int : big_int
  val ten_big_int : big_int
  val sixteen_big_int : big_int
  val twenty_big_int : big_int
  val thirty_big_int : big_int
  val thirty_two_big_int : big_int
  val fourty_big_int : big_int
  val fifty_big_int : big_int
  val sixty_big_int : big_int
  val sixty_four_big_int : big_int
  val seventy_big_int : big_int
  val eighty_big_int : big_int
  val ninety_big_int : big_int
  val hundred_big_int : big_int

  val minus_one_big_int : big_int
  val minus_two_big_int : big_int
  val minus_three_big_int : big_int
  val minus_four_big_int : big_int
  val minus_five_big_int : big_int
  val minus_six_big_int : big_int
  val minus_seven_big_int : big_int
  val minus_eight_big_int : big_int
  val minus_nine_big_int : big_int
  val minus_ten_big_int : big_int
  val minus_sixteen_big_int : big_int
  val minus_twenty_big_int : big_int
  val minus_thirty_big_int : big_int
  val minus_thirty_two_big_int : big_int
  val minus_fourty_big_int : big_int
  val minus_fifty_big_int : big_int
  val minus_sixty_big_int : big_int
  val minus_sixty_four_big_int : big_int
  val minus_seventy_big_int : big_int
  val minus_eighty_big_int : big_int
  val minus_ninety_big_int : big_int
  val minus_hundred_big_int : big_int
    (** The constant big integers [1], [2], [3], ..., [-1], [-2],
      [-3], ... . *)

  val is_zero_big_int : big_int -> bool
  val is_one_big_int : big_int -> bool
  val is_minus_one_big_int : big_int -> bool
    (** These functions return true iff the [big_int] parameter is
      equal to [0] / [1] / [-1]. *)

  val compare_int_big_int : int -> big_int -> int
    (** [compare_int_big_int i bi] compares [int] [i]
      to [big_int] [bi], returning [0] if [i] and [bi] are
      numerically equal, or [1] if [i] is greater than [bi], or [-1]
      if [i] is less than [bi]. *)

  val is_odd_big_int : big_int -> bool
  val is_even_big_int : big_int -> bool
    (** These functions return true iff the [big_int] parameter is
      odd / even. *)

  val lsl_big_int : big_int -> int -> big_int
    (** Logical shift left the [big_int] by a number of [bits].  The
      result is undefined if [bits < 0].  The sign bit is ignored
      for the purposes of shifting. *)

  val lsr_big_int : big_int -> int -> big_int
    (** Logical shift right the [big_int] by a number of [bits].  The
      result is undefined if [bits < 0].  The sign bit is ignored
      for the purposes of shifting. *)

  val land_big_int : big_int -> big_int -> big_int
    (** Logical bitwise AND of two [big_int]s.  The sign bit is ignored. *)

  val lor_big_int : big_int -> big_int -> big_int
    (** Logical bitwise OR of two [big_int]s.  The sign bit is ignored. *)

  val lxor_big_int : big_int -> big_int -> big_int
    (** Logical bitwise XOR of two [big_int]s.  The sign bit is ignored. *)

  val double_big_int : big_int -> big_int
    (** [double_big_int n] is equivalent to [lsl_big_int n 1]. *)

  val half_big_int : big_int -> big_int
    (** [half_big_int n] is equivalent to [lsr_big_int n 1]. *)

  val add_two_big_int : big_int -> big_int
  val sub_two_big_int : big_int -> big_int
    (** Add / subtract [2] from the [big_int]. *)

  val power_of_two_big_int : int -> big_int
    (** [power_of_two_big_int n] returns [2^n] as a [big_int]. *)

  val binary_of_big_int : big_int -> int list
    (** [binary_of_big_int n] returns [n] as a
      list of [0]s and [1]s, representing the shortest
      binary representation of [n].  The most significant
      bit is the head of the list. *)

  val big_int_of_binary : int list -> big_int
    (** [big_int_of_binary bits].  [bits] should be a list
      of [0]s and [1]s only.  The function returns the big_int
      of the binary representation from the list.  The most
      significant bit should be first in the list. *)

  val binary_string_of_big_int : big_int -> string
    (** [binary_string_of_big_int] returns [n] as a
      string containing only ['0'] and ['1'] characters, representing
      the shortest binary representation of [n].  The most
      significant bit is the first character of the string. *)

  val big_int_of_binary_string : string -> big_int
    (** [big_int_of_binary_string bits].  [bits] should be a list of
      ['0'] and ['1'] characters only.  The function returns the
      big_int of the binary representation in the string.  The most
      significant bit should be first character of the string. *)

  val random_big_int : ?f:(unit -> int * int) -> int -> big_int
    (** [random_big_int bits] returns a random big_int of length
      [bits] bits.  The result will be between [0] and [2^bits - 1].

      If the optional [~f] parameter is not passed, then
      the standard OCaml random number generator is used
      (ie. the function {!Random.bits}).

      To gain more control over the source of randomness -- for
      instance to supply random numbers from an external source of
      entropy -- the caller should supply a function [~f] of type
      [unit -> int * int].  For each call this function should return
      [(random, bits)].  The first element of the tuple should be a
      positive random integer.  The second element of the tuple should
      be the number of bits of randomness contained in the random
      integer, where [1 <= bits <= 30].  [random_big_int] may raise
      [Failure] if [~f] returns a negative random integer, or if
      [bits] is outside the proscribed range.  *)

  val random_prime_big_int : ?f:(unit -> int * int) ->
    ?prime_test:(big_int -> bool) -> int -> big_int
    (** [random_prime_big_int bits] returns a random prime
      in the range [0] to [2^bits - 1].  [bits >= 1] else
      this function will raise [Invalid_argument].

      The optional function parameter [~f] can be used to pass
      in an external source of entropy, as is described in
      {!random_big_int}.

      The optional function parameter [~prime_test] can be used to
      pass in a primality testing function.  By default the function
      {!is_prime_bit_int} is used. *)

  val miller_rabin_primality_big_int : big_int -> rounds:int -> bool
    (** Probabilistic primality test for big int using the
      Miller-Rabin method.  [~rounds] is the number of rounds
      of testing to perform.  The confidence that the number is
      actually prime if this function returns [true] is
      [1 - 1 / 4^rounds]. *)

  val is_prime_big_int : big_int -> bool
    (** Probabilistic test of primality using a suitable algorithm
      with reasonable defaults. *)

(*
  val factorize_big_int : big_int -> (big_int * int) list
    (** Factorize the [big_int] into factors using a suitable algorithm.
      Returns a list of the unique factors and the multiplicity of
      each.  For example, [factorize_big_int (big_int_of_int 100)]
      would return the list [[ big_int_of_int 2, 2; big_int_of_int 5,
      2 ]], meaning that [100 = 2^2 * 5^2].  Note that factorizing
      large numbers can be slow. *)
*)

  (** {6 Older Functions} *)
  (** Please refer to the OCaml Manual for documentation for these
    functions. *)

  val zero_big_int : big_int
  val unit_big_int : big_int
  val minus_big_int : big_int -> big_int
  val abs_big_int : big_int -> big_int
  val add_big_int : big_int -> big_int -> big_int
  val succ_big_int : big_int -> big_int
  val add_int_big_int : int -> big_int -> big_int
  val sub_big_int : big_int -> big_int -> big_int
  val pred_big_int : big_int -> big_int
  val mult_big_int : big_int -> big_int -> big_int
  val mult_int_big_int : int -> big_int -> big_int
  val square_big_int: big_int -> big_int
  val sqrt_big_int: big_int -> big_int
  val quomod_big_int : big_int -> big_int -> big_int * big_int
  val div_big_int : big_int -> big_int -> big_int
  val mod_big_int : big_int -> big_int -> big_int
  val gcd_big_int : big_int -> big_int -> big_int
  val power_int_positive_int: int -> int -> big_int
  val power_big_int_positive_int: big_int -> int -> big_int
  val power_int_positive_big_int: int -> big_int -> big_int
  val power_big_int_positive_big_int: big_int -> big_int -> big_int

  val sign_big_int : big_int -> int
  val compare_big_int : big_int -> big_int -> int
  val eq_big_int : big_int -> big_int -> bool
  val le_big_int : big_int -> big_int -> bool
  val ge_big_int : big_int -> big_int -> bool
  val lt_big_int : big_int -> big_int -> bool
  val gt_big_int : big_int -> big_int -> bool
  val max_big_int : big_int -> big_int -> big_int
  val min_big_int : big_int -> big_int -> big_int
  val num_digits_big_int : big_int -> int

  val string_of_big_int : big_int -> string
  val big_int_of_string : string -> big_int

  val big_int_of_int : int -> big_int
  val is_int_big_int : big_int -> bool
  val int_of_big_int : big_int -> int
  val float_of_big_int : big_int -> float

  (** {6 For internal use} *)
  val nat_of_big_int : big_int -> Nat.nat
  val big_int_of_nat : Nat.nat -> big_int
  val base_power_big_int: int -> int -> big_int -> big_int
  val sys_big_int_of_string: string -> int -> int -> big_int
  val round_futur_last_digit : string -> int -> int -> bool
  val approx_big_int: int -> big_int -> string

end

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com