Commit 6e779e69a89c828a02b20323c6c7b494750e8dcf
2019-11-22T11:31:20
Merge pull request #462 from czurnieden/repair_div_recursive Repair of sign handling in mp_div_recursive
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
diff --git a/demo/test.c b/demo/test.c
index 281255b..e1b6f0f 100644
--- a/demo/test.c
+++ b/demo/test.c
@@ -729,7 +729,7 @@ static int test_mp_sqrt(void)
printf("\nmp_sqrt() error!");
goto LBL_ERR;
}
- DO(mp_root_n(&a, 2u, &c));
+ DO(mp_root_n(&a, 2, &c));
if (mp_cmp_mag(&b, &c) != MP_EQ) {
printf("mp_sqrt() bad result!\n");
goto LBL_ERR;
@@ -2082,16 +2082,53 @@ static int test_s_mp_div_recursive(void)
DO(s_mp_div_recursive(&a, &b, &c_q, &c_r));
DO(s_mp_div_school(&a, &b, &d_q, &d_r));
if (mp_cmp(&c_q, &d_q) != MP_EQ) {
- fprintf(stderr, "1. Recursive division failed at sizes %d / %d, wrong quotient\n",
+ fprintf(stderr, "1a. Recursive division failed at sizes %d / %d, wrong quotient\n",
10 * size, size);
goto LBL_ERR;
}
if (mp_cmp(&c_r, &d_r) != MP_EQ) {
- fprintf(stderr, "1. Recursive division failed at sizes %d / %d, wrong remainder\n",
+ fprintf(stderr, "1a. Recursive division failed at sizes %d / %d, wrong remainder\n",
10 * size, size);
goto LBL_ERR;
}
printf("\rsizes = %d / %d", 2 * size, size);
+
+ /* Relation 10:1 negative numerator*/
+ DO(mp_rand(&a, 10 * size));
+ DO(mp_neg(&a, &a));
+ DO(mp_rand(&b, size));
+ DO(s_mp_div_recursive(&a, &b, &c_q, &c_r));
+ DO(s_mp_div_school(&a, &b, &d_q, &d_r));
+ if (mp_cmp(&c_q, &d_q) != MP_EQ) {
+ fprintf(stderr, "1b. Recursive division failed at sizes %d / %d, wrong quotient\n",
+ 10 * size, size);
+ goto LBL_ERR;
+ }
+ if (mp_cmp(&c_r, &d_r) != MP_EQ) {
+ fprintf(stderr, "1b. Recursive division failed at sizes %d / %d, wrong remainder\n",
+ 10 * size, size);
+ goto LBL_ERR;
+ }
+ printf("\rsizes = %d / %d, negative numerator", 2 * size, size);
+
+ /* Relation 10:1 negative denominator*/
+ DO(mp_rand(&a, 10 * size));
+ DO(mp_rand(&b, size));
+ DO(mp_neg(&b, &b));
+ DO(s_mp_div_recursive(&a, &b, &c_q, &c_r));
+ DO(s_mp_div_school(&a, &b, &d_q, &d_r));
+ if (mp_cmp(&c_q, &d_q) != MP_EQ) {
+ fprintf(stderr, "1c. Recursive division failed at sizes %d / %d, wrong quotient\n",
+ 10 * size, size);
+ goto LBL_ERR;
+ }
+ if (mp_cmp(&c_r, &d_r) != MP_EQ) {
+ fprintf(stderr, "1c. Recursive division failed at sizes %d / %d, wrong remainder\n",
+ 10 * size, size);
+ goto LBL_ERR;
+ }
+ printf("\rsizes = %d / %d, negative denominator", 2 * size, size);
+
/* Relation 2:1 */
DO(mp_rand(&a, 2 * size));
DO(mp_rand(&b, size));
@@ -2326,7 +2363,7 @@ static int unit_tests(int argc, char **argv)
T1(mp_set_double, MP_SET_DOUBLE),
#endif
T1(mp_signed_rsh, MP_SIGNED_RSH),
- T2(mp_sqrt, MP_SQRT, mp_root_n),
+ T2(mp_sqrt, MP_SQRT, MP_ROOT_N),
T1(mp_sqrtmod_prime, MP_SQRTMOD_PRIME),
T1(mp_xor, MP_XOR),
T2(s_mp_div_recursive, S_MP_DIV_RECURSIVE, S_MP_DIV_SCHOOL),
diff --git a/s_mp_div_recursive.c b/s_mp_div_recursive.c
index 5491f22..df9a297 100644
--- a/s_mp_div_recursive.c
+++ b/s_mp_div_recursive.c
@@ -159,7 +159,7 @@ mp_err s_mp_div_recursive(const mp_int *a, const mp_int *b, mp_int *q, mp_int *r
if ((err = mp_add(&Q, &Q1, &Q)) != MP_OKAY) goto LBL_ERR;
/* get sign before writing to c */
- Q.sign = (mp_iszero(&Q) ? MP_ZPOS : a->sign);
+ R.sign = (mp_iszero(&Q) ? MP_ZPOS : a->sign);
if (q != NULL) {
mp_exch(&Q, q);