(**************************************************************************)
(*                                                                        *)
(*                                 OCaml                                  *)
(*                                                                        *)
(*     Valerie Menissier-Morain, 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 Lesser General Public License version 2.1, with the          *)
(*   special exception on linking described in the file LICENSE.          *)
(*                                                                        *)
(**************************************************************************)

(** 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. *)

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). *)

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). *)

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. *)

(** {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. *)

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]. *)

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.  *)

val num_bits_big_int : big_int -> int
        (** Return the number of significant bits in the absolute
            value of the given big integer.  [num_bits_big_int a]
            returns 0 if [a] is 0; otherwise it returns a positive
            integer [n] such that [2^(n-1) <= |a| < 2^n].

            @since 4.03.0 *)

(** {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). *)

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. *)
(* TODO: document error condition. *)

val big_int_of_string_opt: string -> big_int option
(** Convert a string to a big integer, in decimal.
    The string consists of an optional [-] or [+] sign,
    followed by one or several decimal digits. Other the function
    returns [None].
    @since 4.05
*)


(** {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. *)

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 int_of_big_int_opt: big_int -> int option
(** Convert a big integer to a small integer (type [int]).  Return
    [None] if the big integer is not representable as a small
    integer.
    @since 4.05
*)

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\]. *)

val int32_of_big_int_opt: big_int -> int32 option
(** Convert a big integer to a 32-bit integer.  Return [None] if the
    big integer is outside the range \[-2{^31}, 2{^31}-1\].
    @since 4.05
*)

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 nativeint_of_big_int_opt: big_int -> nativeint option
(** Convert a big integer to a native integer. Return [None] if the
    big integer is outside the range [[Nativeint.min_int,
    Nativeint.max_int]];
    @since 4.05
*)

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\]. *)

val int64_of_big_int_opt: big_int -> int64 option
(** Convert a big integer to a 64-bit integer. Return [None] if the
    big integer is outside the range \[-2{^63}, 2{^63}-1\].
    @since 4.05
*)

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. *)

val or_big_int : big_int -> big_int -> big_int
        (** Bitwise logical 'or'.
            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. *)

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. *)

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. *)

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. *)

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. *)

(**/**)

(** {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 : bytes -> int -> int -> bool
val approx_big_int: int -> big_int -> string

val round_big_int_to_float: big_int -> bool -> float
(* @since 4.03.0 *)
