mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2014-03-19, 15:33   #122
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

12748 Posts
Default

It took a while, but I finally got a running executable. Thanks!
Puzzle-Peter is offline   Reply With Quote
Old 2014-07-16, 15:20   #123
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

12748 Posts
Default

Quote:
Originally Posted by Puzzle-Peter View Post
It took a while, but I finally got a running executable. Thanks!
After quite some time I wanted to start a real effort and compared polysieve to polysieve2. Something doesn't quite work out.
I am using 62601*2^36641-1 for s
P0=-6
P1=-3
Q0=0
Q1=0
Q2=2
Q3=1

c=-1, 1, 5

with these parameters, polysieve will produce a file while polysieve 2 exits and tells me that 18841 will divide every candidate for c=5. What is happening here?

Last fiddled with by Puzzle-Peter on 2014-07-16 at 15:20
Puzzle-Peter is offline   Reply With Quote
Old 2014-07-16, 21:14   #124
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

23×271 Posts
Default

I can't find a version of polysieve2 on my pc that gives that behavior. Can you provide the exact parameters(bound_small_primes etc). Is this using the gmp version?
henryzz is offline   Reply With Quote
Old 2014-07-19, 07:16   #125
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22×52×7 Posts
Default

Quote:
Originally Posted by henryzz View Post
I can't find a version of polysieve2 on my pc that gives that behavior. Can you provide the exact parameters(bound_small_primes etc). Is this using the gmp version?
It's been a while since I built it, but I believe it is the gmp version. I tried to rebuild but didn't remember about the -lgmp. Anyway this is what I used and what I got:

Params in the declarations:
Denom 1024
SmallPrimes2 256
Sieve_len 16384
Hash_bits3 27


Input and output:

Code:
  Sieve P(s)+a*Q(s)+c for multiple c values, with fixed s=k*b^n+d; P,Q is polynom.
  Give k: 62601
  Give b: 2
  Give n: 36641
  Give d: -1
  Give the degree of the P polynom: 1
  Give the 0-th coefficient of P: -6
  Give the 1-th coefficient of P: -3
  Give the degree of the Q polynom: 3
  Give the 0-th coefficient of Q: 0
  Give the 1-th coefficient of Q: 0
  Give the 2-th coefficient of Q: 2
  Give the 3-th coefficient of Q: 1
  Give the number of c values for the sieve: 3
  0-th c value: -1
  1-th c value: 1
  2-th c value: 5
  Give start and end value for 'a' (in billions)! 0 1000
  Give the limit for the wheel sieve (bound_small_primes): 11
  Give the limit for sieving primes (smallPrimes): 1000000000
  Give the limit for sieving primes (maxp): 10000000000
  Give the name of the file to output the numbers! test.txt
  Using primes for wheelsieve up to 11
  initialization of all small primes done, primepi(1000000000)=50847534
  Prime divisors of Q(s) up to 1000000000: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 
53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 
167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 
277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 
401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 
523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 
653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 
797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 
937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 
1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 
1171 1181 1187 1193 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 


[snip, exceeding 10,000 characters]

13421 13441 13451 13457 13463 13469 13477 13487 13499 13513 13523 13537 13553 
13567 13577 13591 13597 13613 13619 13627 13633 13649 13669 13679 13681 13687 
13691 13693 13697 13709 13711 13721 13723 13729 13751 13757 13759 13763 13781 
13789 13799 13807 13829 13831 13841
  Warning: 13841 | P(s)+a*Q(s)+(5) for every a value. Exit.
  25.282u 1.173s 1:16.00 34.8%

Last fiddled with by Puzzle-Peter on 2014-07-19 at 07:18
Puzzle-Peter is offline   Reply With Quote
Old 2014-07-19, 11:49   #126
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

23·271 Posts
Default

I still can't reproduce this. Could you attach your source code so I can do a comparison. Also what platform/compiler are you using?

I have attached a binary that works for me.
Attached Files
File Type: zip polysieve2_gmp.zip (325.9 KB, 179 views)
henryzz is offline   Reply With Quote
Old 2014-07-19, 15:52   #127
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

23·271 Posts
Default

I managed a fair speedup today by replacing the mulmod with a faster version.
This reduced one run from 130 seconds to 100 seconds.
Code:
lli mulmod(lli a, lli b, lli n) {
    lli d, dummy; /* d will get a*b mod c */
    asm ("imulq %3\n\t" /* mul a*b -> rdx:rax */
         "idivq %4\n\t" /* (a*b)/c -> quot in rax remainder in rdx */
         :"=a"(dummy), "=&d"(d) /* output */
         :"a"(a), "rm"(b), "rm"(n) /* input */
         :"cc" /* imulq and idivq can set conditions */
        );
    return d;
  }
Instead of:
Code:
lli mulmod(lli a,lli b,lli p){// return (a*b)%p
    lli y=(lli)((double)a*(double)b/p+0.5);
    lli r=a*b-y*p;
    if(r<0)r+=p;
    return r;
}
henryzz is offline   Reply With Quote
Old 2014-07-21, 14:57   #128
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22×52×7 Posts
Default

This is confusing me big time.

I seem to be unable to produce a new executable for polysieve2-gmp. I try
Code:
 gcc polysieve2-gmp.c -lgmp
and I get the message
Code:
   /usr/bin/ld: cannot find –lgmp
I did successfully compile the non-gmp version however and this time it's the number 53 that supposedly divides all of the +5 candidates. Comparing the code to polysieve.c shows only some very minor differences that should not be responsible for the difference in behavior. I do not understand this at all. For this test I used the code versions from post #119.

Platform is Linux

Redhat enterprise 2.6.18-371.3.1.e15

Compiler is gcc 4.1.2-54


Last fiddled with by Puzzle-Peter on 2014-07-21 at 14:58
Puzzle-Peter is offline   Reply With Quote
Old 2014-07-21, 18:33   #129
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

23×271 Posts
Default

Try modifying the order of the commands in your compile string. -lgmp might want to be first on your system. It might be worth seeing if adding optimization(-O3) changes the behavior. It would be amusing if there was a bug without optimization which is fixed with optimization.

Your gcc version is 7 years old. I am using 4.8.2. Might be worth updating if you can.

Robert do you have any ideas?
henryzz is offline   Reply With Quote
Old 2014-07-22, 18:39   #130
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22×52×7 Posts
Default

It's getting more confusing every day. I managed to compile the gmp version, had to tell the linker the path to libgmp.a. The resulting executable showed the same behavior as the old one, regardless of any -O flags.

I then compared polysieve to polysieve2 and the only real difference seemed to be that bound_small_primes and smallPrimes are set in one version and user input in the other. So I edited polysieve2 to have them set rather than input. Now it worked, even when I set these variables to exactly the same values that I always entered during test runs. Setting only one of them and having the user input the other was no good, I tried it both ways round.

So I tried that with polysieve2-gmp and it did not give me that "all candidates have a divisor" message, but it produced a completely different list of candidates. I'll plug them into PFGW and see what happens using -l. Polysieve and polysieve2-non-gmp give identical output.

I can't say I understand anything that's happening.
Puzzle-Peter is offline   Reply With Quote
Old 2014-07-22, 19:41   #131
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

3·19·29 Posts
Default

Quote:
Originally Posted by Puzzle-Peter View Post
I
So I tried that with polysieve2-gmp and it did not give me that "all candidates have a divisor" message, but it produced a completely different list of candidates. I'll plug them into PFGW and see what happens using -l. Polysieve and polysieve2-non-gmp give identical output.
I have written the first code (polysieve.c), what was my first impression is that even this line is wrong: "Prime divisors of Q(s) up to 1000000000: 2 3 5 7 (...)"
as Q(s)=s^3+2*s^2 is odd (in fact Q(s)=s^2*(s+2) is the prime factorization, so there is no small prime divisor of Q(s)).
R. Gerbicz is offline   Reply With Quote
Old 2014-07-23, 18:42   #132
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22·52·7 Posts
Default

OK, I tried to feed the output of the gmp executable into PFGW and many of the candidates had small factors. Something is wrong here, I just don't know what it is.

Edit:
Will these codes do the trick mentioned in post #113 and following? If so, how do I tell it to do it - just set bound_small_primes to 0?

Last fiddled with by Puzzle-Peter on 2014-07-23 at 18:50
Puzzle-Peter is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How/Where to get Jens Kruse Andersen's prime constellation sieve? Stargate38 And now for something completely different 2 2017-04-28 00:08
Efficiently finding a linear progression in data fivemack Math 27 2015-12-12 18:42
GPU Prime Sieve tapion64 GPU Computing 7 2014-04-10 06:15
Sieve depth vs. prime probability Unregistered Information & Answers 2 2010-05-25 20:51
Prime in Riesel Sieve Project Sloth Prime Sierpinski Project 1 2006-05-10 02:02

All times are UTC. The time now is 04:19.


Wed Oct 4 04:19:35 UTC 2023 up 21 days, 2:01, 0 users, load averages: 1.33, 1.35, 1.29

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

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