* 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
/*----- Test rig ----------------------------------------------------------*/
-
#ifdef TEST_RIG
-#define MP(x) mp_readstring(MP_NEW, #x, 0, 0)
-
static int vreduce(dstr *v)
{
mp *d = *(mp **)v[0].buf;