bigint.h

eC++编译器源码

/**********************************************************************

	File:   BigInt.h
	Rev:    b-1
	Date:   02/01/90

***********************************************************************

	Module to allow computation with large integers.

***********************************************************************

	Modification Log:

	b-1:    02/01/90        David Warme
		: Added documentation.
		: Added SubInt.

**********************************************************************/



/**********************************************************************
 *
 * This module defines an opaque data-type called Integer, together
 * with several useful operations that allow computation with extended-
 * precision integers.
 *
 * There is a bothersome incongruity between the types
 * INTEGER and Integer -- the all-caps one is really for SMALL numbers!
 *
 * NOTE: The current definition and implementation DO NOT handle
 * integers of ARBITRARY precision!  It is necessary for the caller
 * to explicitly specify the maximum size of each Integer variable
 * (in words) at the time it is created.  Hopefully, this shortfall
 * can be corrected in the future to allow truly dynamic integers.
 *
 * The following is a brief synopsis of each operation provided:
 *
 *      VAR     x,y,z : Integer;        -- BIG integer
 *              num   : INTEGER;        -- normal integer
 *              r,s   : INTEGER;        -- remainders and signs.
 *              power : CARDINAL;       -- non-negative integer powers.
 *              buffer: ARRAY OF CHAR;  -- string for printable conversion.
 *              width : CARDINAL;       -- width of printed representation.
 *
 *      Open (x, nwords);       -- create a big integer variable
 *                                 (initially zero)
 *      Close (x);              -- destroy a big integer variable
 *                                 (frees up its storage)
 *      Zero (x);               -- x := 0;
 *      Negate (x);             -- x := -x;
 *
 *      ConstI (x, num);        -- x := num;  (small integer)
 *      AddInt (x, num);        -- x := x + num;
 *      TimesInt (x, num);      -- x := x * num;
 * r := DivideInt (x, num);     -- r := x mod num;
 *                                 x := x div num;
 *      PowerInt (x, power);    -- x := x ** power;
 * s := CompareInt (x, num);    -- s := signum (x - num);
 *
 *      Assign (x, y);          -- x := y;    (COPY y into x)
 *      Add (x, y);             -- x := x + y;
 *      Times (x, y);           -- x := x * y;
 *      Subtract (x, y);        -- x := x - y;
 *      Divide (x, y, z);       -- z := x mod y;
 *                                 x := x div y;
 * s := Compare (x, y);         -- s := signum (x - y);
 *
 *      Read (x, buffer);       -- x <== decimal string in buffer
 *      Write (x, width);       -- write x to stdout in decimal.
 *      WriteS (buffer, pos,    -- write x to string in decimal.
 *              x, width);         (currently UNIMPLEMENTED!!!)
 *
 *
 *********************************************************************/

#pragma BigInt

  typedef void *Integer;


/************************************************/
/*                                              */
/*              Basic Operations                */
/*                                              */
/************************************************/

  void Open   (Integer &p,               /* create (and zero) p of    */
	       unsigned int numWords);   /* given number of words.    */

  void Close (Integer &x);            /* destroy given big integer */

  void Zero (Integer x);                 /* x := 0;                   */

  void Negate (Integer x);               /* x := - x;                 */


/************************************************/
/*                                              */
/*   Opertions Between Big and Small Integers   */
/*                                              */
/************************************************/

  void ConstI (Integer x,            /* x := const;               */
		    int constant);

  void AddInt (Integer x,            /* x := x + const;           */
		    int constant);

  void SubInt (Integer x,            /* x := x - const;           */
		    int constant);

  void TimesInt (Integer x,          /* x := x * const;           */
		      int constant);

  int DivideInt (Integer x,         /* r := x mod divisor;       */
		       int divisor);       /* x := x div divisor;       */
				      /* returns remainder         */

  void PowerInt (Integer x,          /* x := x ** power;          */
		      unsigned int power);

  int CompareInt (Integer left,        /* <- sgn (left - right);    */
		  int  right);
				      /* returns -1, 0, or +1      */

/************************************************/
/*                                              */
/*      Opertions Purely on Big Integers        */
/*                                              */
/************************************************/

  void Assign (Integer target,           /* target := value;          */
		    Integer value);          /*      <value is COPIED>    */

  void Add (Integer result,              /* result := result + value; */
		 Integer value);             /*      Add(x,x) is OK...    */

  void Subtract (Integer result,         /* result := result - value; */
		      Integer value);

  void Times (Integer x,                 /* x := x * y;               */
		   Integer y);                /*      Times(x,x) is OK...  */

  void Divide (Integer x,        /* remainder := x mod y;     */
		    Integer y,        /* x := x div y;             */
		    Integer remainder);

  int Compare (Integer left,           /* <- sgn (left - right);    */
		     Integer right);
				      /* returns -1, 0, or +1      */


/************************************************/
/*                                              */
/*              Input and Output                */
/*                                              */
/************************************************/

  void Read       (Integer x,        /* x <== Convert (const);    */
			char s[]); /*   Syntax: [+|-](0-9)*     */

  void Write      (Integer x,        /* write out x in decimal    */
			unsigned int width);      /* minimum width of output   */

/* THIS ROUTINE DOES NOT YET WORK! */
  void WriteS     (char &s[],
			    unsigned int pos,
			    Integer x,
			    unsigned int width);