My Project
Loading...
Searching...
No Matches
bigintmat.cc File Reference
#include "misc/auxiliary.h"
#include "coeffs/bigintmat.h"
#include "misc/intvec.h"
#include "coeffs/rmodulon.h"
#include <cmath>

Go to the source code of this file.

Macros

#define swap(_i, _j)
 
#define MIN(a, b)
 

Functions

static coeffs numbercoeffs (number n, coeffs c)
 create Z/nA of type n_Zn
 
bool operator== (const bigintmat &lhr, const bigintmat &rhr)
 
bool operator!= (const bigintmat &lhr, const bigintmat &rhr)
 
bigintmatbimAdd (bigintmat *a, bigintmat *b)
 Matrix-Add/-Sub/-Mult so oder mit operator+/-/* ? @Note: NULL as a result means an error (non-compatible matrices?)
 
bigintmatbimAdd (bigintmat *a, long b)
 
bigintmatbimSub (bigintmat *a, bigintmat *b)
 
bigintmatbimSub (bigintmat *a, long b)
 
bigintmatbimMult (bigintmat *a, bigintmat *b)
 
bigintmatbimMult (bigintmat *a, long b)
 
bigintmatbimMult (bigintmat *a, number b, const coeffs cf)
 
intvecbim2iv (bigintmat *b)
 
bigintmativ2bim (intvec *b, const coeffs C)
 
bigintmatbimCopy (const bigintmat *b)
 same as copy constructor - apart from it being able to accept NULL as input
 
static int intArrSum (int *a, int length)
 
static int findLongest (int *a, int length)
 
static int getShorter (int *a, int l, int j, int cols, int rows)
 
bigintmatbimChangeCoeff (bigintmat *a, coeffs cnew)
 Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.
 
void bimMult (bigintmat *a, bigintmat *b, bigintmat *c)
 Multipliziert Matrix a und b und speichert Ergebnis in c.
 
static void reduce_mod_howell (bigintmat *A, bigintmat *b, bigintmat *eps, bigintmat *x)
 
static bigintmatprependIdentity (bigintmat *A)
 
static number bimFarey (bigintmat *A, number N, bigintmat *L)
 
static number solveAx_dixon (bigintmat *A, bigintmat *B, bigintmat *x, bigintmat *kern)
 
static number solveAx_howell (bigintmat *A, bigintmat *b, bigintmat *x, bigintmat *kern)
 
number solveAx (bigintmat *A, bigintmat *b, bigintmat *x)
 solve Ax=b*d. x needs to be pre-allocated to the same number of columns as b. the minimal denominator d is returned. Currently available for Z, Q and Z/nZ (and possibly for all fields: d=1 there) Beware that the internal functions can find the kernel as well - but the interface is lacking.
 
void diagonalForm (bigintmat *A, bigintmat **S, bigintmat **T)
 
int kernbase (bigintmat *a, bigintmat *c, number p, coeffs q)
 a basis for the nullspace of a mod p: only used internally in Round2. Don't use it.
 
bool nCoeffs_are_equal (coeffs r, coeffs s)
 

Macro Definition Documentation

◆ MIN

#define MIN ( a,
b )
Value:
(a < b ? a : b)
CanonicalForm b
Definition cfModGcd.cc:4111

◆ swap

#define swap ( _i,
_j )
Value:
int __i = (_i), __j=(_j); \
number c = v[__i]; \
v[__i] = v[__j]; \
v[__j] = c \
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39

Function Documentation

◆ bim2iv()

intvec * bim2iv ( bigintmat * b)

Definition at line 339 of file bigintmat.cc.

340{
341 intvec * iv = new intvec(b->rows(), b->cols(), 0);
342 for (int i=0; i<(b->rows())*(b->cols()); i++)
343 (*iv)[i] = n_Int((*b)[i], b->basecoeffs()); // Geht das so?
344 return iv;
345}
int i
Definition cfEzgcd.cc:132
static FORCE_INLINE long n_Int(number &n, const coeffs r)
conversion of n to an int; 0 if not possible in Z/pZ: the representing int lying in (-p/2 ....
Definition coeffs.h:548

◆ bimAdd() [1/2]

bigintmat * bimAdd ( bigintmat * a,
bigintmat * b )

Matrix-Add/-Sub/-Mult so oder mit operator+/-/* ? @Note: NULL as a result means an error (non-compatible matrices?)

Definition at line 180 of file bigintmat.cc.

181{
182 if (a->cols() != b->cols()) return NULL;
183 if (a->rows() != b->rows()) return NULL;
184 if (a->basecoeffs() != b->basecoeffs()) { return NULL; }
185
186 const coeffs basecoeffs = a->basecoeffs();
187
188 int i;
189
190 bigintmat * bim = new bigintmat(a->rows(), a->cols(), basecoeffs);
191
192 for (i=a->rows()*a->cols()-1;i>=0; i--)
193 bim->rawset(i, n_Add((*a)[i], (*b)[i], basecoeffs), basecoeffs);
194
195 return bim;
196}
Matrices of numbers.
Definition bigintmat.h:51
int cols() const
Definition bigintmat.h:144
int rows() const
Definition bigintmat.h:145
void rawset(int i, number n, const coeffs C=NULL)
replace an entry with the given number n (only delete old). NOTE: starts at [0]. Should be named set_...
Definition bigintmat.h:196
coeffs basecoeffs() const
Definition bigintmat.h:146
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of 'a' and 'b', i.e., a+b
Definition coeffs.h:651
The main handler for Singular numbers which are suitable for Singular polynomials.
#define NULL
Definition omList.c:12

◆ bimAdd() [2/2]

bigintmat * bimAdd ( bigintmat * a,
long b )

Definition at line 197 of file bigintmat.cc.

198{
199
200 const int mn = si_min(a->rows(),a->cols());
201
202 const coeffs basecoeffs = a->basecoeffs();
203 number bb=n_Init(b,basecoeffs);
204
205 int i;
206
207 bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
208
209 for (i=1; i<=mn; i++)
210 BIMATELEM(*bim,i,i)=n_Add(BIMATELEM(*a,i,i), bb, basecoeffs);
211
212 n_Delete(&bb,basecoeffs);
213 return bim;
214}
static int si_min(const int a, const int b)
Definition auxiliary.h:126
#define BIMATELEM(M, I, J)
Definition bigintmat.h:133
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:459
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition coeffs.h:539

◆ bimChangeCoeff()

bigintmat * bimChangeCoeff ( bigintmat * a,
coeffs cnew )

Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.

Definition at line 1797 of file bigintmat.cc.

1798{
1799 coeffs cold = a->basecoeffs();
1800 bigintmat *b = new bigintmat(a->rows(), a->cols(), cnew);
1801 // Erzeugt Karte von alten coeffs nach neuen
1802 nMapFunc f = n_SetMap(cold, cnew);
1803 number t1;
1804 number t2;
1805 // apply map to all entries.
1806 for (int i=1; i<=a->rows(); i++)
1807 {
1808 for (int j=1; j<=a->cols(); j++)
1809 {
1810 t1 = a->get(i, j);
1811 t2 = f(t1, cold, cnew);
1812 b->set(i, j, t2);
1813 n_Delete(&t1, cold);
1814 n_Delete(&t2, cnew);
1815 }
1816 }
1817 return b;
1818}
FILE * f
Definition checklibs.c:9
number get(int i, int j) const
get a copy of an entry. NOTE: starts at [1,1]
Definition bigintmat.cc:117
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition coeffs.h:701
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition coeffs.h:80
int j
Definition facHensel.cc:110

◆ bimCopy()

bigintmat * bimCopy ( const bigintmat * b)

same as copy constructor - apart from it being able to accept NULL as input

Definition at line 403 of file bigintmat.cc.

404{
405 if (b == NULL)
406 return NULL;
407
408 return new bigintmat(b);
409}

◆ bimFarey()

static number bimFarey ( bigintmat * A,
number N,
bigintmat * L )
static

Definition at line 2038 of file bigintmat.cc.

2039{
2040 coeffs Z = A->basecoeffs(),
2041 Q = nInitChar(n_Q, 0);
2042 number den = n_Init(1, Z);
2043 nMapFunc f = n_SetMap(Q, Z);
2044
2045 for(int i=1; i<= A->rows(); i++)
2046 {
2047 for(int j=1; j<= A->cols(); j++)
2048 {
2049 number ad = n_Mult(den, A->view(i, j), Z);
2050 number re = n_IntMod(ad, N, Z);
2051 n_Delete(&ad, Z);
2052 number q = n_Farey(re, N, Z);
2053 n_Delete(&re, Z);
2054 if (!q)
2055 {
2056 n_Delete(&ad, Z);
2057 n_Delete(&den, Z);
2058 return NULL;
2059 }
2060
2061 number d = n_GetDenom(q, Q),
2062 n = n_GetNumerator(q, Q);
2063
2064 n_Delete(&q, Q);
2065 n_Delete(&ad, Z);
2066 number dz = f(d, Q, Z),
2067 nz = f(n, Q, Z);
2068 n_Delete(&d, Q);
2069 n_Delete(&n, Q);
2070
2071 if (!n_IsOne(dz, Z))
2072 {
2073 L->skalmult(dz, Z);
2074 n_InpMult(den, dz, Z);
2075#if 0
2076 PrintS("den increasing to ");
2077 n_Print(den, Z);
2078 PrintLn();
2079#endif
2080 }
2081 n_Delete(&dz, Z);
2082 L->rawset(i, j, nz);
2083 }
2084 }
2085
2086 nKillChar(Q);
2087 PrintS("bimFarey worked\n");
2088#if 0
2089 L->Print();
2090 PrintS("\n * 1/");
2091 n_Print(den, Z);
2092 PrintLn();
2093#endif
2094 return den;
2095}
CanonicalForm den(const CanonicalForm &f)
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition bigintmat.cc:437
bool skalmult(number b, coeffs c)
Multipliziert zur Matrix den Skalar b hinzu.
Definition bigintmat.cc:933
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition coeffs.h:637
static FORCE_INLINE number n_GetDenom(number &n, const coeffs r)
return the denominator of n (if elements of r are by nature not fractional, result is 1)
Definition coeffs.h:604
@ n_Q
rational (GMP) numbers
Definition coeffs.h:30
void n_Print(number &a, const coeffs r)
print a number (BEWARE of string buffers!) mostly for debugging
Definition numbers.cc:655
static FORCE_INLINE number n_Farey(number a, number b, const coeffs r)
Definition coeffs.h:760
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition numbers.cc:406
static FORCE_INLINE number n_IntMod(number a, number b, const coeffs r)
for r a field, return n_Init(0,r) always: n_Div(a,b,r)*b+n_IntMod(a,b,r)==a n_IntMod(a,...
Definition coeffs.h:629
static FORCE_INLINE void n_InpMult(number &a, number b, const coeffs r)
multiplication of 'a' and 'b'; replacement of 'a' by the product a*b
Definition coeffs.h:642
static FORCE_INLINE number n_GetNumerator(number &n, const coeffs r)
return the numerator of n (if elements of r are by nature not fractional, result is n)
Definition coeffs.h:609
void nKillChar(coeffs r)
undo all initialisations
Definition numbers.cc:556
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition coeffs.h:472
void PrintS(const char *s)
Definition reporter.cc:284
void PrintLn()
Definition reporter.cc:310
#define A
Definition sirandom.c:24
#define Q
Definition sirandom.c:26

◆ bimMult() [1/4]

bigintmat * bimMult ( bigintmat * a,
bigintmat * b )

Definition at line 253 of file bigintmat.cc.

254{
255 const int ca = a->cols();
256 const int cb = b->cols();
257
258 const int ra = a->rows();
259 const int rb = b->rows();
260
261 if (ca != rb)
262 {
263#ifndef SING_NDEBUG
264 Werror("wrong bigintmat sizes at multiplication a * b: acols: %d != brows: %d\n", ca, rb);
265#endif
266 return NULL;
267 }
268
269 assume (ca == rb);
270
271 if (a->basecoeffs() != b->basecoeffs()) { return NULL; }
272
273 const coeffs basecoeffs = a->basecoeffs();
274
275 int i, j, k;
276
277 number sum;
278
279 bigintmat * bim = new bigintmat(ra, cb, basecoeffs);
280
281 for (i=1; i<=ra; i++)
282 for (j=1; j<=cb; j++)
283 {
284 sum = n_Init(0, basecoeffs);
285
286 for (k=1; k<=ca; k++)
287 {
288 number prod = n_Mult( BIMATELEM(*a, i, k), BIMATELEM(*b, k, j), basecoeffs);
289
290 n_InpAdd(sum, prod, basecoeffs);
291
292 n_Delete(&prod, basecoeffs);
293 }
294 bim->rawset(i, j, sum, basecoeffs);
295 }
296 return bim;
297}
int k
Definition cfEzgcd.cc:99
static FORCE_INLINE void n_InpAdd(number &a, number b, const coeffs r)
addition of 'a' and 'b'; replacement of 'a' by the sum a+b
Definition coeffs.h:647
fq_nmod_poly_t prod
Definition facHensel.cc:100
#define assume(x)
Definition mod2.h:389
void Werror(const char *fmt,...)
Definition reporter.cc:189

◆ bimMult() [2/4]

void bimMult ( bigintmat * a,
bigintmat * b,
bigintmat * c )

Multipliziert Matrix a und b und speichert Ergebnis in c.

Definition at line 1922 of file bigintmat.cc.

1923{
1924 if (!nCoeffs_are_equal(a->basecoeffs(), b->basecoeffs()))
1925 {
1926 WerrorS("Error in bimMult. Coeffs do not agree!");
1927 return;
1928 }
1929 if ((a->rows() != c->rows()) || (b->cols() != c->cols()) || (a->cols() != b->rows()))
1930 {
1931 WerrorS("Error in bimMult. Dimensions do not agree!");
1932 return;
1933 }
1934 bigintmat *tmp = bimMult(a, b);
1935 c->copy(tmp);
1936
1937 delete tmp;
1938}
bool nCoeffs_are_equal(coeffs r, coeffs s)
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition bigintmat.cc:253
bool copy(bigintmat *b)
Kopiert Einträge von b auf Bigintmat.
void WerrorS(const char *s)
Definition feFopen.cc:24

◆ bimMult() [3/4]

bigintmat * bimMult ( bigintmat * a,
long b )

Definition at line 299 of file bigintmat.cc.

300{
301
302 const int mn = a->rows()*a->cols();
303
304 const coeffs basecoeffs = a->basecoeffs();
305 number bb=n_Init(b,basecoeffs);
306
307 int i;
308
309 bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
310
311 for (i=0; i<mn; i++)
312 bim->rawset(i, n_Mult((*a)[i], bb, basecoeffs), basecoeffs);
313
314 n_Delete(&bb,basecoeffs);
315 return bim;
316}

◆ bimMult() [4/4]

bigintmat * bimMult ( bigintmat * a,
number b,
const coeffs cf )

Definition at line 318 of file bigintmat.cc.

319{
320 if (cf!=a->basecoeffs()) return NULL;
321
322 const int mn = a->rows()*a->cols();
323
324 const coeffs basecoeffs = a->basecoeffs();
325
326 int i;
327
328 bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
329
330 for (i=0; i<mn; i++)
331 bim->rawset(i, n_Mult((*a)[i], b, basecoeffs), basecoeffs);
332
333 return bim;
334}
CanonicalForm cf
Definition cfModGcd.cc:4091

◆ bimSub() [1/2]

bigintmat * bimSub ( bigintmat * a,
bigintmat * b )

Definition at line 216 of file bigintmat.cc.

217{
218 if (a->cols() != b->cols()) return NULL;
219 if (a->rows() != b->rows()) return NULL;
220 if (a->basecoeffs() != b->basecoeffs()) { return NULL; }
221
222 const coeffs basecoeffs = a->basecoeffs();
223
224 int i;
225
226 bigintmat * bim = new bigintmat(a->rows(), a->cols(), basecoeffs);
227
228 for (i=a->rows()*a->cols()-1;i>=0; i--)
229 bim->rawset(i, n_Sub((*a)[i], (*b)[i], basecoeffs), basecoeffs);
230
231 return bim;
232}
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
Definition coeffs.h:656

◆ bimSub() [2/2]

bigintmat * bimSub ( bigintmat * a,
long b )

Definition at line 234 of file bigintmat.cc.

235{
236 const int mn = si_min(a->rows(),a->cols());
237
238 const coeffs basecoeffs = a->basecoeffs();
239 number bb=n_Init(b,basecoeffs);
240
241 int i;
242
243 bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
244
245 for (i=1; i<=mn; i++)
246 BIMATELEM(*bim,i,i)=n_Sub(BIMATELEM(*a,i,i), bb, basecoeffs);
247
248 n_Delete(&bb,basecoeffs);
249 return bim;
250}

◆ diagonalForm()

void diagonalForm ( bigintmat * A,
bigintmat ** S,
bigintmat ** T )

Definition at line 2461 of file bigintmat.cc.

2462{
2463 bigintmat * t, *s, *a=A;
2464 coeffs R = a->basecoeffs();
2465 if (T)
2466 {
2467 *T = new bigintmat(a->cols(), a->cols(), R),
2468 (*T)->one();
2469 t = new bigintmat(*T);
2470 }
2471 else
2472 {
2473 t = *T;
2474 }
2475
2476 if (S)
2477 {
2478 *S = new bigintmat(a->rows(), a->rows(), R);
2479 (*S)->one();
2480 s = new bigintmat(*S);
2481 }
2482 else
2483 {
2484 s = *S;
2485 }
2486
2487 int flip=0;
2488 do
2489 {
2490 bigintmat * x, *X;
2491 if (flip)
2492 {
2493 x = s;
2494 X = *S;
2495 }
2496 else
2497 {
2498 x = t;
2499 X = *T;
2500 }
2501
2502 if (x)
2503 {
2504 x->one();
2505 bigintmat * r = new bigintmat(a->rows()+a->cols(), a->cols(), R);
2506 bigintmat * rw = new bigintmat(1, a->cols(), R);
2507 for(int i=0; i<a->cols(); i++)
2508 {
2509 x->getrow(i+1, rw);
2510 r->setrow(i+1, rw);
2511 }
2512 for (int i=0; i<a->rows(); i++)
2513 {
2514 a->getrow(i+1, rw);
2515 r->setrow(i+a->cols()+1, rw);
2516 }
2517 r->hnf();
2518 for(int i=0; i<a->cols(); i++)
2519 {
2520 r->getrow(i+1, rw);
2521 x->setrow(i+1, rw);
2522 }
2523 for(int i=0; i<a->rows(); i++)
2524 {
2525 r->getrow(i+a->cols()+1, rw);
2526 a->setrow(i+1, rw);
2527 }
2528 delete rw;
2529 delete r;
2530
2531#if 0
2532 Print("X: %ld\n", X);
2533 X->Print();
2534 Print("\nx: %ld\n", x);
2535 x->Print();
2536#endif
2537 bimMult(X, x, X);
2538#if 0
2539 Print("\n2:X: %ld %ld %ld\n", X, *S, *T);
2540 X->Print();
2541 Print("\n2:x: %ld\n", x);
2542 x->Print();
2543 PrintLn();
2544#endif
2545 }
2546 else
2547 {
2548 a->hnf();
2549 }
2550
2551 int diag = 1;
2552 for(int i=a->rows(); diag && i>0; i--)
2553 {
2554 for(int j=a->cols(); j>0; j--)
2555 {
2556 if ((a->rows()-i)!=(a->cols()-j) && !n_IsZero(a->view(i, j), R))
2557 {
2558 diag = 0;
2559 break;
2560 }
2561 }
2562 }
2563#if 0
2564 PrintS("Diag ? %d\n", diag);
2565 a->Print();
2566 PrintLn();
2567#endif
2568 if (diag) break;
2569
2570 a = a->transpose(); // leaks - I need to write inpTranspose
2571 flip = 1-flip;
2572 } while (1);
2573 if (flip)
2574 a = a->transpose();
2575
2576 if (S) *S = (*S)->transpose();
2577 if (s) delete s;
2578 if (t) delete t;
2579 A->copy(a);
2580}
Variable x
Definition cfModGcd.cc:4090
void hnf()
transforms INPLACE to HNF
bigintmat * transpose()
Definition bigintmat.cc:35
void setrow(int i, bigintmat *m)
Setzt i-te Zeile gleich übergebenem Vektor (Matrix) m.
Definition bigintmat.cc:855
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition bigintmat.cc:125
void one()
Macht Matrix (Falls quadratisch) zu Einheitsmatrix.
void getrow(int i, bigintmat *a)
Schreibt i-te Zeile in Vektor (Matrix) a.
Definition bigintmat.cc:786
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition coeffs.h:468
#define Print
Definition emacs.cc:80
const CanonicalForm int s
Definition facAbsFact.cc:51
std::pair< ideal, ring > flip(const ideal I, const ring r, const gfan::ZVector interiorPoint, const gfan::ZVector facetNormal, const gfan::ZVector adjustedInteriorPoint, const gfan::ZVector adjustedFacetNormal)
Definition flip.cc:17
STATIC_VAR jList * T
Definition janet.cc:30
#define R
Definition sirandom.c:27

◆ findLongest()

static int findLongest ( int * a,
int length )
static

Definition at line 531 of file bigintmat.cc.

532{
533 int l = 0;
534 int index;
535 for (int i=0; i<length; i++)
536 {
537 if (a[i] > l)
538 {
539 l = a[i];
540 index = i;
541 }
542 }
543 return index;
544}
int l
Definition cfEzgcd.cc:100
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
static int index(p_Length length, p_Ord ord)

◆ getShorter()

static int getShorter ( int * a,
int l,
int j,
int cols,
int rows )
static

Definition at line 546 of file bigintmat.cc.

547{
548 int sndlong = 0;
549 int min;
550 for (int i=0; i<rows; i++)
551 {
552 int index = cols*i+j;
553 if ((a[index] > sndlong) && (a[index] < l))
554 {
555 min = floor(log10((double)cols))+floor(log10((double)rows))+5;
556 if ((a[index] < min) && (min < l))
557 sndlong = min;
558 else
559 sndlong = a[index];
560 }
561 }
562 if (sndlong == 0)
563 {
564 min = floor(log10((double)cols))+floor(log10((double)rows))+5;
565 if (min < l)
566 sndlong = min;
567 else
568 sndlong = 1;
569 }
570 return sndlong;
571}
static int min(int a, int b)
Definition fast_mult.cc:268
const signed long floor(const ampf< Precision > &x)
Definition amp.h:773
const ampf< Precision > log10(const ampf< Precision > &x)
Definition amp.h:1022

◆ intArrSum()

static int intArrSum ( int * a,
int length )
static

Definition at line 523 of file bigintmat.cc.

524{
525 int sum = 0;
526 for (int i=0; i<length; i++)
527 sum += a[i];
528 return sum;
529}

◆ iv2bim()

bigintmat * iv2bim ( intvec * b,
const coeffs C )

Definition at line 347 of file bigintmat.cc.

348{
349 const int l = (b->rows())*(b->cols());
350 bigintmat * bim = new bigintmat(b->rows(), b->cols(), C);
351
352 for (int i=0; i < l; i++)
353 bim->rawset(i, n_Init((*b)[i], C), C);
354
355 return bim;
356}

◆ kernbase()

int kernbase ( bigintmat * a,
bigintmat * c,
number p,
coeffs q )

a basis for the nullspace of a mod p: only used internally in Round2. Don't use it.

Definition at line 2585 of file bigintmat.cc.

2586{
2587#if 0
2588 PrintS("Kernel of ");
2589 a->Print();
2590 PrintS(" modulo ");
2591 n_Print(p, q);
2592 PrintLn();
2593#endif
2594
2595 coeffs coe = numbercoeffs(p, q);
2596 bigintmat *m = bimChangeCoeff(a, coe), *U, *V;
2597 diagonalForm(m, &U, &V);
2598#if 0
2599 PrintS("\ndiag form: ");
2600 m->Print();
2601 PrintS("\nU:\n");
2602 U->Print();
2603 PrintS("\nV:\n");
2604 V->Print();
2605 PrintLn();
2606#endif
2607
2608 int rg = 0;
2609#undef MIN
2610#define MIN(a,b) (a < b ? a : b)
2611 for(rg=0; rg<MIN(m->rows(), m->cols()) && !n_IsZero(m->view(m->rows()-rg,m->cols()-rg), coe); rg++);
2612
2613 bigintmat * k = new bigintmat(m->cols(), m->rows(), coe);
2614 for(int i=0; i<rg; i++)
2615 {
2616 number A = n_Ann(m->view(m->rows()-i, m->cols()-i), coe);
2617 k->set(m->cols()-i, i+1, A);
2618 n_Delete(&A, coe);
2619 }
2620 for(int i=rg; i<m->cols(); i++)
2621 {
2622 k->set(m->cols()-i, i+1-rg, n_Init(1, coe));
2623 }
2624 bimMult(V, k, k);
2625 c->copy(bimChangeCoeff(k, q));
2626 return c->cols();
2627}
bigintmat * bimChangeCoeff(bigintmat *a, coeffs cnew)
Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.
#define MIN(a, b)
void diagonalForm(bigintmat *A, bigintmat **S, bigintmat **T)
static coeffs numbercoeffs(number n, coeffs c)
create Z/nA of type n_Zn
Definition bigintmat.cc:20
int m
Definition cfEzgcd.cc:128
int p
Definition cfModGcd.cc:4086
static FORCE_INLINE number n_Ann(number a, const coeffs r)
if r is a ring with zero divisors, return an annihilator!=0 of b otherwise return NULL
Definition coeffs.h:680

◆ nCoeffs_are_equal()

bool nCoeffs_are_equal ( coeffs r,
coeffs s )

Definition at line 2629 of file bigintmat.cc.

2630{
2631 if ((r == NULL) || (s == NULL))
2632 return false;
2633 if (r == s)
2634 return true;
2635 if ((getCoeffType(r)==n_Z) && (getCoeffType(s)==n_Z))
2636 return true;
2637 if ((getCoeffType(r)==n_Zp) && (getCoeffType(s)==n_Zp))
2638 {
2639 if (r->ch == s->ch)
2640 return true;
2641 else
2642 return false;
2643 }
2644 // n_Zn stimmt wahrscheinlich noch nicht
2645 if ((getCoeffType(r)==n_Zn) && (getCoeffType(s)==n_Zn))
2646 {
2647 if (r->ch == s->ch)
2648 return true;
2649 else
2650 return false;
2651 }
2652 if ((getCoeffType(r)==n_Q) && (getCoeffType(s)==n_Q))
2653 return true;
2654 // FALL n_Zn FEHLT NOCH!
2655 //if ((getCoeffType(r)==n_Zn) && (getCoeffType(s)==n_Zn))
2656 return false;
2657}
@ n_Zn
only used if HAVE_RINGS is defined
Definition coeffs.h:44
@ n_Zp
\F{p < 2^31}
Definition coeffs.h:29
@ n_Z
only used if HAVE_RINGS is defined
Definition coeffs.h:43
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition coeffs.h:429

◆ numbercoeffs()

static coeffs numbercoeffs ( number n,
coeffs c )
static

create Z/nA of type n_Zn

Definition at line 20 of file bigintmat.cc.

21{
22 mpz_t p;
23 number2mpz(n, c, p);
24 ZnmInfo *pp = new ZnmInfo;
25 pp->base = p;
26 pp->exp = 1;
27 coeffs nc = nInitChar(n_Zn, (void*)pp);
28 mpz_clear(p);
29 delete pp;
30 return nc;
31}
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition cf_gcd.cc:676
static FORCE_INLINE void number2mpz(number n, coeffs c, mpz_t m)
Definition coeffs.h:984

◆ operator!=()

bool operator!= ( const bigintmat & lhr,
const bigintmat & rhr )

Definition at line 174 of file bigintmat.cc.

175{
176 return !(lhr==rhr);
177}

◆ operator==()

bool operator== ( const bigintmat & lhr,
const bigintmat & rhr )

Definition at line 157 of file bigintmat.cc.

158{
159 if (&lhr == &rhr) { return true; }
160 if (lhr.cols() != rhr.cols()) { return false; }
161 if (lhr.rows() != rhr.rows()) { return false; }
162 if (lhr.basecoeffs() != rhr.basecoeffs()) { return false; }
163
164 const int l = (lhr.rows())*(lhr.cols());
165
166 for (int i=0; i < l; i++)
167 {
168 if (!n_Equal(lhr[i], rhr[i], lhr.basecoeffs())) { return false; }
169 }
170
171 return true;
172}
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff 'a' and 'b' represent the same number; they may have different representations.
Definition coeffs.h:464

◆ prependIdentity()

static bigintmat * prependIdentity ( bigintmat * A)
static

Definition at line 2026 of file bigintmat.cc.

2027{
2028 coeffs R = A->basecoeffs();
2029 bigintmat *m = new bigintmat(A->rows()+A->cols(), A->cols(), R);
2030 m->copySubmatInto(A, 1, 1, A->rows(), A->cols(), A->cols()+1, 1);
2031 number one = n_Init(1, R);
2032 for(int i=1; i<= A->cols(); i++)
2033 m->set(i,i,one);
2034 n_Delete(&one, R);
2035 return m;
2036}

◆ reduce_mod_howell()

static void reduce_mod_howell ( bigintmat * A,
bigintmat * b,
bigintmat * eps,
bigintmat * x )
static

Definition at line 1940 of file bigintmat.cc.

1941{
1942 //write b = Ax + eps where eps is "small" in the sense of bounded by the
1943 //pivot entries in H. H does not need to be Howell (or HNF) but need
1944 //to be triagonal in the same direction.
1945 //b can have multiple columns.
1946#if 0
1947 PrintS("reduce_mod_howell: A:\n");
1948 A->Print();
1949 PrintS("\nb:\n");
1950 b->Print();
1951#endif
1952
1953 coeffs R = A->basecoeffs();
1954 assume(x->basecoeffs() == R);
1955 assume(b->basecoeffs() == R);
1956 assume(eps->basecoeffs() == R);
1957 if (!A->cols())
1958 {
1959 x->zero();
1960 eps->copy(b);
1961
1962#if 0
1963 PrintS("\nx:\n");
1964 x->Print();
1965 PrintS("\neps:\n");
1966 eps->Print();
1967 PrintS("\n****************************************\n");
1968#endif
1969 return;
1970 }
1971
1972 bigintmat * B = new bigintmat(b->rows(), 1, R);
1973 for(int i=1; i<= b->cols(); i++)
1974 {
1975 int A_col = A->cols();
1976 b->getcol(i, B);
1977 for(int j = B->rows(); j>0; j--)
1978 {
1979 number Ai = A->view(A->rows() - B->rows() + j, A_col);
1980 if (n_IsZero(Ai, R) &&
1981 n_IsZero(B->view(j, 1), R))
1982 {
1983 continue; //all is fine: 0*x = 0
1984 }
1985 else if (n_IsZero(B->view(j, 1), R))
1986 {
1987 x->rawset(x->rows() - B->rows() + j, i, n_Init(0, R));
1988 A_col--;
1989 }
1990 else if (n_IsZero(Ai, R))
1991 {
1992 A_col--;
1993 }
1994 else
1995 {
1996 // "solve" ax=b, possibly enlarging d
1997 number Bj = B->view(j, 1);
1998 number q = n_Div(Bj, Ai, R);
1999 x->rawset(x->rows() - B->rows() + j, i, q);
2000 for(int k=j; k>B->rows() - A->rows(); k--)
2001 {
2002 //B[k] = B[k] - x[k]A[k][j]
2003 number s = n_Mult(q, A->view(A->rows() - B->rows() + k, A_col), R);
2004 B->rawset(k, 1, n_Sub(B->view(k, 1), s, R));
2005 n_Delete(&s, R);
2006 }
2007 A_col--;
2008 }
2009 if (!A_col)
2010 {
2011 break;
2012 }
2013 }
2014 eps->setcol(i, B);
2015 }
2016 delete B;
2017#if 0
2018 PrintS("\nx:\n");
2019 x->Print();
2020 PrintS("\neps:\n");
2021 eps->Print();
2022 PrintS("\n****************************************\n");
2023#endif
2024}
void setcol(int j, bigintmat *m)
Setzt j-te Spalte gleich übergebenem Vektor (Matrix) m.
Definition bigintmat.cc:821
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of 'a' and 'b', i.e., a/b; raises an error if 'b' is not invertible in r exceptio...
Definition coeffs.h:616
b *CanonicalForm B
Definition facBivar.cc:52

◆ solveAx()

number solveAx ( bigintmat * A,
bigintmat * b,
bigintmat * x )

solve Ax=b*d. x needs to be pre-allocated to the same number of columns as b. the minimal denominator d is returned. Currently available for Z, Q and Z/nZ (and possibly for all fields: d=1 there) Beware that the internal functions can find the kernel as well - but the interface is lacking.

Definition at line 2418 of file bigintmat.cc.

2419{
2420#if 0
2421 PrintS("Solve Ax=b for A=\n");
2422 A->Print();
2423 PrintS("\nb = \n");
2424 b->Print();
2425 PrintS("\nx = \n");
2426 x->Print();
2427 PrintLn();
2428#endif
2429
2430 coeffs R = A->basecoeffs();
2431 assume (R == b->basecoeffs());
2432 assume (R == x->basecoeffs());
2433 assume ((x->cols() == b->cols()) && (x->rows() == A->cols()) && (A->rows() == b->rows()));
2434
2435 switch (getCoeffType(R))
2436 {
2437 case n_Z:
2438 return solveAx_dixon(A, b, x, NULL);
2439 case n_Zn:
2440 case n_Znm:
2441 case n_Z2m:
2442 return solveAx_howell(A, b, x, NULL);
2443 case n_Zp:
2444 case n_Q:
2445 case n_GF:
2446 case n_algExt:
2447 case n_transExt:
2448 WarnS("have field, should use Gauss or better");
2449 break;
2450 default:
2451 if (R->cfXExtGcd && R->cfAnn)
2452 { //assume it's Euclidean
2453 return solveAx_howell(A, b, x, NULL);
2454 }
2455 WerrorS("have no solve algorithm");
2456 break;
2457 }
2458 return NULL;
2459}
static number solveAx_dixon(bigintmat *A, bigintmat *B, bigintmat *x, bigintmat *kern)
static number solveAx_howell(bigintmat *A, bigintmat *b, bigintmat *x, bigintmat *kern)
@ n_GF
\GF{p^n < 2^16}
Definition coeffs.h:32
@ n_Znm
only used if HAVE_RINGS is defined
Definition coeffs.h:45
@ n_algExt
used for all algebraic extensions, i.e., the top-most extension in an extension tower is algebraic
Definition coeffs.h:35
@ n_Z2m
only used if HAVE_RINGS is defined
Definition coeffs.h:46
@ n_transExt
used for all transcendental extensions, i.e., the top-most extension in an extension tower is transce...
Definition coeffs.h:38
#define WarnS
Definition emacs.cc:78

◆ solveAx_dixon()

static number solveAx_dixon ( bigintmat * A,
bigintmat * B,
bigintmat * x,
bigintmat * kern )
static

Definition at line 2097 of file bigintmat.cc.

2097 {
2098 coeffs R = A->basecoeffs();
2099
2100 assume(getCoeffType(R) == n_Z);
2101
2102 number p = n_Init(536870909, R); // PreviousPrime(2^29); not clever
2103 coeffs Rp = numbercoeffs(p, R); // R/pR
2104 bigintmat *Ap = bimChangeCoeff(A, Rp),
2105 *m = prependIdentity(Ap),
2106 *Tp, *Hp;
2107 delete Ap;
2108
2109 m->howell();
2110 Hp = new bigintmat(A->rows(), A->cols(), Rp);
2111 Hp->copySubmatInto(m, A->cols()+1, 1, A->rows(), A->cols(), 1, 1);
2112 Tp = new bigintmat(A->cols(), A->cols(), Rp);
2113 Tp->copySubmatInto(m, 1, 1, A->cols(), A->cols(), 1, 1);
2114
2115 int i, j;
2116
2117 for(i=1; i<= A->cols(); i++)
2118 {
2119 for(j=m->rows(); j>A->cols(); j--)
2120 {
2121 if (!n_IsZero(m->view(j, i), Rp)) break;
2122 }
2123 if (j>A->cols()) break;
2124 }
2125// Print("Found nullity (kern dim) of %d\n", i-1);
2126 bigintmat * kp = new bigintmat(A->cols(), i-1, Rp);
2127 kp->copySubmatInto(Tp, 1, 1, A->cols(), i-1, 1, 1);
2128 kp->howell();
2129
2130 delete m;
2131
2132 //Hp is the mod-p howell form
2133 //Tp the transformation, mod p
2134 //kp a basis for the kernel, in howell form, mod p
2135
2136 bigintmat * eps_p = new bigintmat(B->rows(), B->cols(), Rp),
2137 * x_p = new bigintmat(A->cols(), B->cols(), Rp),
2138 * fps_p = new bigintmat(kp->cols(), B->cols(), Rp);
2139
2140 //initial solution
2141
2142 number zero = n_Init(0, R);
2143 x->skalmult(zero, R);
2144 n_Delete(&zero, R);
2145
2146 bigintmat * b = new bigintmat(B);
2147 number pp = n_Init(1, R);
2148 i = 1;
2149 do
2150 {
2151 bigintmat * b_p = bimChangeCoeff(b, Rp), * s;
2152 bigintmat * t1, *t2;
2153 reduce_mod_howell(Hp, b_p, eps_p, x_p);
2154 delete b_p;
2155 if (!eps_p->isZero())
2156 {
2157 PrintS("no solution, since no modular solution\n");
2158
2159 delete eps_p;
2160 delete x_p;
2161 delete Hp;
2162 delete kp;
2163 delete Tp;
2164 delete b;
2165 n_Delete(&pp, R);
2166 n_Delete(&p, R);
2167 nKillChar(Rp);
2168
2169 return NULL;
2170 }
2171 t1 = bimMult(Tp, x_p);
2172 delete x_p;
2173 x_p = t1;
2174 reduce_mod_howell(kp, x_p, x_p, fps_p); //we're not all interested in fps_p
2175 s = bimChangeCoeff(x_p, R);
2176 t1 = bimMult(A, s);
2177 t2 = bimSub(b, t1);
2178 t2->skaldiv(p);
2179 delete b;
2180 delete t1;
2181 b = t2;
2182 s->skalmult(pp, R);
2183 t1 = bimAdd(x, s);
2184 delete s;
2185 x->swapMatrix(t1);
2186 delete t1;
2187
2188 if(kern && i==1)
2189 {
2190 bigintmat * ker = bimChangeCoeff(kp, R);
2191 t1 = bimMult(A, ker);
2192 t1->skaldiv(p);
2193 t1->skalmult(n_Init(-1, R), R);
2194 b->appendCol(t1);
2195 delete t1;
2196 x->appendCol(ker);
2197 delete ker;
2198 x_p->extendCols(kp->cols());
2199 eps_p->extendCols(kp->cols());
2200 fps_p->extendCols(kp->cols());
2201 }
2202
2203 n_InpMult(pp, p, R);
2204
2205 if (b->isZero())
2206 {
2207 //exact solution found, stop
2208 delete eps_p;
2209 delete fps_p;
2210 delete x_p;
2211 delete Hp;
2212 delete kp;
2213 delete Tp;
2214 delete b;
2215 n_Delete(&pp, R);
2216 n_Delete(&p, R);
2217 nKillChar(Rp);
2218
2219 return n_Init(1, R);
2220 }
2221 else
2222 {
2223 bigintmat *y = new bigintmat(x->rows(), x->cols(), R);
2224 number d = bimFarey(x, pp, y);
2225 if (d)
2226 {
2227 bigintmat *c = bimMult(A, y);
2228 bigintmat *bd = new bigintmat(B);
2229 bd->skalmult(d, R);
2230 if (kern)
2231 {
2232 bd->extendCols(kp->cols());
2233 }
2234 if (*c == *bd)
2235 {
2236 x->swapMatrix(y);
2237 delete y;
2238 delete c;
2239 if (kern)
2240 {
2241 y = new bigintmat(x->rows(), B->cols(), R);
2242 c = new bigintmat(x->rows(), kp->cols(), R);
2243 x->splitcol(y, c);
2244 x->swapMatrix(y);
2245 delete y;
2246 kern->swapMatrix(c);
2247 delete c;
2248 }
2249
2250 delete bd;
2251
2252 delete eps_p;
2253 delete fps_p;
2254 delete x_p;
2255 delete Hp;
2256 delete kp;
2257 delete Tp;
2258 delete b;
2259 n_Delete(&pp, R);
2260 n_Delete(&p, R);
2261 nKillChar(Rp);
2262
2263 return d;
2264 }
2265 delete c;
2266 delete bd;
2267 n_Delete(&d, R);
2268 }
2269 delete y;
2270 }
2271 i++;
2272 } while (1);
2273 delete eps_p;
2274 delete fps_p;
2275 delete x_p;
2276 delete Hp;
2277 delete kp;
2278 delete Tp;
2279 n_Delete(&pp, R);
2280 n_Delete(&p, R);
2281 nKillChar(Rp);
2282 return NULL;
2283}
static void reduce_mod_howell(bigintmat *A, bigintmat *b, bigintmat *eps, bigintmat *x)
static bigintmat * prependIdentity(bigintmat *A)
bigintmat * bimSub(bigintmat *a, bigintmat *b)
Definition bigintmat.cc:216
static number bimFarey(bigintmat *A, number N, bigintmat *L)
bigintmat * bimAdd(bigintmat *a, bigintmat *b)
Matrix-Add/-Sub/-Mult so oder mit operator+/-/* ? @Note: NULL as a result means an error (non-compati...
Definition bigintmat.cc:180
void swapMatrix(bigintmat *a)
int isZero()
void extendCols(int i)
append i zero-columns to the matrix
void skaldiv(number b)
Macht Ganzzahldivision aller Matrixeinträge mit b.
void copySubmatInto(bigintmat *, int sr, int sc, int nr, int nc, int tr, int tc)
copy the submatrix of b, staring at (a,b) having n rows, m cols into the given matrix at pos....
void howell()
dito, but Howell form (only different for zero-divsors)
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53

◆ solveAx_howell()

static number solveAx_howell ( bigintmat * A,
bigintmat * b,
bigintmat * x,
bigintmat * kern )
static

Definition at line 2286 of file bigintmat.cc.

2287{
2288 // try to solve Ax=b, more precisely, find
2289 // number d
2290 // bigintmat x
2291 // sth. Ax=db
2292 // where d is small-ish (divides the determinant of A if this makes sense)
2293 // return 0 if there is no solution.
2294 //
2295 // if kern is non-NULL, return a basis for the kernel
2296
2297 //Algo: we do row-howell (triangular matrix). The idea is
2298 // Ax = b <=> AT T^-1x = b
2299 // y := T^-1 x, solve AT y = b
2300 // and return Ty.
2301 //Howell does not compute the trafo, hence we need to cheat:
2302 //B := (I_n | A^t)^t, then the top part of the Howell form of
2303 //B will give a useful trafo
2304 //Then we can find x by back-substitution and lcm/gcd to find the denominator
2305 //The defining property of Howell makes this work.
2306
2307 coeffs R = A->basecoeffs();
2309 m->howell(); // since m contains the identity, we'll have A->cols()
2310 // many cols.
2311 number den = n_Init(1, R);
2312
2313 bigintmat * B = new bigintmat(A->rows(), 1, R);
2314 for(int i=1; i<= b->cols(); i++)
2315 {
2316 int A_col = A->cols();
2317 b->getcol(i, B);
2318 B->skalmult(den, R);
2319 for(int j = B->rows(); j>0; j--)
2320 {
2321 number Ai = m->view(m->rows()-B->rows() + j, A_col);
2322 if (n_IsZero(Ai, R) &&
2323 n_IsZero(B->view(j, 1), R))
2324 {
2325 continue; //all is fine: 0*x = 0
2326 }
2327 else if (n_IsZero(B->view(j, 1), R))
2328 {
2329 x->rawset(x->rows() - B->rows() + j, i, n_Init(0, R));
2330 A_col--;
2331 }
2332 else if (n_IsZero(Ai, R))
2333 {
2334 delete m;
2335 delete B;
2336 n_Delete(&den, R);
2337 return 0;
2338 }
2339 else
2340 {
2341 // solve ax=db, possibly enlarging d
2342 // so x = db/a
2343 number Bj = B->view(j, 1);
2344 number g = n_Gcd(Bj, Ai, R);
2345 number xi;
2346 if (n_Equal(Ai, g, R))
2347 { //good: den stable!
2348 xi = n_Div(Bj, Ai, R);
2349 }
2350 else
2351 { //den <- den * (a/g), so old sol. needs to be adjusted
2352 number inc_d = n_Div(Ai, g, R);
2353 n_InpMult(den, inc_d, R);
2354 x->skalmult(inc_d, R);
2355 B->skalmult(inc_d, R);
2356 xi = n_Div(Bj, g, R);
2357 n_Delete(&inc_d, R);
2358 } //now for the back-substitution:
2359 x->rawset(x->rows() - B->rows() + j, i, xi);
2360 for(int k=j; k>0; k--)
2361 {
2362 //B[k] = B[k] - x[k]A[k][j]
2363 number s = n_Mult(xi, m->view(m->rows()-B->rows() + k, A_col), R);
2364 B->rawset(k, 1, n_Sub(B->view(k, 1), s, R));
2365 n_Delete(&s, R);
2366 }
2367 n_Delete(&g, R);
2368 A_col--;
2369 }
2370 if (!A_col)
2371 {
2372 if (B->isZero()) break;
2373 else
2374 {
2375 delete m;
2376 delete B;
2377 n_Delete(&den, R);
2378 return 0;
2379 }
2380 }
2381 }
2382 }
2383 delete B;
2384 bigintmat *T = new bigintmat(A->cols(), A->cols(), R);
2385 T->copySubmatInto(m, 1, 1, A->cols(), A->cols(), 1, 1);
2386 if (kern)
2387 {
2388 int i, j;
2389 for(i=1; i<= A->cols(); i++)
2390 {
2391 for(j=m->rows(); j>A->cols(); j--)
2392 {
2393 if (!n_IsZero(m->view(j, i), R)) break;
2394 }
2395 if (j>A->cols()) break;
2396 }
2397 Print("Found nullity (kern dim) of %d\n", i-1);
2398 bigintmat * ker = new bigintmat(A->rows(), i-1, R);
2399 ker->copySubmatInto(T, 1, 1, A->rows(), i-1, 1, 1);
2400 kern->swapMatrix(ker);
2401 delete ker;
2402 }
2403 delete m;
2404 bigintmat * y = bimMult(T, x);
2405 x->swapMatrix(y);
2406 delete y;
2407 x->simplifyContentDen(&den);
2408#if 0
2409 PrintS("sol = 1/");
2410 n_Print(den, R);
2411 PrintS(" *\n");
2412 x->Print();
2413 PrintLn();
2414#endif
2415 return den;
2416}
g
Definition cfModGcd.cc:4098
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of 'a' and 'b' in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ,...
Definition coeffs.h:665