Peter Bruin on Sat, 01 Feb 2014 18:08:43 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

bb_field.{sub,div}


Hello,

While experimenting with some more linear algebra over finite fields, I
noticed that the bb_field structure did not have subtraction and
division.  Of course they can be emulated using the other functions, but
it would still nice to have them, if only for completeness.

The attached patch adds bb_field.sub() and bb_field.div().  I found one
use for sub() in the existing code, and it is covered by the testsuite;
there seems to be no direct use for div(), but I did test it both in
some experimental code of my own and by verifying that replacing -(1/x)
by (-1)/x in some places (that are already covered) works correctly.

Thanks,

Peter

diff --git a/doc/develop.tex b/doc/develop.tex
index a711cec..f21d45d 100644
--- a/doc/develop.tex
+++ b/doc/develop.tex
@@ -393,11 +393,13 @@ available to handle field elements:
 \bprog
   struct bb_field
   {
-    GEN (*red)(void *E ,GEN);
-    GEN (*add)(void *E ,GEN, GEN);
-    GEN (*mul)(void *E ,GEN, GEN);
-    GEN (*neg)(void *E ,GEN);
-    GEN (*inv)(void *E ,GEN);
+    GEN (*red)(void *E, GEN);
+    GEN (*add)(void *E, GEN, GEN);
+    GEN (*sub)(void *E, GEN, GEN);
+    GEN (*mul)(void *E, GEN, GEN);
+    GEN (*div)(void *E, GEN, GEN);
+    GEN (*neg)(void *E, GEN);
+    GEN (*inv)(void *E, GEN);
     int (*equal0)(GEN);
     GEN (*s)(void *E, long);
   };
diff --git a/src/basemath/F2x.c b/src/basemath/F2x.c
index 0e523f5..cc852c2 100644
--- a/src/basemath/F2x.c
+++ b/src/basemath/F2x.c
@@ -1437,6 +1437,10 @@ _F2xq_rmul(void *E, GEN x, GEN y)
 { (void) E; return F2x_mul(x,y); }
 
 static GEN
+_F2xq_div(void *E, GEN x, GEN y)
+{ return F2xq_div(x, y, (GEN) E); }
+
+static GEN
 _F2xq_inv(void *E, GEN x)
 { return F2xq_inv(x, (GEN) E); }
 
@@ -1449,7 +1453,8 @@ _F2xq_s(void *E, long x)
   return odd(x)? pol1_F2x(T[1]): pol0_F2x(T[0]);
 }
 
-static const struct bb_field F2xq_field={_F2xq_red,_F2xq_add,_F2xq_rmul,_F2xq_neg,
+static const struct bb_field F2xq_field={_F2xq_red,_F2xq_add,_F2xq_add,
+					 _F2xq_rmul,_F2xq_div,_F2xq_neg,
                                          _F2xq_inv,_F2xq_equal0,_F2xq_s};
 
 const struct bb_field *get_F2xq_field(void **E, GEN T)
diff --git a/src/basemath/Flx.c b/src/basemath/Flx.c
index 301478f..9903766 100644
--- a/src/basemath/Flx.c
+++ b/src/basemath/Flx.c
@@ -2042,6 +2042,12 @@ static GEN
 _Flxq_add(void *E, GEN x, GEN y)
 { struct _Flxq *s = (struct _Flxq *)E;
   return Flx_add(x,y,s->p); }
+
+static GEN
+_Flxq_sub(void *E, GEN x, GEN y)
+{ struct _Flxq *s = (struct _Flxq *)E;
+  return Flx_sub(x,y,s->p); }
+
 static GEN
 _Flxq_sqr(void *data, GEN x)
 {
@@ -2576,6 +2582,11 @@ _Flxq_rmul(void *E, GEN x, GEN y)
   return Flx_mul(x,y,s->p); }
 
 static GEN
+_Flxq_div(void *E, GEN x, GEN y)
+{ struct _Flxq *s = (struct _Flxq *)E;
+  return Flxq_div(x, y, s->T, s->p); }
+
+static GEN
 _Flxq_inv(void *E, GEN x)
 { struct _Flxq *s = (struct _Flxq *)E;
   return Flxq_inv(x,s->T,s->p); }
@@ -2590,7 +2601,8 @@ _Flxq_s(void *E, long x)
   return Fl_to_Flx(u, get_Flx_var(s->T));
 }
 
-static const struct bb_field Flxq_field={_Flxq_red,_Flxq_add,_Flxq_rmul,_Flxq_neg,
+static const struct bb_field Flxq_field={_Flxq_red,_Flxq_add,_Flxq_sub,
+					 _Flxq_rmul,_Flxq_div,_Flxq_neg,
                                          _Flxq_inv,_Flxq_equal0,_Flxq_s};
 
 const struct bb_field *get_Flxq_field(void **E, GEN T, ulong p)
diff --git a/src/basemath/alglin1.c b/src/basemath/alglin1.c
index 45a7278..95d2531 100644
--- a/src/basemath/alglin1.c
+++ b/src/basemath/alglin1.c
@@ -302,7 +302,7 @@ _gen_get_col(GEN a, GEN b, long li, void *E, const struct bb_field *ff)
   {
     pari_sp av = avma;
     GEN m = gel(b,i);
-    for (j=i+1; j<=li; j++) m = ff->add(E,m, ff->neg(E,ff->mul(E,gcoeff(a,i,j), gel(u,j))));
+    for (j=i+1; j<=li; j++) m = ff->sub(E, m, ff->mul(E,gcoeff(a,i,j), gel(u,j)));
     m = ff->red(E, m);
     gel(u,i) = gerepileupto(av, ff->red(E,ff->mul(E,m, gcoeff(a,i,i))));
   }
diff --git a/src/basemath/arith1.c b/src/basemath/arith1.c
index 2631732..90e5a7a 100644
--- a/src/basemath/arith1.c
+++ b/src/basemath/arith1.c
@@ -2620,12 +2620,18 @@ static GEN
 _Fp_add(void *E, GEN x, GEN y) { (void) E; return addii(x,y); }
 
 static GEN
+_Fp_sub(void *E, GEN x, GEN y) { (void) E; return subii(x,y); }
+
+static GEN
 _Fp_neg(void *E, GEN x) { (void) E; return negi(x); }
 
 static GEN
 _Fp_rmul(void *E, GEN x, GEN y) { (void) E; return mulii(x,y); }
 
 static GEN
+_Fp_div(void *E, GEN x, GEN y) { return Fp_div(x, y, (GEN) E); }
+
+static GEN
 _Fp_inv(void *E, GEN x) { return Fp_inv(x,(GEN)E); }
 
 static int
@@ -2634,7 +2640,8 @@ _Fp_equal0(GEN x) { return signe(x)==0; }
 static GEN
 _Fp_s(void *E, long x) { (void) E; return stoi(x); }
 
-static const struct bb_field Fp_field={_Fp_red,_Fp_add,_Fp_rmul,_Fp_neg,
+static const struct bb_field Fp_field={_Fp_red,_Fp_add,_Fp_sub,
+				       _Fp_rmul,_Fp_div,_Fp_neg,
                                         _Fp_inv,_Fp_equal0,_Fp_s};
 
 const struct bb_field *get_Fp_field(void **E, GEN p)
diff --git a/src/basemath/polarit3.c b/src/basemath/polarit3.c
index e9b904c..8b84495 100644
--- a/src/basemath/polarit3.c
+++ b/src/basemath/polarit3.c
@@ -676,6 +676,19 @@ _Fq_add(void *E, GEN x, GEN y)
 }
 
 static GEN
+_Fq_sub(void *E, GEN x, GEN y)
+{
+  (void) E;
+  switch((typ(x)==t_POL)|((typ(y)==t_POL)<<1))
+  {
+    case 0: return subii(x,y);
+    case 1: return ZX_Z_sub(x,y);
+    case 2: return Z_ZX_sub(x,y);
+    default: return ZX_sub(x,y);
+  }
+}
+
+static GEN
 _Fq_neg(void *E, GEN x) { (void) E; return typ(x)==t_POL?ZX_neg(x):negi(x); }
 
 static GEN
@@ -692,6 +705,13 @@ _Fq_mul(void *E, GEN x, GEN y)
 }
 
 static GEN
+_Fq_div(void *E, GEN x, GEN y)
+{
+  struct _Fq_field *s = (struct _Fq_field *)E;
+  return Fq_div(x, y, s->T, s->p);
+}
+
+static GEN
 _Fq_inv(void *E, GEN x)
 { struct _Fq_field *s = (struct _Fq_field *)E;
   return Fq_inv(x,s->T,s->p);
@@ -703,7 +723,8 @@ _Fq_equal0(GEN x) { return signe(x)==0; }
 static GEN
 _Fq_s(void *E, long x) { (void) E; return stoi(x); }
 
-static const struct bb_field Fq_field={_Fq_red,_Fq_add,_Fq_mul,_Fq_neg,
+static const struct bb_field Fq_field={_Fq_red,_Fq_add,_Fq_sub,
+				       _Fq_mul,_Fq_div,_Fq_neg,
                                        _Fq_inv,_Fq_equal0,_Fq_s};
 
 const struct bb_field *get_Fq_field(void **E, GEN T, GEN p)
diff --git a/src/headers/paridecl.h b/src/headers/paridecl.h
index 4f17f0f..ec01cf3 100644
--- a/src/headers/paridecl.h
+++ b/src/headers/paridecl.h
@@ -33,11 +33,13 @@ struct bb_group
 /* black box fields */
 struct bb_field
 {
-  GEN (*red)(void *E ,GEN);
-  GEN (*add)(void *E ,GEN, GEN);
-  GEN (*mul)(void *E ,GEN, GEN);
-  GEN (*neg)(void *E ,GEN);
-  GEN (*inv)(void *E ,GEN);
+  GEN (*red)(void *E, GEN);
+  GEN (*add)(void *E, GEN, GEN);
+  GEN (*sub)(void *E, GEN, GEN);
+  GEN (*mul)(void *E, GEN, GEN);
+  GEN (*div)(void *E, GEN, GEN);
+  GEN (*neg)(void *E, GEN);
+  GEN (*inv)(void *E, GEN);
   int (*equal0)(GEN);
   GEN (*s)(void *E, long);
 };