Twin Primes Segmented Sieve of Zakiya (SSoZ) Explained

Announcements
1

I just released this new paper which I go into detail to explain the math and software to implement the Segmented Sieve of Zakiya (SSoZ) algorithm to find Twin and Cousin Primes.

Twin Primes Segmented Sieve of Zakiya (SSoZ) Explained

I present the code and benchmarks for 6 languages: D, Go, C++, Nim, Rust, and Crystal.

It’s been decades since I’ve done anything serious in Fortran, but see it’s still supposed to be very performant.

I’m hoping someone(s) would do Fortran versions to compare against the other code.
If there are questions about the code or math you can’t get from the paper please let me know.

2 Likes
3

I’ve posted this request here, like with Julia, et al, because I’d like to see how well other languages can do these algorithms.

where some have questioned the validity of the algorithm?

I have seen no refutation of the algorithms.
Nobody has expressed to me that the results I present in the paper are incorrect|false. Are you?

First read the paper, and try to understand it.
Then run any of the 6 implementations I’ve done and check out the results for yourself.
If you think something is wrong let me know specifically what it is.
A few have asked some questions, which is good, and I’ve answered them, but the data and results are reproducible and speak for themselves. And the code doesn’t lie. :slightly_smiling_face:

4

I don’t know much about primes. Reading this thread had me asking, “What fraction of primes < n, for a given n, are twin primes?” and, if the answer to that question is not << 1, why not use a general prime number sieve and then sift out the subset that are twin primes?

Kim Walisch has a well-organized and documented repository for a C++/C implementation of a segmented sieve with wheel factorization. Collaborators have contributed bindings for other languages including Julia, Nim, Python, Rust, etc. Admittedly, these bindings would not allow one to compare the performances of various languages for prime number sieving, since the underlying algorithm is implemented in C++, but such a library could be useful in further development of the OP’s twin primes explorations.

5

In my paper I compare my Twin Primes SSoZ implementations (in 6 languages) against his Primesieve program, which is done in C++. Please checkout how much faster (in < 300 ploc) it is, and simpler. It also gives you the largest Twin|Cousin prime in an interval. (Primesieve doesn’t give results for Cousin Primes.)

The math using Prime Generators is the most efficient there is for finding primes (of all types) which I show and explain, and also the simplest. I also show (with graphs) how the number space that all primes (including specifically Twins|Cousins) exist within decreases as the Pn generators moduli increase.

For a more detailed understanding of math behind the algorithms please read the references in the papers, especially [3] and [4]. This paper is written to give enough of the mathematical foundation to explain how|why the software works. In fact, you can just translate the code into Fortran without needing to know the math, but of course, it would be easier to understand how|why the code works if you did.

I’m glad to see on my analytics page a number of people from here were curious enough to read and/or download the paper. I encourage you to take any of the implementations I’ve provided and run them on your systems to see them in operation for yourselves. Hopefully, people will be intrigued enough to code Fortran versions to see how fast they run in comparison.

6

It’s been some time for people to read the paper, understand it, and try coding a Fortran version.
Has anybody tried?

7

@jzakiya , modern Fortran is a relatively simple language to learn and pick up. You will find it best toward your effort if you tried out Fortran yourself with your method.

8

While looking around for available papers related to the topic of calculating \pi(N), the number of primes \le N, I came across an informative paper from 1996, Computing π(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko Method by M. Deleglise and J. Rivat, in Mathematics of Computation. The paper provides historical context, describes the algorithms used, and provides expressions for time and space complexity of the algorithms.

9

If that’s the case, why don’t you code an implementation?
I want to see what a good Fortran coder can do with the algorithm.
Do any of those people hangout here?

10

I have no idea what that has to do with my algorithm and coding it in Fortran.
Have you even read my paper, and seen the empirical results?

11

Well, I’m simply not interested in finding twin and cousin primes and have no incentive or motivation whatsoever to look at any method toward this, no curiosity even.

But given your posts here and elsewhere, you appear to have an incentive and a drive and motivation to see your method having multiple implementations. By trying it yourself, you get to learn Fortran also, an added bonus.

DIY might just be the message to you by the lack of replies here or with the majority of any replies that do get posted.

3 Likes
12

I would add, as already stated in the Julia community:
If you provide us a basic running version, we can help you to improve your code.

Here is a very basic Fortran crash-course:

  • declare variables with integer :: myint or real :: myfloat or logical :: mybool and don’t try to assign values in the same line
  • for constant variables, use integer, parameter :: max_n
  • all declarations have to appear before any executable statement
  • if only accepts logical variables and can look like this if (i < 10) then … else if (myflag) … end if
  • Loops are done with do i=1,10 … end do. This loop will have 10 iterations, if you only need every n’th value, use do i=2,10,2, which will result in i = 2, 4, 6, 8 and 10
  • arrays start at 1, are declared like integer :: vector(10), matrix(3, 3) and the index order is conversely to the order in C, so you want to iterate over the first index in the inner most loop: print*, matrix(inner_loop_index, outer_loop_index)
  • Fortran is case-insensitive, so myvar == MYVAR == mYvAr (all small letters highly recommended)

Here’s a basic construct, you can complete with your algorithm

twinprimes.f90:

program twinprimes
    implicit none

    ! first all declarations
    real, parameter :: pi = 3.14
    integer :: radius
    integer :: height
    real :: tmp

    ! then assignments and calculations
    height = 10
    tmp = height * pi
    do radius=1,5
        print*, "Radius: ", radius, "Volume: ", radius**2 * tmp
    end do
end program
13

FYI.

I’ve updated the paper (Revised June 28, 2022) to mostly reflect corrections to 2 places in the code where arithmetic overflows could occur. All the coded versions have been fixed. The paper|code can be gotten from the links previously provided.

14

As others have remarked, there is no strong reason to port the OP’s codes from languages such as C++, D, Rust, etc., into Fortran. If properly done, the converted version may be expected to perform at the same level as the existing codes.

There is also a limitation of Fortran that can be a significant obstacle in this context: Fortran does not support unsigned integer types (exception: Sun Fortran for SunOS/Solaris/Linux). It may be easier to modify, e.g., the C++ version of OP’s codes to use only signed integers before even considering porting to Fortran. If the signed version of, say, the C++ program does not work, there is no point in considering a conversion to Fortran.