mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-08-26, 19:10   #34
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

419 Posts
Default

I have been provided with a Java implementation of this sieve a couple of months ago. You can find it here:
https://github.com/TilmanNeumann/jav...act/SSOZJ.java


My impression was that it is very fast.
Thanks Jabari and Pascal.
Till is offline   Reply With Quote
Old 2020-08-26, 19:18   #35
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,347 Posts
Default

Quote:
Originally Posted by jzakiya View Post
Had never heard or seen anything about the black-key sieve. It obviously hasn't been adopted much. But again, I provide a comprehensive mathematical framework which explains how to use any even number as the modulus for a prime generator, i.e. a generalized method to explain how it works, and why, with coded examples.
I would argue the opposite: people have been building on the ideas behind that particular sieve for almost 20 years now. The point is that sieving by residues, wheel factorization and wheel sieving are not new ideas. The fact that you have re-discovered them, re-explained them, and provided good example code is to be commended, but it is arrogant to then name the ideas after yourself.

Quote:
Originally Posted by jzakiya View Post
Also its interesting that apparently the Sieve of Eratosthenes, Sieve of Atkin, and Sieve of Sundaram are totally good form, but the Sieve of Zakiya somehow is not. Why? Who should my sieves and techniques be named after? So only certain types of people have work named after them?
You may have noticed that Atkin's paper is called "Prime sieves using binary quadratic forms". No mention of his name there. Other people thought it was neat, and started calling it the Atkin sieve.

Sundaram's sieve was introduced by someone else, I can't find the actual paper online.

I don't know whether Eratosthenes named his algorithm after himself or not, but I'd say one way or another he gets a pass... standards were probably quite different 2000 years ago.
bsquared is offline   Reply With Quote
Old 2020-08-26, 19:37   #36
jzakiya
 
Jul 2014

25 Posts
Default

For some reason(s) you are hellbent on discrediting my work, and any and everybody else's independent use of it. If other people can find just a smidgen of new knowledge and benefit from it then it has value. Why you continue to try to deny that only you can answer, with others left to guess.
jzakiya is offline   Reply With Quote
Old 2020-08-26, 20:03   #37
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101000100112 Posts
Default

Quote:
Originally Posted by jzakiya View Post
For some reason(s) you are hellbent on discrediting my work, and any and everybody else's independent use of it. If other people can find just a smidgen of new knowledge and benefit from it then it has value. Why you continue to try to deny that only you can answer, with others left to guess.
When have I said that it doesn't have value? In fact I said that your work is to be commended. And that I will experiment to see if there are any benefits I can apply for my own code. I'm glad you wrote it all up.

But there is a difference between good implementation and theoretical advancement, the latter of which is what the self-naming promotes. In my opinion, the things you have written about sieving (not touching the twin-prime conjecture stuff, here) are not the same caliber of work as the sieve of Eratosthenes itself, or Atkin's or Pritchard's work, and naming it as such strikes me as wrong. Were I to peer-review such claims as an article submission I would say the same and recommend rejection. Take it or leave it.
bsquared is offline   Reply With Quote
Old 2020-08-26, 20:46   #38
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

5·1,787 Posts
Default

Quote:
Originally Posted by jzakiya View Post
For some reason(s) you are hellbent on discrediting my work, and any and everybody else's independent use of it.
You may not like what bsquared is saying. But consider the following opinions of others who are competent to pass judgement:
Quote:
Originally Posted by Batalov View Post
No, it's not.

MOD NOTE: thread is moved to Misc.Math subforum
Misc Math is an area for things that really are not good math at all.
Quote:
Originally Posted by sweety439 View Post
This is a special case of Schinzel's hypothesis H.
Which means you found part of someone else's work. Nothing new in the concept.
Quote:
Originally Posted by Gelly View Post
This seems to entirely sidestep the point of a proof in the name of using empirical evidence to support your claims. There exist many conjectures that are based off of "obvious" properties that are heuristic, but there's no known reason for them.
Data that supports an idea does not make a proof.
Quote:
Originally Posted by CRGreathouse View Post
I have a great appreciation for engineers (having both a grandfather and a father-in-law of that profession) and engineering. In terms of how to communicate results in a mathematical paper, results without proof come in several forms:
  • Conjectures. These are statements which are believed to be true, but for which no proof can be found at present. (There are some subtleties here: by proposing a conjecture, you're implicitly suggesting that you think the problem is at least somewhat hard and worthy of study.)
  • Claims. These are statements which the author claims to be true, but for which the author does not provide a proof. (Actually, sometimes a proof does occur at a later point, but that's a different matter.) Sometimes this is used for informal statements that could not have a formal proof; otherwise there is some reason (e.g., article page limits, or because proving the claim is an exercise in the text) for which the proof is omitted. The understanding in such cases is that the author would be able to provide more details if contacted. be true and use as the basis for a mathematical system (like ZFC, NF, etc.)
I would characterize your statements as claims, and as such, they can't be used in any of your proofs (as they aren't themselves proven).
Quote:
Originally Posted by Batalov View Post
Don't get confused with people's polite way, when in this polite way they are telling you that you results are rubbish.


Because there is nothing to discuss there. In the words of Pauli, "This is not even wrong."
Quote:
Originally Posted by retina View Post
I was commenting on your assertion that testing up to <some_limit> is enough to confirm or refute. It isn't. It would merely provide evidence to support or not support. It can't confirm or refute anything.
It is not just bsquared, it is a chorus.
Uncwilly is online now   Reply With Quote
Old 2020-08-27, 16:17   #39
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,939 Posts
Default

Quote:
Originally Posted by bsquared View Post
Sundaram's sieve was introduced by someone else, I can't find the actual paper online.
Aiyar published the paper, but credits the sieve itself to Sundaram. But the sieve itself is just a disguised version of a naïve sieve of Eratosthenes which sieves by odds rather than primes, so Sundaram doesn't really deserve any credit.
CRGreathouse is offline   Reply With Quote
Old 2020-08-27, 16:56   #40
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

419 Posts
Default

Yes, one should not name stuff after himself.
You should have one or two friends that do that for you

Apart from that: I didn't look at the paper but the implementation I got looks pretty fast. Unfortunately I have no other implementation to compare it to. So I am happy that bsquared appointed himself to investigate it.

Btw. exploiting an unproven hypothesis (Schinzels H) in software wouldn't be such a low feat either, or not?
Till is offline   Reply With Quote
Old 2020-08-27, 18:56   #41
jzakiya
 
Jul 2014

3210 Posts
Default

I referenced all my implementations against primesieve, who I informed back in 2014 about my sieves using prime generators.

https://github.com/kimwalisch/primesieve

The fastest twinprime sieve that runs on a common laptop is the Rust version of my twinprimes_ssoz, followed closely by the Nim version.

Because I don't have access to a GPU I haven't done a CUDA/OpenCL version, which should fly with all of their independent cores. It's also equally amenable to implement in distributed/cloud networks, as it's inherently designed to be done in parallel processing systems.

I haven't tried Pascal's Java version yet, so I can't tell you how it compares.

I'm certain my implementations can be improved upon for various hardware environments. I would encourage people to do so and post their results.

Also, primesieve is a very good program done in very optimized C++, that has been actively maintained and improved for a number of years. It has thousands of lines of code, spanning hundreds? of files, to implement.

My Rust, Nim, D, Crystal, et al versions consist of one file of less than 300 lines of actual code.
jzakiya is offline   Reply With Quote
Old 2020-08-27, 19:11   #42
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,347 Posts
Default

I've just compared the java version of ssojz that Till provided with primesieve and yafu and I'm indeed impressed.

Counting twin primes to 10^11 with 16 threads:
ssojz: 3.34 sec

Counting twin (and triple... up to sextuple) primes to 10^11 with 16 threads:
primesieve: 2.88 sec

Counting primes (no twins or other tuples) to 10^11 with 16 threads:
yafu: 1.99 sec

Last fiddled with by bsquared on 2020-08-27 at 19:40 Reason: corrected yafu time
bsquared is offline   Reply With Quote
Old 2020-08-27, 19:30   #43
jzakiya
 
Jul 2014

25 Posts
Default

If you can, compile/test the Nim and Rust versions (Rust just released 1.46). They should be faster, especially with 16 cores.
My base I7 system only had 4C|8T.
I'm salivating on getting an AMD Threadrippper 12C|24T system.
jzakiya is offline   Reply With Quote
Old 2020-08-27, 19:55   #44
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111001100112 Posts
Default

Quote:
Originally Posted by bsquared View Post
Counting twin primes to 10^11 with 16 threads:
ssojz: 3.34 sec

Counting twin (and triple... up to sextuple) primes to 10^11 with 16 threads:
primesieve: 2.88 sec

Counting primes (no twins or other tuples) to 10^11 with 16 threads:
yafu: 1.99 sec
That is extremely impressive, especially considering it's in Java. I wonder how the Rust implementation will fare.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Twin Prime Constellations robert44444uk Prime Gap Searches 21 2019-06-09 12:51
How do you efficiently sieve for prime 3/4-tuples? Puzzle-Peter Software 156 2019-06-03 20:19
find very easy twin prime in the infamy twin primes hal1se Miscellaneous Math 13 2018-11-05 16:34
Highest Prime is also a twin prime... NOT hydeer Lone Mersenne Hunters 9 2018-04-03 22:54
Twin Prime Days, Prime Day Clusters cuBerBruce Puzzles 3 2014-12-01 18:15

All times are UTC. The time now is 15:50.

Wed Dec 2 15:50:24 UTC 2020 up 83 days, 13:01, 2 users, load averages: 1.30, 1.57, 1.85

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