diff options
| author | Kaz Kylheku <kaz@kylheku.com> | 2014-02-19 20:45:22 -0800 |
|---|---|---|
| committer | Kaz Kylheku <kaz@kylheku.com> | 2014-02-19 20:45:22 -0800 |
| commit | 124e7dd6977a0853d7a8399921e31fd1ccde2dcb (patch) | |
| tree | 358586d1275e7927f72b9995ca68de48d5e557ae /mpi-patches/faster-square-root | |
| parent | 916b0f4a081b26ebb4b58afbcb651fc74dbe23cc (diff) | |
| download | txr-124e7dd6977a0853d7a8399921e31fd1ccde2dcb.tar.gz txr-124e7dd6977a0853d7a8399921e31fd1ccde2dcb.tar.bz2 txr-124e7dd6977a0853d7a8399921e31fd1ccde2dcb.zip | |
* mpi-patches/faster-square-root (mp_sqrt): Bugfix: was computing square
roots that were incorrect in the last digit/bit, because it was not
generating the guess mask all the way down to bit zero. Also, added
an early test to bail the loop when an the guess at the root happens
to be right.
* mpi-patches/add-bitops: Refreshed.
* mpi-patches/fix-ctype-warnings: Likewise.
* mpi-patches/mpi-to-double: Likewise.
Diffstat (limited to 'mpi-patches/faster-square-root')
| -rw-r--r-- | mpi-patches/faster-square-root | 20 |
1 files changed, 13 insertions, 7 deletions
diff --git a/mpi-patches/faster-square-root b/mpi-patches/faster-square-root index 30f3da91..36fa4993 100644 --- a/mpi-patches/faster-square-root +++ b/mpi-patches/faster-square-root @@ -1,7 +1,7 @@ Index: mpi-1.8.6/mpi.c =================================================================== ---- mpi-1.8.6.orig/mpi.c 2012-03-04 11:45:43.071884757 -0800 -+++ mpi-1.8.6/mpi.c 2012-03-04 11:45:43.556157007 -0800 +--- mpi-1.8.6.orig/mpi.c 2014-02-17 22:25:46.042680203 -0800 ++++ mpi-1.8.6/mpi.c 2014-02-19 19:00:21.279452088 -0800 @@ -158,6 +158,9 @@ mp_err s_mp_grow(mp_int *mp, mp_size min); /* increase allocated size */ mp_err s_mp_pad(mp_int *mp, mp_size min); /* left pad with zeroes */ @@ -12,7 +12,7 @@ Index: mpi-1.8.6/mpi.c void s_mp_clamp(mp_int *mp); /* clip leading zeroes */ void s_mp_exch(mp_int *a, mp_int *b); /* swap a and b in place */ -@@ -1535,77 +1538,55 @@ +@@ -1535,77 +1538,61 @@ /* {{{ mp_sqrt(a, b) */ @@ -85,8 +85,9 @@ Index: mpi-1.8.6/mpi.c + if ((err = mp_init(&guess_sqr))) + goto cleanup_guess; + -+ for (mask_shift = s_highest_bit_mp(a) / 2; mask_shift > 0; mask_shift--) { ++ for (mask_shift = s_highest_bit_mp(a) / 2; mask_shift >= 0; mask_shift--) { + mp_int *temp; ++ int cmp; + + if ((err = mp_copy(proot, pguess))) + goto cleanup; @@ -97,10 +98,15 @@ Index: mpi-1.8.6/mpi.c + if ((err = s_mp_sqr(&guess_sqr))) + goto cleanup; + -+ if (s_mp_cmp(&guess_sqr, a) <= 0) { ++ cmp = s_mp_cmp(&guess_sqr, a); ++ ++ if (cmp < 0) { + temp = proot; + proot = pguess; + pguess = temp; ++ } else if (cmp == 0) { ++ proot = pguess; ++ break; + } } @@ -130,7 +136,7 @@ Index: mpi-1.8.6/mpi.c /* }}} */ -@@ -2554,21 +2535,9 @@ +@@ -2554,21 +2541,9 @@ int mp_count_bits(mp_int *mp) { @@ -153,7 +159,7 @@ Index: mpi-1.8.6/mpi.c } /* end mp_count_bits() */ /* }}} */ -@@ -3132,6 +3101,27 @@ +@@ -3132,6 +3107,27 @@ abort(); } |