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