~mdw
/
catacomb
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
cleanup: Big pile of whitespace fixes, all at once.
[catacomb]
/
mpcrt.c
diff --git
a/mpcrt.c
b/mpcrt.c
index
51d9b68
..
bf6459f
100644
(file)
--- a/
mpcrt.c
+++ b/
mpcrt.c
@@
-1,13
+1,13
@@
/* -*-c-*-
*
/* -*-c-*-
*
- * $Id
: mpcrt.c,v 1.2 1999/12/10 23:22:32 mdw Exp
$
+ * $Id$
*
* Chinese Remainder Theorem computations (Gauss's algorithm)
*
* (c) 1999 Straylight/Edgeware
*/
*
* Chinese Remainder Theorem computations (Gauss's algorithm)
*
* (c) 1999 Straylight/Edgeware
*/
-/*----- Licensing notice --------------------------------------------------*
+/*----- Licensing notice --------------------------------------------------*
*
* This file is part of Catacomb.
*
*
* This file is part of Catacomb.
*
@@
-15,33
+15,23
@@
* it under the terms of the GNU Library General Public License as
* published by the Free Software Foundation; either version 2 of the
* License, or (at your option) any later version.
* it under the terms of the GNU Library General Public License as
* published by the Free Software Foundation; either version 2 of the
* License, or (at your option) any later version.
- *
+ *
* Catacomb 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 Library General Public License for more details.
* Catacomb 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 Library General Public License for more details.
- *
+ *
* You should have received a copy of the GNU Library General Public
* License along with Catacomb; if not, write to the Free
* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
* MA 02111-1307, USA.
*/
* You should have received a copy of the GNU Library General Public
* License along with Catacomb; if not, write to the Free
* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
* MA 02111-1307, USA.
*/
-/*----- Revision history --------------------------------------------------*
- *
- * $Log: mpcrt.c,v $
- * Revision 1.2 1999/12/10 23:22:32 mdw
- * Interface changes for suggested destinations. Use Barrett reduction.
- *
- * Revision 1.1 1999/11/22 20:50:57 mdw
- * Add support for solving Chinese Remainder Theorem problems.
- *
- */
-
/*----- Header files ------------------------------------------------------*/
#include "mp.h"
#include "mpcrt.h"
/*----- Header files ------------------------------------------------------*/
#include "mp.h"
#include "mpcrt.h"
+#include "mpmul.h"
#include "mpbarrett.h"
/*----- Main code ---------------------------------------------------------*/
#include "mpbarrett.h"
/*----- Main code ---------------------------------------------------------*/
@@
-79,9
+69,11
@@
void mpcrt_create(mpcrt *c, mpcrt_mod *v, size_t k, mp *n)
if (n != MP_NEW)
n = MP_COPY(n);
else {
if (n != MP_NEW)
n = MP_COPY(n);
else {
- n = MP_COPY(v[0].m);
- for (i = 1; i < k; i++)
- n = mp_mul(n, n, v[i].m);
+ mpmul mm;
+ mpmul_init(&mm);
+ for (i = 0; i < k; i++)
+ mpmul_add(&mm, v[i].m);
+ n = mpmul_done(&mm);
}
/* --- A quick hack if %$k = 2$% --- */
}
/* --- A quick hack if %$k = 2$% --- */
@@
-101,7
+93,10
@@
void mpcrt_create(mpcrt *c, mpcrt_mod *v, size_t k, mp *n)
*/
if (!v[0].ni && !v[1].ni) {
*/
if (!v[0].ni && !v[1].ni) {
- mp_gcd(0, &v[0].ni, &v[1].ni, v[0].n, v[1].n);
+ mp *g = MP_NEW;
+ mp_gcd(&g, &v[0].ni, &v[1].ni, v[0].n, v[1].n);
+ assert(MP_EQ(g, MP_ONE));
+ mp_drop(g);
v[0].ni = mp_add(v[0].ni, v[0].ni, v[1].n);
} else {
int i, j;
v[0].ni = mp_add(v[0].ni, v[0].ni, v[1].n);
} else {
int i, j;
@@
-111,7
+106,7
@@
void mpcrt_create(mpcrt *c, mpcrt_mod *v, size_t k, mp *n)
i = 0, j = 1;
else
i = 1, j = 0;
i = 0, j = 1;
else
i = 1, j = 0;
-
+
x = mp_mul(MP_NEW, v[j].n, v[j].ni);
x = mp_sub(x, x, MP_ONE);
mp_div(&x, 0, x, v[i].n);
x = mp_mul(MP_NEW, v[j].n, v[j].ni);
x = mp_sub(x, x, MP_ONE);
mp_div(&x, 0, x, v[i].n);
@@
-129,7
+124,7
@@
void mpcrt_create(mpcrt *c, mpcrt_mod *v, size_t k, mp *n)
if (!v[i].n)
mp_div(&v[i].n, 0, n, v[i].m);
if (!v[i].ni)
if (!v[i].n)
mp_div(&v[i].n, 0, n, v[i].m);
if (!v[i].ni)
-
mp_gcd(0, &v[i].ni, 0
, v[i].n, v[i].m);
+
v[i].ni = mp_modinv(MP_NEW
, v[i].n, v[i].m);
if (!v[i].nni)
v[i].nni = mp_mul(MP_NEW, v[i].n, v[i].ni);
}
if (!v[i].nni)
v[i].nni = mp_mul(MP_NEW, v[i].n, v[i].ni);
}
@@
-223,7
+218,7
@@
static int verify(size_t n, dstr *v)
mpcrt_create(&c, m, n, 0);
b = mpcrt_solve(&c, MP_NEW, r);
mpcrt_create(&c, m, n, 0);
b = mpcrt_solve(&c, MP_NEW, r);
- if (
MP_CMP(a, !=
, b)) {
+ if (
!MP_EQ(a
, b)) {
fputs("\n*** failed\n", stderr);
fputs("n = ", stderr);
mp_writefile(c.mb.m, stderr, 10);
fputs("\n*** failed\n", stderr);
fputs("n = ", stderr);
mp_writefile(c.mb.m, stderr, 10);
@@
-250,8
+245,8
@@
static int verify(size_t n, dstr *v)
mp_drop(a);
mp_drop(b);
mpcrt_destroy(&c);
mp_drop(a);
mp_drop(b);
mpcrt_destroy(&c);
- free(m);
- free(r);
+
x
free(m);
+
x
free(r);
assert(mparena_count(MPARENA_GLOBAL) == 0);
return (ok);
}
assert(mparena_count(MPARENA_GLOBAL) == 0);
return (ok);
}