home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Programmierung / SOURCE.mdf / programm / msdos / c / djgpp / include / integer.h < prev    next >
C/C++ Source or Header  |  1991-03-03  |  27KB  |  1,115 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2.  
  3. /* 
  4. Copyright (C) 1988 Free Software Foundation
  5.     written by Doug Lea (dl@rocky.oswego.edu)
  6.  
  7. This file is part of GNU CC.
  8.  
  9. GNU CC is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY.  No author or distributor
  11. accepts responsibility to anyone for the consequences of using it
  12. or for whether it serves any particular purpose or works at all,
  13. unless he says so in writing.  Refer to the GNU CC General Public
  14. License for full details.
  15.  
  16. Everyone is granted permission to copy, modify and redistribute
  17. GNU CC, but only under the conditions described in the
  18. GNU CC General Public License.   A copy of this license is
  19. supposed to have been given to you along with GNU CC so you
  20. can know your rights and responsibilities.  It should be in a
  21. file named COPYING.  Among other things, the copyright notice
  22. and this notice must be preserved on all copies.  
  23. */
  24.  
  25. #ifndef _Integer_h
  26. #ifdef __GNUG__
  27. #pragma once
  28. #pragma interface
  29. #endif
  30. #define _Integer_h 1
  31.  
  32. #include <stream.h>
  33.  
  34. struct IntRep                    // internal Integer representations
  35. {
  36.   unsigned short  len;          // current length
  37.   unsigned short  sz;           // allocated space
  38.   short           sgn;          // 1 means >= 0; 0 means < 0 
  39.   unsigned short  s[1];         // represented as ushort array starting here
  40. };
  41.  
  42. extern IntRep*  Ialloc(IntRep*, const unsigned short *, int, int, int);
  43. extern IntRep*  Icalloc(IntRep*, int);
  44. extern IntRep*  Icopy_long(IntRep*, long);
  45. extern IntRep*  Icopy(IntRep*, const IntRep*);
  46. extern IntRep*  Iresize(IntRep*, int);
  47. extern IntRep*  add(const IntRep*, int, const IntRep*, int, IntRep*);
  48. extern IntRep*  add(const IntRep*, int, long, IntRep*);
  49. extern IntRep*  multiply(const IntRep*, const IntRep*, IntRep*);
  50. extern IntRep*  multiply(const IntRep*, long, IntRep*);
  51. extern IntRep*  lshift(const IntRep*, long, IntRep*);
  52. extern IntRep*  lshift(const IntRep*, const IntRep*, int, IntRep*);
  53. extern IntRep*  bitop(const IntRep*, const IntRep*, IntRep*, char);
  54. extern IntRep*  bitop(const IntRep*, long, IntRep*, char);
  55. extern IntRep*  power(const IntRep*, long, IntRep*);
  56. extern IntRep*  div(const IntRep*, const IntRep*, IntRep*);
  57. extern IntRep*  mod(const IntRep*, const IntRep*, IntRep*);
  58. extern IntRep*  div(const IntRep*, long, IntRep*);
  59. extern IntRep*  mod(const IntRep*, long, IntRep*);
  60. extern IntRep*  compl(const IntRep*, IntRep*);
  61. extern IntRep*  abs(const IntRep*, IntRep*);
  62. extern IntRep*  negate(const IntRep*, IntRep*);
  63. extern IntRep*  pow(const IntRep*, long);
  64. extern IntRep*  gcd(const IntRep*, const IntRep* y);
  65. extern int      compare(const IntRep*, const IntRep*);
  66. extern int      compare(const IntRep*, long);
  67. extern int      ucompare(const IntRep*, const IntRep*);
  68. extern int      ucompare(const IntRep*, long);
  69. extern char*    Itoa(const IntRep* x, int base = 10, int width = 0);
  70. extern IntRep*  atoIntRep(const char* s, int base = 10);
  71. extern long     Itolong(const IntRep*);
  72. extern double   Itodouble(const IntRep*);
  73. extern int      Iislong(const IntRep*);
  74. extern int      Iisdouble(const IntRep*);
  75. extern long     lg(const IntRep*);
  76.  
  77.  
  78. class Integer
  79. {
  80. protected:
  81.   IntRep*         rep;
  82. public:
  83.                   Integer();
  84.                   Integer(long);
  85.                   Integer(const Integer&);
  86.  
  87.                   ~Integer();
  88.  
  89.   void            operator =  (const Integer&);
  90.   void            operator =  (long);
  91.  
  92. // unary operations to self
  93.  
  94.   void            operator ++ ();
  95.   void            operator -- ();
  96.   void            negate();          // negate in-place
  97.   void            abs();             // absolute-value in-place
  98.   void            complement();      // bitwise complement in-place
  99.  
  100. // assignment-based operations
  101.  
  102.   void            operator += (const Integer&);
  103.   void            operator -= (const Integer&);
  104.   void            operator *= (const Integer&);
  105.   void            operator /= (const Integer&);
  106.   void            operator %= (const Integer&);
  107.   void            operator <<=(const Integer&);
  108.   void            operator >>=(const Integer&);
  109.   void            operator &= (const Integer&);
  110.   void            operator |= (const Integer&);
  111.   void            operator ^= (const Integer&);
  112.  
  113.   void            operator += (long);
  114.   void            operator -= (long);
  115.   void            operator *= (long);
  116.   void            operator /= (long);
  117.   void            operator %= (long);
  118.   void            operator <<=(long);
  119.   void            operator >>=(long);
  120.   void            operator &= (long);
  121.   void            operator |= (long);
  122.   void            operator ^= (long);
  123.  
  124. // (constructive binary operations are inlined below)
  125.  
  126. #ifdef __GNUG__
  127.   friend Integer operator <? (const Integer& x, const Integer& y); // min
  128.   friend Integer operator >? (const Integer& x, const Integer& y); // max
  129. #endif
  130.  
  131. // builtin Integer functions that must be friends
  132.  
  133.   friend long     lg (const Integer&); // floor log base 2 of abs(x)
  134.   friend double   ratio(const Integer& x, const Integer& y);
  135.                   // return x/y as a double
  136.  
  137.   friend Integer  gcd(const Integer&, const Integer&);
  138.   friend int      even(const Integer&); // true if even
  139.   friend int      odd(const Integer&); // true if odd
  140.   friend int      sign(const Integer&); // returns -1, 0, +1
  141.  
  142.   friend void     setbit(Integer& x, long b);   // set b'th bit of x
  143.   friend void     clearbit(Integer& x, long b); // clear b'th bit
  144.   friend int      testbit(const Integer& x, long b);  // return b'th bit
  145.  
  146. // procedural versions of operators
  147.  
  148.   friend void     abs(const Integer& x, Integer& dest);
  149.   friend void     negate(const Integer& x, Integer& dest);
  150.   friend void     complement(const Integer& x, Integer& dest);
  151.  
  152.   friend int      compare(const Integer&, const Integer&);  
  153.   friend int      ucompare(const Integer&, const Integer&); 
  154.   friend void     add(const Integer& x, const Integer& y, Integer& dest);
  155.   friend void     sub(const Integer& x, const Integer& y, Integer& dest);
  156.   friend void     mul(const Integer& x, const Integer& y, Integer& dest);
  157.   friend void     div(const Integer& x, const Integer& y, Integer& dest);
  158.   friend void     mod(const Integer& x, const Integer& y, Integer& dest);
  159.   friend void     divide(const Integer& x, const Integer& y, 
  160.                          Integer& q, Integer& r);
  161.   friend void     and(const Integer& x, const Integer& y, Integer& dest);
  162.   friend void     or(const Integer& x, const Integer& y, Integer& dest);
  163.   friend void     xor(const Integer& x, const Integer& y, Integer& dest);
  164.   friend void     lshift(const Integer& x, const Integer& y, Integer& dest);
  165.   friend void     rshift(const Integer& x, const Integer& y, Integer& dest);
  166.   friend void     pow(const Integer& x, const Integer& y, Integer& dest);
  167.  
  168.   friend int      compare(const Integer&, long);  
  169.   friend int      ucompare(const Integer&, long); 
  170.   friend void     add(const Integer& x, long y, Integer& dest);
  171.   friend void     sub(const Integer& x, long y, Integer& dest);
  172.   friend void     mul(const Integer& x, long y, Integer& dest);
  173.   friend void     div(const Integer& x, long y, Integer& dest);
  174.   friend void     mod(const Integer& x, long y, Integer& dest);
  175.   friend void     divide(const Integer& x, long y, Integer& q, long& r);
  176.   friend void     and(const Integer& x, long y, Integer& dest);
  177.   friend void     or(const Integer& x, long y, Integer& dest);
  178.   friend void     xor(const Integer& x, long y, Integer& dest);
  179.   friend void     lshift(const Integer& x, long y, Integer& dest);
  180.   friend void     rshift(const Integer& x, long y, Integer& dest);
  181.   friend void     pow(const Integer& x, long y, Integer& dest);
  182.  
  183.   friend int      compare(long, const Integer&);  
  184.   friend int      ucompare(long, const Integer&); 
  185.   friend void     add(long x, const Integer& y, Integer& dest);
  186.   friend void     sub(long x, const Integer& y, Integer& dest);
  187.   friend void     mul(long x, const Integer& y, Integer& dest);
  188.   friend void     and(long x, const Integer& y, Integer& dest);
  189.   friend void     or(long x, const Integer& y, Integer& dest);
  190.   friend void     xor(long x, const Integer& y, Integer& dest);
  191.  
  192. // coercion & conversion
  193.  
  194.   int             fits_in_long() const;
  195.   int             fits_in_double() const;
  196.  
  197.                   operator long() const;
  198.                   operator double() const;
  199.  
  200.   friend char*    Itoa(const Integer& x, int base = 10, int width = 0);
  201.   friend Integer  atoI(const char* s, int base = 10);
  202.   
  203.   friend istream& operator >> (istream& s, Integer& y);
  204.   friend ostream& operator << (ostream& s, const Integer& y);
  205.  
  206. // error detection
  207.  
  208.   int             initialized() const;
  209.   volatile void   error(const char* msg) const;
  210.   int             OK() const;  
  211. };
  212.  
  213.  
  214. //  (These are declared inline)
  215.  
  216.   int      operator == (const Integer&, const Integer&);
  217.   int      operator == (const Integer&, long);
  218.   int      operator != (const Integer&, const Integer&);
  219.   int      operator != (const Integer&, long);
  220.   int      operator <  (const Integer&, const Integer&);
  221.   int      operator <  (const Integer&, long);
  222.   int      operator <= (const Integer&, const Integer&);
  223.   int      operator <= (const Integer&, long);
  224.   int      operator >  (const Integer&, const Integer&);
  225.   int      operator >  (const Integer&, long);
  226.   int      operator >= (const Integer&, const Integer&);
  227.   int      operator >= (const Integer&, long);
  228.   Integer  operator -  (const Integer&);
  229.   Integer  operator ~  (const Integer&);
  230.   Integer  operator +  (const Integer&, const Integer&);
  231.   Integer  operator +  (const Integer&, long);
  232.   Integer  operator +  (long, const Integer&);
  233.   Integer  operator -  (const Integer&, const Integer&);
  234.   Integer  operator -  (const Integer&, long);
  235.   Integer  operator -  (long, const Integer&);
  236.   Integer  operator *  (const Integer&, const Integer&);
  237.   Integer  operator *  (const Integer&, long);
  238.   Integer  operator *  (long, const Integer&);
  239.   Integer  operator /  (const Integer&, const Integer&);
  240.   Integer  operator /  (const Integer&, long);
  241.   Integer  operator %  (const Integer&, const Integer&);
  242.   Integer  operator %  (const Integer&, long);
  243.   Integer  operator << (const Integer&, const Integer&);
  244.   Integer  operator << (const Integer&, long);
  245.   Integer  operator >> (const Integer&, const Integer&);
  246.   Integer  operator >> (const Integer&, long);
  247.   Integer  operator &  (const Integer&, const Integer&);
  248.   Integer  operator &  (const Integer&, long);
  249.   Integer  operator &  (long, const Integer&);
  250.   Integer  operator |  (const Integer&, const Integer&);
  251.   Integer  operator |  (const Integer&, long);
  252.   Integer  operator |  (long, const Integer&);
  253.   Integer  operator ^  (const Integer&, const Integer&);
  254.   Integer  operator ^  (const Integer&, long);
  255.   Integer  operator ^  (long, const Integer&);
  256.  
  257.   Integer  abs(const Integer&); // absolute value
  258.   Integer  sqr(const Integer&); // square
  259.  
  260.   Integer  pow(const Integer& x, const Integer& y);
  261.   Integer  pow(const Integer& x, long y);
  262.   Integer  Ipow(long x, long y); // x to the y as Integer 
  263.  
  264.  
  265. extern char*    dec(const Integer& x, int width = 0);
  266. extern char*    oct(const Integer& x, int width = 0);
  267. extern char*    hex(const Integer& x, int width = 0);
  268. extern Integer  sqrt(const Integer&); // floor of square root
  269. extern Integer  lcm(const Integer& x, const Integer& y); // least common mult
  270.   
  271.  
  272. typedef Integer IntTmp; // for backward compatibility
  273.  
  274. #if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
  275.  
  276.  
  277. inline Integer::Integer() :rep(0) {}
  278.  
  279. inline Integer::Integer(long y) :rep(Icopy_long(0, y)) {}
  280.  
  281. inline Integer::Integer(const Integer&  y) :rep(Icopy(0, y.rep)) {}
  282.  
  283. inline Integer::~Integer() { delete rep; }
  284.  
  285. inline void  Integer::operator = (const Integer&  y)
  286. {
  287.   rep = Icopy(rep, y.rep);
  288. }
  289.  
  290. inline void Integer::operator = (long y)
  291. {
  292.   rep = Icopy_long(rep, y); 
  293. }
  294.  
  295. inline Integer::operator long() const
  296. { 
  297.   return Itolong(rep);
  298. }
  299.  
  300. inline int Integer::initialized() const
  301. {
  302.   return rep != 0;
  303. }
  304.  
  305. inline int Integer::fits_in_long() const
  306. {
  307.   return Iislong(rep);
  308. }
  309.  
  310. inline Integer::operator double() const
  311. { 
  312.   return Itodouble(rep);
  313. }
  314.  
  315. inline int Integer::fits_in_double() const
  316. {
  317.   return Iisdouble(rep);
  318. }
  319.  
  320. // procedural versions
  321.  
  322. inline int compare(const Integer& x, const Integer& y)
  323. {
  324.   return compare(x.rep, y.rep);
  325. }
  326.  
  327. inline int ucompare(const Integer& x, const Integer& y)
  328. {
  329.   return ucompare(x.rep, y.rep);
  330. }
  331.  
  332. inline int compare(const Integer& x, long y)
  333. {
  334.   return compare(x.rep, y);
  335. }
  336.  
  337. inline int ucompare(const Integer& x, long y)
  338. {
  339.   return ucompare(x.rep, y);
  340. }
  341.  
  342. inline int compare(long x, const Integer& y)
  343. {
  344.   return -compare(y.rep, x);
  345. }
  346.  
  347. inline int ucompare(long x, const Integer& y)
  348. {
  349.   return -ucompare(y.rep, x);
  350. }
  351.  
  352. inline void  add(const Integer& x, const Integer& y, Integer& dest)
  353. {
  354.   dest.rep = add(x.rep, 0, y.rep, 0, dest.rep);
  355. }
  356.  
  357. inline void  sub(const Integer& x, const Integer& y, Integer& dest)
  358. {
  359.   dest.rep = add(x.rep, 0, y.rep, 1, dest.rep);
  360. }
  361.  
  362. inline void  mul(const Integer& x, const Integer& y, Integer& dest)
  363. {
  364.   dest.rep = multiply(x.rep, y.rep, dest.rep);
  365. }
  366.  
  367. inline void  div(const Integer& x, const Integer& y, Integer& dest)
  368. {
  369.   dest.rep = div(x.rep, y.rep, dest.rep);
  370. }
  371.  
  372. inline void  mod(const Integer& x, const Integer& y, Integer& dest)
  373. {
  374.   dest.rep = mod(x.rep, y.rep, dest.rep);
  375. }
  376.  
  377. inline void  and(const Integer& x, const Integer& y, Integer& dest)
  378. {
  379.   dest.rep = bitop(x.rep, y.rep, dest.rep, '&');
  380. }
  381.  
  382. inline void  or(const Integer& x, const Integer& y, Integer& dest)
  383. {
  384.   dest.rep = bitop(x.rep, y.rep, dest.rep, '|');
  385. }
  386.  
  387. inline void  xor(const Integer& x, const Integer& y, Integer& dest)
  388. {
  389.   dest.rep = bitop(x.rep, y.rep, dest.rep, '^');
  390. }
  391.  
  392. inline void  lshift(const Integer& x, const Integer& y, Integer& dest)
  393. {
  394.   dest.rep = lshift(x.rep, y.rep, 0, dest.rep);
  395. }
  396.  
  397. inline void  rshift(const Integer& x, const Integer& y, Integer& dest)
  398. {
  399.   dest.rep = lshift(x.rep, y.rep, 1, dest.rep);
  400. }
  401.  
  402. inline void  pow(const Integer& x, const Integer& y, Integer& dest)
  403. {
  404.   dest.rep = power(x.rep, long(y), dest.rep); // not incorrect
  405. }
  406.  
  407. inline void  add(const Integer& x, long y, Integer& dest)
  408. {
  409.   dest.rep = add(x.rep, 0, y, dest.rep);
  410. }
  411.  
  412. inline void  sub(const Integer& x, long y, Integer& dest)
  413. {
  414.   dest.rep = add(x.rep, 0, -y, dest.rep);
  415. }
  416.  
  417. inline void  mul(const Integer& x, long y, Integer& dest)
  418. {
  419.   dest.rep = multiply(x.rep, y, dest.rep);
  420. }
  421.  
  422. inline void  div(const Integer& x, long y, Integer& dest)
  423. {
  424.   dest.rep = div(x.rep, y, dest.rep);
  425. }
  426.  
  427. inline void  mod(const Integer& x, long y, Integer& dest)
  428. {
  429.   dest.rep = mod(x.rep, y, dest.rep);
  430. }
  431.  
  432. inline void  and(const Integer& x, long y, Integer& dest)
  433. {
  434.   dest.rep = bitop(x.rep, y, dest.rep, '&');
  435. }
  436.  
  437. inline void  or(const Integer& x, long y, Integer& dest)
  438. {
  439.   dest.rep = bitop(x.rep, y, dest.rep, '|');
  440. }
  441.  
  442. inline void  xor(const Integer& x, long y, Integer& dest)
  443. {
  444.   dest.rep = bitop(x.rep, y, dest.rep, '^');
  445. }
  446.  
  447. inline void  lshift(const Integer& x, long y, Integer& dest)
  448. {
  449.   dest.rep = lshift(x.rep, y, dest.rep);
  450. }
  451.  
  452. inline void  rshift(const Integer& x, long y, Integer& dest)
  453. {
  454.   dest.rep = lshift(x.rep, -y, dest.rep);
  455. }
  456.  
  457. inline void  pow(const Integer& x, long y, Integer& dest)
  458. {
  459.   dest.rep = power(x.rep, y, dest.rep);
  460. }
  461.  
  462. inline void abs(const Integer& x, Integer& dest)
  463. {
  464.   dest.rep = abs(x.rep, dest.rep);
  465. }
  466.  
  467. inline void negate(const Integer& x, Integer& dest)
  468. {
  469.   dest.rep = negate(x.rep, dest.rep);
  470. }
  471.  
  472. inline void complement(const Integer& x, Integer& dest)
  473. {
  474.   dest.rep = compl(x.rep, dest.rep);
  475. }
  476.  
  477. inline void  add(long x, const Integer& y, Integer& dest)
  478. {
  479.   dest.rep = add(y.rep, 0, x, dest.rep);
  480. }
  481.  
  482. inline void  sub(long x, const Integer& y, Integer& dest)
  483. {
  484.   dest.rep = add(y.rep, 1, x, dest.rep);
  485. }
  486.  
  487. inline void  mul(long x, const Integer& y, Integer& dest)
  488. {
  489.   dest.rep = multiply(y.rep, x, dest.rep);
  490. }
  491.  
  492. inline void  and(long x, const Integer& y, Integer& dest)
  493. {
  494.   dest.rep = bitop(y.rep, x, dest.rep, '&');
  495. }
  496.  
  497. inline void  or(long x, const Integer& y, Integer& dest)
  498. {
  499.   dest.rep = bitop(y.rep, x, dest.rep, '|');
  500. }
  501.  
  502. inline void  xor(long x, const Integer& y, Integer& dest)
  503. {
  504.   dest.rep = bitop(y.rep, x, dest.rep, '^');
  505. }
  506.  
  507.  
  508. // operator versions
  509.  
  510. inline int operator == (const Integer&  x, const Integer&  y)
  511. {
  512.   return compare(x, y) == 0; 
  513. }
  514.  
  515. inline int operator == (const Integer&  x, long y)
  516. {
  517.   return compare(x, y) == 0; 
  518. }
  519.  
  520. inline int operator != (const Integer&  x, const Integer&  y)
  521. {
  522.   return compare(x, y) != 0; 
  523. }
  524.  
  525. inline int operator != (const Integer&  x, long y)
  526. {
  527.   return compare(x, y) != 0; 
  528. }
  529.  
  530. inline int operator <  (const Integer&  x, const Integer&  y)
  531. {
  532.   return compare(x, y) <  0; 
  533. }
  534.  
  535. inline int operator <  (const Integer&  x, long y)
  536. {
  537.   return compare(x, y) <  0; 
  538. }
  539.  
  540. inline int operator <= (const Integer&  x, const Integer&  y)
  541. {
  542.   return compare(x, y) <= 0; 
  543. }
  544.  
  545. inline int operator <= (const Integer&  x, long y)
  546. {
  547.   return compare(x, y) <= 0; 
  548. }
  549.  
  550. inline int operator >  (const Integer&  x, const Integer&  y)
  551. {
  552.   return compare(x, y) >  0; 
  553. }
  554.  
  555. inline int operator >  (const Integer&  x, long y)
  556. {
  557.   return compare(x, y) >  0; 
  558. }
  559.  
  560. inline int operator >= (const Integer&  x, const Integer&  y)
  561. {
  562.   return compare(x, y) >= 0; 
  563. }
  564.  
  565. inline int operator >= (const Integer&  x, long y)
  566. {
  567.   return compare(x, y) >= 0; 
  568. }
  569.  
  570.  
  571. inline void  Integer::operator += (const Integer& y)
  572. {
  573.   add(*this, y, *this);
  574. }
  575.  
  576. inline void  Integer::operator += (long y)
  577. {
  578.   add(*this, y, *this);
  579. }
  580.  
  581. inline void Integer::operator ++ ()
  582. {
  583.   add(*this, 1, *this);
  584. }
  585.  
  586.  
  587. inline void  Integer::operator -= (const Integer& y)
  588. {
  589.   sub(*this, y, *this);
  590. }
  591.  
  592. inline void  Integer::operator -= (long y)
  593. {
  594.   sub(*this, y, *this);
  595. }
  596.  
  597. inline void Integer::operator -- ()
  598. {
  599.   add(*this, -1, *this);
  600. }
  601.  
  602.  
  603.  
  604. inline void Integer::operator *= (const Integer& y)
  605. {
  606.   mul(*this, y, *this);
  607. }
  608.  
  609. inline void Integer::operator *= (long y)
  610. {
  611.   mul(*this, y, *this);
  612. }
  613.  
  614.  
  615. inline void  Integer::operator &= (const Integer& y)
  616. {
  617.   and(*this, y, *this);
  618. }
  619.  
  620. inline void  Integer::operator &= (long y)
  621. {
  622.   and(*this, y, *this);
  623. }
  624.  
  625. inline void  Integer::operator |= (const Integer& y)
  626. {
  627.   or(*this, y, *this);
  628. }
  629.  
  630. inline void  Integer::operator |= (long y)
  631. {
  632.   or(*this, y, *this);
  633. }
  634.  
  635.  
  636. inline void  Integer::operator ^= (const Integer& y)
  637. {
  638.   xor(*this, y, *this);
  639. }
  640.  
  641. inline void  Integer::operator ^= (long y)
  642. {
  643.   xor(*this, y, *this);
  644. }
  645.  
  646.  
  647.  
  648. inline void Integer::operator /= (const Integer& y)
  649. {
  650.   div(*this, y, *this);
  651. }
  652.  
  653. inline void Integer::operator /= (long y)
  654. {
  655.   div(*this, y, *this);
  656. }
  657.  
  658.  
  659. inline void Integer::operator %= (const Integer& y)
  660. {
  661.   mod(*this, y, *this);
  662. }
  663.  
  664. inline void Integer::operator %= (long y)
  665. {
  666.   mod(*this, y, *this);
  667. }
  668.  
  669.  
  670. inline void Integer::operator <<= (const Integer&  y)
  671. {
  672.   lshift(*this, y, *this);
  673. }
  674.  
  675. inline void Integer::operator <<= (long  y)
  676. {
  677.   lshift(*this, y, *this);
  678. }
  679.  
  680.  
  681. inline void Integer::operator >>= (const Integer&  y)
  682. {
  683.   rshift(*this, y, *this);
  684. }
  685.  
  686. inline void  Integer::operator >>= (long y)
  687. {
  688.   rshift(*this, y, *this);
  689. }
  690.  
  691. #ifdef __GNUG__
  692. inline Integer operator <? (const Integer& x, const Integer& y)
  693. {
  694.   return (compare(x.rep, y.rep) <= 0) ? x : y;
  695. }
  696.  
  697. inline Integer operator >? (const Integer& x, const Integer& y)
  698. {
  699.   return (compare(x.rep, y.rep) >= 0)?  x : y;
  700. }
  701. #endif
  702.  
  703.  
  704. inline void Integer::abs()
  705. {
  706.   ::abs(*this, *this);
  707. }
  708.  
  709. inline void Integer::negate()
  710. {
  711.   ::negate(*this, *this);
  712. }
  713.  
  714.  
  715. inline void Integer::complement()
  716. {
  717.   ::complement(*this, *this);
  718. }
  719.  
  720.  
  721. inline int sign(const Integer& x)
  722. {
  723.   return (x.rep->len == 0) ? 0 : ( (x.rep->sgn == 1) ? 1 : -1 );
  724. }
  725.  
  726. inline int even(const Integer& y)
  727. {
  728.   return y.rep->len == 0 || !(y.rep->s[0] & 1);
  729. }
  730.  
  731. inline int odd(const Integer& y)
  732. {
  733.   return y.rep->len > 0 && (y.rep->s[0] & 1);
  734. }
  735.  
  736. inline char* Itoa(const Integer& y, int base, int width)
  737. {
  738.   return Itoa(y.rep, base, width);
  739. }
  740.  
  741.  
  742. inline ostream& operator << (ostream& s, const Integer& y)
  743. {
  744.   return s << Itoa(y.rep);
  745. }
  746.  
  747. inline long lg(const Integer& x) 
  748. {
  749.   return lg(x.rep);
  750. }
  751.  
  752. // constructive operations 
  753.  
  754. #if defined(__GNUG__) && !defined(NO_NRV)
  755.  
  756. inline Integer  operator +  (const Integer& x, const Integer& y) return r
  757. {
  758.   add(x, y, r);
  759. }
  760.  
  761. inline Integer  operator +  (const Integer& x, long y) return r
  762. {
  763.   add(x, y, r);
  764. }
  765.  
  766. inline Integer  operator +  (long  x, const Integer& y) return r
  767. {
  768.   add(x, y, r);
  769. }
  770.  
  771. inline Integer  operator -  (const Integer& x, const Integer& y) return r
  772. {
  773.   sub(x, y, r);
  774. }
  775.  
  776. inline Integer  operator -  (const Integer& x, long y) return r
  777. {
  778.   sub(x, y, r);
  779. }
  780.  
  781. inline Integer  operator -  (long  x, const Integer& y) return r
  782. {
  783.   sub(x, y, r);
  784. }
  785.  
  786. inline Integer  operator *  (const Integer& x, const Integer& y) return r
  787. {
  788.   mul(x, y, r);
  789. }
  790.  
  791. inline Integer  operator *  (const Integer& x, long y) return r
  792. {
  793.   mul(x, y, r);
  794. }
  795.  
  796. inline Integer  operator *  (long  x, const Integer& y) return r
  797. {
  798.   mul(x, y, r);
  799. }
  800.  
  801. inline Integer sqr(const Integer& x) return r
  802. {
  803.   mul(x, x, r);
  804. }
  805.  
  806. inline Integer  operator &  (const Integer& x, const Integer& y) return r
  807. {
  808.   and(x, y, r);
  809. }
  810.  
  811. inline Integer  operator &  (const Integer& x, long y) return r
  812. {
  813.   and(x, y, r);
  814. }
  815.  
  816. inline Integer  operator &  (long  x, const Integer& y) return r
  817. {
  818.   and(x, y, r);
  819. }
  820.  
  821. inline Integer  operator |  (const Integer& x, const Integer& y) return r
  822. {
  823.   or(x, y, r);
  824. }
  825.  
  826. inline Integer  operator |  (const Integer& x, long y) return r
  827. {
  828.   or(x, y, r);
  829. }
  830.  
  831. inline Integer  operator |  (long  x, const Integer& y) return r
  832. {
  833.   or(x, y, r);
  834. }
  835.  
  836. inline Integer  operator ^  (const Integer& x, const Integer& y) return r
  837. {
  838.   xor(x, y, r);
  839. }
  840.  
  841. inline Integer  operator ^  (const Integer& x, long y) return r
  842. {
  843.   xor(x, y, r);
  844. }
  845.  
  846. inline Integer  operator ^  (long  x, const Integer& y) return r
  847. {
  848.   xor(x, y, r);
  849. }
  850.  
  851. inline Integer  operator /  (const Integer& x, const Integer& y) return r
  852. {
  853.   div(x, y, r);
  854. }
  855.  
  856. inline Integer operator /  (const Integer& x, long y) return r
  857. {
  858.   div(x, y, r);
  859. }
  860.  
  861. inline Integer operator %  (const Integer& x, const Integer& y) return r
  862. {
  863.   mod(x, y, r);
  864. }
  865.  
  866. inline Integer operator %  (const Integer& x, long y) return r
  867. {
  868.   mod(x, y, r);
  869. }
  870.  
  871. inline Integer operator <<  (const Integer& x, const Integer& y) return r
  872. {
  873.   lshift(x, y, r);
  874. }
  875.  
  876. inline Integer operator <<  (const Integer& x, long y) return r
  877. {
  878.   lshift(x, y, r);
  879. }
  880.  
  881. inline Integer operator >>  (const Integer& x, const Integer& y) return r;
  882. {
  883.   rshift(x, y, r);
  884. }
  885.  
  886. inline Integer operator >>  (const Integer& x, long y) return r
  887. {
  888.   rshift(x, y, r);
  889. }
  890.  
  891. inline Integer pow(const Integer& x, long y) return r
  892. {
  893.   pow(x, y, r);
  894. }
  895.  
  896. inline Integer Ipow(long x, long y) return r(x)
  897. {
  898.   pow(r, y, r);
  899. }
  900.  
  901. inline Integer pow(const Integer& x, const Integer& y) return r
  902. {
  903.   pow(x, y, r);
  904. }
  905.  
  906.  
  907.  
  908. inline Integer abs(const Integer& x) return r
  909. {
  910.   abs(x, r);
  911. }
  912.  
  913. inline Integer operator - (const Integer& x) return r
  914. {
  915.   negate(x, r);
  916. }
  917.  
  918. inline Integer operator ~ (const Integer& x) return r
  919. {
  920.   complement(x, r);
  921. }
  922.  
  923. inline Integer  atoI(const char* s, int base) return r
  924. {
  925.   r.rep = atoIntRep(s, base);
  926. }
  927.  
  928. inline Integer  gcd(const Integer& x, const Integer& y) return r
  929. {
  930.   r.rep = gcd(x.rep, y.rep);
  931. }
  932.  
  933. #else /* NO_NRV */
  934.  
  935. inline Integer  operator +  (const Integer& x, const Integer& y) 
  936. {
  937.   Integer r; add(x, y, r); return r;
  938. }
  939.  
  940. inline Integer  operator +  (const Integer& x, long y) 
  941. {
  942.   Integer r; add(x, y, r); return r;
  943. }
  944.  
  945. inline Integer  operator +  (long  x, const Integer& y) 
  946. {
  947.   Integer r; add(x, y, r); return r;
  948. }
  949.  
  950. inline Integer  operator -  (const Integer& x, const Integer& y) 
  951. {
  952.   Integer r; sub(x, y, r); return r;
  953. }
  954.  
  955. inline Integer  operator -  (const Integer& x, long y) 
  956. {
  957.   Integer r; sub(x, y, r); return r;
  958. }
  959.  
  960. inline Integer  operator -  (long  x, const Integer& y) 
  961. {
  962.   Integer r; sub(x, y, r); return r;
  963. }
  964.  
  965. inline Integer  operator *  (const Integer& x, const Integer& y) 
  966. {
  967.   Integer r; mul(x, y, r); return r;
  968. }
  969.  
  970. inline Integer  operator *  (const Integer& x, long y) 
  971. {
  972.   Integer r; mul(x, y, r); return r;
  973. }
  974.  
  975. inline Integer  operator *  (long  x, const Integer& y) 
  976. {
  977.   Integer r; mul(x, y, r); return r;
  978. }
  979.  
  980. inline Integer sqr(const Integer& x) 
  981. {
  982.   Integer r; mul(x, x, r); return r;
  983. }
  984.  
  985. inline Integer  operator &  (const Integer& x, const Integer& y) 
  986. {
  987.   Integer r; and(x, y, r); return r;
  988. }
  989.  
  990. inline Integer  operator &  (const Integer& x, long y) 
  991. {
  992.   Integer r; and(x, y, r); return r;
  993. }
  994.  
  995. inline Integer  operator &  (long  x, const Integer& y) 
  996. {
  997.   Integer r; and(x, y, r); return r;
  998. }
  999.  
  1000. inline Integer  operator |  (const Integer& x, const Integer& y) 
  1001. {
  1002.   Integer r; or(x, y, r); return r;
  1003. }
  1004.  
  1005. inline Integer  operator |  (const Integer& x, long y) 
  1006. {
  1007.   Integer r; or(x, y, r); return r;
  1008. }
  1009.  
  1010. inline Integer  operator |  (long  x, const Integer& y) 
  1011. {
  1012.   Integer r; or(x, y, r); return r;
  1013. }
  1014.  
  1015. inline Integer  operator ^  (const Integer& x, const Integer& y) 
  1016. {
  1017.   Integer r; xor(x, y, r); return r;
  1018. }
  1019.  
  1020. inline Integer  operator ^  (const Integer& x, long y) 
  1021. {
  1022.   Integer r; xor(x, y, r); return r;
  1023. }
  1024.  
  1025. inline Integer  operator ^  (long  x, const Integer& y) 
  1026. {
  1027.   Integer r; xor(x, y, r); return r;
  1028. }
  1029.  
  1030. inline Integer  operator /  (const Integer& x, const Integer& y) 
  1031. {
  1032.   Integer r; div(x, y, r); return r;
  1033. }
  1034.  
  1035. inline Integer operator /  (const Integer& x, long y) 
  1036. {
  1037.   Integer r; div(x, y, r); return r;
  1038. }
  1039.  
  1040. inline Integer operator %  (const Integer& x, const Integer& y) 
  1041. {
  1042.   Integer r; mod(x, y, r); return r;
  1043. }
  1044.  
  1045. inline Integer operator %  (const Integer& x, long y) 
  1046. {
  1047.   Integer r; mod(x, y, r); return r;
  1048. }
  1049.  
  1050. inline Integer operator <<  (const Integer& x, const Integer& y) 
  1051. {
  1052.   Integer r; lshift(x, y, r); return r;
  1053. }
  1054.  
  1055. inline Integer operator <<  (const Integer& x, long y) 
  1056. {
  1057.   Integer r; lshift(x, y, r); return r;
  1058. }
  1059.  
  1060. inline Integer operator >>  (const Integer& x, const Integer& y) 
  1061. {
  1062.   Integer r; rshift(x, y, r); return r;
  1063. }
  1064.  
  1065. inline Integer operator >>  (const Integer& x, long y) 
  1066. {
  1067.   Integer r; rshift(x, y, r); return r;
  1068. }
  1069.  
  1070. inline Integer pow(const Integer& x, long y) 
  1071. {
  1072.   Integer r; pow(x, y, r); return r;
  1073. }
  1074.  
  1075. inline Integer Ipow(long x, long y) 
  1076. {
  1077.   Integer r(x); pow(r, y, r); return r;
  1078. }
  1079.  
  1080. inline Integer pow(const Integer& x, const Integer& y) 
  1081. {
  1082.   Integer r; pow(x, y, r); return r;
  1083. }
  1084.  
  1085.  
  1086.  
  1087. inline Integer abs(const Integer& x) 
  1088. {
  1089.   Integer r; abs(x, r); return r;
  1090. }
  1091.  
  1092. inline Integer operator - (const Integer& x) 
  1093. {
  1094.   Integer r; negate(x, r); return r;
  1095. }
  1096.  
  1097. inline Integer operator ~ (const Integer& x) 
  1098. {
  1099.   Integer r; complement(x, r); return r;
  1100. }
  1101.  
  1102. inline Integer  atoI(const char* s, int base) 
  1103. {
  1104.   Integer r; r.rep = atoIntRep(s, base); return r;
  1105. }
  1106.  
  1107. inline Integer  gcd(const Integer& x, const Integer& y) 
  1108. {
  1109.   Integer r; r.rep = gcd(x.rep, y.rep); return r;
  1110. }
  1111.  
  1112. #endif
  1113. #endif
  1114. #endif
  1115.