[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);
else
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:
170141183460469225450570946617781744489
170141183460469229545748130981302223887
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.
--
Torbjörn
- Re: 70x speed-up for seq's common cases, (continued)
Re: 70x speed-up for seq's common cases, Pádraig Brady, 2012/09/14
Re: 70x speed-up for seq's common cases, Torbjorn Granlund, 2012/09/14
Re: 70x speed-up for seq's common cases, Jim Meyering, 2012/09/15
- Re: 70x speed-up for seq's common cases,
Torbjorn Granlund <=