Commit 921be35779f7d71080ad85c27ed58671602d59b3
2010-11-26T22:24:23
Improving performance of bn_mp_expt_d The loop was always iterating DIGIT_BIT times, instead of halting when possible. This changes makes sure it executes less operations. This change has also been incorporated into Rubinius / https://github.com/evanphx/rubinius which uses libtommath
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
diff --git a/bn_mp_expt_d.c b/bn_mp_expt_d.c
index 64c1b41..427ef06 100644
--- a/bn_mp_expt_d.c
+++ b/bn_mp_expt_d.c
@@ -18,7 +18,7 @@
/* calculate c = a**b using a square-multiply algorithm */
int mp_expt_d (mp_int * a, mp_digit b, mp_int * c)
{
- int res, x;
+ int res;
mp_int g;
if ((res = mp_init_copy (&g, a)) != MP_OKAY) {
@@ -28,23 +28,23 @@ int mp_expt_d (mp_int * a, mp_digit b, mp_int * c)
/* set initial result */
mp_set (c, 1);
- for (x = 0; x < (int) DIGIT_BIT; x++) {
- /* square */
- if ((res = mp_sqr (c, c)) != MP_OKAY) {
- mp_clear (&g);
- return res;
- }
-
+ while (b > 0) {
/* if the bit is set multiply */
- if ((b & (mp_digit) (((mp_digit)1) << (DIGIT_BIT - 1))) != 0) {
+ if (b & 1) {
if ((res = mp_mul (c, &g, c)) != MP_OKAY) {
- mp_clear (&g);
- return res;
+ mp_clear (&g);
+ return res;
}
}
+ /* square */
+ if (b > 1 && (res = mp_sqr (c, c)) != MP_OKAY) {
+ mp_clear (&g);
+ return res;
+ }
+
/* shift to next bit */
- b <<= 1;
+ b >>= 1;
}
mp_clear (&g);