[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: Torbjorn Granlund
Subject: Re: 70x speed-up for seq's common cases
Date: Sun, 16 Sep 2012 02:57:11 +0200
User-agent: Gnus/5.11 (Gnus v5.11) Emacs/22.3 (berkeley-unix)

Jim Meyering <address@hidden> writes:

  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?
I tested this when this code was committed, using a special script.  The
problem is making Pollard rho find a factor of 65 bits or more, and
since this Pollard rho code accepts 128-bit numbers, that means finding
the 2nd largest factor.  I could find only these two examples:


These will take a few minutes to run through our code, even on the
fastest hardware, since they are absolutely worst-case numbers for
Pollard rho.


reply via email to

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