1 // -*- C++ -*- 2 //============================================================================================== 3 // 4 // This file is part of LiDIA --- a library for computational number theory 5 // 6 // Copyright (c) 1994--2001 the LiDIA Group. All rights reserved. 7 // 8 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/ 9 // 10 //---------------------------------------------------------------------------------------------- 11 // 12 // $Id$ 13 // 14 // Author : Markus Maurer (MM) 15 // Changes : See CVS log 16 // 17 //============================================================================================== 18 19 20 #ifndef LIDIA_QUADRATIC_NUMBER_STANDARD_H_GUARD_ 21 #define LIDIA_QUADRATIC_NUMBER_STANDARD_H_GUARD_ 22 23 24 #ifndef LIDIA_BIGINT_H_GUARD_ 25 # include "LiDIA/bigint.h" 26 #endif 27 #ifndef LIDIA_BIGRATIONAL_H_GUARD_ 28 # include "LiDIA/bigrational.h" 29 #endif 30 #ifndef LIDIA_XBIGFLOAT_H_GUARD_ 31 # include "LiDIA/xbigfloat.h" 32 #endif 33 34 35 36 #ifdef LIDIA_NAMESPACE 37 namespace LiDIA { 38 # define IN_NAMESPACE_LIDIA 39 #endif 40 41 42 43 class qo_node; 44 class quadratic_order; 45 46 47 48 // Remaining includes after class definition. 49 // Necessary, because quadratic_number_standard .h needs 50 // quadratic order.h and vice versa. 51 52 // 53 // A quadratic number z \in Q(sqrt(Delta)) is represented as 54 // 55 // z = (a + b sqrt(Delta))/d 56 // 57 // where a, b, d \in \Z, d > 0, and Delta is a quadratic discriminant. 58 // Delta must not be a square in Q. 59 // 60 // gcd(a, b, d) == 1. 61 // 62 63 class quadratic_number_standard 64 { 65 private: 66 67 bigint a, b, d; 68 qo_node *QO; 69 70 static char output_mode; 71 72 static const char WITHOUT_DISCRIMINANT; 73 static const char WITH_DISCRIMINANT; 74 75 void check_and_normalize(char *s); 76 77 78 public: 79 80 // 81 // constructors / destructor 82 // 83 84 quadratic_number_standard (); 85 quadratic_number_standard (const quadratic_number_standard & x); 86 ~quadratic_number_standard (); 87 88 // 89 // access 90 // 91 92 bigint get_discriminant () const; 93 const quadratic_order & which_order() const; 94 const quadratic_order & get_order() const; 95 96 void get (bigint & pa, bigint & pb, bigint & pd); 97 98 const bigint & get_a () const; 99 const bigint & get_b () const; 100 const bigint & get_d () const; 101 102 // 103 // assignments 104 // 105 106 quadratic_number_standard & operator = (const quadratic_number_standard & x); 107 108 void assign_order(const quadratic_order & QO2); 109 void set_order(const quadratic_order & QO2); 110 111 void set (const bigint & pa, const bigint & pb, const bigint & pd); 112 void assign (const bigint & pa, const bigint & pb, const bigint & pd); 113 114 void assign_one (); 115 void assign_one (const quadratic_order & QO2); 116 void assign_zero(); 117 void assign_zero (const quadratic_order & QO2); 118 119 void assign (const quadratic_number_standard & x); 120 121 void randomize(); 122 123 friend void swap (quadratic_number_standard & x, quadratic_number_standard & y); 124 125 // 126 // comparisons 127 // 128 129 friend bool operator == (const quadratic_number_standard & x, 130 const quadratic_number_standard & y); 131 132 friend bool operator == (const bigint & n, 133 const quadratic_number_standard & x); 134 135 friend bool operator == (const quadratic_number_standard & x, 136 const bigint & n); 137 138 friend bool operator == (const bigrational & n, 139 const quadratic_number_standard & x); 140 141 friend bool operator == (const quadratic_number_standard & x, 142 const bigrational & n); 143 144 friend bool operator != (const quadratic_number_standard & x, 145 const quadratic_number_standard & y); 146 147 friend bool operator != (const bigint & n, 148 const quadratic_number_standard & x); 149 150 friend bool operator != (const quadratic_number_standard & x, 151 const bigint & n); 152 153 friend bool operator != (const bigrational & n, 154 const quadratic_number_standard & x); 155 156 friend bool operator != (const quadratic_number_standard & x, 157 const bigrational & n); 158 159 bool is_one() const; 160 bool is_zero() const; 161 162 bool is_positive() const; 163 bool is_negative() const; 164 165 bool is_rational_number () const; 166 bool is_integer () const; 167 bool is_unit () const; 168 169 // 170 // arithmetic 171 // 172 173 void negate (); 174 void invert (); 175 176 friend void negate (quadratic_number_standard & c, 177 const quadratic_number_standard & a); 178 179 friend void add (quadratic_number_standard & c, 180 const quadratic_number_standard & a, 181 const quadratic_number_standard & b); 182 183 friend void subtract (quadratic_number_standard & c, 184 const quadratic_number_standard & a, 185 const quadratic_number_standard & b); 186 187 friend void multiply (quadratic_number_standard & c, 188 const quadratic_number_standard & a, 189 const quadratic_number_standard & b); 190 191 friend void multiply (quadratic_number_standard & c, 192 const bigint & n, 193 const quadratic_number_standard & a); 194 195 friend void multiply (quadratic_number_standard & c, 196 const quadratic_number_standard & a, 197 const bigint & n); 198 199 friend void multiply (quadratic_number_standard & c, 200 const bigrational & n, 201 const quadratic_number_standard & a); 202 203 friend void multiply (quadratic_number_standard & c, 204 const quadratic_number_standard & a, 205 const bigrational & n); 206 207 void multiply_by_denominator(); 208 209 friend void inverse (quadratic_number_standard & x, 210 const quadratic_number_standard & y); 211 212 friend void divide (quadratic_number_standard & c, 213 const quadratic_number_standard & a, 214 const quadratic_number_standard & b); 215 216 friend void divide (quadratic_number_standard & c, 217 const bigrational & n, 218 const quadratic_number_standard & a); 219 220 friend void divide (quadratic_number_standard & c, 221 const quadratic_number_standard & a, 222 const bigrational & n); 223 224 friend void square (quadratic_number_standard & c, 225 const quadratic_number_standard & a); 226 227 friend void power (quadratic_number_standard & c, 228 const quadratic_number_standard & a, 229 unsigned long e); 230 231 friend void power (quadratic_number_standard & c, 232 const quadratic_number_standard & a, 233 const bigint & e); 234 235 friend quadratic_number_standard 236 operator - (const quadratic_number_standard & a); 237 238 friend 239 quadratic_number_standard operator + (const quadratic_number_standard & a, 240 const quadratic_number_standard & b); 241 friend 242 quadratic_number_standard operator - (const quadratic_number_standard & a, 243 const quadratic_number_standard & b); 244 friend 245 quadratic_number_standard operator * (const quadratic_number_standard & a, 246 const quadratic_number_standard & b); 247 friend 248 quadratic_number_standard operator * (const bigint & a, 249 const quadratic_number_standard & b); 250 friend 251 quadratic_number_standard operator * (const quadratic_number_standard & a, 252 const bigint & b); 253 friend 254 quadratic_number_standard operator / (const quadratic_number_standard & a, 255 const quadratic_number_standard & b); 256 friend 257 quadratic_number_standard operator / (const bigrational & a, 258 const quadratic_number_standard & b); 259 friend 260 quadratic_number_standard operator / (const quadratic_number_standard & a, 261 const bigrational & b); 262 quadratic_number_standard & operator += (const quadratic_number_standard & x); 263 264 quadratic_number_standard & operator -= (const quadratic_number_standard & x); 265 266 quadratic_number_standard & operator *= (const quadratic_number_standard & x); 267 268 quadratic_number_standard & operator /= (const quadratic_number_standard & x); 269 270 // 271 // special purpose functions 272 // 273 274 void absolute_value(); 275 int get_sign() const; 276 277 void norm (bigrational & n) const; 278 bigrational norm () const; 279 280 void trace (bigrational & t) const; 281 bigrational trace () const; 282 283 friend bigrational norm (const quadratic_number_standard & y); 284 friend bigrational trace(const quadratic_number_standard & y); 285 286 287 void conjugate(); 288 friend void conjugate (quadratic_number_standard & x, const quadratic_number_standard & y); 289 290 long b_value () const; 291 long b_value (const bigint & sq_Delta) const; 292 293 void get_relative_approximation (xbigfloat & l, long k) const; 294 void get_absolute_Ln_approximation (xbigfloat & l, long k) const; 295 xbigfloat get_absolute_Ln_approximation (long k) const; 296 297 void get_absolute_Ln_approximation_old (xbigfloat & l, long k) const; 298 void get_absolute_Ln_approximation_with_check (xbigfloat & l, long k) const; 299 void get_absolute_Ln_approximation_with_check_old (xbigfloat & l, long k) const; 300 301 void get_Ln_estimate(xbigfloat & l, xbigfloat & u) const; 302 303 bool check_Ln_correctness (lidia_size_t trials = 5) const; 304 305 // 306 // input / output 307 // 308 309 friend std::istream & operator >> (std::istream & in, quadratic_number_standard &); 310 311 friend std::ostream & operator << (std::ostream & out, const quadratic_number_standard &); 312 313 friend int string_to_quadratic_number_standard (const char* s, quadratic_number_standard & x); 314 }; 315 316 // friend functions 317 318 void swap (quadratic_number_standard & x, quadratic_number_standard & y); 319 320 // 321 // comparisons 322 // 323 324 bool operator == (const quadratic_number_standard & x, 325 const quadratic_number_standard & y); 326 bool operator == (const bigint & n, 327 const quadratic_number_standard & x); 328 bool operator == (const quadratic_number_standard & x, 329 const bigint & n); 330 bool operator == (const bigrational & n, 331 const quadratic_number_standard & x); 332 bool operator == (const quadratic_number_standard & x, 333 const bigrational & n); 334 bool operator != (const quadratic_number_standard & x, 335 const quadratic_number_standard & y); 336 bool operator != (const bigint & n, 337 const quadratic_number_standard & x); 338 bool operator != (const quadratic_number_standard & x, 339 const bigint & n); 340 bool operator != (const bigrational & n, 341 const quadratic_number_standard & x); 342 bool operator != (const quadratic_number_standard & x, 343 const bigrational & n); 344 345 // 346 // arithmetic 347 // 348 349 void negate (quadratic_number_standard & c, 350 const quadratic_number_standard & a); 351 void add (quadratic_number_standard & c, 352 const quadratic_number_standard & a, 353 const quadratic_number_standard & b); 354 void subtract (quadratic_number_standard & c, 355 const quadratic_number_standard & a, 356 const quadratic_number_standard & b); 357 void multiply (quadratic_number_standard & c, 358 const quadratic_number_standard & a, 359 const quadratic_number_standard & b); 360 void multiply (quadratic_number_standard & c, 361 const bigint & n, 362 const quadratic_number_standard & a); 363 void multiply (quadratic_number_standard & c, 364 const quadratic_number_standard & a, 365 const bigint & n); 366 void multiply (quadratic_number_standard & c, 367 const bigrational & n, 368 const quadratic_number_standard & a); 369 void multiply (quadratic_number_standard & c, 370 const quadratic_number_standard & a, 371 const bigrational & n); 372 void inverse (quadratic_number_standard & x, 373 const quadratic_number_standard & y); 374 void divide (quadratic_number_standard & c, 375 const quadratic_number_standard & a, 376 const quadratic_number_standard & b); 377 void divide (quadratic_number_standard & c, 378 const bigrational & n, 379 const quadratic_number_standard & a); 380 void divide (quadratic_number_standard & c, 381 const quadratic_number_standard & a, 382 const bigrational & n); 383 void square (quadratic_number_standard & c, 384 const quadratic_number_standard & a); 385 void power (quadratic_number_standard & c, 386 const quadratic_number_standard & a, 387 unsigned long e); 388 void power (quadratic_number_standard & c, 389 const quadratic_number_standard & a, 390 const bigint & e); 391 392 quadratic_number_standard operator - (const quadratic_number_standard & a); 393 quadratic_number_standard operator + (const quadratic_number_standard & a, 394 const quadratic_number_standard & b); 395 quadratic_number_standard operator - (const quadratic_number_standard & a, 396 const quadratic_number_standard & b); 397 quadratic_number_standard operator * (const quadratic_number_standard & a, 398 const quadratic_number_standard & b); 399 quadratic_number_standard operator * (const bigint & a, 400 const quadratic_number_standard & b); 401 quadratic_number_standard operator * (const quadratic_number_standard & a, 402 const bigint & b); 403 quadratic_number_standard operator / (const quadratic_number_standard & a, 404 const quadratic_number_standard & b); 405 quadratic_number_standard operator / (const bigrational & a, 406 const quadratic_number_standard & b); 407 quadratic_number_standard operator / (const quadratic_number_standard & a, 408 const bigrational & b); 409 410 // 411 // special purpose functions 412 // 413 414 bigrational norm (const quadratic_number_standard & y); 415 bigrational trace(const quadratic_number_standard & y); 416 417 void conjugate (quadratic_number_standard & x, 418 const quadratic_number_standard & y); 419 420 // 421 // input / output 422 // 423 424 std::istream & operator >> (std::istream & in, quadratic_number_standard &); 425 std::ostream & operator << (std::ostream & out, 426 const quadratic_number_standard &); 427 int string_to_quadratic_number_standard (const char* s, 428 quadratic_number_standard & x); 429 430 431 #ifdef LIDIA_NAMESPACE 432 } // end of namespace LiDIA 433 # undef IN_NAMESPACE_LIDIA 434 #endif 435 436 437 438 #endif // LIDIA_QUADRATIC_NUMBER_STANDARD_H_GUARD_ 439