_primes_sieve.nx source
↩ module page · 75 lines · 2523 B
1// _primes_sieve.nx -- Sieve of Eratosthenes, NishiLang.
2//
3// Implements the standard "drag race" benchmark from
4// PlummersSoftwareLLC/Primes (Dave's Garage / Dave Plummer):
5// count primes <= 1,000,000.
6//
7// Per Dave's rules: report number of complete passes in a 5-second
8// window. We use a NORMAL byte sieve (1 byte per odd number) -- the
9// "PrimeSieve" base impl Dave compares against. Some entries
10// optimize with bit-packing + wheel factorization; we keep this
11// implementation algorithmically simple to match the reference.
12//
13// We don't have wall-clock in NishiLang, so this version runs a
14// SINGLE pass; the harness shell script wraps with time/loop logic
15// to report passes/sec.
16
17import "syscalls.nx"
18
19const SIEVE_SIZE: i64 = 1000000
20
21func run_single_pass() -> i64 {
22 // Allocate sieve: 1 byte per odd number from 3.
23 // Index i represents number (2*i + 3); index 0 = 3, 1 = 5, etc.
24 let half: i64 = SIEVE_SIZE / 2
25 let buf: *u8 = sys_mmap(half)
26 // Zero-init (sys_mmap on Linux returns zero pages but be explicit).
27 var i: i64 = 0
28 while i < half {
29 buf[i] = 0 as u8
30 i = i + 1
31 }
32 // Sieve odd numbers >= 3. sqrt(SIEVE_SIZE) ~ 1000.
33 var factor: i64 = 3
34 while factor * factor <= SIEVE_SIZE {
35 let factor_idx: i64 = (factor - 3) / 2
36 // Find next un-marked odd starting from factor.
37 var fi: i64 = factor_idx
38 var done: i64 = 0
39 while done == 0 {
40 if fi >= half { done = 1 }
41 if done == 0 {
42 if buf[fi] == (0 as u8) { done = 1 }
43 if done == 0 { fi = fi + 1 }
44 }
45 }
46 if fi >= half { return -1 } // sentinel
47 let cur_num: i64 = 2 * fi + 3
48 // Mark composites starting at cur_num*cur_num, step 2*cur_num.
49 var mult: i64 = cur_num * cur_num
50 while mult <= SIEVE_SIZE {
51 let idx: i64 = (mult - 3) / 2
52 buf[idx] = 1 as u8
53 mult = mult + 2 * cur_num
54 }
55 factor = cur_num + 2
56 }
57 // Count primes: 2 is prime (special-case), plus all unmarked odd numbers
58 var count: i64 = 1 // count the prime 2
59 var k: i64 = 0
60 while k < half {
61 if buf[k] == (0 as u8) {
62 let n: i64 = 2 * k + 3
63 if n <= SIEVE_SIZE { count = count + 1 }
64 }
65 k = k + 1
66 }
67 return count
68}
69
70func main() -> i64 {
71 let c: i64 = run_single_pass()
72 // Expected: 78498 primes <= 1,000,000.
73 if c != 78498 { return 2 }
74 return 0
75}