[Gmp-commit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Tue Aug 13 20:16:50 UTC 2019
details: /var/hg/gmp/rev/905368e1d069
changeset: 17807:905368e1d069
user: Torbjorn Granlund <tg at gmplib.org>
date: Tue Aug 13 22:13:39 2019 +0200
description:
Add more variants of of x86_64 gcd_11.asm and tweak existing ones.
details: /var/hg/gmp/rev/4ab0629f9da7
changeset: 17808:4ab0629f9da7
user: Torbjorn Granlund <tg at gmplib.org>
date: Tue Aug 13 22:16:47 2019 +0200
description:
Merge.
diffstat:
ChangeLog | 11 ++++
doc/gmp.texi | 16 ++++--
mini-gmp/ChangeLog | 4 +
mini-gmp/mini-gmp.c | 10 ++--
mpn/x86_64/bd2/gcd_11.asm | 68 +++++++++++++-------------
mpn/x86_64/bd4/gcd_11.asm | 93 +++++++++++++++++++++++++++++++++++++
mpn/x86_64/core2/gcd_11.asm | 59 +++++++++++------------
mpn/x86_64/coreihwl/gcd_11.asm | 93 +++++++++++++++++++++++++++++++++++++
mpn/x86_64/coreinhm/gcd_11.asm | 93 +++++++++++++++++++++++++++++++++++++
mpn/x86_64/coreisbr/gcd_11.asm | 37 ++++++++++++++
mpn/x86_64/zen/gcd_11.asm | 2 +-
mpn/x86_64/zen2/gcd_11.asm | 102 +++++++++++++++++++++++++++++++++++++++++
mpz/millerrabin.c | 96 ++++++++++++++++++++++++++++++++-----
tests/misc.c | 4 +-
tests/mpz/t-pprime_p.c | 4 +-
15 files changed, 598 insertions(+), 94 deletions(-)
diffs (truncated from 911 to 300 lines):
diff -r b252c7e4f9b6 -r 4ab0629f9da7 ChangeLog
--- a/ChangeLog Thu Aug 08 16:29:36 2019 +0200
+++ b/ChangeLog Tue Aug 13 22:16:47 2019 +0200
@@ -1,3 +1,14 @@
+2018-11-07 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ From Seth Troisi:
+ * doc/gmp.texi: Update mpz_millerrabin documentation.
+
+ * mpn/x86_64/bd2/gcd_11.asm: Micro-optimisation.
+ * doc/gmp.texi: Further update in mpz_millerrabin.
+ * tests/misc.c: Silence a warning.
+ * tests/mpz/t-pprime_p.c (const primes): One more prime in the list.
+ * mpz/millerrabin.c: Return 2 for surely prime numbers (BPSW checked).
+
2019-08-08 Niels Möller <nisse at lysator.liu.se>
* tests/refmpn.c (refmpn_gcd_11): New function, based on refmpn_gcd_1.
diff -r b252c7e4f9b6 -r 4ab0629f9da7 doc/gmp.texi
--- a/doc/gmp.texi Thu Aug 08 16:29:36 2019 +0200
+++ b/doc/gmp.texi Tue Aug 13 22:16:47 2019 +0200
@@ -3548,12 +3548,16 @@
return 1 if @var{n} is probably prime (without being certain), or return 0 if
@var{n} is definitely non-prime.
-This function performs some trial divisions, then @var{reps} Miller-Rabin
-probabilistic primality tests. A higher @var{reps} value will reduce the
-chances of a non-prime being identified as ``probably prime''. A composite
-number will be identified as a prime with a probability of less than
- at m{4^{-reps},4^(- at var{reps})}. Reasonable values of @var{reps} are between 15
-and 50.
+This function performs some trial divisions, a Baillie-PSW probable prime
+test, then @var{reps-24} Miller-Rabin probabilistic primality tests. A
+higher @var{reps} value will reduce the chances of a non-prime being
+identified as ``probably prime''. A composite number will be identified as a
+prime with an asymptotic probability of less than @m{4^{-reps},4^(- at var{reps})}.
+Reasonable values of @var{reps} are between 15 and 50.
+
+GMP versions up to and including 6.1.2 did not use the Baillie-PSW
+primality test. In those older versions of GMP, this function performed
+ at var{reps} Miller-Rabin tests.
@end deftypefun
@deftypefun void mpz_nextprime (mpz_t @var{rop}, const mpz_t @var{op})
diff -r b252c7e4f9b6 -r 4ab0629f9da7 mini-gmp/ChangeLog
--- a/mini-gmp/ChangeLog Thu Aug 08 16:29:36 2019 +0200
+++ b/mini-gmp/ChangeLog Tue Aug 13 22:16:47 2019 +0200
@@ -1,3 +1,7 @@
+2018-11-07 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mini-gmp/mini-gmp.c: Silence a couple of warnings.
+
2018-10-30 Marco Bodrato <bodrato at mail.dm.unipi.it>
* mini-gmp.c (mpz_probab_prime_p): BPSW test for primality.
diff -r b252c7e4f9b6 -r 4ab0629f9da7 mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Thu Aug 08 16:29:36 2019 +0200
+++ b/mini-gmp/mini-gmp.c Tue Aug 13 22:16:47 2019 +0200
@@ -2,7 +2,7 @@
Contributed to the GNU project by Niels Möller
-Copyright 1991-1997, 1999-2018 Free Software Foundation, Inc.
+Copyright 1991-1997, 1999-2019 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -295,7 +295,7 @@
}
static void *
-gmp_default_realloc (void *old, size_t old_size, size_t new_size)
+gmp_default_realloc (void *old, size_t unused_old_size, size_t new_size)
{
void * p;
@@ -308,7 +308,7 @@
}
static void
-gmp_default_free (void *p, size_t size)
+gmp_default_free (void *p, size_t unused_size)
{
free (p);
}
@@ -1595,7 +1595,7 @@
int LOCAL_GMP_LIMB_BITS = GMP_LIMB_BITS;
unsigned long r = 0;
mp_size_t n = GMP_ABS (u->_mp_size);
- n = GMP_MIN (n, 1 + (GMP_ULONG_BITS - 1) / GMP_LIMB_BITS);
+ n = GMP_MIN (n, 1 + (mp_size_t) (GMP_ULONG_BITS - 1) / GMP_LIMB_BITS);
while (--n >= 0)
r = (r << LOCAL_GMP_LIMB_BITS) + u->_mp_d[n];
return r;
@@ -3499,7 +3499,7 @@
b0 = mpz_scan0 (n, 0);
/* D= P^2 - 4Q; P = 1; Q = (1-D)/4 */
- Q = (D & 2) ? (D >> 2) + 1 : -(long) (D >> 2);
+ Q = (D & 2) ? (long) (D >> 2) + 1 : -(long) (D >> 2);
if (! gmp_lucas_mod (V, Qk, Q, b0, n)) /* If Ud != 0 */
while (V->_mp_size != 0 && --b0 != 0) /* while Vk != 0 */
diff -r b252c7e4f9b6 -r 4ab0629f9da7 mpn/x86_64/bd2/gcd_11.asm
--- a/mpn/x86_64/bd2/gcd_11.asm Thu Aug 08 16:29:36 2019 +0200
+++ b/mpn/x86_64/bd2/gcd_11.asm Tue Aug 13 22:16:47 2019 +0200
@@ -1,4 +1,4 @@
-dnl AMD64 mpn_gcd_11 optimised for AMD BD2-BD4, Zen.
+dnl AMD64 mpn_gcd_11 optimised for AMD BD2, BD3, BT2.
dnl Based on the K7 gcd_1.asm, by Kevin Ryde. Rehacked for AMD64 by Torbjorn
dnl Granlund.
@@ -36,30 +36,31 @@
C cycles/bit (approx)
-C AMD K8,K9 ?
-C AMD K10 ?
-C AMD bd1 ?
-C AMD bd2 ?
+C AMD K8,K9 -
+C AMD K10 -
+C AMD bd1 -
+C AMD bd2 3.27 *
C AMD bd3 ?
-C AMD bd4 3.65
-C AMD bt1 ?
-C AMD bt2 ?
-C AMD zn1 3.5
-C AMD zn2 3.8
-C Intel P4 ?
-C Intel core2 ?
-C Intel NHM ?
-C Intel SBR ?
-C Intel IBR ?
+C AMD bd4 3.79
+C AMD bt1 -
+C AMD bt2 3.64 *
+C AMD zn1 3.25
+C AMD zn2 3.50
+C Intel P4 -
+C Intel CNR -
+C Intel PNR -
+C Intel NHM -
+C Intel WSM -
+C Intel SBR -
+C Intel IBR -
C Intel HWL ?
C Intel BWL ?
C Intel SKL ?
-C Intel atom ?
-C Intel SLM ?
-C Intel GLM ?
-C Intel GLM+ ?
-C VIA nano ?
-C Numbers measured with: speed -CD -s16-64 -t48 mpn_gcd_1
+C Intel atom -
+C Intel SLM -
+C Intel GLM -
+C Intel GLM+ -
+C VIA nano -
define(`u0', `%rdi')
define(`v0', `%rsi')
@@ -72,22 +73,21 @@
ALIGN(16)
PROLOGUE(mpn_gcd_11)
FUNC_ENTRY(2)
- mov v0, %r10 C
- sub u0, %r10 C
+ mov v0, %rax C
+ sub u0, v0 C
jz L(end) C
- ALIGN(16) C K10 BD1 BD2 ZEN CNR NHM SBR
-L(top): rep;bsf %r10, %rcx C tzcnt! 3 3 3 2 6 5 5
- mov u0, %r9 C 2 2 2 2 3 3 4
- sub v0, u0 C 2 2 2 2 4 3 4
- cmovc %r10, u0 C if x-y < 0 0,3 0,3 0,3 0,3 0,6 0,5 0,5
- cmovc %r9, v0 C use x,y-x 0,3 0,3 0,3 0,3 2,8 1,7 1,7
- shr R8(%rcx), u0 C 1,7 1,6 1,5 1,4 2,8 2,8 2,8
- mov v0, %r10 C 1 1 1 1 4 3 3
- sub u0, %r10 C 2 2 2 1 5 4 4
+ ALIGN(16) C
+L(top): rep;bsf v0, %rcx C tzcnt!
+ mov u0, %r9 C
+ sub %rax, u0 C u - v
+ cmovc v0, u0 C u = |u - v|
+ cmovc %r9, %rax C v = min(u,v)
+ shr R8(%rcx), u0 C
+ mov %rax, v0 C
+ sub u0, v0 C v - u
jnz L(top) C
-L(end): mov v0, %rax
- FUNC_EXIT()
+L(end): FUNC_EXIT()
ret
EPILOGUE()
diff -r b252c7e4f9b6 -r 4ab0629f9da7 mpn/x86_64/bd4/gcd_11.asm
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/x86_64/bd4/gcd_11.asm Tue Aug 13 22:16:47 2019 +0200
@@ -0,0 +1,93 @@
+dnl AMD64 mpn_gcd_11 optimised for AMD BD4, ZN1.
+
+dnl Based on the K7 gcd_1.asm, by Kevin Ryde. Rehacked for AMD64 by Torbjorn
+dnl Granlund.
+
+dnl Copyright 2000-2002, 2005, 2009, 2011, 2012, 2017, 2019 Free Software
+dnl Foundation, Inc.
+
+dnl This file is part of the GNU MP Library.
+dnl
+dnl The GNU MP Library is free software; you can redistribute it and/or modify
+dnl it under the terms of either:
+dnl
+dnl * the GNU Lesser General Public License as published by the Free
+dnl Software Foundation; either version 3 of the License, or (at your
+dnl option) any later version.
+dnl
+dnl or
+dnl
+dnl * the GNU General Public License as published by the Free Software
+dnl Foundation; either version 2 of the License, or (at your option) any
+dnl later version.
+dnl
+dnl or both in parallel, as here.
+dnl
+dnl The GNU MP Library is distributed in the hope that it will be useful, but
+dnl WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+dnl or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+dnl for more details.
+dnl
+dnl You should have received copies of the GNU General Public License and the
+dnl GNU Lesser General Public License along with the GNU MP Library. If not,
+dnl see https://www.gnu.org/licenses/.
+
+include(`../config.m4')
+
+
+C cycles/bit (approx)
+C AMD K8,K9 -
+C AMD K10 -
+C AMD bd1 -
+C AMD bd2 -
+C AMD bd3 -
+C AMD bd4 2.86 *
+C AMD bt1 -
+C AMD bt2 -
+C AMD zn1 2.66 *
+C AMD zn2 3.48
+C Intel P4 -
+C Intel CNR -
+C Intel PNR -
+C Intel NHM -
+C Intel WSM -
+C Intel SBR -
+C Intel IBR -
+C Intel HWL ?
+C Intel BWL ?
+C Intel SKL ?
+C Intel atom -
+C Intel SLM -
+C Intel GLM -
+C Intel GLM+ -
+C VIA nano -
+
+define(`u0', `%rdi')
+define(`v0', `%rsi')
+
+ABI_SUPPORT(DOS64)
+ABI_SUPPORT(STD64)
+
+ASM_START()
+ TEXT
+ ALIGN(16)
+PROLOGUE(mpn_gcd_11)
+ FUNC_ENTRY(2)
+ mov v0, %rax C
+ sub u0, v0 C
+ jz L(end) C
+
+ ALIGN(16) C
+L(top): rep;bsf v0, %rcx C
+ sub %rax, u0 C u - v
+ cmovc v0, u0 C u = |u - v|
+ cmovc %r9, %rax C v = min(u,v)
+ shrx( %rcx, u0, %r9) C
+ shrx( %rcx, u0, u0) C
+ mov %rax, v0 C
+ sub u0, v0 C v - u
+ jnz L(top) C
+
+L(end): FUNC_EXIT()
+ ret
+EPILOGUE()
diff -r b252c7e4f9b6 -r 4ab0629f9da7 mpn/x86_64/core2/gcd_11.asm
--- a/mpn/x86_64/core2/gcd_11.asm Thu Aug 08 16:29:36 2019 +0200
+++ b/mpn/x86_64/core2/gcd_11.asm Tue Aug 13 22:16:47 2019 +0200
@@ -1,4 +1,4 @@
More information about the gmp-commit
mailing list