Symbolism: include/symbolism/N.h Source File

00001 #pragma once
00002 #include <iostream>
00003 #include <gmp.h>
00004 #include <cassert>
00005 #include <symbolism/exception.h>
00006 
00007 namespace symbolism {
00008 namespace ring {
00009 
00161 class N
00162 {
00163     public:
00164 
00166 
00168         typedef mp_limb_t limb_t;
00169 
00171         typedef long unsigned int size_t;
00172 
00174         static const int bits_per_limb = 8 * sizeof(limb_t);
00175 
00177         size_t size;
00178 
00180         union
00181         {
00183             limb_t  limb;
00184 
00190             limb_t* data;
00191         };
00192 
00194         inline N();
00195         inline N(const N& copy);
00196         inline N(const limb_t value);
00197         inline ~N();
00198 
00200         inline limb_t* limbs();
00201         inline const limb_t* limbs() const;
00202         inline void set(const N& copy);
00203         inline void set(const limb_t value);
00204         inline friend void swap(N& a, N& b);
00205         inline N& operator=(const N& copy);
00206         inline N& operator=(const limb_t value);
00207         inline friend size_t max(const size_t a, const size_t b);
00208         inline void reserve(size_t newsize);
00209         inline void resize(size_t newsize);
00210         inline void truncate(size_t newsize);
00211         inline void normalize();
00212 
00214         inline bool is_zero() const;
00215         inline bool is_one() const;
00216         inline int compare(const N& a) const;
00217         inline int compare(const limb_t a) const;
00218         inline friend bool operator==(const N& a, const N& b);
00219         inline friend bool operator!=(const N& a, const N& b);
00220         inline friend bool operator> (const N& a, const N& b);
00221         inline friend bool operator>=(const N& a, const N& b);
00222         inline friend bool operator< (const N& a, const N& b);
00223         inline friend bool operator<=(const N& a, const N& b);
00224 
00226         inline size_t two_multiplicity() const;
00227         inline void binary_not(const N& a);
00228         inline void binary_not();
00229         inline void binary_and(const N& a, const N& b);
00230         inline void binary_and(const N& a);
00231         inline void binary_or(const N& a, const N& b);
00232         inline void binary_or(const N& a);
00233         inline void binary_xor(const N& a, const N& b);
00234         inline void binary_xor(const N& a);
00235         inline void left_shift(const N& a, unsigned int count);
00236         inline void left_shift(unsigned int count);
00237         inline void right_shift(const N& a, unsigned int count);
00238         inline void right_shift(unsigned int count);
00239         inline friend N operator~(const N& a);
00240         inline friend N operator&(const N& a, const N& b);
00241         inline friend N operator|(const N& a, const N& b);
00242         inline friend N operator<<(const N& a, unsigned int count);
00243         inline friend N operator>>(const N& a, unsigned int count);
00244         inline N& operator<<=(const limb_t count);
00245         inline N& operator>>=(const limb_t cout);
00246         inline N& operator&=(const N& a);
00247         inline N& operator|=(const N& a);
00248 
00250         inline void add(const N& a, const N& b);
00251         inline void add(const N& a);
00252         inline void add_one();
00253         inline friend N operator+(const N& a, const N& b);
00254         inline N& operator+=(const N& rhs);
00255         inline N& operator++();
00256         inline N operator++(int);
00257 
00259         inline void sub(const N& a, const N& b);
00260         inline void sub(const N& a);
00261         inline void sub_one();
00262         inline friend N operator-(const N& a, const N& b);
00263         inline N& operator-=(const N& rhs);
00264         inline N& operator--();
00265         inline N operator--(int);
00266 
00268         inline void mul(const N& a, const N& b);
00269         inline void mul(const N& a);
00270         inline friend N operator*(const N& a, const N& b);
00271         inline N& operator*=(const N& rhs);
00272 
00274         inline void addmul(const N& a, const limb_t b);
00275         inline void submul(const N& a, const limb_t b);
00276 
00278         inline void exact_div(const N& a, const N& b);
00279         inline void exact_div(const N& a);
00280         inline void div(N& rem, const N& a, const N& b);
00281         inline void div(N& rem, const N& a);
00282         inline void quo(const N& a, const N& b);
00283         inline void quo(const N& a);
00284         inline void rem(const N& a, const N& b);
00285         inline void rem(const N& a);
00286         inline friend N operator/(const N& a, const N& b);
00287         inline N& operator/=(const N& rhs);
00288         inline friend N operator%(const N& a, const N& b);
00289         inline N& operator%=(const N& rhs);
00290         inline friend N div(N& rem, const N& a, const N& b);
00291         inline friend N div_exact(const N& a, const N& b);
00292         inline friend N quo(const N& a, const N& b);
00293         inline friend N rem(const N& a, const N& b);
00294 
00296         inline void gcd(const N& a, const N& b);
00297         inline void gcd(const N& b);
00298         inline void extended_gcd(N& x, N& y, const N& a, const N& b);
00299         inline void lcm(const N& a, const N& b);
00300         inline void lcm(const N& b);
00301 
00303         inline friend N gcd(const N& a, const N& b);
00304 
00306         void random(const size_t newsize);
00307         void random2(const size_t newsize);
00308 
00310         inline limb_t to_int() const;
00311         std::string to_binary() const;
00312         std::string to_hexadecimal() const;
00313         std::string to_decimal() const;
00314         std::string to_english() const;
00315         void write_english(std::ostream& out) const;
00316         inline friend std::ostream& operator<<(std::ostream& out, const N& n);
00317 
00318     public:
00320         void reserve_small(size_t newsize);
00321         void reserve_large(size_t newsize);
00322         void resize_small(size_t newsize);
00323         void resize_large(size_t newsize);
00324         void truncate_large(size_t newsize);
00325         void normalize_large();
00326 
00328         inline size_t two_multiplicity_large() const;
00329         inline size_t two_multiplicity_small() const;
00330         void left_shift_large(const N& a, unsigned int count);
00331         inline void left_shift_small(const limb_t a, unsigned int count);
00332         void left_shift_large(unsigned int count);
00333         inline void left_shift_small(unsigned int count);
00334         void right_shift_large(const N& a, unsigned int count);
00335         inline void right_shift_small(const limb_t a, unsigned int count);
00336         void right_shift_large(unsigned int count);
00337         inline void right_shift_small(unsigned int count);
00338 
00340         inline void add_carry_small(const limb_t carry = 1);
00341         inline void add_carry_large(const limb_t carry = 1);
00342         void add_large_large(const N& a, const N& b);
00343         void add_large_small(const N& a, const limb_t b);
00344         inline void add_small_small(const limb_t a, const limb_t b);
00345         void add_large_large(const N& a);
00346         void add_large_small(const limb_t a);
00347         void add_small_large(const N& a);
00348         inline void add_small_small(const limb_t a);
00349         void add_one_large();
00350         inline void add_one_small();
00351 
00353         void sub_large_large(const N& a, const N& b);
00354         void sub_large_small(const N& a, const limb_t b);
00355         inline void sub_small_small(const limb_t a, const limb_t b);
00356         void sub_large_large(const N& a);
00357         void sub_large_small(const limb_t a);
00358         inline void sub_small_small(const limb_t a);
00359         void sub_one_large();
00360         inline void sub_one_small();
00361 
00363         void mul_large_large(const N& a, const N& b);
00364         void mul_large_small(const N& a, const limb_t b);
00365         inline void mul_small_small(const limb_t a, const limb_t b);
00366         void mul_large_large(const N& a);
00367         void mul_large_small(const limb_t a);
00368         void mul_small_large(const N& a);
00369         inline void mul_small_small(const limb_t a);
00370 
00372         void addmul_large_large(const N& a, const limb_t b);
00373         void addmul_large_small(const limb_t a, const limb_t b);
00374         void addmul_small_large(const N& a, const limb_t b);
00375         inline void addmul_small_small(const limb_t a, const limb_t b);
00376         void submul_large_large(const N& a, const limb_t b);
00377         void submul_large_small(const limb_t a, const limb_t b);
00378         void submul_small_large(const N& a, const limb_t b);
00379         inline void submul_small_small(const limb_t a, const limb_t b);
00380 
00382         void exact_div_large_large(const N& a, const N& b);
00383         void exact_div_large_small(const N& a, const limb_t b);
00384         inline void exact_div_small_small(const limb_t a, const limb_t b);
00385         void exact_div_large_large(const N& b);
00386         void exact_div_large_small(const limb_t b);
00387         inline void exact_div_small_small(const limb_t b);
00388         void div_large_large(N& rem, const N& a, const N& b);
00389         void div_large_small(N& rem, const N& a, const limb_t b);
00390         void div_small_large(N& rem, const limb_t a, const N& b);
00391         inline void div_small_small(N& rem, const limb_t a, const limb_t b);
00392         void div_large_large(N& rem, const N& b);
00393         void div_large_small(N& rem, const limb_t b);
00394         void div_small_large(N& rem, const N& b);
00395         inline void div_small_small(N& rem, const limb_t b);
00396         void quo_large_large(const N& a, const N& b);
00397         void quo_large_small(const N& a, const limb_t b);
00398         void quo_small_large(const limb_t a, const N& b);
00399         inline void quo_small_small(const limb_t a, const limb_t b);
00400         void quo_large_large(const N& b);
00401         void quo_large_small(const limb_t b);
00402         void quo_small_large(const N& b);
00403         inline void quo_small_small(const limb_t b);
00404         void rem_large_large(const N& a, const N& b);
00405         void rem_large_small(const N& a, const limb_t b);
00406         void rem_small_large(const limb_t a, const N& b);
00407         inline void rem_small_small(const limb_t a, const limb_t b);
00408         void rem_large_large(const N& b);
00409         void rem_large_small(const limb_t b);
00410         void rem_small_large(const N& b);
00411         inline void rem_small_small(const limb_t b);
00412 
00414         void gcd_large_large(const N& a, const N& b);
00415         void gcd_large_small(const N& a, const limb_t b);
00416         void gcd_small_small(const limb_t a, const limb_t b);
00417         void gcd_large_large(const N& b);
00418         void gcd_large_small(const limb_t b);
00419         void gcd_small_large(const N& b);
00420         void gcd_small_small(const limb_t b);
00421 
00423 };
00424 
00425 class not_implemented_exception: public utility::exception
00426 {
00427     DECLARE_EXCEPTION_CONSTRUCTORS(not_implemented_exception);
00428 
00429     virtual const std::string description() const throw()
00430     {
00431         return "The operation you requested has not been implemented"
00432                " yet. You can help Symbolism by implementing it!";
00433     }
00434 };
00435 
00436 class can_not_shrink_exception: public utility::exception
00437 {
00438     DECLARE_EXCEPTION_CONSTRUCTORS(can_not_shrink_exception);
00439 
00440     virtual const std::string description() const throw()
00441     {
00442         return "The number of limbs can not be lowered without"
00443                " changing the numbers value. Consider using"
00444                " N::truncate or N::reserve.";
00445     }
00446 };
00447 
00448 class result_negative_exception: public utility::exception
00449 {
00450     DECLARE_EXCEPTION_CONSTRUCTORS(result_negative_exception);
00451 
00452     virtual const std::string description() const throw()
00453     {
00454         return "The result of this operation is negative, while"
00455                " the datatype can only contain positive numbers.";
00456     }
00457 };
00458 
00459 class inexact_division_exception: public utility::exception
00460 {
00461     DECLARE_EXCEPTION_CONSTRUCTORS(inexact_division_exception);
00462 
00463     virtual const std::string description() const throw()
00464     {
00465         return "The exact division that was requested has left"
00466                " a non-zero remainder.";
00467     }
00468 };
00469 
00470 class division_by_zero_exception: public utility::exception
00471 {
00472     DECLARE_EXCEPTION_CONSTRUCTORS(division_by_zero_exception);
00473 
00474     virtual const std::string description() const throw()
00475     {
00476         return "A division has been requested with a zero"
00477                " denominator.";
00478     }
00479 };
00480 
00481 // Macro to optimize branch prediction
00482 #define fast_true(a) __builtin_expect(a, 1)
00483 #define fast_false(a) __builtin_expect(a, 0)
00484 
00485 // Optimize branches for small numbers
00486 #define this_small fast_true(size == 0)
00487 #define is_small(a) fast_true(a.size == 0)
00488 
00489 #include "N.Constructors.h"
00490 #include "N.Accessors.h"
00491 #include "N.Size.h"
00492 #include "N.Comparisson.h"
00493 #include "N.Binary.h"
00494 #include "N.Assignment.h"
00495 #include "N.Addition.h"
00496 #include "N.Substraction.h"
00497 #include "N.Multiplication.h"
00498 #include "N.Division.h"
00499 #include "N.AddSubmul.h"
00500 #include "N.GCD.h"
00501 #include "N.Random.h"
00502 #include "N.Conversion.h"
00503 
00504 }}