(***********************************************************************)
(*                                                                     *)
(*                           Objective Caml                            *)
(*                                                                     *)
         , projet Cristal , INRIA Rocquencourt     
(*                                                                     *)
   Copyright 1996 Institut National de Recherche en Informatique et   
   en Automatique .   All rights reserved .   This file is distributed    
   under the terms of the GNU Library General Public License , with    
(*  the special exception on linking described in file ../../LICENSE.  *)
(*                                                                     *)
(***********************************************************************)

  $ I d : big_int.mli 10327 2010 - 04 - 29 13:53:01Z xleroy $

(** Operations on arbitrary-precision integers.

   Big integers (type [big_int]) are signed integers of arbitrary size.
*)

open Nat

type big_int
        (** The type of big integers. *)

val zero_big_int : big_int
        (** The big integer [0]. *)
val unit_big_int : big_int
* The big integer [ 1 ] .

* { 6 Arithmetic operations }

val minus_big_int : big_int -> big_int
        (** Unary negation. *)
val abs_big_int : big_int -> big_int
        (** Absolute value. *)
val add_big_int : big_int -> big_int -> big_int
        (** Addition. *)
val succ_big_int : big_int -> big_int
* Successor ( add 1 ) .
val add_int_big_int : int -> big_int -> big_int
        (** Addition of a small integer to a big integer. *)
val sub_big_int : big_int -> big_int -> big_int
        (** Subtraction. *)
val pred_big_int : big_int -> big_int
* Predecessor ( subtract 1 ) .
val mult_big_int : big_int -> big_int -> big_int
* Multiplication of two big integers .
val mult_int_big_int : int -> big_int -> big_int
        (** Multiplication of a big integer by a small integer *)
val square_big_int: big_int -> big_int
        (** Return the square of the given big integer *)
val sqrt_big_int: big_int -> big_int
        (** [sqrt_big_int a] returns the integer square root of [a],
           that is, the largest big integer [r] such that [r * r <= a].
           Raise [Invalid_argument] if [a] is negative. *)
val quomod_big_int : big_int -> big_int -> big_int * big_int
* Euclidean division of two big integers . 
            The first part of the result is the quotient , 
            the second part is the remainder . 
            Writing [ ( q , r ) = quomod_big_int a b ] , we have 
            [ a = q * b + r ] and [ 0 < = r < |b| ] . 
            Raise [ Division_by_zero ] if the divisor is zero .
           The first part of the result is the quotient,
           the second part is the remainder.
           Writing [(q,r) = quomod_big_int a b], we have
           [a = q * b + r] and [0 <= r < |b|].
           Raise [Division_by_zero] if the divisor is zero. *)
val div_big_int : big_int -> big_int -> big_int
* Euclidean quotient of two big integers . 
            This is the first result [ q ] of [ quomod_big_int ] ( see above ) .
           This is the first result [q] of [quomod_big_int] (see above). *)
val mod_big_int : big_int -> big_int -> big_int
* Euclidean modulus of two big integers . 
            This is the second result [ r ] of [ quomod_big_int ] ( see above ) .
           This is the second result [r] of [quomod_big_int] (see above). *)
val gcd_big_int : big_int -> big_int -> big_int
* Greatest common divisor of two big integers .
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
* Exponentiation functions .   Return the big integer 
            representing the first argument [ a ] raised to the power [ b ] 
            ( the second argument ) .   Depending 
            on the function , [ a ] and [ b ] can be either small integers 
            or big integers .   Raise [ Invalid_argument ] if [ b ] is negative .
           representing the first argument [a] raised to the power [b]
           (the second argument).  Depending
           on the function, [a] and [b] can be either small integers
           or big integers.  Raise [Invalid_argument] if [b] is negative. *)

* { 6 Comparisons and tests }

val sign_big_int : big_int -> int
* Return [ 0 ] if the given big integer is zero , 
            [ 1 ] if it is positive , and [ -1 ] if it is negative .
           [1] if it is positive, and [-1] if it is negative. *)
val compare_big_int : big_int -> big_int -> int
* [ compare_big_int a b ] returns [ 0 ] if [ a ] and [ b ] are equal , 
            [ 1 ] if [ a ] is greater than [ b ] , and [ -1 ] if [ a ] is smaller 
            than [ b ] .
           [1] if [a] is greater than [b], and [-1] if [a] is smaller
           than [b]. *)
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
* Usual boolean comparisons between two big integers .
val max_big_int : big_int -> big_int -> big_int
* Return the greater of its two arguments .
val min_big_int : big_int -> big_int -> big_int
* Return the smaller of its two arguments .
val num_digits_big_int : big_int -> int
        (** Return the number of machine words used to store the
           given big integer.  *)

* { 6 Conversions to and from strings }

val string_of_big_int : big_int -> string
* Return the string representation of the given big integer , 
            in decimal ( base 10 ) .
           in decimal (base 10). *)
val big_int_of_string : string -> big_int
* Convert a string to a big integer , in decimal . 
            The string consists of an optional [ - ] or [ + ] sign , 
            followed by one or several decimal digits .
           The string consists of an optional [-] or [+] sign,
           followed by one or several decimal digits. *)

* { 6 Conversions to and from other numerical types }

val big_int_of_int : int -> big_int
        (** Convert a small integer to a big integer. *)
val is_int_big_int : big_int -> bool
* Test whether the given big integer is small enough to 
            be representable as a small integer ( type [ int ] ) 
            without loss of precision .   On a 32 - bit platform , 
            [ is_int_big_int a ] returns [ true ] if and only if 
            [ a ] is between 2{^30 } and 2{^30}-1 .   On a 64 - bit platform , 
            [ is_int_big_int a ] returns [ true ] if and only if 
            [ a ] is between -2{^62 } and 2{^62}-1 .
           be representable as a small integer (type [int])
           without loss of precision.  On a 32-bit platform,
           [is_int_big_int a] returns [true] if and only if
           [a] is between 2{^30} and 2{^30}-1.  On a 64-bit platform,
           [is_int_big_int a] returns [true] if and only if
           [a] is between -2{^62} and 2{^62}-1. *)
val int_of_big_int : big_int -> int
        (** Convert a big integer to a small integer (type [int]).
           Raises [Failure "int_of_big_int"] if the big integer
           is not representable as a small integer. *)

val big_int_of_int32 : int32 -> big_int
* Convert a 32 - bit integer to a big integer .
val big_int_of_nativeint : nativeint -> big_int
        (** Convert a native integer to a big integer. *)
val big_int_of_int64 : int64 -> big_int
* Convert a 64 - bit integer to a big integer .
val int32_of_big_int : big_int -> int32
* Convert a big integer to a 32 - bit integer . 
             Raises [ Failure ] if the big integer is outside the 
             range [ [ -2{^31 } , 2{^31}-1 ] ] .
            Raises [Failure] if the big integer is outside the
            range [[-2{^31}, 2{^31}-1]]. *)
val nativeint_of_big_int : big_int -> nativeint
        (** Convert a big integer to a native integer.
            Raises [Failure] if the big integer is outside the
            range [[Nativeint.min_int, Nativeint.max_int]]. *)
val int64_of_big_int : big_int -> int64
* Convert a big integer to a 64 - bit integer . 
             Raises [ Failure ] if the big integer is outside the 
             range [ [ -2{^63 } , 2{^63}-1 ] ] .
            Raises [Failure] if the big integer is outside the
            range [[-2{^63}, 2{^63}-1]]. *)

val float_of_big_int : big_int -> float
        (** Returns a floating-point number approximating the
           given big integer. *)

* { 6 Bit - oriented operations }

val and_big_int : big_int -> big_int -> big_int
* Bitwise logical ` ` and '' . 
             The arguments must be positive or zero .
            The arguments must be positive or zero. *)
val or_big_int : big_int -> big_int -> big_int
* Bitwise logical ` ` or '' . 
             The arguments must be positive or zero .
            The arguments must be positive or zero. *)
val xor_big_int : big_int -> big_int -> big_int
* Bitwise logical ` ` exclusive or '' . 
             The arguments must be positive or zero .
            The arguments must be positive or zero. *)
val shift_left_big_int : big_int -> int -> big_int
* [ shift_left_big_int b n ] returns [ b ] shifted left by [ n ] bits . 
             Equivalent to multiplication by [ 2^n ] .
            Equivalent to multiplication by [2^n]. *)
val shift_right_big_int : big_int -> int -> big_int
* [ shift_right_big_int b n ] returns [ b ] shifted right by [ n ] bits . 
             Equivalent to division by [ 2^n ] with the result being 
             rounded towards minus infinity .
            Equivalent to division by [2^n] with the result being
            rounded towards minus infinity. *)
val shift_right_towards_zero_big_int : big_int -> int -> big_int
* [ shift_right_towards_zero_big_int b n ] returns [ b ] shifted 
             right by [ n ] bits .   The shift is performed on the absolute 
             value of [ b ] , and the result has the same sign as [ b ] . 
             Equivalent to division by [ 2^n ] with the result being 
             rounded towards zero .
            right by [n] bits.  The shift is performed on the absolute
            value of [b], and the result has the same sign as [b].
            Equivalent to division by [2^n] with the result being
            rounded towards zero. *)
val extract_big_int : big_int -> int -> int -> big_int
* [ extract_big_int bi ofs n ] returns a nonnegative number 
             corresponding to bits [ ofs ] to [ ofs + n - 1 ] of the 
             binary representation of [ bi ] .   If [ bi ] is negative , 
             a two 's complement representation is used .
            corresponding to bits [ofs] to [ofs + n - 1] of the
            binary representation of [bi].  If [bi] is negative,
            a two's complement representation is used. *)

(**/**)

* { 6 For internal use }
val nat_of_big_int : big_int -> nat
val big_int_of_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

val init : unit -> unit

*********************************************************************
                                                                     
                           Objective Caml                            
                                                                     
                                                                     
  the special exception on linking described in file ../../LICENSE.  
                                                                     
*********************************************************************
* Operations on arbitrary-precision integers.

   Big integers (type [big_int]) are signed integers of arbitrary size.

* The type of big integers. 
* The big integer [0]. 
* Unary negation. 
* Absolute value. 
* Addition. 
* Addition of a small integer to a big integer. 
* Subtraction. 
* Multiplication of a big integer by a small integer 
* Return the square of the given big integer 
* [sqrt_big_int a] returns the integer square root of [a],
           that is, the largest big integer [r] such that [r * r <= a].
           Raise [Invalid_argument] if [a] is negative. 
* Return the number of machine words used to store the
           given big integer.  
* Convert a small integer to a big integer. 
* Convert a big integer to a small integer (type [int]).
           Raises [Failure "int_of_big_int"] if the big integer
           is not representable as a small integer. 
* Convert a native integer to a big integer. 
* Convert a big integer to a native integer.
            Raises [Failure] if the big integer is outside the
            range [[Nativeint.min_int, Nativeint.max_int]]. 
* Returns a floating-point number approximating the
           given big integer. 
*/*
         , projet Cristal , INRIA Rocquencourt     
   Copyright 1996 Institut National de Recherche en Informatique et   
   en Automatique .   All rights reserved .   This file is distributed    
   under the terms of the GNU Library General Public License , with    

  $ I d : big_int.mli 10327 2010 - 04 - 29 13:53:01Z xleroy $


open Nat

type big_int

val zero_big_int : big_int
val unit_big_int : big_int
* The big integer [ 1 ] .

* { 6 Arithmetic operations }

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
* Successor ( add 1 ) .
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
* Predecessor ( subtract 1 ) .
val mult_big_int : big_int -> big_int -> big_int
* Multiplication of two big integers .
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
* Euclidean division of two big integers . 
            The first part of the result is the quotient , 
            the second part is the remainder . 
            Writing [ ( q , r ) = quomod_big_int a b ] , we have 
            [ a = q * b + r ] and [ 0 < = r < |b| ] . 
            Raise [ Division_by_zero ] if the divisor is zero .
           The first part of the result is the quotient,
           the second part is the remainder.
           Writing [(q,r) = quomod_big_int a b], we have
           [a = q * b + r] and [0 <= r < |b|].
           Raise [Division_by_zero] if the divisor is zero. *)
val div_big_int : big_int -> big_int -> big_int
* Euclidean quotient of two big integers . 
            This is the first result [ q ] of [ quomod_big_int ] ( see above ) .
           This is the first result [q] of [quomod_big_int] (see above). *)
val mod_big_int : big_int -> big_int -> big_int
* Euclidean modulus of two big integers . 
            This is the second result [ r ] of [ quomod_big_int ] ( see above ) .
           This is the second result [r] of [quomod_big_int] (see above). *)
val gcd_big_int : big_int -> big_int -> big_int
* Greatest common divisor of two big integers .
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
* Exponentiation functions .   Return the big integer 
            representing the first argument [ a ] raised to the power [ b ] 
            ( the second argument ) .   Depending 
            on the function , [ a ] and [ b ] can be either small integers 
            or big integers .   Raise [ Invalid_argument ] if [ b ] is negative .
           representing the first argument [a] raised to the power [b]
           (the second argument).  Depending
           on the function, [a] and [b] can be either small integers
           or big integers.  Raise [Invalid_argument] if [b] is negative. *)

* { 6 Comparisons and tests }

val sign_big_int : big_int -> int
* Return [ 0 ] if the given big integer is zero , 
            [ 1 ] if it is positive , and [ -1 ] if it is negative .
           [1] if it is positive, and [-1] if it is negative. *)
val compare_big_int : big_int -> big_int -> int
* [ compare_big_int a b ] returns [ 0 ] if [ a ] and [ b ] are equal , 
            [ 1 ] if [ a ] is greater than [ b ] , and [ -1 ] if [ a ] is smaller 
            than [ b ] .
           [1] if [a] is greater than [b], and [-1] if [a] is smaller
           than [b]. *)
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
* Usual boolean comparisons between two big integers .
val max_big_int : big_int -> big_int -> big_int
* Return the greater of its two arguments .
val min_big_int : big_int -> big_int -> big_int
* Return the smaller of its two arguments .
val num_digits_big_int : big_int -> int

* { 6 Conversions to and from strings }

val string_of_big_int : big_int -> string
* Return the string representation of the given big integer , 
            in decimal ( base 10 ) .
           in decimal (base 10). *)
val big_int_of_string : string -> big_int
* Convert a string to a big integer , in decimal . 
            The string consists of an optional [ - ] or [ + ] sign , 
            followed by one or several decimal digits .
           The string consists of an optional [-] or [+] sign,
           followed by one or several decimal digits. *)

* { 6 Conversions to and from other numerical types }

val big_int_of_int : int -> big_int
val is_int_big_int : big_int -> bool
* Test whether the given big integer is small enough to 
            be representable as a small integer ( type [ int ] ) 
            without loss of precision .   On a 32 - bit platform , 
            [ is_int_big_int a ] returns [ true ] if and only if 
            [ a ] is between 2{^30 } and 2{^30}-1 .   On a 64 - bit platform , 
            [ is_int_big_int a ] returns [ true ] if and only if 
            [ a ] is between -2{^62 } and 2{^62}-1 .
           be representable as a small integer (type [int])
           without loss of precision.  On a 32-bit platform,
           [is_int_big_int a] returns [true] if and only if
           [a] is between 2{^30} and 2{^30}-1.  On a 64-bit platform,
           [is_int_big_int a] returns [true] if and only if
           [a] is between -2{^62} and 2{^62}-1. *)
val int_of_big_int : big_int -> int

val big_int_of_int32 : int32 -> big_int
* Convert a 32 - bit integer to a big integer .
val big_int_of_nativeint : nativeint -> big_int
val big_int_of_int64 : int64 -> big_int
* Convert a 64 - bit integer to a big integer .
val int32_of_big_int : big_int -> int32
* Convert a big integer to a 32 - bit integer . 
             Raises [ Failure ] if the big integer is outside the 
             range [ [ -2{^31 } , 2{^31}-1 ] ] .
            Raises [Failure] if the big integer is outside the
            range [[-2{^31}, 2{^31}-1]]. *)
val nativeint_of_big_int : big_int -> nativeint
val int64_of_big_int : big_int -> int64
* Convert a big integer to a 64 - bit integer . 
             Raises [ Failure ] if the big integer is outside the 
             range [ [ -2{^63 } , 2{^63}-1 ] ] .
            Raises [Failure] if the big integer is outside the
            range [[-2{^63}, 2{^63}-1]]. *)

val float_of_big_int : big_int -> float

* { 6 Bit - oriented operations }

val and_big_int : big_int -> big_int -> big_int
* Bitwise logical ` ` and '' . 
             The arguments must be positive or zero .
            The arguments must be positive or zero. *)
val or_big_int : big_int -> big_int -> big_int
* Bitwise logical ` ` or '' . 
             The arguments must be positive or zero .
            The arguments must be positive or zero. *)
val xor_big_int : big_int -> big_int -> big_int
* Bitwise logical ` ` exclusive or '' . 
             The arguments must be positive or zero .
            The arguments must be positive or zero. *)
val shift_left_big_int : big_int -> int -> big_int
* [ shift_left_big_int b n ] returns [ b ] shifted left by [ n ] bits . 
             Equivalent to multiplication by [ 2^n ] .
            Equivalent to multiplication by [2^n]. *)
val shift_right_big_int : big_int -> int -> big_int
* [ shift_right_big_int b n ] returns [ b ] shifted right by [ n ] bits . 
             Equivalent to division by [ 2^n ] with the result being 
             rounded towards minus infinity .
            Equivalent to division by [2^n] with the result being
            rounded towards minus infinity. *)
val shift_right_towards_zero_big_int : big_int -> int -> big_int
* [ shift_right_towards_zero_big_int b n ] returns [ b ] shifted 
             right by [ n ] bits .   The shift is performed on the absolute 
             value of [ b ] , and the result has the same sign as [ b ] . 
             Equivalent to division by [ 2^n ] with the result being 
             rounded towards zero .
            right by [n] bits.  The shift is performed on the absolute
            value of [b], and the result has the same sign as [b].
            Equivalent to division by [2^n] with the result being
            rounded towards zero. *)
val extract_big_int : big_int -> int -> int -> big_int
* [ extract_big_int bi ofs n ] returns a nonnegative number 
             corresponding to bits [ ofs ] to [ ofs + n - 1 ] of the 
             binary representation of [ bi ] .   If [ bi ] is negative , 
             a two 's complement representation is used .
            corresponding to bits [ofs] to [ofs + n - 1] of the
            binary representation of [bi].  If [bi] is negative,
            a two's complement representation is used. *)


* { 6 For internal use }
val nat_of_big_int : big_int -> nat
val big_int_of_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

val init : unit -> unit
