[255eaa] | 1 | /**************************************** |
---|
| 2 | * Computer Algebra System SINGULAR * |
---|
| 3 | ****************************************/ |
---|
[3ad53dd] | 4 | /* $Id: rintegers.cc,v 1.12 2008-04-18 13:32:53 wienand Exp $ */ |
---|
[255eaa] | 5 | /* |
---|
| 6 | * ABSTRACT: numbers modulo n |
---|
| 7 | */ |
---|
| 8 | |
---|
| 9 | #include <string.h> |
---|
| 10 | #include "mod2.h" |
---|
| 11 | #include <mylimits.h> |
---|
| 12 | #include "structs.h" |
---|
| 13 | #include "febase.h" |
---|
| 14 | #include "omalloc.h" |
---|
| 15 | #include "numbers.h" |
---|
| 16 | #include "longrat.h" |
---|
| 17 | #include "mpr_complex.h" |
---|
| 18 | #include "ring.h" |
---|
[8e56ad] | 19 | #include "rintegers.h" |
---|
[255eaa] | 20 | #include "gmp.h" |
---|
| 21 | |
---|
| 22 | #ifdef HAVE_RINGZ |
---|
| 23 | |
---|
[1e579c6] | 24 | typedef MP_INT *int_number; |
---|
[bac8611] | 25 | omBin gmp_nrz_bin = omGetSpecBin(sizeof(MP_INT)); |
---|
[1e579c6] | 26 | |
---|
[255eaa] | 27 | /* |
---|
| 28 | * Multiply two numbers |
---|
| 29 | */ |
---|
| 30 | number nrzMult (number a, number b) |
---|
| 31 | { |
---|
[bac8611] | 32 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
[255eaa] | 33 | mpz_init(erg); |
---|
[1e579c6] | 34 | mpz_mul(erg, (int_number) a, (int_number) b); |
---|
[255eaa] | 35 | return (number) erg; |
---|
| 36 | } |
---|
| 37 | |
---|
| 38 | /* |
---|
| 39 | * Give the smallest non unit k, such that a * x = k = b * y has a solution |
---|
| 40 | */ |
---|
| 41 | number nrzLcm (number a,number b,ring r) |
---|
| 42 | { |
---|
[bac8611] | 43 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
[255eaa] | 44 | mpz_init(erg); |
---|
[1e579c6] | 45 | mpz_lcm(erg, (int_number) a, (int_number) b); |
---|
| 46 | return (number) erg; |
---|
[255eaa] | 47 | } |
---|
| 48 | |
---|
| 49 | /* |
---|
| 50 | * Give the largest non unit k, such that a = x * k, b = y * k has |
---|
| 51 | * a solution. |
---|
| 52 | */ |
---|
| 53 | number nrzGcd (number a,number b,ring r) |
---|
| 54 | { |
---|
[bac8611] | 55 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
[1e579c6] | 56 | mpz_init(erg); |
---|
| 57 | mpz_gcd(erg, (int_number) a, (int_number) b); |
---|
| 58 | return (number) erg; |
---|
| 59 | } |
---|
| 60 | |
---|
| 61 | /* |
---|
| 62 | * Give the largest non unit k, such that a = x * k, b = y * k has |
---|
| 63 | * a solution and r, s, s.t. k = s*a + t*b |
---|
| 64 | */ |
---|
| 65 | number nrzExtGcd (number a, number b, number *s, number *t) |
---|
| 66 | { |
---|
[bac8611] | 67 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
| 68 | int_number bs = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
| 69 | int_number bt = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
[255eaa] | 70 | mpz_init(erg); |
---|
[1e579c6] | 71 | mpz_init(bs); |
---|
| 72 | mpz_init(bt); |
---|
| 73 | mpz_gcdext(erg, bs, bt, (int_number) a, (int_number) b); |
---|
| 74 | *s = (number) bs; |
---|
| 75 | *t = (number) bt; |
---|
| 76 | return (number) erg; |
---|
[255eaa] | 77 | } |
---|
| 78 | |
---|
| 79 | void nrzPower (number a, int i, number * result) |
---|
| 80 | { |
---|
[bac8611] | 81 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
[255eaa] | 82 | mpz_init(erg); |
---|
[1e579c6] | 83 | mpz_pow_ui(erg, (int_number) a, i); |
---|
| 84 | *result = (number) erg; |
---|
[255eaa] | 85 | } |
---|
| 86 | |
---|
| 87 | /* |
---|
| 88 | * create a number from int |
---|
| 89 | */ |
---|
| 90 | number nrzInit (int i) |
---|
| 91 | { |
---|
[bac8611] | 92 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
[255eaa] | 93 | mpz_init_set_si(erg, i); |
---|
| 94 | return (number) erg; |
---|
| 95 | } |
---|
| 96 | |
---|
[1e579c6] | 97 | void nrzDelete(number *a, const ring r) |
---|
| 98 | { |
---|
[befecbc] | 99 | if (*a == NULL) return; |
---|
[1e579c6] | 100 | mpz_clear((int_number) *a); |
---|
[bac8611] | 101 | omFreeBin((ADDRESS) *a, gmp_nrz_bin); |
---|
[befecbc] | 102 | *a = NULL; |
---|
[bac8611] | 103 | } |
---|
| 104 | |
---|
| 105 | number nrzCopy(number a) |
---|
| 106 | { |
---|
| 107 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
| 108 | mpz_init_set(erg, (int_number) a); |
---|
| 109 | return (number) erg; |
---|
| 110 | } |
---|
| 111 | |
---|
| 112 | number cfrzCopy(number a, const ring r) |
---|
| 113 | { |
---|
| 114 | return nrzCopy(a); |
---|
| 115 | } |
---|
| 116 | |
---|
| 117 | int nrzSize(number a) |
---|
| 118 | { |
---|
| 119 | if (a == NULL) return 0; |
---|
| 120 | return sizeof(MP_INT); |
---|
[1e579c6] | 121 | } |
---|
| 122 | |
---|
[255eaa] | 123 | /* |
---|
| 124 | * convert a number to int (-p/2 .. p/2) |
---|
| 125 | */ |
---|
| 126 | int nrzInt(number &n) |
---|
| 127 | { |
---|
[230e188] | 128 | return (int) mpz_get_si( (int_number) &n); |
---|
[255eaa] | 129 | } |
---|
| 130 | |
---|
| 131 | number nrzAdd (number a, number b) |
---|
| 132 | { |
---|
[bac8611] | 133 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
[255eaa] | 134 | mpz_init(erg); |
---|
[1e579c6] | 135 | mpz_add(erg, (int_number) a, (int_number) b); |
---|
[255eaa] | 136 | return (number) erg; |
---|
| 137 | } |
---|
| 138 | |
---|
| 139 | number nrzSub (number a, number b) |
---|
| 140 | { |
---|
[bac8611] | 141 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
[255eaa] | 142 | mpz_init(erg); |
---|
[1e579c6] | 143 | mpz_sub(erg, (int_number) a, (int_number) b); |
---|
| 144 | return (number) erg; |
---|
| 145 | } |
---|
| 146 | |
---|
| 147 | number nrzGetUnit (number a) |
---|
| 148 | { |
---|
[97c4ad] | 149 | return nrzInit(1); |
---|
[255eaa] | 150 | } |
---|
| 151 | |
---|
[1e579c6] | 152 | BOOLEAN nrzIsUnit (number a) |
---|
| 153 | { |
---|
| 154 | return 0 == mpz_cmpabs_ui((int_number) a, 1); |
---|
| 155 | } |
---|
| 156 | |
---|
[255eaa] | 157 | BOOLEAN nrzIsZero (number a) |
---|
| 158 | { |
---|
[1e579c6] | 159 | return 0 == mpz_cmpabs_ui((int_number) a, 0); |
---|
[255eaa] | 160 | } |
---|
| 161 | |
---|
| 162 | BOOLEAN nrzIsOne (number a) |
---|
| 163 | { |
---|
[8e56ad] | 164 | return 0 == mpz_cmp_si((int_number) a, 1); |
---|
[b18621] | 165 | } |
---|
| 166 | |
---|
| 167 | BOOLEAN nrzIsMOne (number a) |
---|
| 168 | { |
---|
| 169 | return 0 == mpz_cmp_si((int_number) a, -1); |
---|
[255eaa] | 170 | } |
---|
| 171 | |
---|
| 172 | BOOLEAN nrzEqual (number a,number b) |
---|
| 173 | { |
---|
[1e579c6] | 174 | return 0 == mpz_cmp((int_number) a, (int_number) b); |
---|
[255eaa] | 175 | } |
---|
| 176 | |
---|
| 177 | BOOLEAN nrzGreater (number a,number b) |
---|
| 178 | { |
---|
[1e579c6] | 179 | return 0 < mpz_cmp((int_number) a, (int_number) b); |
---|
[255eaa] | 180 | } |
---|
| 181 | |
---|
[b18621] | 182 | BOOLEAN nrzGreaterZero (number k) |
---|
| 183 | { |
---|
| 184 | return 0 <= mpz_cmp_si((int_number) k, 0); |
---|
| 185 | } |
---|
| 186 | |
---|
[255eaa] | 187 | int nrzComp(number a, number b) |
---|
| 188 | { |
---|
[8e56ad] | 189 | if (nrzEqual(a, b)) return 0; |
---|
| 190 | if (nrzDivBy(a, b)) return -1; |
---|
| 191 | if (nrzDivBy(b, a)) return 1; |
---|
[1e579c6] | 192 | return 2; |
---|
[255eaa] | 193 | } |
---|
| 194 | |
---|
| 195 | BOOLEAN nrzDivBy (number a,number b) |
---|
| 196 | { |
---|
[8e56ad] | 197 | return mpz_divisible_p((int_number) a, (int_number) b) != 0; |
---|
[255eaa] | 198 | } |
---|
| 199 | |
---|
| 200 | number nrzDiv (number a,number b) |
---|
| 201 | { |
---|
[bac8611] | 202 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
| 203 | int_number r = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
[1e579c6] | 204 | mpz_init(erg); |
---|
| 205 | mpz_tdiv_qr(erg, r, (int_number) a, (int_number) b); |
---|
| 206 | if (!nrzIsZero((number) r)) |
---|
| 207 | { |
---|
| 208 | WarnS("Division by non divisible element."); |
---|
| 209 | WarnS("Result is without remainder."); |
---|
| 210 | } |
---|
| 211 | mpz_clear(r); |
---|
[bac8611] | 212 | omFreeBin(r, gmp_nrz_bin); |
---|
[1e579c6] | 213 | return (number) erg; |
---|
[255eaa] | 214 | } |
---|
| 215 | |
---|
| 216 | number nrzIntDiv (number a,number b) |
---|
| 217 | { |
---|
[bac8611] | 218 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
[1e579c6] | 219 | mpz_init(erg); |
---|
| 220 | mpz_tdiv_q(erg, (int_number) a, (int_number) b); |
---|
| 221 | return (number) erg; |
---|
[255eaa] | 222 | } |
---|
| 223 | |
---|
| 224 | number nrzInvers (number c) |
---|
| 225 | { |
---|
[1e579c6] | 226 | if (!nrzIsUnit((number) c)) |
---|
| 227 | { |
---|
| 228 | WarnS("Non invertible element."); |
---|
| 229 | return (number)0; //TODO |
---|
| 230 | } |
---|
[bac8611] | 231 | return c; |
---|
[255eaa] | 232 | } |
---|
| 233 | |
---|
| 234 | number nrzNeg (number c) |
---|
| 235 | { |
---|
[a539ad] | 236 | // nNeg inplace !!! TODO |
---|
| 237 | // int_number erg = (int_number) omAllocBin(gmp_nrn_bin); // evtl. spaeter mit bin |
---|
| 238 | // mpz_init(erg); |
---|
| 239 | mpz_mul_si((int_number) c, (int_number) c, -1); |
---|
| 240 | return c; |
---|
[255eaa] | 241 | } |
---|
| 242 | |
---|
| 243 | nMapFunc nrzSetMap(ring src, ring dst) |
---|
| 244 | { |
---|
| 245 | return NULL; /* default */ |
---|
| 246 | } |
---|
| 247 | |
---|
| 248 | |
---|
| 249 | /* |
---|
| 250 | * set the exponent (allocate and init tables) (TODO) |
---|
| 251 | */ |
---|
| 252 | |
---|
| 253 | void nrzSetExp(int m, ring r) |
---|
| 254 | { |
---|
| 255 | } |
---|
| 256 | |
---|
| 257 | void nrzInitExp(int m, ring r) |
---|
| 258 | { |
---|
| 259 | } |
---|
| 260 | |
---|
| 261 | #ifdef LDEBUG |
---|
[85e68dd] | 262 | //BOOLEAN nrzDBTest (number a, const char *f, const int l) |
---|
| 263 | //{ |
---|
| 264 | // return TRUE;//TODO |
---|
| 265 | //} |
---|
[255eaa] | 266 | #endif |
---|
| 267 | |
---|
| 268 | void nrzWrite (number &a) |
---|
| 269 | { |
---|
[1e579c6] | 270 | char *s,*z; |
---|
| 271 | if (a==NULL) |
---|
| 272 | { |
---|
| 273 | StringAppendS("o"); |
---|
| 274 | } |
---|
| 275 | else |
---|
| 276 | { |
---|
| 277 | int l=mpz_sizeinbase((int_number) a, 10); |
---|
| 278 | if (a->s<2) l=si_max(l,mpz_sizeinbase((int_number) a,10)); |
---|
| 279 | l+=2; |
---|
| 280 | s=(char*)omAlloc(l); |
---|
| 281 | z=mpz_get_str(s,10,(int_number) a); |
---|
| 282 | StringAppendS(z); |
---|
| 283 | omFreeSize((ADDRESS)s,l); |
---|
| 284 | } |
---|
[255eaa] | 285 | } |
---|
| 286 | |
---|
[1e579c6] | 287 | /*2 |
---|
| 288 | * extracts a long integer from s, returns the rest (COPY FROM longrat0.cc) |
---|
| 289 | */ |
---|
[3ad53dd] | 290 | static const char * nlEatLongC(char *s, MP_INT *i) |
---|
[255eaa] | 291 | { |
---|
[3ad53dd] | 292 | const char * start=s; |
---|
| 293 | |
---|
[1e579c6] | 294 | while (*s >= '0' && *s <= '9') s++; |
---|
| 295 | if (*s=='\0') |
---|
[255eaa] | 296 | { |
---|
[1e579c6] | 297 | mpz_set_str(i,start,10); |
---|
| 298 | } |
---|
| 299 | else |
---|
| 300 | { |
---|
| 301 | char c=*s; |
---|
| 302 | *s='\0'; |
---|
| 303 | mpz_set_str(i,start,10); |
---|
| 304 | *s=c; |
---|
[255eaa] | 305 | } |
---|
| 306 | return s; |
---|
| 307 | } |
---|
| 308 | |
---|
[3ad53dd] | 309 | const char * nrzRead (const char *s, number *a) |
---|
[255eaa] | 310 | { |
---|
[bac8611] | 311 | int_number z = (int_number) omAllocBin(gmp_nrz_bin); // evtl. spaeter mit bin |
---|
[255eaa] | 312 | { |
---|
[1e579c6] | 313 | mpz_init(z); |
---|
[3ad53dd] | 314 | s = nlEatLongC((char *) s, z); |
---|
[255eaa] | 315 | } |
---|
[1e579c6] | 316 | *a = (number) z; |
---|
[255eaa] | 317 | return s; |
---|
| 318 | } |
---|
[1e579c6] | 319 | #endif |
---|