mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2022-11-27, 19:51   #210
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·2,179 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
See https://github.com/gerbicz/CM/blob/main/corn.c .
The original code for Cornacchia just called Pari-Gp.
At 8k digits my Cornacchia code is 5.8 times faster, and for larger N it could be even faster.

Original code on approx 8k digits input (N=10^8007+21) using 4 physical cores, without gwnum library:
Code:
-- Size [0]: 26599 bits
   Time for discriminant -1642404: 470.9 (159.5)
   largest prime of d: 97
   largest prime of h: 5
       discriminants: 1.9 (1.9)
       54 qroot:      86.3 (29.3)
    57684 Cornacchia: 184.4 (62.4)
     1644 trial div:  46.0 (11.5)
       90 is_prime:   152.4 (54.4)
-- Size [1]: 26529 bits
   Time for discriminant -6487771: 1707.2 (575.7)
   largest prime of d: 907
   largest prime of h: 13
       discriminants: 2.0 (2.0)
      156 qroot:      255.6 (86.5)
   150518 Cornacchia: 479.9 (161.7)
     3236 trial div:  90.8 (22.8)
      816 is_prime:   1349.8 (462.3)
Using my own code:
Code:
-- Size [0]: 26599 bits
   Time for discriminant -1642404: 319.8 (108.5)
   largest prime of d: 97
   largest prime of h: 5
       discriminants: 1.9 (1.9)
       54 qroot:      86.4 (29.3)
    57684 Cornacchia: 32.9 (11.2)
     1644 trial div:  46.1 (11.6)
       90 is_prime:   152.5 (54.6)
-- Size [1]: 26529 bits
   Time for discriminant -6487771: 1459.2 (493.8)
   largest prime of d: 907
   largest prime of h: 13
       discriminants: 2.0 (2.0)
      156 qroot:      254.5 (86.2)
   150518 Cornacchia: 81.7 (27.7)
     3236 trial div:  91.0 (22.9)
      816 is_prime:   1349.8 (463.5)
Use gmp's half gcd code, do constant number of Euclidean algorithm's steps on the top limbs in constant time(!),
then do several mod tricks/quadratic residue tests to decrease the further computations.
More in the code, probably this time I have over commented. Used my own Legendre symbol code, it is also faster than the built-in kronecker. (calling it only for (k/n), when n is prime, so Legendre=kronecker).

Pointless to test it below 2^512, since it falls back to the original code. Also it is worth to see
the so called second step in the ecpp [I had code that failed in that part, since not saved V in the 1st step].

To compile: maybe it would work without any problem, for me the process:

On lib folder's pari.c replace the bool cm_pari_cornacchia function() with my code.
./configure --enable-mpi
On lib folder's makefile at the 263th line add to that line -I/home/gerbicz/gmp-6.2.1 -L/home/gerbicz/gmp-6.2.1
use your installed gmp's folder name. (this line was for the CFLAGS).
make install
Thanks Robert. The only thing I had to do differently to your instructions was to use

#include "/home/paul/Downloads/gmp-6.2.1/gmp-impl.h"

I am looking forward to seeing a nice speed up in production runs.

Last fiddled with by paulunderwood on 2022-11-27 at 20:59
paulunderwood is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
For which types of primes is GPU primality test software available? bur GPU Computing 6 2020-08-28 06:20
Fastest software for Mersenne primality test? JonathanM Information & Answers 25 2020-06-16 02:47
APR-CL as primality proof f1pokerspeed FactorDB 14 2014-01-09 21:06
Proof of Primality Test for Fermat Numbers princeps Math 15 2012-04-02 21:49
PRIMALITY PROOF for Wagstaff numbers! AntonVrba Math 96 2009-02-25 10:37

All times are UTC. The time now is 22:55.


Mon Nov 28 22:55:35 UTC 2022 up 102 days, 20:24, 0 users, load averages: 1.47, 1.29, 1.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔