[Gmp-commit] /home/hgfiles/gmp: New program gen-jacobitab.

[mercurial at gmplib.org]

details:   /home/hgfiles/gmp/rev/5bb4e6bea5be
changeset: 13432:5bb4e6bea5be
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Fri Feb 19 15:29:32 2010 +0100
description:
New program gen-jacobitab.

diffstat:

 ChangeLog       |    7 +++
 Makefile.am     |   11 +++++
 gen-jacobitab.c |  117 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 135 insertions(+), 0 deletions(-)

diffs (156 lines):

diff -r b26a255205b4 -r 5bb4e6bea5be ChangeLog
--- a/ChangeLog	Fri Feb 19 08:59:10 2010 +0100
+++ b/ChangeLog	Fri Feb 19 15:29:32 2010 +0100
@@ -1,3 +1,10 @@
+2010-02-19  Niels Möller  <nisse at lysator.liu.se>
+
+	* Makefile.am (mpn/jacobitab.h): Added the rules needed to
+	generate this file.
+
+	* gen-jacobitab.c: New file.
+
 2010-02-19  Torbjorn Granlund  <tege at gmplib.org>
 
 	* mpn/generic/powm.c: Honour SQR_BASECASE_THRESHOLD in innerloop
diff -r b26a255205b4 -r 5bb4e6bea5be Makefile.am
--- a/Makefile.am	Fri Feb 19 08:59:10 2010 +0100
+++ b/Makefile.am	Fri Feb 19 15:29:32 2010 +0100
@@ -400,6 +400,17 @@
 	$(CPP_FOR_BUILD) `if test -f $(srcdir)/gen-trialdivtab.c; then echo $(srcdir)/gen-trialdivtab.c; else echo gen-trialdivtab.c; fi` | sed 's/^# \([0-9]\)/#line \1/' | $(ANSI2KNR) > gen-trialdivtab_.c || rm -f gen-trialdivtab_.c
 
 
+mpn/jacobitab.h: gen-jacobitab$(EXEEXT_FOR_BUILD)
+	./gen-jacobitab >mpn/jacobitab.h || (rm -f mpn/jacobitab.h; exit 1)
+BUILT_SOURCES += mpn/jacobitab.h
+
+gen-jacobitab$(EXEEXT_FOR_BUILD): gen-jacobitab$(U_FOR_BUILD).c
+	$(CC_FOR_BUILD) `test -f 'gen-jacobitab$(U_FOR_BUILD).c' || echo '$(srcdir)/'`gen-jacobitab$(U_FOR_BUILD).c -o gen-jacobitab$(EXEEXT_FOR_BUILD)
+DISTCLEANFILES += gen-jacobitab$(EXEEXT_FOR_BUILD)
+EXTRA_DIST += gen-jacobitab.c
+
+gen-jacobitab_.c: gen-jacobitab.c $(ANSI2KNR)
+	$(CPP_FOR_BUILD) `if test -f $(srcdir)/gen-jacobitab.c; then echo $(srcdir)/gen-jacobitab.c; else echo gen-jacobitab.c; fi` | sed 's/^# \([0-9]\)/#line \1/' | $(ANSI2KNR) > gen-jacobitab_.c || rm -f gen-jacobitab_.c
 
 
 mpn/perfsqr.h: gen-psqr$(EXEEXT_FOR_BUILD)
diff -r b26a255205b4 -r 5bb4e6bea5be gen-jacobitab.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gen-jacobitab.c	Fri Feb 19 15:29:32 2010 +0100
@@ -0,0 +1,117 @@
+/* gen-jacobi.c
+
+   Contributed to the GNU project by Niels Möller.
+
+Copyright 2010 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 3 of the License, or (at your
+option) any later version.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+License for more details.
+
+You should have received a copy of the GNU Lesser General Public License
+along with the GNU MP Library.	If not, see http://www.gnu.org/licenses/.  */
+
+/* Generate the lookup table needed for fast left-to-right computation
+   of the Jacobi symbol. */
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+static const struct
+{
+  unsigned char a;
+  unsigned char b;
+} decode_table[13] = {
+  /*  0 */ { 0, 1 },
+  /*  1 */ { 0, 3 },
+  /*  2 */ { 1, 1 },
+  /*  3 */ { 1, 3 },
+  /*  4 */ { 2, 1 },
+  /*  5 */ { 2, 3 },
+  /*  6 */ { 3, 1 },
+  /*  7 */ { 3, 3 }, /* d = 1 */
+  /*  8 */ { 1, 0 },
+  /*  9 */ { 1, 2 },
+  /* 10 */ { 3, 0 },
+  /* 11 */ { 3, 2 },
+  /* 12 */ { 3, 3 }, /* d = 0 */
+  
+};
+#define JACOBI_A(bits) (decode_table[(bits)>>1].a)
+#define JACOBI_B(bits) (decode_table[(bits)>>1].b)
+
+#define JACOBI_E(bits) ((bits) & 1)
+#define JACOBI_D(bits) (((bits)>>1) == 7) /* Gives 0 for don't care states. */
+
+static unsigned
+encode (unsigned a, unsigned b, unsigned d)
+{
+  unsigned i;
+  
+  assert (d < 2);
+  assert (a < 4);
+  assert (b < 4);
+  assert ( (a | b ) & 1);
+
+  if (a == 3 && b == 3)
+    return d ? 7 : 12;
+
+  for (i = 0; i < 12; i++)
+    if (decode_table[i].a == a
+	&& decode_table[i].b == b)
+      return i;
+
+  abort ();
+}
+
+int
+main (int argc, char **argv)
+{
+  unsigned bits;
+
+  for (bits = 0; bits < 208; bits++)
+    {
+      unsigned e, a, b, d_old, d, q;
+
+      if (bits && !(bits & 0xf))
+	printf("\n");
+
+      q = bits & 3;
+      d = (bits >> 2) & 1;
+      
+      e = JACOBI_E (bits >> 3);
+      a = JACOBI_A (bits >> 3);
+      b = JACOBI_B (bits >> 3);
+      d_old = JACOBI_D (bits >> 3);
+
+      if (d != d_old && a == 3 && b == 3)
+	e ^= 1;
+
+      if (d == 1)
+	{
+	  if (b == 2)
+	    e ^= (q & (a >> 1)) ^ (q >> 1);
+	  a = (a - q * b) & 3;
+	}
+      else
+	{
+	  if (a == 2)
+	    e ^= (q & (b >> 1)) ^ (q >> 1);
+	  b = (b - q * a) & 3;
+	}
+      
+      printf("%2d,", (encode (a, b, d) << 1) | e);
+    }
+  printf("\n");
+  
+  return 0;
+}