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
|
#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <cstdint>
class Bigint{
public:
typedef uint32_t digit_t;
typedef int32_t sdigit_t;
typedef uint64_t longdigit_t;
typedef int64_t slongdigit_t;
static const int digit_bits=8*sizeof(digit_t);
private:
std::vector<digit_t> digits;
int sign;
static void add(Bigint&,const Bigint&); //ignores sign of arguments
static void subtract(Bigint&,const Bigint&); //ignores sign of arguments; assumes a>=b
static Bigint product(const Bigint&,const Bigint&);
void shrink();
void normalise();
void checkconsistent();
std::pair<Bigint,Bigint> divmod(const Bigint&,int depth,int maxdepth) const; //ignores all signs
public:
Bigint();
Bigint(const Bigint&)=default;
Bigint(Bigint&&);
explicit Bigint(const std::string&);
explicit Bigint(sdigit_t);
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();
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;
std::string serialiseMantissa() const; //stores everything but the sign
//restores non-negative number; can throw invalid_argument
void deserialiseMantissa(const std::string&);
std::vector<bool> bits() const;
friend std::istream& operator>>(std::istream&,Bigint&);
friend std::ostream& operator<<(std::ostream&,Bigint);
digit_t _digit(int idx) const;
static Bigint mone;
static Bigint zero;
static Bigint one;
static Bigint two;
};
std::istream& operator>>(std::istream&,Bigint&);
std::ostream& operator<<(std::ostream&,Bigint);
|
