Re: CTFE
Secifically, in `~/nim-0.18.0/compiler/vmdef.nim` set `MaxLoopIterations* = 1_000_000_000` (1 Billion) then rebuild sysem: `./koch boot -d:release`
clang 6 compiling error
A 64-bit Linux distro I run in VirtualBox updated from clang 3.9 to 6.0, so I recompiled some code to compare the differences. The code compiled with `--cc:clang` on 3.9, but using 6.0 it gives the following error output. Hint: [Link] /usr/bin/ld: cannot find crtbegin.o: No such file or directory clang-6.0: error: linker command failed with exit code 1 (use -v to see invocation) Error: execution of an external program failed: 'clang -o /home/jzakiya/nim/twinprimes_test4a /home/jzakiya/nim/nimcache/twinprimes_test4a.o /home/jzakiya/nim/nimcache/stdlib_system.o /home/jzakiya/nim/nimcache/stdlib_sharedlist.o /home/jzakiya/nim/nimcache/stdlib_locks.o /home/jzakiya/nim/nimcache/stdlib_math.o /home/jzakiya/nim/nimcache/stdlib_strutils.o /home/jzakiya/nim/nimcache/stdlib_parseutils.o /home/jzakiya/nim/nimcache/stdlib_algorithm.o /home/jzakiya/nim/nimcache/stdlib_typetraits.o /home/jzakiya/nim/nimcache/stdlib_times.o /home/jzakiya/nim/nimcache/stdlib_posix.o /home/jzakiya/nim/nimcache/stdlib_os.o /home/jzakiya/nim/nimcache/stdlib_ospaths.o /home/jzakiya/nim/nimcache/stdlib_osproc.o /home/jzakiya/nim/nimcache/stdlib_strtabs.o /home/jzakiya/nim/nimcache/stdlib_hashes.o /home/jzakiya/nim/nimcache/stdlib_streams.o /home/jzakiya/nim/nimcache/stdlib_cpuinfo.o /home/jzakiya/nim/nimcache/stdlib_linux.o /home/jzakiya/nim/nimcache/stdlib_threadpool.o /home/jzakiya/nim/nimcache/stdlib_cpuload.o /home/jzakiya/nim/nimcache/stdlib_tables.o -pthread -lm -lrt -ldl' [jzakiya@localhost nim]$
Re: Nim, or gcc, problem?
> So you DID inspect C code differences and also checked another compiler, but > you still blame Nim, not gcc, for that time difference? Even to the point of > calling it a security issue? Excuse me @Udiknedormin, maybe you aren't fluent in English? I have not _blamed_ Nim or gcc. I have asked the question, is it a Nim or gcc ` problem`? Since gcc, and clang, produce the same characteristic of the `problem` for the same Nim code (at least on my Intel I7 cpu system), maybe it's something else. I don't know. To me it's an interesting anomaly that needs fuller investigation. Also, I merely made the generic statement that this `could` become a security issue. Any time you have code that behaves in an unexpected way, someone may be able to exploit it. Why do you think Google, Mozilla, et al, pay bounties for people to find security bugs in their code? (In fact, Mozilla funded the creation (and uses) Rust to eliminate a whole class of coding problems afflicting its browser code.) It would be nice if you all chill out, and stop being so defensive, and focus in on the technical merits, and implications, of the issue.
Re: Nim, or gcc, problem?
In order to be taken `super, suPER, SUPER` seriously, let me be hermetically sealed, and scientifically rigorous, in presenting this `problem`. Base Hardware: System76 laptop with Intel I7 6700HQ cpu, 2.6-3.5 GHz clock, 4 cores, 8 threads, 16GB of memory, and 128GB SSD. Base OS: Linux kernel 4.11.11, gcc 4.9.2|clang 3.9.1, PCLinuxOS 64-bit. (This is a pre Meltdown and Spectre patched system) VB OSs: Linux kernels 4.15.x-4.16.x, gcc 7.3.0/1 : clang 3.9.1-6.0 (These are post Meltdown and Spectre kernel patched systems) The results shown here are from my base system, but the `problem` is consistent with any combination of kernel, and gcc or clang, on VB based systems for 64-bit Linux distros. Here are the gists of the tested code: The difference between the code is line 239 in `twins_sieve`. `twinprimes_test.nim` [https://gist.github.com/jzakiya/e140e9f3d660059631b2bb09487220f9](https://gist.github.com/jzakiya/e140e9f3d660059631b2bb09487220f9) `twinprimes_test1.nim` [https://gist.github.com/jzakiya/8f7768c8c9f6e925b200c5f463a2f95c](https://gist.github.com/jzakiya/8f7768c8c9f6e925b200c5f463a2f95c) They were compiled with flags as follows, and run on a `quiet system`. (Rebooted, opened only a terminal, and ran tests.) nim c --cc:gcc --d:release --threads:on twinprimes_test.nim nim c --cc:gcc --d:release --threads:on twinprimes_test1.nim then run echo 500_000_000_000 | ./twinprimes_test echo 500_000_000_000 | ./twinprimes_test1 echo 1_000_000_000_000 | ./twinprimes_test echo 1_000_000_000_000 | ./twinprimes_test1 then compile as nim c --cc:clang --d:release --threads:on twinprimes_test.nim nim c --cc:clang --d:release --threads:on twinprimes_test1.nim and run echo 500_000_000_000 | ./twinprimes_test echo 500_000_000_000 | ./twinprimes_test1 echo 1_000_000_000_000 | ./twinprimes_test echo 1_000_000_000_000 | ./twinprimes_test1 For either compiling with gcc or clang, as the input values become bigger, `twinprimes_test1` times become increasingly slower, as a percentage of `twinprimes_test`, approaching on order of 10% for the two data points shown. For bigger inputs the differences grow larger. (On a good note, I was pleasantly surprised to see clang has faster times for this particular architecture, at least on my base system, as it had always been slower.) Input Number | twinprimes_test | twinprimes_test1| | gcc 4.9.2 | clang 3.9.1 | gcc 4.9.2 | clang 3.9.1 | -- 5e11 | 28.926 |28.241 | 31.759 |30.970 | 1e12 | 63.285 |61.042 | 67.842 |66.678 | Even though the devs have exhibited an extreme lack of _curiosity_ (` willful blindess`) to acknowledge this `problem`, even as just a user, you should pay attention to it, though. I only `discovered` this behavioral phenomena because of serendipty. How many places in your (or Nim's) codebase are similar occurences of just `this` code phenomena lurking, unbekownst to its potential performance hit? This is also, obviously, `a potential security vector`. I've already identified the nim source code difference that (re)produces the problem. I've already identified the compiled code C output created for the Nim source code. What is needed is a forensic analysis of the assembly code differences, which I don't know how to do, nor really have the inclination (or time) to do if I did. It would also obviously be interesting (and rigorous) to see if|how this phenomena exists on different hardware (AMD, ARM, PowerPc, etc), and OS (BSD, Windows, Mac OS, IOS, Android, etc) systems. If the devs don't have even a basic level of intellectual inquisitiveness (pride?) to understand why this phenomena exists (and would have to ultimately `fix` it ), I don't know what more data, motivation, or incentive, is needed.
Re: Nim, or gcc, problem?
I looked at the generated C code for both versions. They have exactly the same
structure (reference names are different) and exactly the same number of total
lines-of-code (loc).
Here's the C code generated for the different Nim versions snippets.
while (1) {
if (!(k < Kn)) goto LA18;
seg->data[k] = (NU8)(seg->data[k] | ((NI) 1));
k += prime;
} LA18: ;
while (1) {
if (!(k < Kn)) goto LA18;
seg->data[k] = ((NU8) 1);
k += prime;
} LA18:
So why does the 2nd snippet produce a binary that's 95 bytes bigger and 4+
seconds slower?
Re: Nim, or gcc, problem?
Oh by the way, the compiled code for `a[k] = 1` was 95 bytes bigger, using gcc 4.9.2
Re: How to add unique items to array?
Hey @dataman, thanks for info on `intsets` FYI, `intsets` has a problem compiling the `card|len` method on `0.17.2` but not on `0.18.0`. Also, while `intsets` indeed will take the correct number of set members, it's at least 3x slower than using `sets`, across the board. So for this case, using a `seq` array is the better alternative. Well, at least I learned some new things today.
Re: How to add unique items to array?
Hey @dataman can you show how to use this to replace using `sets`.
Below is a code prototype using `sets`, what would be the equivalent with
`IntSet`.
proc example(a, b, c) =
var aset: set[uint16]
while n < max
aset = {}
for b in x..y:
.
incl(aset, k.uint16)
.
count += card(aset))
Re: How to add unique items to array?
So @miran and @Stefan_Salewski I used a `set` to replace a `seq`, and it is pretty fast for this case, as I don't have to worry about `deduplicating` the array, which was vey slow as the array size increased. `Sets` did create a much better logical inplace replacement for this case. The structural problem with `sets` is, it only takes up to `uint16` size (2^16-1 = 65,535) elements, and my sets could take upto ~250K elements, so when I do `card(set)` (in place of `arry.len`) I start getting wrong answers once the input size passes a certain point. Is there a way to increase the size, or work around this?
Re: Twinprimes generator that showcases Nim
Hey SolitudeSF thanks for the tip. Hey Miran, this is `Open Source Software` so you can modify it as much as you want. I think all you have to do is comment out the line that puts out the enter number message to get what you want. But as I said in the initial post, people should feel free to beat on it, kick it, and modify it to their hearts content, especially if it `improves` it. Want a GUI frontend, go for it. Want to print output to a file, same thing. Here's one little `improvement` I've been thinking about that someone can pick up. It's fairly simple to conceptualize and easy to code, and would be a good task for someone to do to give them a reason to learn a little more Nim. `primesieve` displays a percentage indicator to give you a sense of how far along it's into the process. This is kinda nice to have, especially as number get larger. This is a nice, short task, of redeeming value, someone can take on. Here's one simple way to do it. Add to Global Var parameters a boolean array `threadsdone: seq[bool]` and initialize at end of `selectPG` as `threasdone = newSeq[bool](rescntp div 2)`. Then at the bottom of `twins_sieve` put `threadsdone[indx] = true`, to indicate the thread had finished. Now in the main routine, just monitor to see|calculate the percentage of the `(rescntp div 2)` threads are done in `threadsdone`. Voila, piece of cake. Just figure out how to display the output to give you what you want. Now that I'm able to compile the code for P17, I'm looking at the optimum PG profiles for inputs >= 1e13. 1e13 takes on the order of 900 secs (15 mins) and 5e13 is on order of 90 mins. Since I only have one laptop, and need it to do real work (this stuff is just for fun, fame, and fortune?) I tend to only run tests now either early when I wake up, or late going to bed. But the key point I hope this `real application` shows, is that Nim can do `real parallel processing` right now! And if Nim would publicize successes like this it could make headway into the numerical processing community (attracting more users|developers), and take mindshare away from Python, Julica, et al. People can start doing FFTs, Walsh Transforms, Video|Audio codecs. How nice it would be to have an Opus Audio codec in Nim to showcase Nim's processing prowess. [https://opus-codec.org](https://opus-codec.org)/ [https://en.wikipedia.org/wiki/Opus_(audio_format](https://en.wikipedia.org/wiki/Opus_\(audio_format)) The single most reason `Ruby` took off is `Rails`, which made people have to learn|develop Ruby. Python is now billing itself as THE numerical analysis language (and Julia in written in Python). Nim needs it niche applications to standout in the software language farmer's market. When people go looking for nice, fresh, juicy tomatoes to put in their salad, your offering must be able to stand out for some reason.
Re: Twinprimes generator that showcases Nim
`UPDATE`, caught, and corrected, a subtle coding error that affected the total twinprimes count being possibly off by 1 (and wrong last twinprime value) when the Kmax residues groups for an input is (very rarely) an exact multiple of the segment size. If anybody is running code please use updated version 2018/04/07. [https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e](https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e) I was hoping a few people would be curious enough to run the code and post (or send me via email) their results on their systems. If you are willing to do so, please list hardware and OS|gcc specs (cpu system, clocks, threads, mem|OS, gcc version, distro version). The next biggest design milestone would be to implement the algorithm using GPUs (graphics processor units). I guess the easiest way to do that is to use something like CUDA, which I don't know if Nim supports.
Re: Twinprimes generator that showcases Nim
`UPDATE`, mostly more tweaking of `proc twins_sieve`. Tried different loop structures|idioms to see what would be faster (`for` vs `while` loops mostly, etc). Made some cosmetic, line order changes. Code `version 2108/04/05` more compact, a little more cleaner, with little more clearer comments than `version 2018/04/03`. [https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e](https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e) Biggest change was compiling source in VB (Virtual Box) image of base OS distros which has `gcc 7.3.0`. Compiled source in it to create binary, then ran binary on base hardware (I7, 8 threads, 16GB mem) to a|b compare with previous version compiled using `gcc 4.9.2`. With gcc 4.9.2 the binary is 264,158 bytes, with gcc 7.3.0 it's 255,720 bytes. Not only was binary smaller, performance with gcc 7.3.0 was discernibly faster. Times are given below for tests done on `quiet` system. Input Number | twinprimes | twinprimes_ssoz | twinprimes_ssoz | primesieve || 4/5/18 gcc 7.3.0 | 4/3/18 gcc 4.9.2 | 1e10 | 27,412,679 | 0.453 | 0.458| 0.572 5e10 |118,903,682 | 2.487 | 2.501| 3.112 1e11 |224,376,048 | 4.831 | 5.110| 6.475 5e11 |986,222,314 | 27.445 |28.583| 35.675 1e12 | 1,870,585,220 | 59.018 |61.236| 75.638 2e12 | 3,552,770,943 | 131.861 | 135.701| 162.975 3e12 | 5,173,760,785 | 218.947 | 223.803| 252.175 4e12 | 6,756,832,076 | 302.756 | 316.653| 354.066 5e12 | 8,312,493,003 | 391.850 | 400.375| 448.066 6e12 | 9,846,842,484 | 486.707 | 497.222| 547.792 7e12 | 11,363,874,338 | 583.041 | 595.554| 642.447 8e12 | 12,866,256,870 | 673.436 | 698.129| 749.884 9e12 | 14,356,002,120 | 766.572 | 809.974| 843.042 1e13 | 15,834,664,872 | 880.372 | 903.161| 953.423 5e13 | 71,018,282,471 |6341.153 | 6396.903|
Can I do this in Nim?
I have this code where I'm setting all the bytes in `seg` to `0`. for b in s_row..s_row+KB-1: seg[b] = 0 Can I do something like: `seg[a..b] = 0` Then I have this code that counts all the `0` in `seg` for k in 0..Kn-1: (if seg[s_row+k] == 0: sum += 1) Is there a way to do something like this: `sum = seg[a..b].count(0)` If so, would they be faster than the current code constructs?
Re: Twinprimes generator that showcases Nim
Hey @miran, thanks. I'll look at your code when I get some time today. It would be really helpful if people could run the code on different (Intel cpus, AMD, ARM, etc) platforms with different number of threads, cache size, etc, and if possible a|b it against `primesieve` on their systems, and post results. I'm going to try and see if I can get (expert) programmers in other language communities (C++, Crystal, D, Rust, etc) to do it in them and compare the results. I initially just want to see what their coded versions looks like (idiomatically), or even if possible (can they do parallel programming, gc, etc). Below are updated times for the current version, produced on my System 76 laptop, Intel I7 6700HQ cpu, 2.6-3.5 GHz clock, with 8 threads, and 16GB of memory. I'm really interested to see how it performs under different threading systems. Input Number | twinprimes | twinprimes_ssoz | primesieve 1e10 | 27,412,679 | 0.458 | 0.572 5e10 |118,903,682 | 2.501 | 3.112 1e11 |224,376,048 | 5.110 | 6.475 5e11 |986,222,314 | 28.583 | 35.675 1e12 | 1,870,585,220 | 61.236 | 75.638 2e12 | 3,552,770,943 | 135.701 |162.975 3e12 | 5,173,760,785 | 223.803 |252.175 4e12 | 6,756,832,076 | 316.653 |354.066 5e12 | 8,312,493,003 | 400.375 |448.066 6e12 | 9,846,842,484 | 497.222 |547.792 7e12 | 11,363,874,338 | 595.554 |642.447 8e12 | 12,866,256,870 | 698.129 |749.884 9e12 | 14,356,002,120 | 809.974 |843.042 1e13 | 15,834,664,872 | 903.161 |953.423
Re: Twinprimes generator that showcases Nim
`New and Improved` (current) version, with significantly reduced memory
footprint as numbers get larger.
Now I create|initialize `nextp` arrays of 1st prime multiples in each thread,
which gets gc'd (garbage collected) at end of thread, thus using a much lower
constant runtime memory. (I could also generate|use the segment memory on a per
thread basis too, but at the end I need full last segment memory to find last
twinprime and correct count.) For this version I need to compile using gc, so
compile as below:
$ nim c --cc:gcc --d:release --threads:on twinprimes_ssoz.nim
Hey @mratsim, I started converting code to C++, and hit a roadblock in passing
multiple outputs from a function to multiple inputs, needed to do `const
paramterspxx = genPGparameters(xx)` and in `selectPG`. And not sure how to
compile to deallocate memory from a thread, as C++ doesn't use GC. Also, the
information you provided on using OpenMP is way over my head. Do you feel like
trying to do an OpenMP implementation in Nim?
Anyway, here's the updated gist file, and source code:
[https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e](https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e)
#[
This Nim source file is a multple threaded implementation to perform an
extremely fast Segmented Sieve of Zakiya (SSoZ) to find Twin Primes <= N.
Based on the size of input value N, it dynamically selects the best PG to
use from PGs P5, P7, P11, and P13, and then sets the optimum segment size.
This code was developed on a System76 laptop with an Intel I7 6700HQ cpu,
2.6-3.5 GHz clock, with 8 threads, and 16GB of memory. I suspect parameter
tuning may have to be done on other hadware systems (ARM, PowerPC, etc) to
achieve optimum performance on them. It was tested on various Linux 64 bit
distros, native and in Virtual Box, using 8 or 4 threads, or 16|4GB of mem.
At time of writing, verified using Nim: 0.17.2, 0.18.0
The code was compiled using these compiler directives|flags. Not usng GC
produces smaller executable, and maybe little faster. Try w/wo to see
difference on your system. For optimum performance use gcc over clang.
$ nim c --cc:gcc --d:release --threads:on twinprimes_ssoz.nim
Then run executable: $ ./twinprimes_ssoz , and enter value for N.
As coded, input values cover the range: 13 -- 2^64-1
This source file, and updates, will be available here:
https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e
Related code, papers, and tutorials, are available here:
https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ
https://www.scribd.com/document/266461408/Primes-Utils-Handbook
Use of this code is free subject to acknowledgment of copyright.
Copyright (c) 2017 Jabari Zakiya -- jzakiya at gmail dot com
Version Date: 2018/04/03
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, gcd, mod functions
import strutils, typetraits # for number input
import times, os # for timing code execution
import osproc # for getting threads count
import threadpool # for parallel processing
{.experimental.} # required to use 'parallel' (<= 0.18.x)
# Compute modular inverse a^(-1) of a to base b, e.g. a*(a^-1) mod b = 1.
proc modinv(a0, b0: int): int =
var (a, b, x0) = (a0, b0, 0)
result = 1
if b == 1: return
while a > 1:
let q = a div b
a = a mod b
swap a, b
result -= q * x0
swap x0, result
if result < 0: result += b0
# Create constant parameters for given PG at compile time.
proc genPGparameters(prime: int): (int, int, int, seq[int], seq[int],
seq[int]) =
echo("generating parameters for P", prime)
let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
var modpg = 1
for prm in primes: (modpg *= prm; if prm == prime: break) # PG's mdoulus
var residues: seq[int] = @[]# generate PG's residue values here
var (pc, inc) = (1, 4)
while pc < modpg: (pc += inc; inc = inc xor 0b110; if gcd(modpg, pc) ==
1: residues.add(pc))
let rescnt = residues.len # PG's residues count
var restwins: seq[int] = @[]# extract twinpair residues here
var j = 0
while j < rescnt-1:
if residues[j]+2 == residues[j+1]:
restwins.add residues[j]; restwins.add residues[j+1]; j += 1
j += 1
let rescntp = restwins.len # twinpair residues count
var inverses: seq[int] = @[] # create PG's residues inverses here
for res in r
Twinprimes generator that showcases Nim
ein that OpenMP can be used with Nim. If so, it
would be interesting if using it in Nim would make the code faster. Whoever
knows how to do that, go for it!
Below is the code and its gist (it's 317 loc, with ~60 separate loc of
comments, compare that to `primesieve`'s code size):
[https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e](https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e)
#[
This Nim source file is a multiple threaded implementation to perform an
extremely fast Segmented Sieve of Zakiya (SSoZ) to find Twin Primes <= N.
Based on the size of input value N, it dynamically selects the best PG to
use from PGs P5, P7, P11, and P13, and then sets the optimum segment size.
This code was developed on a System76 laptop with an Intel I7 6700HQ cpu,
2.6-3.5 GHz clock, with 8 threads, and 16GB of memory. I suspect parameter
tuning may have to be done on other hadware systems (ARM, PowerPC, etc) to
achieve optimum performance on them. It was tested on various Linux 64 bit
distros, native and in Virtual Box, using 8 or 4 threads, or 16|4GB of mem.
At time of writing, verified using Nim: 0.17.2, 0.18.0
The code was compiled using these compiler directives|flags. Not usng GC
produces smaller executable, and maybe little faster. Try w/wo to see
difference on your system. For optimum performance use gcc over clang.
$ nim c --cc:gcc --d:release --threads:on --gc:none twinprimes_ssoz.nim
Then run executable: $ ./twinprimes_ssoz , and enter value for N.
As coded, input values cover the range: 13 -- 2^64-1
This source file, and updates, will be available here:
https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e
Related code, papers, and tutorials, are available here:
https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ
https://www.scribd.com/document/266461408/Primes-Utils-Handbook
Use of this code is free subject to acknowledgment of copyright.
Copyright (c) 2017 Jabari Zakiya -- jzakiya at gmail dot com
Version Date: 2018/03/18
Version Date: 2018/03/27
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
import times, os # for timing code execution
import osproc # for getting threads count
import threadpool # for parallel processing
{.experimental.} # required to use 'parallel' (<= 0.18.x)
# Compute modular inverse a^(-1) of a to base b, e.g. a*(a^-1) mod b = 1
proc modinv(a0, b0: int): int =
var (a, b, x0) = (a0, b0, 0)
result = 1
if b == 1: return
while a > 1:
let q = a div b
a = a mod b
swap a, b
result -= q * x0
swap x0, result
if result < 0: result += b0
# Create constant parameters for given PG at compile time
proc genPGparameters(prime: int): (int, int, int, seq[int], seq[int],
seq[int]) =
echo("generating parameters for P", prime)
let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
var modpg = 1
for prm in primes: (modpg *= prm; if prm == prime: break) # PG's mdoulus
var residues: seq[int] = @[]# generate PG's residue values here
var pc = 1
var inc = 4
while pc < modpg: (pc += inc; inc = inc xor 0b110; if gcd(modpg, pc) ==
1: residues.add(pc))
let rescnt = residues.len # PG's residues count
var restwins: seq[int] = @[]# extract twinpair residues here
var j = 0
while j < rescnt-1:
if residues[j]+2 == residues[j+1]:
restwins.add residues[j]; restwins.add residues[j+1]; j += 1
j += 1
let rescntp = restwins.len # twinpair residues count
var inverses: seq[int] = @[] # create PG's residues inverses here
for res in residues: inverses.add(modinv(res,modpg))
result = (modpg, rescnt, rescntp, residues, restwins, inverses)
# Generate at compile time the parameters for PGs P5-P13
const parametersp5 = genPGparameters(5)
const parametersp7 = genPGparameters(7)
const parametersp11 = genPGparameters(11)
const parametersp13 = genPGparameters(13)
# Global parameters
var
pcnt = 0 # number of primes from r1..sqrt(N)
num = 0'u64 # adjusted (odd) input value
primecnt = 0'u64 # number of primes <= N
nextp: 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
K
Re: Arbitrary Precision Integer Math Operators
OK, so core Nim doesn't have an arbitrary precision math capability. Is it something planned for in the roadmap to 1.0?
Arbitrary Precision Integer Math Operators
I have Ruby/Crystal code that uses arbitrary precision integer numbers (really BIG numbers). Looking at Nim's math libraries they don't appear to be arbitrary precision. [https://nim-lang.org/docs/lib.html#pure-libraries-math-libraries](https://nim-lang.org/docs/lib.html#pure-libraries-math-libraries) I need at least the following operators: gcd(a,b) modinv(a,b) -> (a^-1) base b -> a*(a^-1) mod b = 1 modpow(a,e,b) -> a^e mod b intsqrt(a) -> a ^(1/2) introotn(a,n) -> a^(1/n) All the algorithms are fairly simple (a few lines of code), but does Nim use arbitrary math lib?
Re: Compiler won't scale (still)
> @jzakiya: The limit is at one billion now. +1!!
Re: Compiler won't scale (still)
OK, I set `MaxLoopIterations* = 1_000_000_000` (1 Billion) in `~/nim-0.18.0/compiler/vmdef.nim` and rebuilt doing `./koch boot -d:release` and was able to compile P17. I think this value is way more reasonable, because as stated previously, on modern machines (or really any system with gigahertz clock speeds) we're only talking second for even a billion iterations. I really hope you will up the value. Until so, I'll patch my own systems. Thanks for instructing how to do this. `Again, I strongly urge you to PROMINENTLY DOCUMENT this capability too.`
Re: Stein's (binary) GCD algorithm (iterative version)
Here's a gist of the code. [https://gist.github.com/jzakiya/b096b92c181ed343dab8c130c88f1d39](https://gist.github.com/jzakiya/b096b92c181ed343dab8c130c88f1d39)
Re: Stein's (binary) GCD algorithm (iterative version)
Back in the day I had that book, when I wore a younger man's clothes, and also **Applied Cryptography**. I wonder what happened to them [https://www.goodreads.com/book/show/351301.Applied_Cryptography](https://www.goodreads.com/book/show/351301.Applied_Cryptography)
Stein's (binary) GCD algorithm (iterative version)
On the Ruby issue tracker replacing Euclid's gcd algorithm with Steins (binary) algorithm came up. [https://bugs.ruby-lang.org/issues/13503](https://bugs.ruby-lang.org/issues/13503) Here's the wikipedia article on it. [https://en.wikipedia.org/wiki/Binary_GCD_algorithm](https://en.wikipedia.org/wiki/Binary_GCD_algorithm) Here's a Nim implementation of the iterative version. proc gcd(a, b: int): int = var (a, b) = (a, b) if a == 0: return b if b == 0: return a var k = 0 while ((a or b) and 1) == 0: a = a shr 1 b = b shr 1 k += 1 while (a and 1) == 0: a = a shr 1 while b != 0: while (b and 1) == 0: b = b shr 1 if a > b: swap a,b b -= a result = a shl k Here's a Ruby implementation of it. def gcd(a, b) return b if a.zero? return a if b.zero? k = 0 while (a | b).even? a >>= 1; b >>= 1; k += 1 end a >>= 1 while a.even? until b.zero? b >>= 1 while b.even? a, b = b, a if a > b b -= a end a << k end
Re: Compiler won't scale (still)
Compiling again for P17, with 0.18.0 and 0.17.2, the error messages point to `gcd` function in both cases: # 0.18.0 error message generating parameters for P17 stack trace: (most recent call last) twinprimes_ssozp17par5d3.nim(87) twinprimes_ssozp17par5d3.nim(65) genPGparameters lib/pure/math.nim(452) gcd lib/pure/math.nim(452, 15) Error: interpretation requires too many iteratio # 0.17.2 error message generating parameters for P17 stack trace: (most recent call last) twinprimes_ssozp17par5d3.nim(87) twinprimes_ssozp17par5d3.nim(65) genPGparameters lib/pure/math.nim(439) gcd lib/pure/math.nim(439, 15) Error: interpretation requires too many iterations In both cases it points to the same line in `lib/pure/math.nim` (line 452 in 0.18.0 or 439 in 0.17.2): proc gcd*[T](x, y: T): T = ## Computes the greatest common divisor of ``x`` and ``y``. ## Note that for floats, the result cannot always be interpreted as ## "greatest decimal `z` such that ``z*N == x and z*M == y`` ## where N and M are positive integers." var (x,y) = (x,y)# < this line is pointed to in both cases while y != 0: x = x mod y swap x, y abs x Changing `var (x,y) = (x,y)` to `var x = x; var y = y` or changing variable names, in both cases, creates same results. **Why does this line cause this compiler iteration problem?**
Re: Compiler won't scale (still)
One (last?) trick to reduce the number of iterations. I changed this: var residues: seq[int] = @[] var pc = 1 while pc < modpg: (pc += 2; if gcd(modpg, pc) == 1: residues.add(pc)) let rescnt = residues.len to this: var residues: seq[int] = @[] var pc = 1 var inc = 4 while pc < modpg: (pc += inc; inc = inc xor 0b110; if gcd(modpg, pc) == 1: residues.add(pc)) let rescnt = residues.len This reduces the number of times `gcd` is called from half the numbers (all the odds) upto modpg (modpg/2) to a third (modpg/3). This change produces the P3 PG residue sequence: `pcs = 6m +|- 1` pc = 1, 5, 7, 11, 13, 17, 19... +4 +2 +4 +2 +4 +2 So while it shaves off some iterations of `gcd` it's still not enough to get P17 to compile. `A REQUEST:` It would be really, really nice to use the boolean operators like: `x ^= y; x &= y`; etc.
Re: Compiler won't scale (still)
OK, **I finally got it to compile with the original iteration count** , but
man, did I have to jump through hoops to do it.
To reduce the number of loops, instead of doing `brute force trial-and-error`
to test each residue against the others to find its inverse, I found the code
here
`https://rosettacode.org/wiki/Modular_inverse#Nim`
on Rosetta Code, that had a Nim version already done. [Notice: the code there
doesn't compile without changing `proc mulInv(a0, b0): int =` to `proc
mulInv(a0, b0: int): int =`. In fact, quite a few of those old Rosetta code Nim
examples don't compile, but I digress.]
proc mulInv(a0, b0: int): int =
var (a, b, x0) = (a0, b0, 0)
result = 1
if b == 1: return
while a > 1:
let q = a div b
a = a mod b
swap a, b
result = result - q * x0
swap x0, result
if result < 0: result += b0
Then I was able to eliminate the loop-in-a-loop construct, and just do this:
var inverses: seq[int] = @[]
for res in residues: inverses.add(mulInv(res,modpg))
I was trying to avoid using another function just to do this, since I don't use
it at runtime, but you do what you gotta do.
Does Nim already have this function in its library? If not, can you please add
it (math lib, etc).
Below is final code that compiles with original compiler iteration value, with
some added diagnostic checks.
# Compute modular inverse of a to base b, e.g. a*a_invese mod m = 1
proc mulInv(a0, b0: int): int =
var (a, b, x0) = (a0, b0, 0)
result = 1
if b == 1: return
while a > 1:
let q = a div b
a = a mod b
swap a, b
result = result - q * x0
swap x0, result
if result < 0: result += b0
# Create constant parameters for chosen PG at compile time
proc genPGparameters(prime: int): (int, int, int, seq[int], seq[int],
seq[int]) =
echo("generating parameters for P", prime)
let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
var modpg = 1
for prm in primes: (modpg *= prm; if prm == prime: break)
var pc = 1
var residues: seq[int] = @[]
while pc < modpg: (pc += 2; if gcd(modpg, pc) == 1: residues.add(pc))
let rescnt = residues.len
var restwins: seq[int] = @[]
var j = 0
while j < rescnt-1:
if residues[j]+2 == residues[j+1]:
restwins.add residues[j]; restwins.add residues[j+1]; j += 1
j += 1
let rescntp = restwins.len
inverses: seq[int] = @[]
for res in residues: inverses.add(mulInv(res,modpg))
echo("residues size = ", residues.len)
echo("inverses size = ", inverses.len)
for j in 0..residues.len-1: (if residues[j]*inverses[j] mod modpg != 1:
echo("error at index ",j))
result = (modpg, rescnt, rescntp, residues, restwins, inverses)
# Generate at compile time the parameters for P13
const parameters = genPGparameters(13)
This must be is under the `Magical Limit` using P13.
So what will it do with P17? And the answer is...Nope! It bombs (again)
when trying to compute the 92,160 values for the `residues` array, as it never
gets to the inverse array computation. I ultimately tried changing the
iteration variable upto 1 trillion again before giving up. I think I will need
to rebuild Nim with a new value in that file to make it take. That's for
tomorrow (maybe), unless someone can instruct me how to do it without
rebuilding Nim.
So, at least partial success, and I have learned something new and useful.
**But Please, FIX THIS!, and DOCUMENT IT!**
Re: Compiler won't scale (still)
I started changing the `MaxLoopIterations* = 1500_000 # max iterations of all loops` line in `compiler/vmdef.nim` in increments of 1 million, until it was 20M, recompiling after each change, and still got error. Then I went up in 100M increments until 1 trillion, and still got error. Do I need to recompile|rebuild Nim to make the change? Is merely changing the file sufficient? I doesn't seem so.
Re: Compiler won't scale (still)
I could use Ruby to create all the parameters and dump them into a file too, which would be easier. **I Don 't want to jump through extra HOOPs because the Nim compiler is deficient!!** I don't have to do this in C++. The compiler should work for the human, not the other way around. **PLEASE, PLEASE, PLEASE, FIX THE COMPILER!!**
Compiler won't scale (still)
I raised this issue regarding 0.17.2 but it still persists in 0.18.0.
I want to generate some system constants at compile time.
I need to generate some constant arrays of numbers for a (selectable) prime
generator (PG).
When the array size gets past some (?) value the compiler quits with this
message:
generating parameters for P13
stack trace: (most recent call last)
twinprimes_ssozp13par5d.nim(81)
lib/system.nim(3806) genPGparameters
lib/system.nim(3806, 14) Error: interpretation requires too many iterations
This SERIOUSLY impedes my development process in Nim, which doesn't exist in
C++.
I provide code for the case that will compile, then the version that the
compiler squawks at.
The array `residues` for P13 (prime generator for prime of 13) contains 5760
values. The array `restwins` contains 2970 values.
When I attempt to compile array `inverses`, containing another 5760 values, the
compiler squawks.
I ended up using Ruby to generate the `inverses` array values, then displayed
to terminal, copied, pasted into an editor, line formatted, copied, then pasted
the formatted array values into my Nim source code so I could compile and run
the program.
I need to do the next higher prime generator P17, whose array
`residues|resinvrs` each contain 92,160 values, but the compiler ends when
trying to create just the `residues` array.
So somewhere between (5760 + 2970) = 8730 - 92,160 iterations, the compiler
stops working.
Besides this being an arbitrary decision to have the compiler act like this,
it's undocumented, and there is apparently no (known) mechanism to extend this
arbitrary limit to a user. Is there some compiler flag to eliminate|extend it?
To say the least `This makes me Very Unhappy!! :-(`.
My development has stalled because of this. And it is totally not feasible for
me to generate two 92,160 element arrays in Ruby (which it has no problem
doing) and go through the print|format|copy|paste dance of two 1000+ lines of
numbers, again. And that's just for P17. P19 has 1,658,880 values for each
array,
`It would make me very, very Happy :-)` to eliminate this barrier to my
continued project development.
# This code will compile
import math # for sqrt function
import strutils, typetraits # for number input
import times, os # for timing code execution
import osproc # for getting threads count
import threadpool # for parallel processing
{.experimental.} # required to use 'parallel' (0.17.x)
proc genPGparameters(prime: int): (int, int, int, seq[int], seq[int]) =
echo("generating parameters for P", prime)
let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
var modpg = 1
for prm in primes: (modpg *= prm; if prm == prime: break)
var pc = 1
var residues: seq[int] = @[]
while pc < modpg: (pc += 2; if gcd(modpg, pc) == 1: residues.add(pc))
let rescnt = residues.len
var restwins: seq[int] = @[]
var j = 0
while j < rescnt-1:
if residues[j]+2 == residues[j+1]:
restwins.add residues[j]; restwins.add residues[j+1]; j.inc
j.inc
let rescntp = restwins.len
result = (modpg, rescnt, rescntp, residues, restwins)
# Generate at compile time the parameters for P13
const parameters = genPGparameters(13)
# This won't compile with the addition of creating the 'inverses' array
import math # for sqrt function
import strutils, typetraits # for number input
import times, os # for timing code execution
import osproc # for getting threads count
import threadpool # for parallel processing
{.experimental.} # required to use 'parallel' (0.17.x)
proc genPGparameters(prime: int): (int, int, int, seq[int], seq[int],
seq[int]) =
echo("generating parameters for P", prime)
let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
var modpg = 1
for prm in primes: (modpg *= prm; if prm == prime: break)
var pc = 1
var residues: seq[int] = @[]
while pc < modpg: (pc += 2; if gcd(modpg, pc) == 1: residues.add(pc))
let rescnt = residues.len
var restwins: seq[int] = @[]
var j = 0
while j < rescnt-1:
if residues[j]+2 == residues[j+1]:
restwins.add residues[j]; restwins.add residues[j+1]; j.inc
j.inc
let rescntp = restwins.len
var inverses: seq[int] = @[]
j = 0
while j < rescnt:
let res = residues[j]
for inv in residues:
if res*inv mod modpg == 1: (inverses.add(inv); break)
j.inc
result = (modpg, rescnt, rescntp, residues, restwins, inverses)
# Generate at compile time the parameters for P13
const parameters =
Re: The Nim way to do this
Thanks! Where in the docs are these methods?
The Nim way to do this
I've looked through the docs but haven't found the answer to this. I have an array of integers (prime numbers) and I want to: 1) determine if some number is included in the array and 2) return the index value of the number in the array. In Ruby/Crystal I can do the following. What are the equivalent method(s) in Nim? Ruby 1) primes = [7, 11, 13, 17, 19, 23, 29, 31] if primes.include? num; do_something_here end 2) index = primes.index num I tried to do the following in Nim to give me the equivalent result for 1) in Nim, but the compiler squawks. Nim 1) if count(primes, num) == 1: do_something_here I expected that `count(primes, num)` would return `0` if `num` isn't in `primes` but the compiler gives type mismatch error.
Re: compiler error in 0.18.0 ??
Stafan_Salewski, yes, thanks for reminding about that again. The twinprimes code is old (almost a year, using 0.17.x), when I was just getting seriously into converting C++ code into Nim. Using the original construct for that loop worked, because I always compiled with `gc` on. Then I started playing with compiling with `--gc:none` to see the difference. If you open a terminal window with `htop` while the program ran you can see memory being eaten up in real time - fascinating. I ultimately found that problem too, and all current versions of all my code has corrected that implementation. But when 0.18.0 came out, I realized I had never updated THAT original code, and used it to update with (it works fine doing a default compile). As soon as you showed me that I looked at my current codebase and they all had the correction, so they can run without `gc` and not eat up memory. But to the original issue, I `think` I've traced it to the differences in `gcc` versions. My base system on my laptop is old, and I've never (yet) gotten around to updating it. It uses `gcc 4.9.2`. So what I observed occurred on that configuration. Today I installed 0.18.0 in a VB with the updated distro of my base system, which uses `gcc 7.3.0` and voila! the programs run with-or-without compiling with `gc` on|off. So that `seems` to be the cause of the different behaviors in runtimes (as they all compile on both systems). (Actually, this is one reason|excuse I keep my old configuration around, to see what stuff breaks on it.) One lesson learned: don't change the compiler option settings I put in my code for the exact reason why it's there. I'm going to run tests in other VB distro instances, to make sure the code runs on those systems too. But this makes me feel better that its not 0.18.0 per se, but which compiler is used with it. If I really feel motivated to experiment, I may see what the behavior is on both systems compiling with `clang`.
Re: compiler error in 0.18.0 ??
> Turn of your OS's memory overcommitment. I have no idea what this means. Giving an example would be helpful next time. Unfortunately, 0.18.0 has some bigtime regressions. I compiled the same code in 0.17.2, and not only does it compile and run correctly for all input values, the compiled binary went from ~ 112K bytes to ~85K bytes. So I guess I'm sticking with 0.17.2 for awhile. Below are the source files: **twinprimes_ssozp5a2.nim** \- sieve as single process [https://gist.github.com/jzakiya/8f7f4f0dc8c9efd70870a1b3449c60cc](https://gist.github.com/jzakiya/8f7f4f0dc8c9efd70870a1b3449c60cc) **twinprimes_ssozp5a2a.nim** \- sieve separated into 2 processes [https://gist.github.com/jzakiya/308b20892013f41d808c926b30e9b94d](https://gist.github.com/jzakiya/308b20892013f41d808c926b30e9b94d) Compile as (directions in beginning of file comments) $ nim c --cc:gcc --d:release --gc:none twinprimes_ssozp5a2|a.nim and run and enter big number e.g. 500 billion (500_000_000_000) $ ./twinprimes_ssozp5a2|a Enter integer number: 500 this takes ~246 secs (4 minutes, single thread), on my I7, 3.5GHz, 64-bit Linux distro laptop Large values like this crash twin...5a2a with 0.18.0, but both programs run perfectly with 0.17.2.
compiler error in 0.18.0 ??
So I'm compiling some new code in 0.18.0. This code code compiles and runs correctly as one process with no problems. proc segsieve(Kn: int) = # for Kn resgroups|bytes in segment ... for indx in 0..5: # for nextp row indexes, var r = indx + 1 # indx|r: 0 -> 1, 1 -> 2, 2 -> 3, 3 -> 4 if indx > 3: r += 1 # indx|r: 4 -> 6, 5 -> 7 restracks in seg let biti = uint8(1 shl r)# set its residue track bit mask let row = indx * pcnt # set address to its restrack in 'nextp' for j, prime in primes: # for each prime r1..sqrt(N) if nextp[row + j] < Kn.uint: # if 1st mult resgroup is within 'seg' var k = int(nextp[row + j]) # starting from this resgroup in 'seg' while k < Kn:# for each primenth byte to end of 'seg' seg[k] = seg[k] or biti# mark restrack bit in byte as nonprime k += prime # compute next prime multiple resgroup nextp[row + j] = uint(k-Kn) # save 1st resgroup in next eligible seg else: nextp[row+j] -= Kn.uint # do if 1st mult resgroup not within seg ... Then I separate it into 2 processes, to make it parallel ready, but first run it single threaded. proc residue_sieve(Kn, r, indx: int) = let biti = uint8(1 shl r)# set its residue track bit mask let row = indx * pcnt # set address to its restrack in 'nextp' for j, prime in primes: # for each prime r1..sqrt(N) if nextp[row + j] < Kn.uint: # if 1st mult resgroup is within 'seg' var k = int(nextp[row + j]) # starting from this resgroup in 'seg' while k < Kn:# for each primenth byte to end of 'seg' seg[k] = seg[k] or biti# mark restrack bit in byte as nonprime k += prime # compute next prime multiple resgroup nextp[row + j] = uint(k-Kn) # save 1st resgroup in next eligible seg else: nextp[row+j] -= Kn.uint # do if 1st mult resgroup not within seg proc segsieve(Kn: int) = # for Kn resgroups|bytes in segment ... for indx in 0..5:# for nextp row indexes, var r = indx + 1 # indx|r: 0 -> 1, 1 -> 2, 2 -> 3, 3 -> 4 if indx > 3: r += 1# indx|r: 4 -> 6, 5 -> 7 restracks in seg residue_sieve(Kn,r,indx) # sieve on just the necessary restracks ... It compiles with no problems, and runs correctly, until the input values gets past a certain size, then it throws a runtime SEGFAULT error. SIGSEGV: Illegal storage access. (Attempt to read from nil?) This seems like a clear compiler error. Doing the same algorithm|work in one process compiles|runs correctly, while breaking it into 2 processes compiles, but only works correctly for input values below some ERROR value. It seems the error occurs reading from **nextp[]** or **seg[]** 's mem. I have no idea why it's doing that, or how to fix it. Also, the single process compiled binary (28) is about 18K bytes smaller than for the separated processes (129991).
Re: Advice on OOP in Nim
Ruby is a fully OOP language but doesn't have multiple inheritance either. Every class is open though (you can add/change methods in them), and you can create the equivalence of multiple inheritance by using **modules** and **mixins** where you **include** them in **classes** to extend them. You can use this paradigm with Nim too, as it also provides for **modules**. There's lots of ways to define and do/implement OO paradigms. Below is tutorial info on Ruby's implementation of its OOP paradigm [https://launchschool.com/books/oo_ruby/read/the_object_model](https://launchschool.com/books/oo_ruby/read/the_object_model) [https://www.tutorialspoint.com/ruby/ruby_object_oriented.htm](https://www.tutorialspoint.com/ruby/ruby_object_oriented.htm) Once you figure out the characteristics/features you want to have in your OOP paradigm then you can build it.
Nim for Rubyists
Looking thru the Ruby Weekly newsletter [https://rubyweekly.com](https://rubyweekly.com)/ there was these: **Top five reasons for Rubyist to use Crystal** [https://crystal-lang.org/2018/01/08/top-5-reasons-for-ruby-ists-to-use-crystal.html?utm_source=rubyweekly_medium=email](https://crystal-lang.org/2018/01/08/top-5-reasons-for-ruby-ists-to-use-crystal.html?utm_source=rubyweekly_medium=email) and then the Rustacean foray for mindshare **Rust for Rubyists**: [https://matthias-endler.de/2017/rust-for-rubyists/?utm_source=rubyweekly_medium=email](https://matthias-endler.de/2017/rust-for-rubyists/?utm_source=rubyweekly_medium=email) The article which really spiked my interest in Nim (coming from Ruby) is from July 2017 below: **Nim for the discerning Rubyist** [http://www.bootstrap.me.uk/bootstrapped-blog/nim-for-the-discerning-rubyist](http://www.bootstrap.me.uk/bootstrapped-blog/nim-for-the-discerning-rubyist) It would be really nice to have more of these articles to show Rubyist how to use Nim to their advantage. It would also be really nice to have a **Nim Weekly** newsletter too. I have some things I could possibly contribute. Something to work toward.
Re: Increasing Nim exposure
It appears most of the comments made to my original post are not addressing the issue I raised, which is increasing the exposure of Nim. In fact, some commentators seem to be suggesting they don't see a high need to increase Nim's exposure. I think this is a very insular view and attitude of the world and detrimental to Nim's development, adoption, and future. I also totally agree that every language (be it programming or human) is inherently reflective of a distinct community of people and their way of thinking about, interacting with, and solving problems (and what is even considered a "problem"). **Consider the Tale of Two Languages** **Forth** Most people have never heard of Forth, which was created by one person, Charles Moore, and first released to the world in 1970. He wrote it for himself so he could easily control radio telescopes at the U.S. National Radio Astronomy Observatory, where he worked. [https://en.wikipedia.org/wiki/Forth_(programming_language](https://en.wikipedia.org/wiki/Forth_\(programming_language)) It is a stack based language that's been implemented in hardware cpu systems (Forth Engines), many of which have fueled NASA, and European Space Agency (ESA) missions. [https://en.wikipedia.org/wiki/RTX2010](https://en.wikipedia.org/wiki/RTX2010) [https://www.forth.com/resources/space-applications](https://www.forth.com/resources/space-applications)/ [https://www.forth.com/resources/forth-apps](https://www.forth.com/resources/forth-apps)/ [http://forth.org/successes.html](http://forth.org/successes.html) Many of you are probably too young to remember that in the 1970's into the early 1990's HP was a major player in calculators (especially scientific ones), before the advent and ubiquity of "personal" computers. HP calculators were based on Forth, and used reverse-polish-notation (RPN) and stacks. To this day, IMHO, they are the best calculators on the market (technically) but other cheaper brands (Casio, Texas Instruments (TI), etc) rule that market now. When I was an engineering student at Cornell in the early/mid 1970's it was considered "cool" to have an HP calculator (especially a programmable HP-45, which I saved to pay a ransom sum to get). So when I started working for NASA in 1979, and assigned to use Forth on prototype flight/ground systems, I felt right at home. Forth is one of the most powerful programming environments you can ever use. It allows you to do literally anything you can thinks of, if you can think of it. Whatever the cpu could possibly do, Forth allowed you to control every register, instruction, and byte of memory of it. However, like becoming a "really good" violin player, you had to appreciate, learn, and practice using its capabilities, otherwise, like most people who try to play the violin, it just becomes a piece of wood with strings attached. If you take the time to master it, you can make people laugh, dance, or cry, depending on how you play it. To this day, Forth has a vibrant and vocal user community, but at best now, it's a niche language (though sometimes it's some company's secret development language). [https://groups.google.com/forum/#!forum/comp.lang.forth](https://groups.google.com/forum/#!forum/comp.lang.forth) Why have most of you never even heard of Forth, or seen articles on it, or conferences about it, etc (and all these still do occur)? The major reason is because people in the Forth community have never had the vision, and ultimately the desire, commitment, and unity, to change the language to expand its reach, by making it more friendly and useful to a wider community of people other than themselves. Does this sound familiar? **Ruby** Now consider Ruby. It too was created by one person, Yukihiro "Matz" Matsumoto, and released to the world (Japan) in 1993. [https://en.wikipedia.org/wiki/Ruby_(programming_language](https://en.wikipedia.org/wiki/Ruby_\(programming_language)) It's highest goal is, as quoted from Matz in the wikipedia article: > ..we need to focus on humans, on how humans care about doing programming or > operating the application of the machines. We are the masters. They are the > slaves." Matz, and the Ruby development team, and its community, takes this goal very seriously. So for the traditional Christmas release (December 25, 2017) of the new major version 2.5, it included the method `prepend` to `class Array`, solely because of community desire for (English) linguistic consistency, since there already was an `append` method. And both of these are aliases of the original core methods `unshift` (add elements to beginning of an array) and `push` (add elements to end of an array). These additions were soley requested and added to the language because people wanted to write better readable code. So now, instead of writing: `ary.unshift(1,3,4)` and `ary.push(5,6,7)` you can write `ary.prepend(1,3,4)` and `ary.append(5,6,7)`. Anyone who understands
Increasing Nim exposure
Having access to various Ruby article feeder sites I recently came across this [https://hacklines.com](https://hacklines.com)/ [https://hacklines.com/en?ucc=rubyflow=Ruby%2CRails%2CSinatra](https://hacklines.com/en?ucc=rubyflow=Ruby%2CRails%2CSinatra) which is multilingual. It lists articles and blogposts on a long list of various languages, but not Nim. I think it would be good exposure for Nim to see how to get it on their language list. I also subscribe to different languages (Rust, Elixir, Julia) which use the Discourse ecosystem for their forum/communities communication system. I know Nim has this forum, but using Discourse may make if more accessible to people who haven't even heard of Nim. Just some thoughts. [https://www.discourse.org](https://www.discourse.org)/ [https://users.rust-lang.org](https://users.rust-lang.org)/
experimenting with pointers and slices
I have some working code and **I'm experimenting** with using pointers and slices to achieve the same results. Here's what I conceptually want to do. parallel: for bytn in 0..bprg-1: . var seg_r: seq[uint8] = seg[bytn*Ks..byt*Ks+Ks-1] spawn residue_sieve(n_row, seg_r, Kmax, Ks, bytn) sync()t I want to pass `seg_r` as a slice, but the compiler squawks with this (it never asked me if I can verify its all good ), even when I compile with `--boundChecks:on|off`. ssozp13x1d7bparnew512.nim(192, 40) Error: cannot prove: bytn * Ks <= len(seg) + -1 (bounds check) So I have `seg` a `seq[uint8](m * Ks)` array, and I'm processing each of the `m rows` in parallel. When I pass in `let row_i = bytn * Ks` it r/w fine doing `seg[row_i + k]` inside `residue_sieve`. I'm trying to understand how to do the following cases: 1) define `seg_r` as a slice in `seg` I can read/write each element to as `seg_r[k]` in `residue_sieve`. 2) define `seg_r` as pointer to start of slice at `seg[bytn*Ks]` and r/w as `seg_r[k]` in `residue_sieve`. 3) define `seg_r` as pointer to slice `seg[bytn*Ks..bytn*Ks+Ks-1]` and r/w as I'm doing this to compare timing differences between them in my code (want fastest).
Re: A wish for Nim conferences
Matz's (Ruby's creator) Keynote Address at RubyConf 2017 provides very good guidance for language (any project really) development. It's really worth the TL;DR time. [https://www.youtube.com/watch?v=1-A9eRzCBL0=1=PLE7tQUdRKcyayGHjjxZOmVEGsxX-rczZt](https://www.youtube.com/watch?v=1-A9eRzCBL0=1=PLE7tQUdRKcyayGHjjxZOmVEGsxX-rczZt) A complete list of conference talks. [https://confreaks.tv/events/rubyconf2017](https://confreaks.tv/events/rubyconf2017) Something to shoot for.
Re: Compiling with --gc:none produces unexpected prohibition
This code works as desired in parallel. Thanks for the instructions.
proc column_load(prime, j, k, r: int) {.gcsafe.} =
{.gcsafe.}:
for ri in residues: # for each prime|residue pair
let prod = r * ri # compute res cross-product
let row = posn[prod mod modpg] * pcnt # compute restrack address
# compute|store for each row the resgroup vals for prime in column j
nextp[row + j] = uint(k*(prime + ri) + (prod-2) div modpg)
# Initialize the [rescnt x pcnt] 'nextp' table with resgroup values of the
# 1st prime multiples for each prime r1..sqrt(N) for each PG residue track.
proc nextp_init() =
# load 'nextp' with 1st prime multiples regroups vals on each residue
track
parallel: # do in parallel
for j, prime in primes: # for each prime r1..sqrt(N)
let k = (prime-2) div modpg # find the resgroup it's in
let r = (prime-2) mod modpg + 2 # and its residue value
spawn column_load(prime, j, k, r) # load column resgroups for
prime
sync()
I guess it was surprising that even when I turned off compiling with garbage
collection (`--gc:none`) it still applied gc rules to this structure. Well, I
learned a little bit more about Nim.
Re: How to make this compile
I'm trying to understand what you are suggesting with your response, especially because what I ultimately want to do in this instance I will want to do with other bigger generators. What I assume you are saying is `helper` is some Nim source program that will produce the output that `gemPGparameters` does. The expression you give will then execute `helper` at run time and provide its results to `const parameters` at its compile time. Is this interpretation correct? What I ultimately want to do is create a family of `const parameters` for different prime generators at compile time. Then when the program executes it will select which parameters to use based on the input value. For P17 the `residues` array has 92,160 values, P19 has 1,658,880, P23 has 36,495,360. So I ultimately want a lot of values computed and stored at compile time. Your response suggests the current compiler won't accommodate this amount of data generation at compile time. I guess my question is why? Why not create a compiler directive to remove any time/data constraints to compile time activity? Make the compiler do what the programmer wants. Also, just from your response I don't have enough detailed information to make your suggestion work. Is this suggestion verified to provide the results I want? If so, can you give a detailed example of how to implement it? I understand Nim is still young and in core fundamental development, so I hope you take this situation into consideration for future compiler development. I've been able to do a lot with Nim as it is (and I understand it), so these improvements will greatly extend its usefulness to the class of problems I am now working on. Thanks for taking this into consideration.
How to make this compile
The code below works, but when I try to run it using P17 the compiler throws an
error about the `gcd` proc. Using P17 causes `gcd` to be called on the order of
250,000 times, as `modpg = 510510`
Here's the code.
# Create constant parameters for chosen PG at compile time
proc genPGparameters(prime: int): (int, int, int, seq[int]) =
echo("generating parameters for P", prime)
let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
var modpg = 1; var excluded_primescnt = 0
for prm in primes:
excluded_primescnt += 1; modpg *= prm; if prm == prime: break
var pc = 3; var residues: seq[int]; residues = @[]
while pc < modpg:
if gcd(modpg, pc) == 1: residues.add(pc)
pc += 2
residues.add(modpg + 1)
let rescnt = residues.len
result = (modpg, rescnt, excluded_primescnt, residues)
# Generate at compile time the parameters for P17
const parameters = genPGparameters(17)
Here's the relevant compiler output.
generating parameters for P17
stack trace: (most recent call last)
ssozp17x1d5bparnew128.nim(59)
ssozp17x1d5bparnew128.nim(52) genPGparameters
lib/pure/math.nim(439) gcd
lib/pure/math.nim(439, 15) Error: interpretation requires too many
iterations
➜ nim
I can't see how `gcd` could care how many times it's being called, so it seems
it must be the compiler not liking it being called past a certain number.
Whatever the reason, how do I get this code to finish compiling?
A wish for Nim conferences
When Nim starts having conferences it would be nice for them to feel like those for Ruby. [https://avdi.codes/rubyconf-2017/?utm_source=rubyweekly_medium=email](https://avdi.codes/rubyconf-2017/?utm_source=rubyweekly_medium=email)
Re: floating point output formating
@dom96 if you want people to voluntarily, out of their concern for the project, and goodness of their own `heart`, contribute to Nim, first you need to `check your attitude`, and learn how not to chase people away. [https://medium.freecodecamp.org/how-to-attract-new-contributors-to-your-open-source-project-46f8b791d787](https://medium.freecodecamp.org/how-to-attract-new-contributors-to-your-open-source-project-46f8b791d787) [https://www.itworld.com/article/2768358/open-source-tools/how-to-attract-more-people-to-your-open-source-project.html](https://www.itworld.com/article/2768358/open-source-tools/how-to-attract-more-people-to-your-open-source-project.html) Writing better documentation has very little to do with how much money or people a project has. Like I (and all these links I've been providing) said `it's an ATTITUDE`. You took whatever time you took, with whatever resources you had, to create the documentation that exists now. Well, take at least the same time and resources to make them better, and stop making excuses. The most relevant thing you said was you think writing documentation is `boring`, and it shows! Instead of telling me what I should/could do you should do it yourself. `It ain't my project and I have no responsibility to make it better`. The fact that I (and others) take time to inform you all about errors and deficiencies in your project (and you've made it clear this isn't an `our` project) should be seen as a `gift`. You know, you can do what @bluenote has done and try to write some better, correct, and useful documentation. It's amazing how much you can accomplish if you just improved one function/page/module of documentation each day/week/month. And if you really, really, really want people to contribute to documentation don't require people to jump through the hoop of writing/submitting `pull requests`. I personally hate making pr's just for documentation, it so primitive. Instead, create a `wiki` (there's this little project called `wikipedia` you know), so people who are writers, or willing to write, can actually do documentation in a way that's more conducive to writing documentation versus code versioning. I know, I know, this would take too much `time and effort` to implement, and it's much easier taking `time and effort` to peruse the forums and tell people you won't take `time and effort` to create better documentation because its `too boring`.
Re: floating point output formating
**Araq you need to chill out!** I took the time to document for you unexpected, deficient, and incorrect behavior of your documentation and you are not even `humble` enough to thank me for it. So why should I bother to keep using your `work in progress` language that you can't even take `positive critical feedback` to improve?
Re: floating point output formating
Upon thinking about it, I think the case for `echo num.formatFloat(ffDecimial,
0)` is incorrect, and should be changed to be consistent with the intent of the
function.
The `0` option should produce a value (currently it would be `rounded`) with no
digits displayed.
`echo (10.456).formatFloat(ffDecimal, 0) -> 10`
`echo (10.556).formatFloat(ffDecimal, 0) -> 11`
Also, its current behavior is redundant, as it mimics the behavior of `echo
num.formatFloat()`. Thus, currently there is no way to use this function to
display no ('0') digits, which is inconsistent (and undocumented) with what a
user would expect of its behavior.
import strutils
let num = 10.5678
echo num.formatFloat()
echo num.formatFloat(ffDecimal, 0)
These revelations about how this one little function actually works, have all
been illuminated because of the effort we've engaged in to document it. How
much more will be revealed about all the other parts of the language once you
begin creating `full case tested` documentation?
Re: floating point output formating
@bluenote, also for `formatFloat`, it should also explain that it seems to using `rounding` of the digits its displays and not truncation. If a user wants to just truncate the displayed digits what function does that, or can this one perform that too. It may be an option to include into this function (and other ones where relevant). let num = 5.1273456 echo num.formatFloat(ffDecimal,1) echo num.formatFloat(ffDecimal,2) echo num.formatFloat(ffDecimal,3) echo num.formatFloat(ffDecimal,4) echo num.formatFloat(ffDecimal,5) echo num.formatFloat(ffDecimal,6) echo num.formatFloat(ffDecimal,7) echo num.formatFloat(ffDecimal,8) This is why you have to have thorough test structures in order to provide `good and accurate human usable` documentation. What you have there now, though technically accurate, doesn't tell the whole story of how the function behaves, and what then should a user do if they want to do `decimal truncation`. It should be explicitly stated it performs `rounding` of the digits before displaying. Is there a function that performs truncation? One significant added benefit of writing thorough tested documentation is, after you do it, you will `really` understand how the language `actually` works, and not just how you thought it did.
Re: floating point output formating
@bluenote I could kiss you! Now just do that for at least everything in that module and that will be a significant start, and benefit to all of us users.
Re: floating point output formating
Hey guys, stop being defensive. If I didn't think Nim is a worthy project, and has great potential, I would have never bothered to take the time to tell you how to improve your project, and it would be in your interest to take comments as mine as `positive critical feedback`. As further `positive critical feedback` please read/study/learn from these sources (there are many, many more with simple internet searches). [https://opensource.com/business/15/5/write-better-docs](https://opensource.com/business/15/5/write-better-docs) [http://www.writethedocs.org/guide/writing/beginners-guide-to-docs](http://www.writethedocs.org/guide/writing/beginners-guide-to-docs)/ [http://blog.screensteps.com/10-examples-of-great-end-user-documentation](http://blog.screensteps.com/10-examples-of-great-end-user-documentation) [https://www.techrepublic.com/blog/10-things/10-things-you-can-do-to-create-better-documentation](https://www.techrepublic.com/blog/10-things/10-things-you-can-do-to-create-better-documentation)/ You can really demonstrate that you understand what I would like you to do if when I go back and look at the docs for `formatFloat`, and everything else on that page, there are use examples for each entry.
Re: floating point output formating
Actually, `the only limits of what you can provide in documentation are self imposed`. `Writing documentation is an attitude!` Either you care about doing it (to benefit/help users) or you don't. Nim has to compete against lots of other languages, and like cars, smartphones, etc, having the better/best technology doesn't mean you will have the biggest following. People will ultimately use first the things that are accessible, easy to use, and cheap (why do Americans eat so much bad fastfood - because its cheap, the stores are everywhere, and they stay open late when people are hungry). Your own 2017 Survey specifically lists lack of documentation as one of the biggest deficiencies of this project, but I don't see an active effort to make it better. [https://nim-lang.org/blog/2017/10/01/community-survey-results-2017.html](https://nim-lang.org/blog/2017/10/01/community-survey-results-2017.html) Let's compare Nim against Rust, two languages promoting themselves as `system` programming languages. Rust is by far a much harder to learn/use language than Nim, but it knows that, and has created very good documentation (and forum) to help people get their heads `(and hearts)` around it. Both Nim and Rust have a document called `[Nim|Rust] by Example`, but tell me which is more helpful/useful to potential users. Let's compare their presentation of `arrays` in each document. Nim: [https://nim-by-example.github.io/arrays](https://nim-by-example.github.io/arrays)/ Rust: [https://rustbyexample.com/primitives/array.html](https://rustbyexample.com/primitives/array.html) As `a potential user` I get a much clearer understanding of how to create, access, and print arrays from Rust's docs, with examples for each use case given. Now let's take a look at Ruby's: [https://www.ruby-lang.org/en/documentation](https://www.ruby-lang.org/en/documentation)/ Granted, Ruby has been around a lot longer than Nim, and has loads of books, videos, and conferences, but it all starts with an `attitude` of the Ruby community, which is probably `The Most Friendly` language community in the world. You can find just about anything you want on this page about how to use Ruby, and this is by design. They didn't limit what they could do. And here's what I mean by `attitude` for this specific instance of trying to find out about outputting floating points. I took about three hours, searching the docs and internet, trying to find out how to print out floats to a given precision, and gave up after being frustrated (fed up). Only then did I resort to asking help in the forums. It was first answered by only providing a link to a cryptic (my impression of it) function, which had no examples of how to use it. I had to ask, again, how to use it, and was finally given a specific example of how. And then when I point out none of those functions on that page (and elsewhere) have specific use case examples, instead of saying, "you're right, we'll get on it", you give excuses (there are limits to what we can do). If I were you all, I'd start immediately upgrading your docs, first by formatting the categories from the point of view of helping potential users (Input/Outputting Data, How to use Files, etc) with clear/concise/helpful use case examples. You can start by copying `best practices` used in other projects docs. Would this take a lot of work and effort -- `Hell Yes!`. But you all need to really understand, you are not only in a battle to win peoples minds, to get them to understand your language, you're also competing to win (and keep) their `hearts`, so they `want` to use your language. People can criticize Ruby all they want, but people who use Ruby, and go to its conferences, do so because they `love it`, even when they move on to other languages (like Elixir). Actually, this specific discussion should have its own thread, so others can chime in, and not be buried at the end of this thread. But please take `to heart` this old saying: `You only have one chance to make a first impression.`
Re: floating point output formating
Thanks a whole lot! The Docs really need to get better by showing clear examples like this for just about everything. It took way too long for me to search and not even find this, and had to resort to asking how to do this here. I also agree the semantics for doing this has to become a lot shorter/simpler/clearer. I don't mean to go off, but outputting is such a standard thing to do in any language it should be readily available in the Docs to show users how to deal with the various cases. Thanks again.
Re: floating point output formating
let num = 10.123456789 echo( formatFloat(num) ) Could I get a little help here to make this work.
Re: compile time code execution problem
let num = 10 const x = 9 echo(num + x) let num = 10.int const x = 9 echo(num + x) let num = 10.uint const x = 9 echo(num + x)
Re: compile time code execution problem
That seems to be the case because you have to explicitly cast `let` s (or the compiler assumes a default cast).
floating point output formating
I compute a floating point number `x`. How do I use `echo|write.stdout` to output it with just 4 decimal digits showing?
queues for parallel processing
I don't know if this is currently possible, but it would be nice to have. It seems I could theoretically speed the execution of this code. proc segsieve(Kmax: uint, KB: int) = # for Kn resgroups|bytes in segment let Ks = KB# make default seg size immutable parallel: # perform SSoZ in parallel for r in 0..rescnt-1:# for each residue track number 'r' let nextp_row = r * pcnt # set the 'nextp' table row address let seg_row = r * Ks # set the 'seg' memory row address spawn residue_sieve(nextp_row, seg_row, Kmax, Ks, r) # do sieve for row 'r' sync() # wait for all row threads to finish for i in 0..rescnt-1: # update 'primecnt' with the count of primecnt += cnts[i] # segment primes for each 'seg' row Here `sync()` causes the following code to wait for execution until all the threads finished executing. It should be theoretically possible to speed overall execution by having the `cnts` from each thread be asynchronously put into a thread queue (FIFO) and extracted and added to `primecnt`. Since here there are a known number of `cnt` values (`rescnt` amount) `primecnt` can then be updated as these values become availble until `rescnt` are added. Is this possible now? Could it be faster?
Re: compile time code execution problem
What I was trying to get at is how to make the generated constant values behave like coding specific numerical numbers. Apparent for numerical constants, when you do this: `const modpg = 2310` the compiler will convert it to whatever is required to make math operations work (at least it did so in my code). But doing: `const modpg = parameter[0]` causes it to retain the `int` casting from the `proc`, which then requires explicit casting when doing math with differently cast values. It would be nice (so I wouldn't need to explicitly recast these values in some places) if I could make the later case behave like the former case (as explicit uncast numbers). I can obviously live with it, but it would be nice to have some sort of `null casting` to make assigned constant values behave the same as explicit numbers. In the former case I had gone thru _casting hell_ to get the math to work with the least amount of explicit casting (to reduce the coding noise), and it would be nice if the generated constants behaved the same.
Re: compile time code execution problem
Hey thanks for the help!
Here's what I had to do to get it to compile/work fully (using Nim 0.17.2).
proc genPGparameters(prime: int): (int, int, int, seq[int]) =
echo("generating parameters for P", prime)
let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
var modpg = 1; var excluded_primescnt = 0
for prm in primes:
excluded_primescnt += 1; modpg *= prm; if prm == prime: break
var pc = 3; var residues = @[1]
while pc < modpg:
if gcd(modpg, pc) == 1: residues.add(pc)
pc += 2
residues.add(modpg + 1)
let rescnt = residues.len-1
result = (modpg, rescnt, excluded_primescnt, residues)
const parameters = genPGparameters(11)
const
modpg= parameters[0]
rescnt = parameters[1]
ep = parameters[2]
residues = parameters[3]
The only quirks I had to deal with after the parameters were generated/assigned
was I had to recast in the code some places where I used `modpg` and `rescnt`
to do math. The compiler told me where the casting incompatibilities were, and
I just had to use `modpg.unit` and `rescnt.uint` in a few places.
The full compiled code is about 5KB larger than the one with explicitly coded
values, buts runs with the same speed. This now will allow me to use any
Strictly Prime (SP) Prime Generator (PG) without having to create a specific
version for them separately. Now I can just change the prime value for
`genPGparameters` and, voila, its done.
The only other question I have is why does the compiler treat differently in
the code when `modpg/rescnt` are assigned specific numerical values versus from
the compiletime generated ones?
I would highly recommend putting this kind of example in the `Docs/Nim
Cookbook`. Coming from Ruby/Elixir, this kind of thing is done all the time.
Re: compile time code execution problem
I do `import math` to get `gcd` in my program, that's why you got that error. I still can't get the output from `getPGparameters` assigned to constants of the same names, to be used later in the program. I thought you could do assignments like: const (a, b, c) = tuple(x, y, z) If tuples aren't the way to do this I don't care, I just want to generate the parameters and assign them at compile time, to make it easier to use.
compile time code execution problem
I want to execute the code below at compile time to initialize the global
variables shown - modpg, rescnt, residues, ep.
proc genPGparameters(prime: int): tuple =
echo("generating parameters for P", prime)
let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
var modpg = 1
var excluded_primes = 0
for prm in primes:
excluded_primes += 1; modpg *= prm; if prm == prime: break
var pc = 3; var residues = @[1]
while pc < modpg:
if gcd(modpg, pc) == 1: residues.add(pc)
pc += 2
residues.add(modpg + 1)
let rescnt = residues.len-1
result = (modpg, rescnt, residues, excluded_primes)
const (modpg, rescnt, residues, ep) = genPGparameters(11)
I get this following error message pointer about the last line.
ssozp11x1c3parnew.nim(58, 7) Error: identifier expected, but found '(
I can't find the docs for this case, but I guess it's something simple. How do
I get the code to work?
Re: How do you get thread count in Nim
Yes, that is what I meant, the `threads` that are available per system (all cpu cores), which you can see using commands such as `lscpu` or `htop`.
Re: How to get real time of parallel code
Thanks, will do.
Re: How do you get thread count in Nim
Yes, that returns the number of available threads, though its doc says processors/cores.
How do you get thread count in Nim
How do you get the number of available system threads inside a Nim proggram?
Re: How to get real time of parallel code
OK. Could you provide the url for doing it.
Re: How to get real time of parallel code
The Unix `time` command [https://en.wikipedia.org/wiki/Time_%28Unix%29](https://en.wikipedia.org/wiki/Time_%28Unix%29) [https://www.lifewire.com/command-return-time-command-4054237](https://www.lifewire.com/command-return-time-command-4054237) returns three (3) variants: `real`, `usr`, `sys`. Nim's `cpuTime()` corresponds to `usr` (total cpu time), whereas `epochTime()` corresponds to `real` (clock time). I would like to recommend that `realTime()` be included in Nim's `time` module to make it shadow that component of the Unix `time` command, which will make it's function and use case much clearer to users. This may only need to create `realTime()` as an alias of `epochTime()`.
Re: How to get real time of parallel code
Yes, that did it. This is a good use case example to distinguish in `time` docs between the use of `cpuTime()` and `epochTime()`. The given example for `cpuTime()` assumes single threaded use and not the effect of multi processor/threads use. [https://nim-lang.org/docs/times.html](https://nim-lang.org/docs/times.html)
Re: Problem using
The `cnt +=` operation in parallel is ripe for creating a `reduction` like option for Nim that's in `OpenMP`. [https://stackoverflow.com/questions/13290245/reduction-with-openmp#13290673](https://stackoverflow.com/questions/13290245/reduction-with-openmp#13290673)
Re: Problem using
OK, I had to clean it up a little to make it work, but here is the code that gets it to compile. var cnt: array[rescnt, uint] parallel: for i in 0..rescnt-1: cnt[i] = spawn segcount(i*KB, Kn) sync() for i in 0..rescnt-1: primecnt += cnt[i].uint So was the issue that the single value of `cnt` was getting clobbered by each thread's return value, causing the type mismatch? Thanks for getting it to compile, but if you can explain why this works I'd appreciate it even more.
Re: Problem using
The error messages keep saying the issue is a mismatch with FlowVar[T]. In Chapter 6 of **Nim in Action** here is what it says they are. `FlowVar[T] can be thought of as a container similar to the Future[T] type, which you used in chapter 3. At first, the container has nothing inside it. When the spawned procedure is executed in a separate thread, it returns a value sometime in the future. When that happens, the returned value is put into the FlowVar container.` Here is updated `segcount` proc segcount(row, Kn: int): uint = var cnt = 0'u for k in 0..
Re: Problem using
In the previous snippet I forgot the `spawn`. The code below compiles, but is slower. var cnt = 0# count for the primes, the '1' bytes for i in 0..
Re: Problem using
After reading the **Nim in Action** book I got it to compile by placing a `^` before `spawn`, but it makes the program slower. The problem has to do with `segcount` returning a `FlowVar[T]` mismatch. And when I use `parallel:` it won't compile, and shows even more errors. Doing more research. var cnt = 0# count for the primes, the '1' bytes for i in 0..
Re: Problem using
I've done it both with/out `parallel:` as shown below, but get the same compiler output. parallel: var cnt = 0 # count for the segment primes '1' bytes for i in 0..
Problem using "spawn"
OK, I've racked my brain enough and need help. Using 0.17.2 on Linux, I have this `proc` below. proc segcount(row, Kn: int): int = var cnt = 0 for k in 0..
Re: Recovering Nim source code
>From looking at the xxx.c file in the `nimcache` directory I ultimately >figured out which source code version the executable was created from.
Re: Another reason to deprecate ..
The intent of the post was to provide information **from a user's perspective** with real world code on how to make Nim better _from the user's perspective_. Why did you make the assumption I didn't compile my code with `--d:release`? I did. What I hoped you appreciated was that using fixed numerical values are much more performamnt than using `
OpenMP and Nim
I want to be able to do true parallel processing of highly numerical algorithms, and currently I don't know if Nim can do this, and if so, I can't find many coding examples of more than rudimentary examples. So I was wondering since Nim compiles to C/C++ whether it currently can work with OpenMP. I assume it can't, since I haven't seen any documentation saying it can, so I'm wondering are there any plans to allow using OpenMP in Nim to provide true parallel processing?
Re: Subtle memory management error found
**1)** In **nextp_init** in the line below, **i** can start from eithre '0' or '1'. for i in 0|1..
Re: Subtle memory management error found
Actually I'm not a C/C++ programmer, I'm (mostly now) a Ruby programmer who is functional in C++, and haven't really done anything in C of any note. I've been looking to see how to view the C/C++ that Nim is generating but I don't know how to do that. Can you show me how to do that? Remember, **I'm a Nim newbie**, though I've been programming for over 40 years. I know how to program what I want to do, I just have to figure out the linguistics of the language to make it do what I want. Oh, I forgot to add. **The nature of the problem is this:** If an input value only requires one **segment slice** you get the correct answers because the **nextp** table uses its initial values to process the **seg** array. However, **nextp** is being updated with wrong **k** values, so when you process more than one segment slice you start to get more **prime candidates (pcs)** being marked as non-prime than should be. This means the updated **k** values being computed and stored in **nextp** are too small, because they are knocking out more pcs than should be. If you look at the total primes count, the Nim version gives a smaller and smaller total **primecnt** as more slices are processed than the correct answers with the C++ code. I think something is happening in the **loop/conditional structure** that is making these **k** values too small and causes more pcs to be marked in **seg**. But for the life of me I have no idea of why that is happening and what's causing it. **It has to be happening under the hood, in the internals of the language**, because the structure of the source code should work in Nim, like its does in C++.
Subtle memory management error found
I have identified a very subtle memory management error that took me weeks to
characterize.
I'm directly translating a working C++ program to Nim. The problem seems to be
that the Nim code erroneously addresses the **seg** array beyonds its bounds,
because the **k** values used to update the **nextp** array are thrown off,
which causes incorrect values in **seg** to accumulate as the segment
iterations increase.
In **Listing 1** I show the corresponding code where the problem occurs. In it
I output the values shown to see the difference in values that start to occur
between the C++ and Nim code. Here I output the values for **k** and
**seg[ki]** before they are updated in the loop. Both versions output the same
values for the first complete segment iteration process. Starting within the
second iteration those values start to become different, as **nextp** is not
getting the correct values in the Nim version.
Listing 1.
C++
for (uint j=0; j < pcnt; ++j){// for each prime r1..sqrt(N)
if (nextp[row+j] < Kn) {// if 1st mult resgroup is within
'seg'
uint k = nextp[row+j];// starting from this resgroup in
'seg'
uint ki = k*bprg + byti; // convert it to a byte address
in seg[]
uint prime = primes[j]; // get prime, convert it to
number of
uint prmstep = prime * bprg; // bytes to nextp primenth
resgroup byte
for (; k < Kn; k += prime){ // for each primenth byte to end
of 'seg'
cout << "(" << r << "," << prime << "," << k << "," <<
(seg[ki] & 255) << "," << biti << ") ";
seg[ki] |= biti;// mark restrack bit in byte as
nonprime
ki += prmstep; // byte in next prime multiple
resgroup
}
nextp[row+j] = k - Kn;// save 1st resgroup in next eligible
seg
}
else nextp[row+j] -= Kn;// when 1st mult resgroup > seg
resgroup range
}
---
Nim
for j, prime in primes: # for each prime r1..sqrt(N)
if nextp[row + j] < uint(Kn): # if 1st mult resgroup is within 'seg'
var k = int(nextp[row + j]) # starting from this resgroup in 'seg'
var ki = k*bprg + byti # convert it to a byte addres in 'seg'
let prmstep = prime * bprg # set number of bytes to next prime
mult
while k < Kn:# for each primenth byte to end of
'seg'
write(stdout, "(",r, ",", prime, ",", k,",",seg[ki], ",", biti,")
")
seg[ki] = seg[ki] or biti # mark restrack bit in byte as nonprime
ki += prmstep # byte in next prime multiple resgroup
k += prime# set resgroup of next prime multiple
nextp[row + j] = uint(k-Kn) # save 1st resgroup in next eligible
seg
else: nextp[row+j] -= uint(Kn) # when 1st mult resgroup > seg
resgroup range
In **Listing 2** below, instead of outputting the values before they are
updated I do it afterwards. This should throw a **Segfault** error, and did in
the C++ code when it tried to output **seg[ki]** at an out-of-bound address.
However, the Nim code keeps outputting out-of-bounds values for **seg[ki]**
until the loop finished.
After hitting the docs I saw that compiling using **\--d:release** turns off
array bounds checking. So I compiled the **Listing 2** code as: **$ nim c -r
file.nim** and now the Nim output also gave a segfault error, but it didn't
occur at the same spot (**r** and **prime** values) as the C++ compiled code.
So then I compiled the **Listing 1** Nim code similarly, and it gave better
results, but it still produced errors.
I'm convinced now that I can't rewrite the Nim code to produce the correct
results because something is happening at the compile(r) level that I don't
understand and can't control.
Is there some compile flag to be set, or something that can be done, to make
the Nim code work correctly, and/or is this a bug in the compile process?
This was run with Nim 0.17.0, but I also got it to run under 0.12.0 (with a VB
VM Linux distros) with same results.
Listing 2
C++
for (uint j=0; j < pcnt; ++j){// for each prime r1..sqrt(N)
if (nextp[row+j] < Kn) {// if 1st mult resgroup is within
'seg'
uint k = nextp[row+j];// starting from this resgroup in
'seg'
uint ki = k*bprg + byti; // convert it to a byte address
in seg[]
uint prime = primes[j]; // get prime, convert it to
number of
uint prmstep = prime * bprg; // bytes to nextp primenth
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
user 0m3.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
user 0m40.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
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 in Action print book is 50% off today
The error was observed in the pdf version but doesn't exist in the ePub version.
Re: Nim in Action print book is 50% off today
Is there an errata page for the book on the website, or somewhere. I found a few typos|errors in the book for correction, e.g. the data in Table 2.2 on page 27. The ranges for uint[8|16|32] have a mistaken '0' on the end of the 'range' numbers for those types.
Re: Nim in Action print book is 50% off today
That's what I assumed, when I got combo 2). I assumed the pBook was the printed book, and didn't know the difference between an eBook and pdf|ePub|kindle, so I made sure I got the pdf and ePub versions, since I have various readers for them.
Re: Nim in Action print book is 50% off today
When I went to the Manning website it offered two combo deals. 1) $49.99 -- pBook + eBook + liveBook 2) $39.99 -- pdf + ePub + kindle + liveBook Using the 50% off discount code gave: 1) $49.99 - $25.00 = $24.99; 2) $39.99 - $20.00 = $19.99 I assumed the pBook in combo 1) was for the print version, while it's not included in combo 2). Is this correct? I went ahead and got combo 2) anyway (Save the Trees!). Best to open an account to get access to more than one download of the electronic versions if needed.
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
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
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.
Editor profiles fo Nim
I mostly use the KDE Kate and Atom editors for code writing and notice they don't seem to have Nim profiles for **.nim** files. Do you know editors that do, and have editor profiles been something the devs have on their todo list?
Nim documentation
Is there an available list of all the current Nim methods, functions, etc, similar to what Ruby provides, as below? [https://ruby-doc.org/core-2.4.1](https://ruby-doc.org/core-2.4.1)/
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 prim
Re: Using spawn and/or parallel: for parallel programming
Compiling with **\--threadAnalysis:off** did allow the program to compile and run with no segfaults, and it produces the correct results, but it's 2x slower than the serial version. In the code snippet, the **next**, **seg**, and **primes** arrays (seqs), and the constant **rescnt** are global parameters. **primes** is only being read from. Each thread of **residue_sieve** is using independent memory chunks of **seg** to read/write to. The problem may be with **next** which is read/written to in each thread, though never from the same location for any thread (where it is read/written to for each thread is differennt). Is there **detailed documentation** of some non-trivial example to show how to actually create running parallel code? If I need to re-architect the algorithm I first want to really understand the details of what needs to be done before I undertake that task.
Using spawn and/or parallel: for parallel programming
Using Nim 0.17. Afer reading the Nim manual on Parallel programming, and how to use **spawn** and **parallel** I can't get the following code to compile. proc residue_sieve(r: int, Kn: int) = let row = r * pcnt# set address to ith row in next[] let seg_rti: int = r * KB # start of seg mem for this restrack for j, prime in primes:# for each prime <= sqrt(N) for restrack if next[row+j] < uint(Kn): # if 1st mult resgroup index <= seg size var k: int = int(next[row+j]) # get its resgroup value while k < Kn: # for each primenth byte < segment size seg[seg_rti + k] += 1'u8 # set ith residue in segment as nonprime k += prime # compute next prime multiple resgroup next[row+j] = uint(k - Kn) # 1st resgroup in next eligible segment else: next[row+j] -= uint(Kn)# if 1st mult resgroup index > seg size proc segsieve(Kn: int) = # for Kn resgroups in segment for b in 0 ..
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) +
Re: Inputing numbers
Whoops, sorry, forgot to run the executable (probably should go to bed now) [jzakiya@jabari-pc nim]$ ./inputtest Enter integer number: 34422 You inputed 34422 with type BiggestUInt [jzakiya@jabari-pc nim]$ Made the same mistake on target program, but it works now too. Definitely time to go to bed now.
Re: Inputing numbers
I'm am running Manjaro KDE (gcc 7.1.1, clang 4.0.1) in a VirtualBox VM using another Linux distros as VB host. When I run this file: inputtest.nim import strutils, typetraits stdout.write "Enter integer number: " let val = stdin.readline.parseBiggestUInt echo "You inputed ", val, " with type ", val.type.name Here are the compile and runtime results [jzakiya@jabari-pc nim]$ nim c --cc:clang --d:release inputtest.nim Hint: used config file '/etc/nim.cfg' [Conf] Hint: system [Processing] Hint: inputtest [Processing] Hint: strutils [Processing] Hint: parseutils [Processing] Hint: math [Processing] Hint: algorithm [Processing] Hint: typetraits [Processing] CC: inputtest CC: stdlib_system CC: stdlib_strutils CC: stdlib_typetraits CC: stdlib_parseutils CC: stdlib_math CC: stdlib_algorithm Hint: [Link] Hint: operation successful (14862 lines compiled; 0.920 sec total; 17.938MiB peakmem; Release Build) [SuccessX] [jzakiya@jabari-pc nim]$ ./inputtest.nim bash: ./inputtest.nim: Permission denied [jzakiya@jabari-pc nim]$
Re: Inputing numbers
These don't work. When the program displays Enter number value: it should stay there until I type a number and hit and then proceed. For both cases shown the program just falls through. [jzakiya@jabari-pc nim]$ ./myprogram Enter number value: Error: unhandled exception: Unknown IO Error [IOError] Essentially, I want to do the equivalent C++ code below to enter nunbers. cout << "Enter number value: "; uint64 val; cin >> val;
