1 #include "tommath.h"
2 #include <limits>
3 #ifdef NSPIRE
4 extern "C" {
5 #include <nspireio/nspireio.h>
6 }
7 #endif
8
9 typedef mp_int mpz_t;
10
mpz_init(mpz_t & a)11 inline int mpz_init(mpz_t & a){ return mp_init(&a);}
mpz_init2(mpz_t & a,int size)12 inline int mpz_init2(mpz_t & a,int size){ return mp_init_size(&a,size);}
mpz_init_set(mpz_t & a,const mpz_t & b)13 inline int mpz_init_set(mpz_t & a,const mpz_t & b){ return mp_init_copy(&a,(mp_int *)&b);}
mpz_init_set_si(mpz_t & a,long b)14 inline void mpz_init_set_si(mpz_t & a,long b){ mp_init_set_int(&a,b>0?b:-b); if (b<0) mp_neg(&a,&a);}
mpz_init_set_ui(mpz_t & a,unsigned long b)15 inline int mpz_init_set_ui(mpz_t & a,unsigned long b){ return mp_init_set_int(&a,b); }
mpz_clear(mpz_t & a)16 inline void mpz_clear(mpz_t & a){ mp_clear(&a);}
mpz_sgn(const mpz_t & a)17 inline int mpz_sgn(const mpz_t & a){ return mp_cmp_d((mp_int *)&a,0);}
mpz_set(mpz_t & a,const mpz_t & b)18 inline int mpz_set(mpz_t & a,const mpz_t & b){ return mp_copy((mp_int *)&b,&a);}
mpz_set_ui(mpz_t & a,unsigned int ui)19 inline void mpz_set_ui(mpz_t & a,unsigned int ui){ mp_set_int(&a,ui); }
mpz_set_si(mpz_t & a,int ui)20 inline void mpz_set_si(mpz_t & a,int ui){ mp_set_int(&a,ui>0?ui:-ui); if (ui<0) mp_neg(&a,&a); }
mpz_mod(mpz_t & c,const mpz_t & a,const mpz_t & b)21 inline int mpz_mod(mpz_t & c,const mpz_t & a,const mpz_t & b){ return mp_mod((mp_int *)&a,(mp_int *)&b,&c); }
mpz_add(mpz_t & c,const mpz_t & a,const mpz_t & b)22 inline int mpz_add(mpz_t & c,const mpz_t & a,const mpz_t & b){ return mp_add((mp_int *)&a,(mp_int *)&b,&c); }
mpz_add_ui(mpz_t & c,const mpz_t & a,unsigned int B)23 inline void mpz_add_ui(mpz_t & c,const mpz_t & a,unsigned int B){ mp_int b; mp_init_set_int(&b,B); mp_add((mp_int *)&a,&b,&c); mp_clear(&b); }
mpz_sub(mpz_t & c,const mpz_t & a,const mpz_t & b)24 inline int mpz_sub(mpz_t & c,const mpz_t & a,const mpz_t & b){ return mp_sub((mp_int *)&a,(mp_int *)&b,&c); }
mpz_sub_ui(mpz_t & c,const mpz_t & a,unsigned int B)25 inline void mpz_sub_ui(mpz_t & c,const mpz_t & a,unsigned int B){ mp_int b; mp_init_set_int(&b,B); mp_sub((mp_int *)&a,&b,&c); mp_clear(&b); }
mpz_mul(mpz_t & c,const mpz_t & a,const mpz_t & b)26 inline int mpz_mul(mpz_t & c,const mpz_t & a,const mpz_t & b){ return mp_mul((mp_int *)&a,(mp_int *)&b,&c); }
mpz_ior(mpz_t & c,const mpz_t & a,const mpz_t & b)27 inline int mpz_ior(mpz_t & c,const mpz_t & a,const mpz_t & b){ return mp_or((mp_int *)&a,(mp_int *)&b,&c); }
mpz_xor(mpz_t & c,const mpz_t & a,const mpz_t & b)28 inline int mpz_xor(mpz_t & c,const mpz_t & a,const mpz_t & b){ return mp_xor((mp_int *)&a,(mp_int *)&b,&c); }
mpz_and(mpz_t & c,const mpz_t & a,const mpz_t & b)29 inline int mpz_and(mpz_t & c,const mpz_t & a,const mpz_t & b){ return mp_and((mp_int *)&a,(mp_int *)&b,&c); }
mpz_pow_ui(mpz_t & c,const mpz_t & a,unsigned int B)30 inline int mpz_pow_ui(mpz_t & c,const mpz_t & a,unsigned int B){ return mp_expt_d((mp_int *)&a,B,&c); }
mpz_ui_pow_ui(mpz_t & c,unsigned int A,unsigned int B)31 inline void mpz_ui_pow_ui(mpz_t & c,unsigned int A,unsigned int B){ mp_int a ; mp_init_set_int(&a,A); mp_expt_d(&a,B,&c); mp_clear(&a);}
mpz_powm(mpz_t & d,const mpz_t & a,const mpz_t & b,const mpz_t & c)32 inline int mpz_powm(mpz_t & d,const mpz_t & a,const mpz_t & b,const mpz_t & c){ return mp_exptmod((mp_int *)&a,(mp_int *)&b,(mp_int *)&c,&d); }
mpz_powm_ui(mpz_t & d,const mpz_t & a,unsigned int B,const mpz_t & c)33 inline void mpz_powm_ui(mpz_t & d,const mpz_t & a,unsigned int B,const mpz_t & c){ mp_int b; mp_init_set_int(&b,B); mp_exptmod((mp_int *)&a,&b,(mp_int *)&c,&d); mp_clear(&b);}
mpz_gcd(mpz_t & c,const mpz_t & a,const mpz_t & b)34 inline int mpz_gcd(mpz_t & c,const mpz_t & a,const mpz_t & b){ return mp_gcd((mp_int *)&a,(mp_int *)&b,&c); }
mpz_gcdext(mpz_t & d,mpz_t & u,mpz_t & v,const mpz_t & a,const mpz_t & b)35 inline int mpz_gcdext(mpz_t & d,mpz_t & u, mpz_t & v,const mpz_t & a,const mpz_t & b){ return mp_exteuclid((mp_int *)&a,(mp_int *)&b,&u,&v,&d); }
gcdint(int a,int b)36 inline int gcdint(int a,int b){
37 int r;
38 while (b){
39 r=a%b;
40 a=b;
41 b=r;
42 }
43 return a<0?-a:a;
44 }
mpz_lcm(mpz_t & c,const mpz_t & a,const mpz_t & b)45 inline int mpz_lcm(mpz_t & c,const mpz_t & a,const mpz_t & b){ return mp_lcm((mp_int *)&a,(mp_int *)&b,&c); }
mpz_mul_ui(mpz_t & c,mpz_t & a,unsigned int B)46 inline void mpz_mul_ui(mpz_t & c,mpz_t & a,unsigned int B){ mp_mul_d(&a,B,&c); } // { mp_int b; mp_init_set_int(&b,B); mp_mul((mp_int *)&a,&b,&c); mp_clear(&b); }
mpz_mul_2exp(mpz_t & c,const mpz_t & a,unsigned int B)47 inline int mpz_mul_2exp(mpz_t & c,const mpz_t & a,unsigned int B){ return mp_mul_2d((mp_int *)&a,B,&c); }
mpz_tdiv_q_2exp(mpz_t & c,const mpz_t & a,unsigned int B)48 inline void mpz_tdiv_q_2exp(mpz_t & c,const mpz_t & a,unsigned int B){ mp_int d; mp_init(&d); mp_div_2d((mp_int *)&a,B,&c,&d); mp_clear(&d); }
mpz_tdiv_r_2exp(mpz_t & d,const mpz_t & a,unsigned int B)49 inline void mpz_tdiv_r_2exp(mpz_t & d,const mpz_t & a,unsigned int B){ mp_int c; mp_init(&c); mp_div_2d((mp_int *)&a,B,&c,&d); mp_clear(&c); }
mpz_addmul(mpz_t & c,const mpz_t & a,const mpz_t & b)50 inline void mpz_addmul(mpz_t & c,const mpz_t & a,const mpz_t & b){ mp_int ab; mp_init(&ab); mp_mul((mp_int *)&a,(mp_int *)&b,&ab); mp_add(&c,&ab,&c); mp_clear(&ab); }
mpz_addmul_ui(mpz_t & c,const mpz_t & a,unsigned int B)51 inline void mpz_addmul_ui(mpz_t & c,const mpz_t & a,unsigned int B){ mp_int ab,b; mp_init(&ab); mp_init_set_int(&b,B); mp_mul((mp_int *)&a,&b,&ab); mp_add(&c,&ab,&c); mp_clear(&ab); mp_clear(&b); }
mpz_submul(mpz_t & c,const mpz_t & a,const mpz_t & b)52 inline void mpz_submul(mpz_t & c,const mpz_t & a,const mpz_t & b){ mp_int ab; mp_init(&ab); mp_mul((mp_int *)&a,(mp_int *)&b,&ab); mp_sub(&c,&ab,&c); mp_clear(&ab); }
mpz_submul_ui(mpz_t & c,const mpz_t & a,unsigned int B)53 inline void mpz_submul_ui(mpz_t & c,const mpz_t & a,unsigned int B){ mp_int ab; mp_init(&ab); mp_int b; mp_init_set_int(&b,B); mp_mul((mp_int *)&a,&b,&ab); mp_sub(&c,&ab,&c); mp_clear(&ab); mp_clear(&b);}
mpz_fdiv_r(mpz_t & c,const mpz_t & a,const mpz_t & b)54 inline int mpz_fdiv_r(mpz_t & c,const mpz_t & a,const mpz_t & b){ return mp_mod((mp_int *)&a,(mp_int *)&b,&c); }
mpz_tdiv_r(mpz_t & c,const mpz_t & a,const mpz_t & b)55 inline int mpz_tdiv_r(mpz_t & c,const mpz_t & a,const mpz_t & b){ return mp_mod((mp_int *)&a,(mp_int *)&b,&c); }
mpz_fdiv_r_ui(mpz_t & c,const mpz_t & a,unsigned b)56 inline void mpz_fdiv_r_ui(mpz_t & c,const mpz_t & a,unsigned b){ mp_digit C; mp_mod_d((mp_int *)&a,b,&C); mp_set_int(&c,C); }
mpz_fdiv_q_ui(mpz_t & c,const mpz_t & a,unsigned b)57 inline void mpz_fdiv_q_ui(mpz_t & c,const mpz_t & a,unsigned b){ mp_digit C; mp_div_d((mp_int *)&a,b,&c,&C);}
mpz_divexact_ui(mpz_t & c,const mpz_t & a,unsigned b)58 inline void mpz_divexact_ui(mpz_t & c,const mpz_t & a,unsigned b){ mp_digit C; mp_div_d((mp_int *)&a,b,&c,&C);}
mpz_fdiv_qr_ui(mpz_t & c,mpz_t & d,const mpz_t & a,unsigned b)59 inline void mpz_fdiv_qr_ui(mpz_t & c,mpz_t& d,const mpz_t & a,unsigned b){ mp_digit D; mp_div_d((mp_int *)&a,b,&c,&D); mp_set_int(&d,D); }
mpz_fdiv_q(mpz_t & c,const mpz_t & a,const mpz_t & b)60 inline void mpz_fdiv_q(mpz_t & c,const mpz_t & a,const mpz_t & b){ mp_int d; mp_init(&d); mp_div((mp_int *)&a,(mp_int *)&b,&c,&d); mp_clear(&d); }
mpz_tdiv_q(mpz_t & c,const mpz_t & a,const mpz_t & b)61 inline void mpz_tdiv_q(mpz_t & c,const mpz_t & a,const mpz_t & b){ mp_int d; mp_init(&d); mp_div((mp_int *)&a,(mp_int *)&b,&c,&d); mp_clear(&d); }
mpz_fdiv_qr(mpz_t & c,mpz_t & d,const mpz_t & a,const mpz_t & b)62 inline int mpz_fdiv_qr(mpz_t & c,mpz_t & d,const mpz_t & a,const mpz_t & b){ return mp_div((mp_int *)&a,(mp_int *)&b,&c,&d); }
mpz_tdiv_qr(mpz_t & c,mpz_t & d,const mpz_t & a,const mpz_t & b)63 inline int mpz_tdiv_qr(mpz_t & c,mpz_t & d,const mpz_t & a,const mpz_t & b){ return mp_div((mp_int *)&a,(mp_int *)&b,&c,&d); }
mpz_sqrt(mpz_t & a,const mpz_t & b)64 inline int mpz_sqrt(mpz_t & a,const mpz_t & b){ return mp_sqrt((mp_int *)&b,&a);}
mpz_sqr(mpz_t & a,const mpz_t & b)65 inline int mpz_sqr(mpz_t & a,const mpz_t & b){ return mp_sqr((mp_int *)&b,&a);}
mpz_neg(mpz_t & a,const mpz_t & b)66 inline int mpz_neg(mpz_t & a,const mpz_t & b){ return mp_neg((mp_int *)&b,&a);}
mpz_abs(mpz_t & a,const mpz_t & b)67 inline int mpz_abs(mpz_t & a,const mpz_t & b){ return mp_abs((mp_int *)&b,&a);}
mpz_cmp(const mpz_t & a,const mpz_t & b)68 inline int mpz_cmp(const mpz_t & a,const mpz_t & b){ return mp_cmp((mp_int *)&a,(mp_int *)&b);}
mpz_cmp_ui(const mpz_t & a,unsigned int B)69 inline int mpz_cmp_ui(const mpz_t & a,unsigned int B){ return mp_cmp_d((mp_int *)&a,B);}
mpz_cmp_si(const mpz_t & a,int B)70 inline int mpz_cmp_si(const mpz_t & a,int B){ mp_int b; int res; mp_init(&b); mpz_set_si(b,B); res=mp_cmp((mp_int *)&a,&b); mp_clear(&b); return res;}
mpz_sizeinbase(const mpz_t & a,int radix)71 inline int mpz_sizeinbase(const mpz_t & a,int radix){ int size; mp_radix_size((mp_int *)&a,radix,&size); return size; }
mpz_get_si(const mpz_t & a)72 inline int mpz_get_si(const mpz_t & a){
73 #if 1
74 if (a.sign!=MP_NEG)
75 return mp_get_int((mp_int *)&a);
76 mp_int * ptr=(mp_int *)&a;
77 mp_neg(ptr,ptr);
78 long u=mp_get_int(ptr);
79 mp_neg(ptr,ptr);
80 return -u;
81 #else
82 mp_int tmp,res;
83 mp_init_set_int(&tmp,1<<16); mp_init(&res);
84 mp_mul(&tmp,&tmp,&tmp);
85 int neg = a.sign==MP_NEG?-1:1;
86 if (neg){
87 mp_copy((mp_int*)&a,&res);
88 res.sign=MP_ZPOS;
89 mp_mod(&res,&tmp,&res);
90 }
91 else
92 mp_mod((mp_int *)&a,&tmp,&res);
93 if (res.sign==MP_NEG)
94 mp_add(&res,&tmp,&res);
95 char s[16];
96 mp_toradix(&res,s,10);
97 mp_clear(&tmp);
98 mp_clear(&res);
99 return neg*strtol(s,0,10);
100 #endif
101 } // WARNING
mpz_get_ui(const mpz_t & a)102 inline unsigned mpz_get_ui(const mpz_t & a){
103 #if 1
104 return mp_get_int((mp_int *)&a);
105 #else
106 mp_int tmp,res;
107 mp_init_set_int(&tmp,1<<16); mp_init(&res);
108 mp_mul(&tmp,&tmp,&tmp);
109 mp_mod((mp_int *)&a,&tmp,&res);
110 if (res.sign==MP_NEG)
111 mp_add(&res,&tmp,&res);
112 char s[16];
113 mp_toradix(&res,s,10);
114 mp_clear(&tmp);
115 mp_clear(&res);
116 return strtol(s,0,10);
117 #endif
118 } // WARNING
mpz_gcd_ui(mpz_t * c,const mpz_t & a,unsigned B)119 inline int mpz_gcd_ui(mpz_t * c,const mpz_t & a,unsigned B){
120 mpz_t b; mp_init_set_int(&b,B);
121 mp_mod((mp_int *)&a,&b,&b);
122 int res=mpz_get_ui(b);
123 mp_clear(&b);
124 return gcdint(B,res);
125 }
mpz_set_str(mpz_t & z,const char * s,int base)126 inline int mpz_set_str(mpz_t & z,const char * s,int base){return mp_read_radix(&z,s,base);}
mpz_get_str(char * s,int base,const mpz_t & z)127 inline int mpz_get_str(char * s,int base,const mpz_t & z){return mp_toradix((mp_int *)&z,s,base);}
mpz_get_d(const mpz_t & z)128 inline double mpz_get_d(const mpz_t & z){
129 if (mp_count_bits((mp_int *)&z)>1023) {
130 #ifdef NSPIRE
131 return 1e300/1e-300;
132 #else
133 return std::numeric_limits<double>::infinity();
134 #endif
135 }
136 char s[512];
137 mp_toradix((mp_int *)&z,s,10);
138 #ifdef NSPIRE
139 return Strtod(s,0);
140 #else
141 return strtod(s,0);
142 #endif
143 }
mpz_set_d(mpz_t & z,double d)144 inline void mpz_set_d(mpz_t & z,double d){
145 #if 1
146 unsigned long long u=*(unsigned long long*)(&d);
147 unsigned long long m=u & 0x000fffffffffffffULL;
148 long mh=(1<<24)+(m>>28);
149 long ml=m&0x0fffffff;
150 u >>= 52;
151 int e=u%(1<<11);
152 e -= 1024+51;
153 u >>= 11;
154 if (u)
155 mh=-mh;
156 mpz_set_si(z,mh);
157 mpz_mul_2exp(z,z,28);
158 if (u)
159 mpz_sub_ui(z,z,ml);
160 else
161 mpz_add_ui(z,z,ml);
162 if (e>0)
163 mpz_mul_2exp(z,z,e);
164 if (e<0)
165 mpz_tdiv_q_2exp(z,z,-e);
166 #else
167 char ch[32];
168 sprintf(ch,"%.14g",d);
169 mp_read_radix(&z,ch,10);
170 #endif
171 }
mpz_fac_ui(mpz_t & z,unsigned int i)172 inline void mpz_fac_ui(mpz_t & z,unsigned int i){
173 mpz_set_ui(z,1);
174 for (unsigned long int j=2;j<=i;j++){
175 mpz_mul_ui(z,z,j);
176 }
177 }
mpz_invert(mpz_t & res,const mpz_t & a,const mpz_t & m)178 inline int mpz_invert(mpz_t & res,const mpz_t & a,const mpz_t & m){
179 mp_int v, d;
180 mp_init(&v); mp_init(&d);
181 mp_exteuclid((mp_int *)&a,(mp_int *)&m,&res,&v,&d);
182 int r=!mpz_cmp_ui(d,1);
183 mp_clear(&v); mp_clear(&d);
184 return r;
185 }
186
mpz_probab_prime_p(const mpz_t & a,int)187 inline int mpz_probab_prime_p(const mpz_t & a,int){
188 int result;
189 mp_prime_is_prime((mp_int *)&a, mp_prime_rabin_miller_trials(mp_count_bits((mp_int *)&a)),&result);
190 return result;
191 }
mpz_legendre(const mpz_t & a,const mpz_t & n)192 inline int mpz_legendre(const mpz_t & a,const mpz_t & n){
193 int result;
194 mp_jacobi((mp_int *)&a,(mp_int *)&n,&result);
195 return result;
196 }
mpz_jacobi(const mpz_t & a,const mpz_t & n)197 inline int mpz_jacobi(const mpz_t & a,const mpz_t & n){
198 int result;
199 mp_jacobi((mp_int *)&a,(mp_int *)&n,&result);
200 return result;
201 }
mpz_perfect_square_p(const mpz_t & a)202 inline bool mpz_perfect_square_p(const mpz_t & a){
203 int res;
204 mp_is_square((mp_int *)&a,&res);
205 return res!=0;
206 }
mpz_popcount(const mpz_t & a)207 inline int mpz_popcount(const mpz_t & a){
208 return 0; // FIXME, should be numbers of bits set to 1
209 }
mpz_hamdist(const mpz_t & a,const mpz_t & b)210 inline int mpz_hamdist(const mpz_t & a,const mpz_t & b){
211 mpz_t c;
212 mp_init(&c);
213 mp_xor(&c,(mp_int *) &a,(mp_int *)&b);
214 int res=mpz_popcount(c);
215 mp_clear(&c);
216 return res;
217 }
218
219 #define LONGFLOAT_DOUBLE
220 typedef double mpf_t;
221 #define mpf_clear(x)
222 #define mpf_init(x)
223 #define mpf_init_set(x,y) (x=y)
224 #define mpf_init_set_d(x,y) (x=y)
225 #define mpf_init_set_si(x,y) (x=y)
226 #define mpf_set_z(x,y)
227 #define mpf_set(x,y) (x=y)
mpf_set_str(double & x,const char * s,int base)228 inline int mpf_set_str(double & x,const char * s,int base){ if (base!=10) return 1; x=strtod(s,0); return 0; }
229 #define mpf_get_d(x) (x)
230 #define mpf_add(x,y,z) (x=y+z)
231 #define mpf_sub(x,y,z) (x=y-z)
232 #define mpf_mul(x,y,z) (x=y*z)
233 #define mpf_neg(x,y) (x=-y)
234 #define mpf_ui_div(z,x,y) (z=x/y)
235 #define mpf_sqrt(x,y) (x=sqrt(y))
236 #define mpf_sgn(x) (x>0?1:-1)
237