* Arguments: @gfreduce *r@ = structure to fill in
* @mp *x@ = an integer
*
- * Returns: Zero if successful; nonzero on failure.
+ * Returns: Zero if successful; nonzero on failure. The current
+ * algorithm always succeeds when given positive @x@. Earlier
+ * versions used to fail on particular kinds of integers, but
+ * this is guaranteed not to happen any more.
*
* Use: Initializes a context structure for reduction.
*/
}
}
- /* --- This doesn't always work --- *
+ /* --- Fix up wrong-sided decompositions --- *
*
- * If %$d \ge 2^{n-1}$% then the above recurrence will output a subtraction
- * as the final instruction, which may sometimes underflow. (It interprets
- * such numbers as being in the form %$2^{n-1} + d$%.) This is clearly
- * bad, so detect the situation and fail gracefully.
+ * At this point, we haven't actually finished up the state machine
+ * properly. We stopped scanning just after bit %$n - 1$% -- the most
+ * significant one, which we know in advance must be set (since @x@ is
+ * strictly positive). Therefore we are either in state @X@ or @Z1@. In
+ * the former case, we have nothing to do. In the latter, there are two
+ * subcases to deal with. If there are no other instructions, then @x@ is
+ * a perfect power of two, and %$d = 0$%, so again there is nothing to do.
+ *
+ * In the remaining case, we have decomposed @x@ as %$2^{n-1} + d$%, for
+ * some positive %$d%, which is unfortuante: if we're asked to reduce
+ * %$2^n$%, say, we'll end up with %$-d$% (or would do, if we weren't
+ * sticking to unsigned arithmetic for good performance). So instead, we
+ * rewrite this as %$2^n - 2^{n-1} + d$% and everything will be good.
*/
- if (DA_LEN(&iv) && (DA(&iv)[DA_LEN(&iv) - 1].op & ~1u) == MPRI_SUB) {
- mp_drop(r->p);
- DA_DESTROY(&iv);
- return (-1);
+ if (st == Z1 && DA_LEN(&iv)) {
+ w = 1;
+ b = (bb + d)%MPW_BITS;
+ INSTR(MPRI_ADD | !!b, w, b);
}
#undef INSTR
* Arguments: @gfreduce *r@ = structure to fill in
* @mp *x@ = an integer
*
- * Returns: Zero for success, nonzero on error.
+ * Returns: Zero if successful; nonzero on failure. The current
+ * algorithm always succeeds when given positive @x@. Earlier
+ * versions used to fail on particular kinds of integers, but
+ * this is guaranteed not to happen any more.
*
* Use: Initializes a context structure for reduction.
*/
reduce {
0xc000 0x16cb3 0xacb3;
0x8000 0x345545 0x5545;
+ 0x8001 0x345545 0x54dd;
0xfffef 0x100000 0x11;
0x367aa8f5ba9ac4e8e2ea198b8af2c3b3081deab392ffc05715783b245a62a6fa
0x08e8c03ebf398c63d71d8fd7ca4ece12367a8dde180ca650afb6;
+ 0x52e2c37447f8bca34c4a39b130ea8e5c9a7d8b54564aa88ea773
+ 0x367aa8f5ba9ac4e8e2ea198b8af2c3b3081deab392ffc05715783b245a62a6fa
+ 0x4b6bd8300540dbbd767fe9e64ad2cbde52a9ae2299e3c516152d;
+
0xfffffffdffffffffffffffffffffffff
0x7fb838a8a0a95046b9d9d9fb4440f7bbc1a7bd3b
0xa019c198b9d9d9fb4440f7bc415ff5e4;