Another small patch for nextprime.
I've fairly sure moduli is allocating extra space.
eights:~/Projects/git-gmp$ grep -ri TMP_SALLOC_TYPE
gmp-impl.h:#define TMP_SALLOC_TYPE(n,type) ((type *) TMP_SALLOC ((n) *
sizeof (type)))
gmp-impl.h:#define TMP_SALLOC_LIMBS(n) TMP_SALLOC_TYPE(n,mp_limb_t)
gmp-impl.h:#define TMP_SALLOC_MP_PTRS(n) TMP_SALLOC_TYPE(n,mp_ptr)
mpz/nextprime.c: moduli = TMP_SALLOC_TYPE (prime_limit * sizeof moduli[0],
unsigned short);
I ran t-nextprime and attached a patch, happy to be wrong for some silly
reason
On Wed, Sep 4, 2019 at 11:00 AM Niels Möller <ni...@lysator.liu.se> wrote:
> paul zimmermann <paul.zimmerm...@inria.fr> writes:
>
> > with a small base, no need of k-ary modexp. In the REDC domain, instead
> of
> > computing a'*b'/r mod n, where b' = r*b mod n is the REDC encoding of
> the
> > base b, just compute a'*b mod n.
>
> Right, since the montgomery/redc mapping a <-> a' is linear, the needed
> multiply operation is simply
>
> x --> x * b (mod m)
>
> no matter if x is in montgomery representation or not. The easy way to
> do that is x * b followed by euclidean division with a single-limb
> quotient. One could perhaps also do x * b / B (mod m), with a
> single-limb hensel quotient. One then has to keep track of those powers
> of B^-1, and it's unclear to me if they can be handled efficiently
> enough to make Hensel-division useful here.
>
> Another trick (I think Marco already mentioned this) may be to find the
> largest k such that c = b^k fits in one limb, and compute
>
> b^e = c^{floor(e/k)] * b^{e mod k}
>
> (and if we handle b = 2 as a special case, one could take k =
> GMP_NUMB_BITS, even if c then doesn't quite fit in one limb)).
>
> That will save log_2(k) squarings, so will make a nticable difference
> only when the exponent is few limbs. But could be relevant for
> millerrabin tests of numbers of a hundred bits or so.
>
> Regards,
> /Niels
>
> --
> Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
> Internet email is subject to wholesale government surveillance.
>
From 9193a47817410aaf849152d16be7fef6986780db Mon Sep 17 00:00:00 2001
From: Seth Troisi <sethtro...@google.com>
Date: Wed, 4 Sep 2019 23:09:28 -0700
Subject: [PATCH] Fixed overalloc
---
mpz/nextprime.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/mpz/nextprime.c b/mpz/nextprime.c
index 4c5ca57..1a0b5b6 100644
--- a/mpz/nextprime.c
+++ b/mpz/nextprime.c
@@ -80,7 +80,7 @@ mpz_nextprime (mpz_ptr p, mpz_srcptr n)
TMP_SMARK;
/* Compute residues modulo small odd primes */
- moduli = TMP_SALLOC_TYPE (prime_limit * sizeof moduli[0], unsigned short);
+ moduli = TMP_SALLOC_TYPE (prime_limit, unsigned short);
for (;;)
{
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
