mersenneforum.org On the Infinity of Twin Prime and other K-tuples
 Register FAQ Search Today's Posts Mark Forums Read

2020-08-27, 20:08   #45
bsquared

"Ben"
Feb 2007

72238 Posts

Quote:
 Originally Posted by jzakiya If you can, compile/test the Nim and Rust versions (Rust just released 1.46). They should be faster, especially with 16 cores.
I've downloaded the code from https://github.com/jzakiya/SSoZ, but I don't know how to compile it. Any pointers?

 2020-08-27, 20:15 #46 jzakiya   Jul 2014 22×3×5 Posts What's even more impressive is that Pascal (the author) was not a Java programmer. He saw my Nim gist version and started posting to me about it. He wanted to try a Java version to give him a reason to learn it. This was in 2019, and he would ask me questions about Java, which I know nothing of, but forged ahead to get better and better versions. So I hadn't seen his final version (I assume this is his latest) until now, and haven't run it yet. I'm sure a Java guru can make it better (which he humbly kept saying) so I hope he gets the recognition for its implementation, especially from where he started.
2020-08-27, 20:34   #47
jzakiya

Jul 2014

22×3×5 Posts

Quote:
 Originally Posted by bsquared I've downloaded the code from https://github.com/jzakiya/SSoZ, but I don't know how to compile it. Any pointers?
The best thing to do is follow these instruction from rust-lang.org

https://www.rust-lang.org/learn/get-started

I created a project folder called twinprimes_ssoz, which should create the necessary file structure. Just put the source file in the /src folder, and follow the compilation instruction in the file. It will download a bunch of crates, so you need internet access. Once compiled, the exe will be in /target/release. The instructions explain all of this, which is easier than it sounds.

The Nim version is actually easier to compile, because all you have to do is install Nim and compile the file per its internal instructions, from wherever you place it.

https://nim-lang.org/
https://nim-lang.org/install.html

The Rust source code was significantly improved by the Rust gurus on its forum from where it started. What would be really interesting is to use Rust to generate a Wasm version. There are so many things than can be done with it given sufficient resources and time.

2020-08-27, 21:30   #48
jzakiya

Jul 2014

22·3·5 Posts

Quote:
 Originally Posted by bsquared I've downloaded the code from https://github.com/jzakiya/SSoZ, but I don't know how to compile it. Any pointers?
Use these versions.

Rust
https://gist.github.com/jzakiya/b96b...eb3f35eb437225

Nim
https://gist.github.com/jzakiya/6c7e...dd62e3e3b2341e

 2020-08-28, 03:06 #49 bsquared     "Ben" Feb 2007 373110 Posts I'm afraid I'm running into problems, probably because of my ignorance of the rust build process. I tried running cargo.exe build in the top level of the SSoZ repository and got this Code: error[E0277]: [usize; 8] is not an iterator --> src\sieve.rs:179:19 | 179 | for ri in res { | ^^^ borrow the array with & or call .iter() on it to iterate over it | = help: the trait std::iter::Iterator is not implemented for [usize; 8] = note: arrays are not iterators, but slices like the following are: &[1, 2, 3] = note: required by std::iter::IntoIterator::into_iter error: aborting due to previous error For more information about this error, try rustc --explain E0277. error: could not compile SSoZ. If I try to run rustc.exe on the twinprimes_ssoz.rs file you pointed to, I get this: Code: PS C:\projects\ssoz> rustc.exe .\twinprimes_ssoz.rs error[E0463]: can't find crate for rayon --> .\twinprimes_ssoz.rs:37:1 | 37 | extern crate rayon; | ^^^^^^^^^^^^^^^^^^^ can't find crate error: aborting due to previous error [EDIT] Ok, I've learned to add dependencies to cargo.toml. Now I've reached this point and have no more ideas for things to try. Code: error[E0432]: unresolved import SSoZ::sieve::largest_twin_prime_before --> src\main.rs:2:5 | 2 | use SSoZ::sieve::largest_twin_prime_before; | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no largest_twin_prime_before in sieve error: aborting due to previous error For more information about this error, try rustc --explain E0432. error: could not compile SSoZ. [EDITEDIT] ok, I figured it out. copied the cargo.toml file with its list of dependencies to a new folder with a src/ subfolder. moved the twinprimes_ssoz.rs file into the src/ subfolder. Renamed the file to main.rs. Then build --release worked. This is a different computer (i7-7800X). Now I get: primesieve-7.4, 12 threads, 10^11 3.61 sec twinprimes_ssoz.rs, 12 threads, 10^11 2.34 sec Twin counts match. Kudos! Last fiddled with by bsquared on 2020-08-28 at 03:56
2020-08-28, 04:07   #50
bsquared

"Ben"
Feb 2007

7×13×41 Posts

Quote:
 Originally Posted by bsquared This is a different computer (i7-7800X). Now I get: primesieve-7.4, 12 threads, 10^11 3.61 sec twinprimes_ssoz.rs, 12 threads, 10^11 2.34 sec Twin counts match. Kudos!
Looks like you still have some work to do at higher offsets though:

primesieve-7.4 10^14 to 10^14+10^11
6.08 sec

twinprimes_ssoz.rs, 10^14 to 10^14+10^11
13.2 sec

primesieve-7.4 10^16 to 10^16+10^11
8.41 sec

twinprimes_ssoz.rs, 10^16 to 10^16+10^11
92.8 sec

 2020-08-28, 05:49 #51 jzakiya   Jul 2014 22·3·5 Posts On my System76 i7 4C|8T 3.5GHz laptop, at least upto 2x10^14 twinprimes_ssoz is faster. But the larger the ranges the more mem|time it takes to run and tweak, and I couldn't dedicate that laptop to doing that (I have a life, and this is a hobby). I could try some of the tricks primesieve uses for large ranges, but then I would have to rearchitect the code, which doesn't interest me right now. Primesieve is actually 3 different algorithms, for small, medium, and large ranges. He does some really artful stuff to precompute table of primes, memory management, etc, for large ranges. Check out his code, its nice. But like I said, he's been at it for years and is an expert C++ programmer. However, what this single file of < 300 loc shows is the prime generator based algorithm is inherently faster, for the reasons I presented in that paper, and is much simpler to code. It gives you the best ROI for the least cost (development time, hardware, mem needs, etc). Also, being the ultimate fastest implementation isn't always the highest priority goal. I give you for free the value of the last twin in the range. In the Nim version (I left it out for Rust) I provide code to display the twins (mid values). Consider my code a reference proof of concept implementation. Now that you have working code you can do whatever you want to apply it to different environments and check those results against it. I've been trying to get people in some universities, who have the  and student workers, to do a distributed network to find the next largest Twins, and also Cousins and Sexy primes, because all you have to do is change which residue pairs to use, but the algorithm is exactly the same. And this is what people should really start to appreciate, one generic algorithm can be used to find prime pairs for any gap size just by picking the appropriate residue pairs for a given Prime Generator.
 2020-08-28, 15:16 #52 mart_r     Dec 2008 you know...around... 15208 Posts Could this code be used to search for gaps between prime twins? It seems it has the potential to be faster than the code I'm using.
2020-08-28, 19:26   #53
jzakiya

Jul 2014

1111002 Posts

Quote:
 Originally Posted by mart_r Could this code be used to search for gaps between prime twins? It seems it has the potential to be faster than the code I'm using.
I assume you mean what are the spacings between pairs of twinprimes?

That's already known depending on the Prime Generator (PG). Once you pick a generator all the residues spacings are determined. For example, using P3, all the twins are of form 6n+/- 1. For P5 you have 3 twinpair residues, and know the spacing between them, etc, etc, if that's what you mean.

But here's how to create an implementation to find the largest Twins.

In my paper I give the residue pairs the current largest known Twin exists on for two different PGs. All you have to do to find all larger ones is to pick some large generator, say P19, which has (p19 - 2)# twinpair residues. Parametize it to find its resgroup k value and twinpair residues, then use that as the starting point for searching. Then any twinpair(s) greater than this are the next largest ones.

Thus, we can reduce the code to very small ranges that can fit in cache, or whatever the optimum memory structure of the system (since we only need the equivalent of bitarrays), and stop only if we find any twins in a range. Then we can numerate their parameters to get their values. This can be done in a GIMPS like network shipping out these independent ranges to as many workers as possible, and whoever finds an occupied range then that's a new unknown Twin pair. Piece of cake!

Once you understand the theory you'll soon realize the potential power you have for finding any kind of primes.

FYI. Yesterday I emailed the author of a paper I had stored in my cache of prime papers, who did extensive numerical analysis to actually count the gaps in primes up to large numbers. I asked if he had histograms of data of the accumulative distributions of the gaps, and he did! and he sent me a zip file of his data. And sure enough, his data confirms exactly what my paper stated, Sexy Primes are the most abundant, followed by Twins and Cousins, and the gaps have an oscillating nature, etc. He even sent me the updated 2018 version (mine was 2011), link to his paper below.

Some heuristics on the gaps between consecutive primes
https://arxiv.org/pdf/1102.0481.pdf

I hope I answered the question you meant.

2020-08-29, 07:52   #54
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

2·11·467 Posts

Quote:
 Originally Posted by mart_r Could this code be used to search for gaps between prime twins?
I thought that is always 2...

2020-09-08, 15:23   #55
mart_r

Dec 2008
you know...around...

11010100002 Posts

Quote:
 Originally Posted by jzakiya In my paper I give the residue pairs the current largest known Twin exists on for two different PGs. All you have to do to find all larger ones is to pick some large generator, say P19, which has (p19 - 2)# twinpair residues. Parametize it to find its resgroup k value and twinpair residues, then use that as the starting point for searching. Then any twinpair(s) greater than this are the next largest ones. Thus, we can reduce the code to very small ranges that can fit in cache, or whatever the optimum memory structure of the system (since we only need the equivalent of bitarrays), and stop only if we find any twins in a range. Then we can numerate their parameters to get their values. This can be done in a GIMPS like network shipping out these independent ranges to as many workers as possible, and whoever finds an occupied range then that's a new unknown Twin pair. Piece of cake! Once you understand the theory you'll soon realize the potential power you have for finding any kind of primes.

I wrote two different programs, one in Excel/VBA and one in Pari, both of those were about or almost half as fast as the Perl program I was using at the time (which was not mine; I'm not yet familiar with coding in Perl or C and won't be in the forseeable future). I used a generator array of the size of P23 in VBA, and possibly there could've been some optimizations within the code, but I hardly got any replys to the codes I posted. I could even go up to P29, it probably would cost me a day of some rewriting, but the program would still only be about half as fast as the program I'm using to search the gaps.

My problem is not the theory, it's the efficient implementation in a language close to the hardware.

Quote:
 Originally Posted by LaurV I thought that is always 2...
Mock me why don't you... after doing most of the computation work in the last few months

 Similar Threads Thread Thread Starter Forum Replies Last Post robert44444uk Prime Gap Searches 45 2022-02-24 18:28 Puzzle-Peter Software 156 2019-06-03 20:19 hal1se Miscellaneous Math 13 2018-11-05 16:34 hydeer Lone Mersenne Hunters 9 2018-04-03 22:54 cuBerBruce Puzzles 3 2014-12-01 18:15

All times are UTC. The time now is 07:32.

Mon Jan 30 07:32:40 UTC 2023 up 165 days, 5:01, 0 users, load averages: 1.36, 1.02, 1.00