20070610, 22:53  #34  
Jun 2003
626_{16} Posts 
Quote:
Quote:
Thanks. Last fiddled with by Citrix on 20070611 at 02:03 

20070613, 23:00  #35 
Mar 2003
New Zealand
13·89 Posts 

20070624, 02:43  #36 
Jun 2003
2×787 Posts 
Geoff,
I have further modified srsieve and simplified the Sieve of Eratosthenes for the idea above. Attached is the code. Ignore all C++ comments that I wrote. It should just take a few minutes to implement my request. ( I hope this reduces work for you and you are able to implement it soon.) So in the code X=2*what ever you want number to multiple of . SO p=X*n+1 where X must be even and n can be odd. Basically in setup_sieve when you generate the composite table for new primes, you have to make sure that the composite table has composites that are odd and composite==1 (mod X). I do this through a simple while loop, since this is only done once. Then in prime_sieve, You make sure low_end_of_range is a multiple of X, this is again done via a simple while loop as only needs to be done once. you calculate the sieve index by uint_fast32_t sieve_index = (composite_table[i]  low_end_of_range1)/X; Then add prime to the sieve index. In the end composite_table[i] = low_end_of_range + 2*X/2*(uint64_t)sieve_index + 1; Then to generate the candiate later you do candidate = low_end_of_range + 2*X/2*i + 1; Then send candidate to fun. Note since all numbers are multiples of X, SPH can be done over X and no factors etc.. need to be stored. Questions/ Thoughts? edit: You can avoid the division by X for each prime, by storing composites as n where composite=n*X+1. Also there are other things that could be improved in your code, I am not sure why you haven't looked into them? Perhaps improving the code will not produce huge speed benefits. Last fiddled with by Citrix on 20070624 at 23:21 
20070629, 03:48  #37  
Mar 2003
New Zealand
13×89 Posts 
Quote:


20070702, 02:18  #38 
Mar 2003
New Zealand
13×89 Posts 
Citrix, I have implemented your changes to prime_sieve() in version 1.5.11x. It seems to produce correct results, but it also seems a lot slower than 1.5.5x.
Last fiddled with by geoff on 20070702 at 02:20 
20070702, 04:01  #39  
Jun 2003
2×787 Posts 
Quote:
(I will try to play with the code and figure out what is slowing it down, thanks for implementing though) 

20070702, 04:20  #40 
Mar 2003
New Zealand
13×89 Posts 
I tried x=720, but I didn't do much testing. I think the slow loop is in setup_sieve(), where I made a note about testing for overflow. It is hard to work out how many iterations this loop actually does.

20070702, 04:27  #41  
Jun 2003
626_{16} Posts 
Quote:
What if x=2. Do we get the same speed? edit: Since x will always have small factors, we can always reduce the number of steps in this to the sum of the factors. Is there any checking to see what is the max X , a user can use? Is SPH done over the factorization of X, in the new version? Last fiddled with by Citrix on 20070702 at 04:48 

20070702, 04:54  #42  
Mar 2003
New Zealand
13·89 Posts 
Quote:
Quote:


20070702, 05:07  #43 
Jun 2003
626_{16} Posts 

20070704, 01:21  #44  
Jun 2003
2·787 Posts 
Quote:
so we need to find c+n*x=0 (mod y) c+n*x=m*y Assuming y <x and x=g (mod y) we get c+n*g=h*y now g<y and y=k (mod g) so c+f*g=k*h and so on until one of the letter is 0. (Basically this can be set up as a recursive loop) Let me know if you have any questions. Is there any limit on the value of x X? 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Windows 10 in Ubuntu, good idea, bad idea, or...?  jasong  jasong  8  20170407 00:23 
Idea (as always)  Dubslow  Forum Feedback  7  20161202 14:26 
Advantage of lattice sieve over line sieve  binu  Factoring  3  20130413 16:32 
idea ?  science_man_88  Homework Help  0  20100423 16:33 
An Idea  ThomRuley  Lone Mersenne Hunters  5  20030715 05:51 