
(********************************************************************)
(*                                                                  *)
(*  bigint.s7i    bigInteger point support library                  *)
(*  Copyright (C) 2006  Thomas Mertes                               *)
(*                                                                  *)
(*  This file is part of the Seed7 Runtime Library.                 *)
(*                                                                  *)
(*  The Seed7 Runtime 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.                                      *)
(*                                                                  *)
(*  The Seed7 Runtime 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 program; if not, write to the    *)
(*  Free Software Foundation, Inc., 51 Franklin Street,             *)
(*  Fifth Floor, Boston, MA  02110-1301, USA.                       *)
(*                                                                  *)
(********************************************************************)


(**
 *  The type 'bigInteger' consists of all integer numbers.
 *  The literals of the type 'bigInteger' are sequences of digits
 *  followed by an underscore character (for example 1_ ).
 *)
const type: bigInteger is          subtype object;
$ system "bigInteger" is bigInteger;

const proc: destroy (ref bigInteger param)                              is action "BIG_DESTR";
const proc: (ref bigInteger param) ::= (ref bigInteger param)           is action "BIG_CREATE";
IN_PARAM_IS_REFERENCE(bigInteger);

const func bigInteger: + (ref bigInteger param)                         is action "BIG_PLUS";
const func bigInteger: - (ref bigInteger param)                         is action "BIG_MINUS";

const proc: (inout bigInteger param) := (ref bigInteger param)          is action "BIG_CPY";
const proc: (inout bigInteger param) +:= (ref bigInteger param)         is action "BIG_GROW";
const proc: (inout bigInteger param) -:= (ref bigInteger param)         is action "BIG_SHRINK";
const proc: (inout bigInteger param) *:= (ref bigInteger param)         is action "BIG_MULT_ASSIGN";
const proc: (inout bigInteger param) <<:= (ref integer param)           is action "BIG_LSHIFT_ASSIGN";
const proc: (inout bigInteger param) >>:= (ref integer param)           is action "BIG_RSHIFT_ASSIGN";
const func bigInteger: (ref bigInteger param) + (ref bigInteger param)  is action "BIG_ADD";
const func bigInteger: (ref bigInteger param) - (ref bigInteger param)  is action "BIG_SBTR";
const func bigInteger: (ref bigInteger param) * (ref bigInteger param)  is action "BIG_MULT";
const func bigInteger: (in bigInteger param) div (in bigInteger param)  is action "BIG_DIV";
const func bigInteger: (in bigInteger param) rem (in bigInteger param)  is action "BIG_REM";
const func bigInteger: (in bigInteger param) mdiv (in bigInteger param) is action "BIG_MDIV";
const func bigInteger: (in bigInteger param) mod (in bigInteger param)  is action "BIG_MOD";
const func bigInteger: (ref bigInteger param) ** (ref integer param)    is action "BIG_IPOW";
# const func bigInteger: (ref bigInteger param) ** (ref bigInteger param) is action "BIG_POW";
const func bigInteger: (in bigInteger param) << (ref integer param)     is action "BIG_LSHIFT";
const func bigInteger: (in bigInteger param) >> (ref integer param)     is action "BIG_RSHIFT";
const func boolean: (ref bigInteger param) = (ref bigInteger param)     is action "BIG_EQ";
const func boolean: (ref bigInteger param) < (ref bigInteger param)     is action "BIG_LT";
const func boolean: (ref bigInteger param) > (ref bigInteger param)     is action "BIG_GT";
const func boolean: (ref bigInteger param) <= (ref bigInteger param)    is action "BIG_LE";
const func boolean: (ref bigInteger param) >= (ref bigInteger param)    is action "BIG_GE";
const func boolean: (ref bigInteger param) <> (ref bigInteger param)    is action "BIG_NE";
const func integer: compare (in bigInteger param, in bigInteger param)  is action "BIG_CMP";
const func integer: hashCode (in bigInteger param)                      is action "BIG_HASHCODE";

const func bigInteger: succ (in bigInteger param)                       is action "BIG_SUCC";
const func bigInteger: pred (in bigInteger param)                       is action "BIG_PRED";
const func bigInteger: abs (in bigInteger param)                        is action "BIG_ABS";
const func bigInteger: log2 (in bigInteger param)                       is action "BIG_LOG2";
const func boolean: odd (in bigInteger param)                           is action "BIG_ODD";
const func integer: ord (in bigInteger param)                           is action "BIG_ORD";
const func bigInteger: gcd (in bigInteger param, in bigInteger param)   is action "BIG_GCD";
const func bigInteger: (attr bigInteger) conv (in integer param)        is action "BIG_ICONV";
const func string: str (ref bigInteger param)                           is action "BIG_STR";
const func string: c_literal (in bigInteger param)                      is action "BIG_CLIT";
const func bigInteger: rand (in bigInteger param, in bigInteger param)  is action "BIG_RAND";
const func integer: bitLength (in bigInteger param)                     is action "BIG_BIT_LENGTH";
const func integer: lowestSetBit (in bigInteger param)                  is action "BIG_LOWEST_SET_BIT";
const func bigInteger: (attr bigInteger) parse (in string param)        is action "BIG_PARSE";

const bigInteger: (attr bigInteger) . value                             is bigInteger parse "0";

const proc: incr (inout bigInteger param)                               is action "BIG_INCR";
const proc: decr (inout bigInteger param)                               is action "BIG_DECR";

const boolean: ord (in bigInteger param, mayRaiseRangeError)            is TRUE;

enable_io(bigInteger);
FOR_DECLS(bigInteger);


(**
 *  Return the integer square root of a bigInteger number.
 *)
const func bigInteger: sqrt (in var bigInteger: number) is func
  result
    var bigInteger: result is 0_;
  local
    var bigInteger: res2 is 0_;
  begin
    if number > 0_ then
      res2 := number;
      repeat
        result := res2;
        res2 := (result + number div result) div 2_;
      until result <= res2;
    else
      raise NUMERIC_ERROR;
    end if;
  end func;


(**
 *  Return the modular multiplicative inverse of a modulo b.
 *  If a and b are not coprime (gcd(a, b) <> 1) the exception
 *  RANGE_ERROR is raised.
 *)
const func bigInteger: modInverse (in var bigInteger: a,
    in var bigInteger: b) is func
  result
    var bigInteger: result is 0_;
  local
    var bigInteger: b_bak is 0_;
    var bigInteger: x is 0_;
    var bigInteger: y is 1_;
    var bigInteger: lastx is 1_;
    var bigInteger: lasty is 0_;
    var bigInteger: temp is 0_;
    var bigInteger: quotient is 0_;
  begin
    if b < 0_ then
      raise RANGE_ERROR;
    end if;
    if a < 0_ and b <> 0_ then
      a := a mod b;
    end if;
    b_bak := b;
    while b <> 0_ do
      temp := b;
      quotient := a div b;
      b := a rem b;
      a := temp;

      temp := x;
      x := lastx - quotient * x;
      lastx := temp;

      temp := y;
      y := lasty - quotient * y;
      lasty := temp;
    end while;
    if a = 1_ then
      result := lastx;
      if result < 0_ then
        result +:= b_bak;
      end if;
    else
      raise RANGE_ERROR;
    end if;
  end func;
