1 2 /* 3 * Integer - Implements an integer of arbitrary size 4 * Copyright (c) 2005-2007 by Mattias Hultgren <tilda_o_tize@hotmail.com> 5 * 6 * 7 * This program is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License as published by 9 * the Free Software Foundation; version 2 of the License. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public 17 * License along with this program; if not, write to the Free Software 18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 19 */ 20 21 #ifndef INTEGER_H_ 22 #define INTEGER_H_ 23 24 #include "vartypes.h" 25 #include "utf8_string.h" 26 27 28 #define INTEGER_H_VERSION "v7" 29 #define INTEGER_H_DATE "2005-04 - 2006-10" 30 31 32 class Integer 33 { 34 private: 35 uint32 size, used; 36 uint32 buf[2]; 37 uint32 *data; 38 bool negative; 39 40 public: 41 Integer(); 42 Integer( const Integer &src ) throw(error_obj); 43 Integer(int32 src); 44 Integer(int64 src); 45 Integer(floatx src) throw(error_obj); 46 Integer & operator=(floatx val) throw(error_obj); 47 operator floatx(void); 48 ~Integer(); 49 50 void enlarge_to( uint32 new_size ) throw(error_obj); 51 52 void extract( Integer *dest, uint32 start, uint32 stop ) const throw(error_obj); 53 get_used(void)54 uint32 get_used(void) const { return used; } get_data(void)55 const uint32* get_data(void) const { return data; } 56 57 58 // *_data are low level functions, and should not be called unless 59 // you are sure what you're doing 60 void add_data( const Integer &nr ) throw(error_obj); 61 void add_data_uint32_shifted( const Integer &nr, uint32 shift) throw(error_obj); // this += nr * 2^(32*shift) 62 // sub_data: this must be larger than nr....no checking for that will be done 63 void sub_data( const Integer &nr ); // this -= nr 64 void sub_data_reverse( const Integer &nr ); // this = nr - this 65 void mul_data( const Integer &factor, Integer *dest ) const throw(error_obj); 66 67 void add( const Integer &val ) throw(error_obj); 68 void sub( const Integer &val ) throw(error_obj); 69 void mul( const Integer &factor, Integer *dest ) const throw(error_obj); 70 71 void mul_by_2(void) throw(error_obj); 72 void mul_by_2_pow_32(uint32 n=1) throw(error_obj); 73 void div_by_2(void) throw(error_obj); 74 void div_by_2_pow_32(void) throw(error_obj); 75 void divide( const Integer ÷r, Integer *ans, Integer *rest ) const throw(error_obj); 76 77 // special function, used by divide *this -= nr * 2^(32*shift) * mult 78 // this must be larger than nr * 2^(32*shift) * mult 79 void sub_uint32_mult_shifted( uint32 mult, const Integer &nr, uint32 shift ); 80 81 // special function, used by divide *this += nr * 2^(32*shift) 82 // this must be large enough and the data should be zero filled 83 void add_uint32_shifted( uint32 nr, uint32 shift ) throw(error_obj); 84 85 uint32 count_used_bits(void) const; 86 87 void set_bit( uint32 bit ) throw(error_obj); 88 void clear_bit( uint32 bit ) throw(error_obj); 89 90 bool check_bit( uint32 bit ) const throw(error_obj); 91 92 Integer operator+(const Integer &val) const throw(error_obj); 93 Integer operator-(const Integer &val) const throw(error_obj); throw(error_obj)94 inline Integer operator*(const Integer &val) const throw(error_obj) { Integer ans; mul(val, &ans); return ans; } 95 inline Integer operator/(const Integer &val) const throw(error_obj) { Integer ans; divide( val, &ans, 0 ); return ans; } 96 inline Integer operator%(const Integer &val) const throw(error_obj) { Integer rest; divide( val, 0, &rest ); return rest; } 97 swap(Integer & nr)98 inline void swap( Integer &nr ) 99 { 100 bool t; 101 uint32 t2, *t3; 102 103 t = negative; 104 negative = nr.negative; 105 nr.negative = t; 106 107 for( int i=0; i<2; i++ ) 108 { 109 t2 = nr.buf[i]; 110 nr.buf[i] = buf[i]; 111 buf[i] = t2; 112 } 113 114 t2 = size; 115 size = nr.size; 116 nr.size = t2; 117 118 t2 = used; 119 used = nr.used; 120 nr.used = t2; 121 122 t3 = (data==buf) ? nr.buf : data; 123 data = (nr.data==nr.buf) ? buf : nr.data; 124 nr.data = t3; 125 } 126 127 Integer & operator=(const Integer &val) throw(error_obj); 128 Integer & operator=(int32 val); 129 Integer & operator=(int64 val); 130 inline Integer & operator+=(const Integer &val) throw(error_obj) { add( val ); return *this; } 131 inline Integer & operator-=(const Integer &val) throw(error_obj) { sub( val ); return *this; } throw(error_obj)132 inline Integer & operator*=(const Integer &val) throw(error_obj) { *this = *this * val; return *this; } 133 inline Integer & operator/=(const Integer &val) throw(error_obj) { *this = *this / val; return *this; } 134 inline Integer & operator%=(const Integer &val) throw(error_obj) { *this = *this % val; return *this; } 135 136 bool operator==(const Integer &val) const; 137 inline bool operator!=(const Integer &val) const { return !(*this == val); } 138 bool operator==(int32 val) const; 139 inline bool operator!=(int32 val) const { return !(*this == val); } 140 141 bool operator<(const Integer &val) const; 142 bool operator>(const Integer &val) const; 143 inline bool operator<=(const Integer &val) const { return !(*this > val); } 144 inline bool operator>=(const Integer &val) const { return !(*this < val); } 145 bool operator<(int32 val) const; 146 bool operator>(int32 val) const; 147 inline bool operator<=(int32 val) const { return !(*this > val); } 148 inline bool operator>=(int32 val) const { return !(*this < val); } 149 150 // -1 this is smaller 151 // 0 they are equal 152 // 1 this is bigger 153 int compare_abs_value( const Integer &val ) const; 154 155 // same as compare_abs_value, but val is temporary shifted left shift-steps 156 // compare_abs_value_shifted( val, shift ) 157 // equals 158 // val.mul_by_2_pow_32( shift ); 159 // compare_abs_value( val ); 160 // val.div_by_2_pow_32( shift ); 161 int compare_abs_value_shifted( const Integer &val, uint32 shift ) const; 162 163 Integer & operator++(void) throw(error_obj); 164 inline Integer & operator++(int) throw(error_obj) { return ++ *this; } 165 Integer & operator--(void) throw(error_obj); 166 inline Integer & operator--(int) throw(error_obj) { return -- *this; } 167 168 friend Integer operator-(const Integer &val) throw(error_obj); 169 negate(void)170 inline void negate(void) { negative = !negative; } isNegative(void)171 inline bool isNegative(void) const { return negative; } isZero(void)172 inline bool isZero(void) const { return (used == 0); } 173 174 operator int64(void); 175 176 void append_to_string( utf8_string &str, uint32 nrofdigits=0 ) const throw(error_obj); 177 178 void power( Integer nr, Integer *dest ) const throw(error_obj); 179 180 void faculty(void) throw(error_obj); 181 182 void perm( Integer n, Integer k ) throw(error_obj); 183 void comb( const Integer &up, Integer down ) throw(error_obj); 184 185 186 friend Integer iSqrt( const Integer &var ) throw(error_obj); 187 188 // gcd - greatest common divisior (using Euklides algorithm) 189 // if any of nr1 & nr2 is zero the return value is zero also 190 friend Integer gcd( Integer nr1, Integer nr2 ) throw(error_obj); 191 192 // lcm - least common multiple ( (nr1*nr2)/gcd(nr1,nr2) ) 193 // if(gcd(nr1,nr2) == 0) the return value is zero also 194 friend Integer lcm( const Integer &nr1, const Integer &nr2 ) throw(error_obj); 195 }; 196 197 198 // dest = [ (n^p) mod m ] 199 void powMod( Integer *dest, Integer n, Integer p, const Integer &m ) throw(error_obj); 200 201 202 #endif // INTEGER_H_ 203