1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <cstdint>
//A bigint implementation based on unsigned 32-bit digits.
//The implementation relies on having native 64-bit arithmetic (or specifically,
//(2*digit_bits)-bit arithmetic).
class Bigint{
public:
typedef uint32_t digit_t;
typedef int32_t sdigit_t; //signed version
typedef uint64_t longdigit_t; //should be twice as large as digit_t
typedef int64_t slongdigit_t; //signed version
static const int digit_bits=8*sizeof(digit_t);
private:
std::vector<digit_t> digits; //little-endian order
int sign; //-1 for negative, 1 for positive; -0 is not a valid state
static void add(Bigint&,const Bigint&); //ignores sign of arguments
static void subtract(Bigint&,const Bigint&); //ignores sign of arguments
static Bigint product(const Bigint&,const Bigint&);
void shrink(); //prune unnecessary zero digits on top
void normalise(); //make sure -0 doesn't occur
//This function is called from all relevant return points of the member functions. It's
//basically a debug check, but it can't hurt to have it since it takes few cpu cycles.
void checkconsistent();
static std::pair<Bigint,Bigint> divmod(Bigint a,const Bigint &div,int maxdepth); //ignores all signs
public:
Bigint();
Bigint(const Bigint&)=default;
Bigint(Bigint&&);
explicit Bigint(const std::string&); //Initialise with a large value
explicit Bigint(sdigit_t); //Initialise with a small value
explicit Bigint(digit_t);
explicit Bigint(slongdigit_t);
explicit Bigint(longdigit_t);
Bigint& operator=(const Bigint&)=default;
Bigint& operator=(Bigint&&);
Bigint& operator=(slongdigit_t);
Bigint& operator=(longdigit_t);
Bigint& operator=(sdigit_t);
Bigint& operator=(digit_t);
Bigint& operator+=(const Bigint&);
Bigint& operator-=(const Bigint&);
Bigint& operator*=(const Bigint&);
Bigint& operator+=(slongdigit_t);
Bigint& operator-=(slongdigit_t);
Bigint& operator*=(slongdigit_t);
Bigint& operator<<=(int);
Bigint& operator>>=(int);
Bigint& negate();
//Division and modulo operators are explicitly NOT included, to promote clever usage
//of the divmod function, which combines both.
Bigint operator+(const Bigint&) const;
Bigint operator-(const Bigint&) const;
Bigint operator*(const Bigint&) const;
Bigint operator+(slongdigit_t) const;
Bigint operator-(slongdigit_t) const;
Bigint operator*(slongdigit_t) const;
Bigint operator<<(int) const;
Bigint operator>>(int) const;
//Uses *mathematical* division-with-remainder.
//If we look at {q,r} = x.divmod(y), then x = q*y + r, and 0<=r<|q|. This is *not* compatible with many other
//programming languages (and, for that matter, the C++ built-in behaviour).
std::pair<Bigint,Bigint> divmod(const Bigint&) const;
bool operator==(const Bigint&) const;
bool operator!=(const Bigint&) const;
bool operator<(const Bigint&) const;
bool operator>(const Bigint&) const;
bool operator<=(const Bigint&) const;
bool operator>=(const Bigint&) const;
bool operator==(slongdigit_t) const;
bool operator!=(slongdigit_t) const;
bool operator<(slongdigit_t) const;
bool operator>(slongdigit_t) const;
bool operator<=(slongdigit_t) const;
bool operator>=(slongdigit_t) const;
int compare(const Bigint&) const; //-1: <; 0: ==; 1: >
int compare(slongdigit_t) const;
int compareAbs(const Bigint&) const; //-1: <; 0: ==; 1: >; disregards sign
int compareAbs(slongdigit_t) const;
int bitcount() const;
slongdigit_t lowdigits() const;
bool even() const;
bool odd() const;
int trailingZeros() const; //throws domain_error if called on zero value
std::string serialiseMantissa() const; //stores everything but the sign
void deserialiseMantissa(const std::string&); //restores non-negative number; can throw invalid_argument
std::vector<bool> bits() const; //Stores bits in little-endian order
friend std::istream& operator>>(std::istream&,Bigint&);
friend std::ostream& operator<<(std::ostream&,Bigint);
static Bigint mone; //Some small values to save a constructor call
static Bigint zero;
static Bigint one;
static Bigint two;
};
std::istream& operator>>(std::istream&,Bigint&);
std::ostream& operator<<(std::ostream&,Bigint); //The output operator supports the `hex` modifier
|
