[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: 70x speed-up for seq's common cases

From: Jim Meyering
Subject: Re: 70x speed-up for seq's common cases
Date: Sat, 15 Sep 2012 20:18:12 +0200

Torbjorn Granlund wrote:
> For general seq use, I suppose we should do away with `incr' and instead
> use a general `add'.  Below is a suggested implementation, and as bonus
> also a `sub'.
> Like `incr', `add' needs an extra byte if space, since if the end value
> is within the increment from a power of 10, a number with one more digit
> than the end value will be created.
> Implementing negative values is a bit tricky.  If a-b is wanted and a <
> b, one must of course compute b-a and separately store a minus sign.  I
> just write a `sub' function, not any code actually handling negative
> numbers.
> The function `add' is reasonably well-tested.  The function `sub' is
> minimally tested (but as a trivial edit of `add' it might b correct
> anyway).

Thanks.  I'm sure someone will find time to experiment with those.

Looking at factor.c, I saw this bit of code,
and confirm that the current tests do not exercise it.

          /* The found factor is two words.  This is highly unlikely, thus hard
             to trigger.  Please be careful before you change this code!  */
          uintmax_t ginv;

          binv (ginv, g0);      /* Compute n = n / g.  Since the result will */
          n0 = ginv * n0;       /* fit one word, we can compute the quotient */
          n1 = 0;               /* modulo B, ignoring the high divisor word. */

          if (!prime2_p (g1, g0))
            factor_using_pollard_rho2 (g1, g0, a + 1, factors);
            factor_insert_large (factors, g1, g0);

Can you provide a test case that exercises that code?

reply via email to

[Prev in Thread] Current Thread [Next in Thread]