Re: Nim newbie request/challenge
The times I previously posted were from a VirtualBox VM, limited to 4GB of ram, and in a "noisy" environment. The times here are derived from my host OS (PCLinuxOS) with full access to the system's 16GB of ram, in a "quiet" environment, i.e. I closed everything and rebooted, then just opened a terminal and ran the timing tests. [jzakiya@localhost nim]$ time ./ssozp5 Enter integer number: 1_000_000_000 segment has 262144 bytes and 262144 residues groups prime candidates = 26665; resgroups = 3334 create nextp[8x3398] array perform segmented SoZ last segment = 41046 resgroups; segment slices = 128 total primes = 50847534; last prime = 99937 real0m6.928s user0m0.393s sys 0m0.000s --- [jzakiya@localhost nim]$ time ./ssozp5 Enter integer number: 10_000_000_000 segment has 262144 bytes and 262144 residues groups prime candidates = 25; resgroups = 4 create nextp[8x9589] array perform segmented SoZ last segment = 148310 resgroups; segment slices = 1272 total primes = 455052511; last prime = 67 real0m5.355s user0m4.247s sys 0m0.000s --- [jzakiya@localhost nim]$ time ./ssozp5 Enter integer number: 100_000_000_000 segment has 262144 bytes and 262144 residues groups prime candidates = 265; resgroups = 34 create nextp[8x27290] array perform segmented SoZ last segment = 172374 resgroups; segment slices = 12716 total primes = 4118054813; last prime = 977 real0m48.434s user0m46.852s sys 0m0.008s --- [jzakiya@localhost nim]$ time ./ssozp5 Enter integer number: 1_000_000_000_000 segment has 262144 bytes and 262144 residues groups prime candidates = 2665; resgroups = 334 create nextp[8x78495] array perform segmented SoZ last segment = 150870 resgroups; segment slices = 127157 total primes = 37607912018; last prime = 9989 real11m0.884s user10m57.985s sys 0m0.010s I also wanted to show that the math that forms the foundation of the Sieve of Zakiya (SoZ) reduces the number of prime candidates to sieve primes from as you use more "efficient" Strictly Prime (SP) generators. This makes the SoZ algorithmically possibly the fastest prime sieve. To illustrate this, below are comparisons of the sequential SoZ between the P5 and P7 prime generators. Because the P7 generator sieves through 8/30 (26.67%) of all integers, compared to 2/6 (33.33%) for P5, it greatly reduces the number of prime candidates it needs to sieve through than P5. These versions just count the primes <= N, and don't numerate them into a list, to demonstrate the true performance of the prime sieve itself. Again, these timings were derived on my host OS in a "quiet" environment, directly after rebooting. [jzakiya@localhost nim]$ time ./sozp5d Enter integer number: 1_000_000_000 50847534 real0m12.074s user0m3.738s sys 0m0.054s [jzakiya@localhost nim]$ time ./sozp7d Enter integer number: 1_000_000_000 50847534 real0m6.938s user0m3.055s sys 0m0.048s [jzakiya@localhost nim]$ time ./sozp5d Enter integer number: 10_000_000_000 455052511 real0m43.221s user0m40.365s sys 0m0.554s [jzakiya@localhost nim]$ time ./sozp7d Enter integer number: 10_000_000_000 455052511 real0m38.520s user0m35.655s sys 0m0.496s Because the **"classical Sieve of Eratosthenes"** searches through the entire number space up to some N, it is always inherently slower than the SoZ method. The ways to increase its performance is to reduce the number space it sieves, by eliminating the even numbers (a 50% reduction of the number space) and applying various wheel and other reduction techniques to eliminate more of the sieved number space. The SoZ inherently works on a reduced number space that can theoretically be made as small as desired by the choice of the prime generator used to perform the sieve. The SoZ is also an inherently parallelizable algorithm, which can take advantage of multicore|threaded systems and CUDA|OpenMP implementations, and others with GPUs (graphic processing units).
Re: Nim newbie request/challenge
Hey thanks. I'll try to play around with the settings to get your code to compile when I get some time. On my System76 Gazelle laptop, with I7-6700HQ, 2.6-3.5GHz, 16GB ram, running in a VB VM for Manjaro KDE, using Nim 0.17.0 compiled with: **$ nim c --cc:clang --d:release ssozp5.nim** I get these times, running on a noisy system (multiple browsers, et al, open) for the sequential version of SSoZ using P5 prime generator. [jzakiya@jabari-pc nim]$ time ./ssozp Enter integer number: 1_000_000_000 segment has 262144 bytes and 262144 residues groups prime candidates = 26665; resgroups = 3334 create next[8x3398] array perform segmented SoZ last segment = 41046 resgroups; segment slices = 128 total primes = 50847534; last prime = 99937 real0m6.915s user0m0.550s sys 0m0.007s [jzakiya@jabari-pc nim]$ time ./ssozp5 Enter integer number: 10_000_000_000 segment has 262144 bytes and 262144 residues groups prime candidates = 25; resgroups = 4 create next[8x9589] array perform segmented SoZ last segment = 148310 resgroups; segment slices = 1272 total primes = 455052511; last prime = 67 real0m11.243s user0m5.260s sys 0m0.010s [jzakiya@jabari-pc nim]$ time ./ssozp5 Enter integer number: 100_000_000_000 segment has 262144 bytes and 262144 residues groups prime candidates = 265; resgroups = 34 create next[8x27290] array perform segmented SoZ last segment = 172374 resgroups; segment slices = 12716 total primes = 4118054813; last prime = 977 real1m7.795s user0m59.667s sys 0m0.027s
Re: Nim newbie request/challenge
You probably need to specify a path while importing. For example, running from ./bin "prime_bench.nim" file: from ../src/lib/lib_euler_primes import primeSieve from os import commandLineParams from strutils import parseUInt let arguments = commandLineParams() echo arguments[0].parseUInt.primeSieve.len $ time ./bin/prime_bench 1_000_000_000 50847534 real0m6.478s user0m6.069s sys 0m0.392s $ time ./bin/prime_bench 10_000_000_000 455052511 real1m33.301s user1m11.694s sys 0m14.762s Compilation was done with -d:release. I tried with march=native but it didn't seem to help. This is on a MacBook Pro 13 2015, so [i5-5257U](https://www.notebookcheck.net/Intel-Core-i5-5257U-Notebook-Processor.127680.0.html). You can compare it to others on [Notebookcheck](https://www.notebookcheck.net/Mobile-Processors-Benchmark-List.2436.0.html).
Re: Nim newbie request/challenge
I tried the run your code but the compiler doesn't see the euler libraries. eulerprimes.nim(24, 6) Error: cannot open 'lib_euler_math' How do I get all the libraries to get it to run? I'd be interested in benchmark times. Can you post your hardware specs and the times for counting the primes <= N, for for N = 10^9, 10^10, and 10^11? I don't know if you've seen my sequential SSoZ code, but I'd be interested in how they compare. I'm still learning Nim, and don't know the correct way to implement a parallel version yet, which if done correctly will be much faster. Studying your code I've already learned some Nim stuff I didn't know. Here again are the gists to some reference versions of the sequential SSoZ using the P5 prime generator. **ssozp5.nim** Find the primes <= N, using sequential Segmented Sieve of Zakiya (SSoZ) with P5 prime generator, written in Nim [https://gist.github.com/jzakiya/94670e6144735eb0041919f633d6011c](https://gist.github.com/jzakiya/94670e6144735eb0041919f633d6011c) **twinprimes_ssozp5.nim** Find Twin Primes <= N, using sequential Segmented Sieve of Zakiya (SSoZ) with P5 prime generator, written in Nim [https://gist.github.com/jzakiya/776b7aae3126168b4cad90de9adc4961](https://gist.github.com/jzakiya/776b7aae3126168b4cad90de9adc4961) **nthprime_ssozp5.nim** Find Nth Primes, using sequential Segmented Sieve of Zakiya (SSoZ) with P5 prime generator, written in Nim [https://gist.github.com/jzakiya/aff4f2e38f9b0f833955b4cc391de3d4](https://gist.github.com/jzakiya/aff4f2e38f9b0f833955b4cc391de3d4)
Re: Nim newbie request/challenge
Hey, welcome to Nim, If you like learning with mathematical challenges, I started Nim and many other languages with Project Euler, which gives you small mathematical challenges for your programming languages craving. [https://projecteuler.net](https://projecteuler.net)/ Here are my [solutions to the first 10 problems](https://github.com/mratsim/nim-projecteuler) including a [fast packed bitarray-based Sieve of Eratosthenes](https://github.com/mratsim/nim-projecteuler/blob/master/lib_euler_primes.nim#L160) with OpenMP parallel loop. I compared it to Rosettacode sieves and primesieve/primegen (C/C++) and various Haskell solutions and even Sieve of Atkins, on my machine it is 1.1 to 2x faster. Probably due to better cache locality.
Re: Nim newbie request/challenge
I agree - Nim is a community driven project, like many open source projects, and it gets better only if you scratch your own itch. Small improvements to the documentation is, like dom96 says, a perfect way to start contributing. [Edit] I agree that not everyone is command-line ninjas, and I think a link or two to good docs on setting the PATH on various systems elsewhere on the internet would be a good addition to the build instructions. I don't think you should expect anyone else to add that to the docs for you. I wouldn't bother, or even consider that information missing, simply because I know how to do this already. [/Edit]
Re: Nim newbie request/challenge
> It's these type of little things that cause unnecessary frustrations and shy > people away from using new things. > > Please think about the things that could potentially go wrong, then create > instructions and documentation that will prevent them. We do try, but we don't have the time to ensure everything is 100%. I think I need to create a page/article about this because I'm finding myself saying this a lot. Please understand that Nim is a volunteer-run open source project. We need _you_ to help us improve it. This isn't to say that I don't appreciate your message, you are giving us feedback on how things can be improved which is already much better than just abandoning Nim without saying a word. But can we step things up a notch and all act on our own feedback? These sorts of improvements are a perfect first contribution. All you need to do is edit the website and create a PR: [https://github.com/nim-lang/website](https://github.com/nim-lang/website). * * * By the way, I've created `choosenim` precisely to make installation as easy as possible. I'd appreciate if you could try it out: [https://github.com/dom96/choosenim#installation](https://github.com/dom96/choosenim#installation)
Re: Nim newbie request/challenge
I also agree with @jzakiya. I personally have only experience with the windows env (I have to use it on daily base (job)) - I used linux since 1994 for about 10 years but finally I throwed it away cause of the awful desktop. Today I cant speak about it because of lacking experience; I never tried it again. The nim installer on windows works very well and out of the box (no extra settings needed). If you like to use your own gcc I recommend the tdm-gcc (works also out of the box but you have to set your cli-path). Also It works without tweaks with the cl.exe (VS2017 community edition for instance) I never got nim running with the gcc of the mingw-installation-manager (the gcc compiler check from nim always failed). I think the docs are very good but sometimes outdated (for instance the examples) but for me its normal. I searched also a while for the nimscript feature of the compiler (the compiler help says nothing about that) and within the nimscript-docpage its a litte bit hidden). The overall feeling for me is that Nim is a very very nice designed and architected piece of software (design by committee is awful) and not burdened with any tweaks. the nimcode itself is fun to read (especially from others and thats not normal for any computer language). And also the new book is very good and worth reading. The idea of the integrated build-system is a big plus (I hate ant, maven and so on especially when the buildscript is more complex than the software itself which needs to be build)
Re: Nim newbie request/challenge
A user may not know, what is terminal (seriously). And this won't work on Windows (quite widely used thing). Probably a couple of links to some articles (somewhere on web, at some OS-related forums), one for POSIX and one for Windows, would give more for less effort.
Re: Nim newbie request/challenge
But you shouldn't write export PATH... in terminal you should write it in your .bashrc or .zshrc or .rc
Re: Nim newbie request/challenge
@jacmoe I disagree. I think that @jzakiya has a point. What if a beginner is trying to pick up Nim? They may not know how to configure their `$PATH`. Something as simple as changing the wording to: You will need to configure your `$PATH` environment variable. On most systems this can be accomplished by entering `export PATH=~/nim-0.17.0/bin:$PATH` in your terminal. I think that is a simple enough change that makes life simpler for less experienced developers.
Re: Nim newbie request/challenge
I think that _configuring the PATH environment variable_ is more than enough, to be honest. It is something that most (perhaps even all?) developers needs to learn how to do, regardless of the operating system.
Re: Nim newbie request/challenge
As I stated, Nim was not installed via these distros, and was being installed per the process given on Nim's website. Putting in the suggested PATH did solve the problem though, so thanks. $ export PATH=~/nim-0.17.0/bin:$PATH However, this just highlights the inadequacies of the installation instructions|documentation. Instead of the online instruction just saying **"Configuring the PATH environment variable"** it should explictly provide the correct procedure, as given here, which would have precluded this whole confusion and discussion. It's these type of little things that cause unnecessary frustrations and shy people away from using new things. Please think about the things that could potentially go wrong, then create instructions and documentation that will prevent them. Maybe the discussioin on this topic should be put into its own thread so that my original thread topic can remain in focus here.
Re: Nim newbie request/challenge
CMIIW, Nim folder is self contained. @jzakiya, very likely you already have Nim installed from package manager, and its installation done like usual any package. If you put the path in front of `$PATH`, it'll solve your problem. $ export PATH=~/nim-0.17.0/bin:$PATH In your case, you put the nim path at the end so the executable couldn't be reached because there's other nim executable at front.
Re: Nim newbie request/challenge
For what it's worth, I have built Nim several times without incident on my Debian box - following the instructions to the letter - so I guess the problem you have is specific to your machine.
Re: Nim newbie request/challenge
$ export PATH=$PATH:~/nim-0.17.0/bin The problem might be the expansion of `~` in the default shell on some O/S. Try $ export PATH=$PATH:$HOME/nim-0.17.0/bin You could create an "Issue" in Nim's GitHub repo so this specific problem can be discussed there, separate from the SSoZ discussion here.
Re: Nim newbie request/challenge
I've been considering creating a Snap package and/or AppImage for Nim for a while. Maybe I'll have a proper look at it after my holiday.
Re: Nim newbie request/challenge
Maybe you can't access Nim directory from user account because it has wrong permissions? And also maybe you have another Nim installed?
Re: Nim newbie request/challenge
The problem with installing seems to have to do with executables not in correct bins. I can go through the install process off the website, and compile the executables in the **nim-0.17.0** directory, created by untarring the tarball. Notes about installation from source After downloading the compressed archive, extract its contents into the desired installation directory. Open a new terminal window, cd into the extracted directory, and execute the following commands: sh build.sh bin/nim c koch ./koch tools Configuring the PATH environment variable The compiler and tool binaries live inside the bin directory. It is common for Nim developers to include two directories in their PATH environment variable: the aforementioned bin directory ~/.nimble/bin (where ~ is the home directory) I've had no luck setting the **PATH** that works, because it gives error messages saying it can't see certain files(?). When I set **PATH** like this: $ export PATH=$PATH:~/nim-0.17.0/bin when I try to compile a source file I get this: ~/nim> $ nim c --cc:clang --d:release x.nim Hint: System[Processing] Error: cannot open 'usr/local/lib/nim/system.nim' I can run the nim executable like so, from **nim-0.17.0/bin/**: ~/nim-0.17.0/bin $ ./nim c --cc:clang --d:release ~/nim/ where the **nim** directory holds my nim sources, but this is so inelegant! Luckily, Manjaro and Antergos (both Arch Linux derivatives) have the latest 0.17.0 version in their repos, so I've just been using them (this is using Virtual Box VMs). I even tried moving the executables around in the other distros to match what I see in Manjaro, with no luck. I am willing to help debug this if you give me detailed instructions to follow.
Re: Nim newbie request/challenge
Can we get a bug report for (6)?
Re: Nim newbie request/challenge
I've been translating various versions of the SSoZ I did in C++ in 2014 to Nim. Here are a few of my observations as a newbie. 1) Nim is much less noisy to write code in, with much less syntactical requirements to worry about (curly braces for if|for statements, etc). 2) Once I figured it out, it's a (just) little bit easier to satisfy integer type unification for doing math. But why can't you just add an **int** to an **uint** without having to manually explicitly cast the numbers. Can't the compiler figure this out? 3) Nim executables are either approxiamently 4|5x (with clang) or 6|7x (with gcc) larger than for C++ for some programs, though I can make them smaller using **strip** on them. 4) However, the Nim executables produce faster runtimes, and run to completion in some cases (for Nth Primes for example) where the comparable C++ throws a runtime Segfault error for the same inputs. 5) Nim is definitely easier to learn than C++ (because of the lower syntatic noise and more robust language paradigms, such as with **for** loops, etc), if you already know how to program (it's easier to figure out). Being young and growing (not 1.0 yet) it doesn't have the level of documentation you can find for C++, nor example code, etc, but the new book will help with that. I would highly recommend, and urge, a significant effort be put into creating as much (good, helpful, relevant) documentation as possible, especially to answer all the low level newbie questions, to attract people who want to try using Nim for really serious stuff. 6) The Nim installation procedure on the website failed to intall Nim on a number of distros (KDE Neon, LinuxMint, Kubuntu, PCLinuxOS) I tried. Even though the Ubuntu derivatives have Nim in their repos it's version 0.12 (not latest 0.17). Please provide instructions that will work, and/or create an AppImage, Snap, etc package to make installation universally simple. Below are the gists source code for my Nim translations of the original C++ implementations of the Segmented Sieve of Zakiya (SSoZ) using the P5 prime generator in each instance (I've done version with P7 too). These are sequential implementation. The main reason I'm interested in Nim is the potential to (easierly) implement these in parallel (than with C++, Rust, Julia, Python, etc). I've rearchitectured the memory model to make it parallel friendly, and now just need to figure out how to play with Nim pointers (and whatever else) to accomplish this. All in all, I see alot of potential for Nim as it matures. Gist files of Nim code of SSoZ versions, transated from C++. **ssozp5.nim** Find the primes <= N, using sequential implementation of SSoZ with P5 prime generator. [https://gist.github.com/jzakiya/94670e6144735eb0041919f633d6011c](https://gist.github.com/jzakiya/94670e6144735eb0041919f633d6011c) **nthprime_ssozp5.nim** Find nth primes, using sequential implementation of SSoZ with P5 prime generator. [https://gist.github.com/jzakiya/aff4f2e38f9b0f833955b4cc391de3d4](https://gist.github.com/jzakiya/aff4f2e38f9b0f833955b4cc391de3d4) **twinprimes_ssozp5.nim** [https://gist.github.com/jzakiya/776b7aae3126168b4cad90de9adc4961](https://gist.github.com/jzakiya/776b7aae3126168b4cad90de9adc4961) Find twin primes <= N, using sequential implementation of SSoZ with P5 prime generator.
Re: Nim newbie request/challenge
I cleaned up the code and added more commments. It should be much easier now to
uderstand what/why the code is doing after reading my paper.
Here is the gist location of the source code for this version.
[https://gist.github.com/jzakiya/94670e6144735eb0041919f633d6011c](https://gist.github.com/jzakiya/94670e6144735eb0041919f633d6011c)
I've created a rearchitected version to run in parallel, and in fact I got it
to compile, and run with correct results, but is 2x slower than the serial
version. If anyone knows how to really create parallel running programs please
let me know.
I will create a github project for all the different versions I|others create,
for different languages, prime generators, parallel versions, etc. So far I
have various C++ versions, and now this Nim version, and I plan to do a Crystal
version too.
If people want to, you can contact me directly via email, which is included in
my pape and the code intro.
I would urge people who run the code to play with the B value for their system
cache. I've only run this code on Intel I5|7 cpu laptops. I'm interested how
the code runs on other systems (AMD, ARM, PowerPC, etc) and operarting systems
(I've only used Linux).
Here's the code in the gist file.
#[
This Nim source file will compile to an executable program to
perform the Segmented Sieve of Zakiya (SSoZ) to find primes <= N.
It is based on the P5 Strictly Prime (SP) Prime Generator.
Prime Genrators have the form: mod*k + ri; ri -> {1,r1..mod-1}
The residues ri are integers coprime to mod, i.e. gcd(ri,mod) = 1
For P5, mod = 2*3*5 = 30 and the number of residues are
rescnt = (2-1)(3-1)(5-1) = 8, which are {1,7,11,13,17,19,23,29}.
Adjust segment byte length parameter B (usually L1|l2 cache size)
for optimum operational performance for cpu|system being used.
Verified on Nim 0.17, using clang (smaller exec) or gcc
$ nim c --cc:[clang|gcc] --d:release ssozp5.nim
Then run executable: $ ./ssozp5 , and enter value for N.
As coded, input values cover the range: 7 -- 2^64-1
Related code, papers, and tutorials, are downloadable here:
http://www.4shared.com/folder/TcMrUvTB/_online.html
Use of this code is free subject to acknowledgment of copyright.
Copyright (c) 2017 Jabari Zakiya -- jzakiya at gmail dot com
Version Date: 2017/08/23
This code is provided under the terms of the
GNU General Public License Version 3, GPLv3, or greater.
License copy/terms are here: http://www.gnu.org/licenses/
]#
import math # for sqrt function
import strutils, typetraits # for number input
# Global var used to count number of primes in 'seg' variable
# Each value is number of '0' bits (primes) for values 0..255
let pbits = [
8,7,7,6,7,6,6,5,7,6,6,5,6,5,5,4,7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3
,7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2
,7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2
,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1
,7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2
,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1
,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1
,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1,4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0
]
# The global residue values for the P5 prime generator.
let residues = [1, 7, 11, 13, 17, 19, 23, 29, 31]
# Global parameters
const
modp5 = 30 # mod value for P5 prime generator
rescnt = 8 # number of residues for P5 prime generator
var
pcnt = 0 # number of primes from r1..sqrt(N)
primecnt = 0'u64 # number of primes <= N
next: seq[uint64]# table of regroups vals for primes multiples
primes: seq[int] # list of primes r1..sqrt(N)
seg: seq[uint8] # segment byte array to perform ssoz
# This routine is used to compute the list of primes r1..sqrt(input_num),
# stored in global var 'primes', and its count stored in global var 'pcnt'.
# Any algorithm (fast|small) can be used. Here the SoZ using P7 is used.
proc sozp7(val: int | int64) = # Use P7 prime gen to finds upto val
let md = 210 # P7 mod value
let rscnt = 48# P7 residue count and residues list
let res = [1, 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,121,127,131,137,139
,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209,211]
var posn = newSeq[int](210) # small array (hash) to convert
for i in 0 .. = modk+res[r]: r += 1 # find last pc position <= num
let maxprms = k*rscnt + r - 1 # maximum number of prime candidates
Re: Nim newbie request/challenge
I don't have time right at this very moment, but I will take a look at this within the next few days and see if there are any changes I can make to get a faster runtime. Love all your comments by the way.
Re: Nim newbie request/challenge
Below is the Nim direct translation of the C++ code in my paper. I have
verified it on Nim 0.17 on Linux. In comparison on this same machine the Nim
code runs a bit faster for some (larger >= 10^9) test values (not
comprehensibly benchmarked yet).
I'll post it to a gist later to make it easier to download. I'm now
re-architecting it to make it parallel friendlier (I hope). Feedback welcome on
style, and performance tips.
ssozp5.nim
#[
This Nim source file will compile to an executable program to
perform the Segmented Sieve of Zakiya (SSoZ) to find primes <= N.
It is based on the P5 Strictly Prime (SP) Prime Generator.
Prime Genrators have the form: mod*k + ri; ri -> {1,r1..mod-1}
The residues ri are integers coprime to mod, i.e. gcd(ri,mod) = 1
For P5, mod = 2*3*5 = 30 and the number of residues are
rescnt = (2-1)(3-1)(5-1) = 8, which are {1,7,11,13,17,19,23,29}.
Adjust segment byte length parameter B (usually L1|l2 cache size)
for optimum operational performance for cpu being used.
Verified on Nim 0.17, using clang (smaller exec) or gcc
$ nim c --cc:[clang|gcc] --d:release ssozp5.nim
Then run executable: $ ./ssozp5 , and enter value for N.
As coded, input values cover the range: 7 -- 2^64-1
Related code, papers, and tutorials, are downloadable here:
http://www.4shared.com/folder/TcMrUvTB/_online.html
Use of this code is free subject to acknowledgment of copyright.
Copyright (c) 2017 Jabari Zakiya -- jzakiya at gmail dot com
Version Date: 2017/08/21
This code is provided under the terms of the
GNU General Public License Version 3, GPLv3, or greater.
License copy/terms are here: http://www.gnu.org/licenses/
]#
import math
import strutils, typetraits
let pbits = [
8,7,7,6,7,6,6,5,7,6,6,5,6,5,5,4,7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3
,7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2
,7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2
,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1
,7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2
,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1
,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1
,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1,4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0
]
let residues = [1, 7, 11, 13, 17, 19, 23, 29, 31]
# Global parameters
const
modp5 = 30 # prime generator mod value
rescnt = 8 # number of residues for prime generator
var
pcnt = 0 # number of primes from r1..sqrt(N)
primecnt = 0'u64 # number of primes <= N
next: seq[uint64]# array of primes first multiples
primes: seq[int] # array of primes <= sqrt(N)
seg: seq[uint8] # seg[B] segment byte array
proc sozp7(val: int | int64) =
let md = 210
let rscnt = 48
let res = [1, 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,121,127,131,137,139
,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209,211]
var posn = newSeq[int](210)
for i in 0 .. = modk+res[r]: r += 1 # find last pc position <= num
let maxprms = k*rscnt + r - 1# maximum number of prime candidates
var prms = newSeq[bool](maxprms) # array of prime candidates set False
let sqrtN = int(sqrt float64(num))
modk=0; r=0; k=0
# sieve to eliminate nonprimes from small primes prms array
for prm in prms:
r += 1; if r > rscnt: (r = 1; modk += md; k += 1)
if prm: continue
let res_r = res[r]
let prime = modk + res_r
if prime > sqrtN: break
let prmstep = prime * rscnt
for ri in res[1..rscnt]:
let prod = res_r * ri # residues cross-product
var nonprm = (k*(prime + ri) + prod div md)*rscnt + posn[prod mod md]
while nonprm < maxprms: prms[nonprm] = true; nonprm += prmstep
# the prms array now has all the positions for primes r1..N
# extract prime numbers and count from prms into primes array
primes = @[7] # r1 prime for P5
modk = 0; r = 0
for prm in prms:
r += 1; if r > rscnt: (r = 1; modk += md)
if not prm: primes.add(modk + res[r])
pcnt = len(primes)
proc next_init() =
var pos = newSeq[int](modp5)
for i in 0 .. seg
size
# count the primes in the segment
for byt in seg[0..= modk+uint64(residues[r]): r += 1 # find last pc position <=
num
let maxpcs = k * uint64(rescnt) + uint64(r-1) # maximum number of prime
candidates
let Kmax = uint64(num-2) div uint64(modp5) + 1 # maximum number of
resgroups for
Re: Nim newbie request/challenge
OK, thanks for the feedback on your problems downloading the paper. Can you tell me what platform you are using, and what country you're accessing from? I see from my Scribd stats that the paper is being downloaded so it appears to be working for others. I'll look at putting the paper up on github, though.
Re: Nim newbie request/challenge
Sounds interesting, I might try doing a direct port from cpp to nim when I get some free time. Btw, download is indeed behind a paywall (looks like scribd offers a month free but after that it's paid). Reading is free though. Copy pasting from the pdf is impossible, as latex or whatever mangles the symbols, but I found a gist [here](https://gist.github.com/jzakiya/2410458be9c79b2f1c9a) Also found this link in the references [https://www.4shared.com/dir/TcMrUvTB/sharing.html](https://www.4shared.com/dir/TcMrUvTB/sharing.html) but it won't let me download anything. I'd suggest setting up a [github pages](https://pages.github.com/) website with an html version (pandoc or similar can convert most formats to html) or at least some kind of git repo with the code, as it's free and most people here are used to cloning things to look at them on their pc (at least I am).
Re: Nim newbie request/challenge
The link I provided in my first post allows you to read/download it free from my Scribd site. Here it is again. [https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ](https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ) I've tested it many times, and there is no filter/paywall to get around. Let me know if this doesn't work and I'll provide another method to get to it.
Re: Nim newbie request/challenge
Can you put the paper on a link that is not behind a paywall? I am normally pretty trained to port from different languages to different languages, but from the paper I can't do copy paste at all.
Re: Nim newbie request/challenge
Thanks. I'm in the process of learning enough Nim to take on this effort. However, I would do what you were thinking, and first try a comparable direct C++ to Nim translation, just to get something to work. But it's going to be some time (with my time/learning curve constraints) to create something workable. I'm hoping someone who's really fluent in Nim, and who thinks in Nim, can perform the algorithm in a Nimby way that best showcases its capabilites. Once you get your head around the algorithm (and/or math) it shouldn't be too hard to understand what the C++ code is doing. Then someone versed in Nim can structure the alogrithm, particularly a true parallel processing version, in an efficient manner.
Re: Nim newbie request/challenge
Honestly, this sounds like an interesting little project to bang out. However, I must admit that I am a humble Web Developer and, by extension, am not well versed in mathematics. The best I could do is translate your C code in the linked document into Nim and maybe make a few small changes. However, without a deeper understanding of your algorithm, I doubt I would be able to optimize it in any meaningful way. It seems like your paper does a good job explaining the concepts behind the algorithm, but I do not have enough free time at the moment to work on this as I am approaching a deadline to launch a web application. My suggestion is for you to possibly try and implement the algorithm in Nim yourself. You will find it to be surprisingly simple, I'm sure. If you then link to the repository here, we can help you by reviewing the code and making pull requests.
