diff options
| author | Marco Bodrato <bodrato@mail.dm.unipi.it> | 2012-02-27 08:25:17 +0100 |
|---|---|---|
| committer | Marco Bodrato <bodrato@mail.dm.unipi.it> | 2012-02-27 08:25:17 +0100 |
| commit | 3da513159964b2309bdc79d667aae4d12bf07911 (patch) | |
| tree | cc48f6a769a79054b23164970583d5500a507719 /mpz/oddfac_1.c | |
| parent | be9ffc43cfa97a67cdca4f4e5603ec3165781630 (diff) | |
| download | gmp-3da513159964b2309bdc79d667aae4d12bf07911.tar.gz | |
oddfac: small speed-up for small argument.
Diffstat (limited to 'mpz/oddfac_1.c')
| -rw-r--r-- | mpz/oddfac_1.c | 38 |
1 files changed, 23 insertions, 15 deletions
diff --git a/mpz/oddfac_1.c b/mpz/oddfac_1.c index 1fbd3bda2..c367b880a 100644 --- a/mpz/oddfac_1.c +++ b/mpz/oddfac_1.c @@ -488,6 +488,11 @@ log_n_max (mp_limb_t n) if n is odd, n > FAC_DSC_THRESHOLD and flag = 1, x is set to n!!. If n is too small, flag is ignored, and an ASSERT can be triggered. + + TODO: FAC_DSC_THRESHOLD is used here with two different roles: + - to decide when prime factorisation is needed, + - to stop the recursion, once sieving is done. + Maybe two thresholds can do a better job. */ void mpz_oddfac_1 (mpz_ptr x, mp_limb_t n, unsigned flag) @@ -512,8 +517,6 @@ mpz_oddfac_1 (mpz_ptr x, mp_limb_t n, unsigned flag) { static const mp_limb_t tabled[] = { ONE_LIMB_ODD_DOUBLEFACTORIAL_TABLE }; mp_limb_t tn; - mp_size_t j; - TMP_SDECL; #if TUNE_PROGRAM_BUILD ASSERT (FAC_DSC_THRESHOLD_LIMIT >= FAC_DSC_THRESHOLD); @@ -523,14 +526,16 @@ mpz_oddfac_1 (mpz_ptr x, mp_limb_t n, unsigned flag) for (tn = n; ABOVE_THRESHOLD (tn, FAC_DSC_THRESHOLD); s++) tn >>= 1; - j = 0; - - TMP_SMARK; - factors = TMP_SALLOC_LIMBS (1 + tn / FACTORS_PER_LIMB); - ASSERT (tn >= FACTORS_PER_LIMB); - if (tn >= numberof (tabled) * 2 + 1) { mp_limb_t prod, max_prod, i; + mp_size_t j; + TMP_SDECL; + + j = 0; + + TMP_SMARK; + factors = TMP_SALLOC_LIMBS (1 + tn / FACTORS_PER_LIMB); + ASSERT (tn >= FACTORS_PER_LIMB); prod = 1; #if TUNE_PROGRAM_BUILD @@ -551,14 +556,17 @@ mpz_oddfac_1 (mpz_ptr x, mp_limb_t n, unsigned flag) } while (tn >= numberof (tabled) * 2 + 1); factors[j++] = prod; + ASSERT (numberof (tablef) > numberof (tabled)); + factors[j++] = tabled[(tn - 1) >> 1]; + factors[j++] = tablef[tn >> 1]; + mpz_prodlimbs (x, factors, j); + + TMP_SFREE; + } else { + MPZ_REALLOC (x, 2); + umul_ppmm (PTR (x)[1], PTR (x)[0], tabled[(tn - 1) >> 1], tablef[tn >> 1]); + SIZ (x) = 2; } - - ASSERT (numberof (tablef) > numberof (tabled)); - factors[j++] = tabled[(tn - 1) >> 1]; - factors[j++] = tablef[tn >> 1]; - mpz_prodlimbs (x, factors, j); - - TMP_SFREE; } if (s != 0) |