[Gmp-commit] /var/hg/gmp: mpz/fac_ui.c: Save half the products for small values

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/a9440b272ec5
changeset: 18268:a9440b272ec5
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Sun Oct 31 14:59:02 2021 +0100
description:
mpz/fac_ui.c: Save half the products for small values

diffstat:

 ChangeLog    |   4 ++++
 mpz/fac_ui.c |  30 ++++++++++++++++++++++--------
 2 files changed, 26 insertions(+), 8 deletions(-)

diffs (67 lines):

diff -r d343c620e614 -r a9440b272ec5 ChangeLog
--- a/ChangeLog	Sun Oct 31 02:09:45 2021 +0100
+++ b/ChangeLog	Sun Oct 31 14:59:02 2021 +0100
@@ -1,3 +1,7 @@
+2021-10-31 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+	* mpz/fac_ui.c: Save half the products for small values.
+
 2021-10-08  Niels Möller  <nisse at lysator.liu.se>
 
 	* tests/mpn/t-addaddmul.c: Unit test for mpn_addaddmul_1msb0.
diff -r d343c620e614 -r a9440b272ec5 mpz/fac_ui.c
--- a/mpz/fac_ui.c	Sun Oct 31 02:09:45 2021 +0100
+++ b/mpz/fac_ui.c	Sun Oct 31 14:59:02 2021 +0100
@@ -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 @@
       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);