[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#45343: factor: missed optimizations
From: |
Denys Vlasenko |
Subject: |
bug#45343: factor: missed optimizations |
Date: |
Sun, 20 Dec 2020 17:16:49 +0100 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.4.0 |
factor ---debug output is rather rudimentary.
In order to understand the logic, I added more printouts
(try attached debug patch)
and immediately noticed some obvious snafus:
$ src/factor ---debug 340282366920938461286658806734041124249
[using arbitrary-precision arithmetic]
340282366920938461286658806734041124249:[trial division
340282366920938461286658806734041124249] [trial stopped 4999(max)] [is number
34028236692093846128665880673404112424
9 prime?] [no] [pollard-rho (1)]
1:1:2:4:8:16:32:64:128:256:512:1024:2048:4096:8192:16384:32768:65536:131072:262144:524288:1048576:2097152:4194304:8388608:16777216:33554432:67108864:134217728:268435456:536870912
[factor found][rho factor 18446744073709551557] [trial division
18446744073709551556] [factor 2] [factor 2] [factor 11] [factor 137] [factor
547] [trial stopped 4999(max)] [is number 5594472617641 prime?] [trial
division 5594472617640] [factor 2] [factor 2] [factor 2] [factor 3] [factor 5]
[factor 1427] [factor 2131] [trial stopped 2131] [is number 15331 prime?] [yes]
[factor 15331] [yes] ...
Look at the ens of the last line.
We don't need to check whether 15331 is prime. We know it is: we just stopped
trial division because next prime divisor to try is larger than
sqrt(number_we_try_to_factor) - therefore number_we_try_to_factor
has no more divisors, ergo it's prime. The fix:
for (unsigned int i = 1; i <= PRIMES_PTAB_ENTRIES;)
{
if (! mpz_divisible_ui_p (t, p))
{
p += primes_diff[i++];
if (mpz_cmp_ui (t, p * p) < 0)
+ mp_factor_insert (factors, t);
+ mpz_set_ui (t, 1);
break;
}
else
... [factor 5594472617641] [factor
18446744073709551557] [trial division 18446744073709551556] [factor 2] [factor
2] [factor 11] [factor 137] [factor 547] [trial stopped 4999(max)] [is number
5594472617641 prime?] [trial division 5594472617640]
[factor 2] [factor 2] [factor 2] [factor 3] [factor 5] [factor 1427] [factor
2131] [trial stopped 2131] [is number 15331 prime?] [yes] [factor 15331] [yes]
[factor 5594472617641] [factor 18446744073709551557] [p
ollard-rho end]
18446744073709551557 18446744073709551557
Second optimization is this: as you see, I deliberately fed it a square
(the factorization result is 18446744073709551557^2).
It happily did not notice it and spent an awful lot of time in pollard rho:
1:1:2:4:8:16:32:64:128:256:512:1024:2048:4096:8192:16384:32768:65536:131072:262144:524288:1048576:2097152:4194304:8388608:16777216:33554432:67108864:134217728:268435456:536870912
A quick check for square drastically cuts down execution time:
/* Use Pollard-rho to compute the prime factors of
arbitrary-precision T, and put the results in FACTORS. */
static void
+mp_factor_big (mpz_t t, struct mp_factors *factors)
+{
+ /* the _big() function assumes trial division was already tried */
+ devmsg ("[is number prime?] ");
+ if (mp_prime_p (t))
+ mp_factor_insert (factors, t);
+ else
+ if (mpz_perfect_square_p (t))
+ {
+ struct mp_factors f2;
+ devmsg ("[it is square] ");
+ mpz_sqrt (t, t);
+ mp_factor_init (&f2);
+ mp_factor_big (t, &f2);
+ for (unsigned long int i = 0; i < f2.nfactors; i++)
+ {
+ unsigned long int e = f2.e[i];
+ while (e--) { //
+ mp_factor_insert (factors, f2.p[i]); //FIXME: obvious
optimization:
+ mp_factor_insert (factors, f2.p[i]); // need to introduce/use
mp_factor_insert_multiplicity(..., e*2);
+ }
+ }
+ mp_factor_clear (&f2);
+ }
+ else
+ mp_factor_using_pollard_rho (t, 1, factors);
+}
+
+static void
mp_factor (mpz_t t, struct mp_factors *factors)
{
mp_factor_init (factors);
@@ -2265,11 +2309,7 @@ mp_factor (mpz_t t, struct mp_factors *f
.
if (mpz_cmp_ui (t, 1) != 0)
{
- devmsg ("[is number prime?] ");
- if (mp_prime_p (t))
- mp_factor_insert (factors, t);
- else
- mp_factor_using_pollard_rho (t, 1, factors);
+ mp_factor_big (t, factors);
}
}
}
zz.diff
Description: Text Data
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- bug#45343: factor: missed optimizations,
Denys Vlasenko <=