This is an automated email from the git hooks/post-receive script.
ppm-guest pushed a commit to annotated tag v0.30
in repository libmath-prime-util-perl.
commit ea68447abee84ea9716fc9b2a6e9dc651b1e3fcf
Author: Dana Jacobsen <d...@acm.org>
Date: Thu Jun 27 13:56:36 2013 -0700
Speedup for P=1,Q=-1 Lucas sequence, which is half the standard/Strong
Lucas test cases
---
factor.c | 20 ++++++++++++++++++++
t/17-pseudoprime.t | 6 ++++++
2 files changed, 26 insertions(+)
diff --git a/factor.c b/factor.c
index 2be4af2..6d9c275 100644
--- a/factor.c
+++ b/factor.c
@@ -520,6 +520,26 @@ void lucas_seq(UV* Uret, UV* Vret, UV* Qkret, UV n, IV P,
IV Q, UV k)
if (V & 1) { V = (n>>1) + (V>>1) + 1; } else { V >>= 1; }
}
}
+ } else if (P == 1 && Q == -1) {
+ /* This is about 30% faster than the generic code below. Since 50% of
+ * Lucas and strong Lucas tests come here, I think it's worth doing. */
+ int sign = Q;
+ while (b > 1) {
+ U = mulmod(U, V, n);
+ if (sign == 1) V = mulsubmod(V, V, 2, n);
+ else V = muladdmod(V, V, 2, n);
+ sign = 1; /* Qk *= Qk */
+ b--;
+ if ( (k >> (b-1)) & UVCONST(1) ) {
+ UV t2 = mulmod(U, Dmod, n);
+ U = addmod(U, V, n);
+ if (U & 1) { U = (n>>1) + (U>>1) + 1; } else { U >>= 1; }
+ V = addmod(V, t2, n);
+ if (V & 1) { V = (n>>1) + (V>>1) + 1; } else { V >>= 1; }
+ sign = -1; /* Qk *= Q */
+ }
+ }
+ if (sign == 1) Qk = 1;
} else {
while (b > 1) {
U = mulmod(U, V, n);
diff --git a/t/17-pseudoprime.t b/t/17-pseudoprime.t
index 04d8d87..36eb7bf 100644
--- a/t/17-pseudoprime.t
+++ b/t/17-pseudoprime.t
@@ -85,6 +85,12 @@ my %lucas_sequences = (
"323 5 -1 81" => [153,195,322],
"49001 25 117 24501" => [20933,18744,19141],
"18971 10001 -1 4743" => [5866,14421,18970],
+ "18971 10001 -1 4743" => [5866,14421,18970],
+ "3613982120 1 -1 3613982121" => [609064756,513522106,3613982119],
+ "3613982121 1 -1 3613982122" => [2586640546,2746447323,1],
+ "3613982121 1 -1 1806991061" => [3535079342,1187662808,3613982120],
+ "547968611 1 -1 547968612" => [1,3,1],
+ "547968611 1 -1 136992153" => [27044236,448467899,547968610],
);
plan tests => 0 + 3
--
Alioth's /usr/local/bin/git-commit-notice on
/srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git
_______________________________________________
Pkg-perl-cvs-commits mailing list
Pkg-perl-cvs-commits@lists.alioth.debian.org
http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits
