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