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