diff options
| author | Marco Bodrato <bodrato@mail.dm.unipi.it> | 2021-10-31 14:59:02 +0100 |
|---|---|---|
| committer | Marco Bodrato <bodrato@mail.dm.unipi.it> | 2021-10-31 14:59:02 +0100 |
| commit | 95598d6a69673f542937add53ab18e4bcdaba3ed (patch) | |
| tree | 0187d8feff869070b6c1a0cbe0a49e48136ecbbd /mpz | |
| parent | d3ce0b51962f3afd1e5938275117149d656b69b8 (diff) | |
| download | gmp-95598d6a69673f542937add53ab18e4bcdaba3ed.tar.gz | |
mpz/fac_ui.c: Save half the products for small values
Diffstat (limited to 'mpz')
| -rw-r--r-- | mpz/fac_ui.c | 30 |
1 files changed, 22 insertions, 8 deletions
diff --git a/mpz/fac_ui.c b/mpz/fac_ui.c index db3cfeee3..a7998b366 100644 --- a/mpz/fac_ui.c +++ b/mpz/fac_ui.c @@ -2,8 +2,8 @@ Contributed to the GNU project by Marco Bodrato. -Copyright 1991, 1993-1995, 2000-2003, 2011, 2012, 2015 Free Software -Foundation, Inc. +Copyright 1991, 1993-1995, 2000-2003, 2011, 2012, 2015, 2021 Free +Software Foundation, Inc. This file is part of the GNU MP Library. @@ -68,21 +68,35 @@ mpz_fac_ui (mpz_ptr x, unsigned long n) mp_limb_t prod, max_prod; mp_size_t j; mp_ptr factors; + mp_limb_t fac, diff = n - numberof (table); TMP_SDECL; TMP_SMARK; - factors = TMP_SALLOC_LIMBS (2 + (n - numberof (table)) / FACTORS_PER_LIMB); + factors = TMP_SALLOC_LIMBS (2 + diff / FACTORS_PER_LIMB); factors[0] = table[numberof (table)-1]; j = 1; - prod = n; + if ((diff & 1) == 0) + { + prod = n; + /* if (diff != 0) */ + fac = --n * numberof (table); + } + else + { + prod = n * numberof (table); + fac = prod + --diff; + } + #if TUNE_PROGRAM_BUILD - max_prod = GMP_NUMB_MAX / FAC_DSC_THRESHOLD_LIMIT; + max_prod = GMP_NUMB_MAX / (FAC_DSC_THRESHOLD_LIMIT * FAC_DSC_THRESHOLD_LIMIT); #else - max_prod = GMP_NUMB_MAX / (FAC_ODD_THRESHOLD | 1); + max_prod = GMP_NUMB_MAX / + (((FAC_ODD_THRESHOLD + numberof (table) + 1) / 2) * + ((FAC_ODD_THRESHOLD + numberof (table)) / 2)); #endif - while (--n >= numberof (table)) - FACTOR_LIST_STORE (n, prod, max_prod, factors, j); + for (;diff != 0; fac += (diff -= 2)) + FACTOR_LIST_STORE (fac, prod, max_prod, factors, j); factors[j++] = prod; mpz_prodlimbs (x, factors, j); |