Changeset 31748 in project


Ignore:
Timestamp:
11/02/14 14:25:36 (6 years ago)
Author:
sjamaan
Message:

numbers: A small simplification and optimization

File:
1 edited

Legend:

Unmodified
Added
Removed
  • release/4/numbers/trunk/numbers-c.c

    r31747 r31748  
    34243424         *q = big_q == C_SCHEME_UNDEFINED ? NULL : C_bignum_digits(big_q),
    34253425          p,               /* product of two halfdigits */
    3426           hat, qhat, rhat; /* estimated quotient and remainder digit */
     3426          hat, qhat, rhat, /* estimated quotient and remainder digit */
     3427          vn_1, vn_2;      /* "cached" values v[n-1], v[n-2] */
    34273428  C_word s, i, j, t, k;    /* loop and other vars */
    34283429
     
    34473448  if (HALF_DIGIT_AT(v, n-1) == 0) n--;
    34483449
     3450  /* These won't change during the loop, but are used in every step. */
     3451  vn_1 = HALF_DIGIT_AT(v, n-1);
     3452  vn_2 = HALF_DIGIT_AT(v, n-2);
     3453
    34493454  /* See also Hacker's Delight, Figure 9-1.  This is almost exactly that. */
    34503455  for (j = m - n; j >= 0; j--) {
    34513456    hat = C_BIGNUM_DIGIT_COMBINE(HALF_DIGIT_AT(u,j+n), HALF_DIGIT_AT(u,j+n-1));
    3452     qhat = hat / HALF_DIGIT_AT(v, n-1);
    3453     rhat = hat - qhat * HALF_DIGIT_AT(v, n-1); /* rhat = hat % v[n-1] */
     3457    qhat = hat / vn_1;
     3458    rhat = hat % vn_1;
    34543459
    34553460again:
    34563461    if (C_BIGNUM_DIGIT_HI_HALF(qhat) > 0 ||
    3457         qhat * HALF_DIGIT_AT(v, n-2) > C_BIGNUM_DIGIT_COMBINE(rhat, HALF_DIGIT_AT(u,j+n-2))) {
     3462        qhat * vn_2 > C_BIGNUM_DIGIT_COMBINE(rhat, HALF_DIGIT_AT(u,j+n-2))) {
    34583463      qhat--;
    3459       rhat += HALF_DIGIT_AT(v, n-1);
     3464      rhat += vn_1;
    34603465      if (C_BIGNUM_DIGIT_HI_HALF(rhat) == 0) goto again;
    34613466    }
     
    34643469    k = 0;
    34653470    for (i = 0; i < n; i++) {
    3466       p = qhat * HALF_DIGIT_AT(v,i);
     3471      p = qhat * HALF_DIGIT_AT(v, i);
    34673472      t = HALF_DIGIT_AT(u,i+j) - k - (p & C_BIGNUM_HALF_DIGIT_MASK);
    34683473      STORE_HALF_DIGIT_AT(u, i+j, t);
     
    34723477    STORE_HALF_DIGIT_AT(u, j+n, t);
    34733478
    3474     if (q != NULL) {
    3475       STORE_HALF_DIGIT_AT(q, j, qhat);
    3476     }
    3477    
    34783479    if (t < 0) {                /* Subtracted too much? */
    3479       if (q != NULL) {
    3480         STORE_HALF_DIGIT_AT(q, j, HALF_DIGIT_AT(q, j) - 1); /* Add back */
    3481       }
     3480      qhat--;
    34823481      k = 0;
    34833482      for (i = 0; i < n; i++) {
     
    34883487      STORE_HALF_DIGIT_AT(u, j+n, (HALF_DIGIT_AT(u, j+n) + k));
    34893488    }
     3489    if (q != NULL) STORE_HALF_DIGIT_AT(q, j, qhat);
    34903490  } /* end j */
    34913491}
Note: See TracChangeset for help on using the changeset viewer.