primegen/algorithm.html at main · SimiaCryptus/primegen · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
<!doctype html>
<html lang="en">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width,initial-scale=1" />
    <title>Orthogonal Stream Prime Generator — reference implementation</title>
    <link rel="stylesheet" href="./css/experiments-primegen-algorithm.css" />
  </head>
  <body>
    <header>
      <h1>
        The Orthogonal Stream Prime Generator
        <small>— executable reference for <code>algorithm.md</code></small>
      </h1>
      <p class="note" style="max-width: 960px">
        Every section below is a live implementation of a numbered claim in the specification: the
        wheel tables (§4.2), the ownership theorem (§2.1) and its multiplier wheel (§2.2–2.4),
        <b>Algorithm A</b> — exact one-touch orthogonal streams (§3), <b>Algorithm B</b> — wheeled
        streaming generator with O(1) state per prime (§4), the bucket-queue segmented layout
        (§5.1), a machine-checkable validation suite, and an empirical measurement of S(N) with a
        log–log fit of θ (§3.7, §9.1). Nothing is loaded from the network.
      </p>
      <div class="row">
        <button class="primary" id="runAll">▶ run everything</button>
        <span id="allStatus" class="dim"></span>
      </div>
    </header>

    <main>
      <!-- ============================================================= -->
      <section>
        <h2>1 · Wheel tables <span class="ref">§4.2 — spokes, step[], gte[]</span></h2>
        <p class="note">
          <code>next_coprime(x) = x + step[x mod W]</code> (strictly greater),
          <code>next_coprime_ge(x) = x + gte[x mod W]</code>. Both tables are built in one backward
          pass over [0,W). κ<sub>W</sub> = φ(W)/W is the candidate density.
        </p>
        <div class="row">
          <label>w (number of wheel primes)</label>
          <input type="number" id="wheelW" value="6" min="1" max="8" />
          <button id="btnWheel">build wheel</button>
        </div>
        <pre id="outWheel" class="dim">—</pre>
      </section>

      <!-- ============================================================= -->
      <section>
        <h2>
          2 · Ownership explorer
          <span class="ref">Thm 2.1, Cor 2.2, Lem 2.3, Cor 2.4, Prop 2.6</span>
        </h2>
        <p class="note">
          Θ<sub>p</sub> = p·A<sub>p</sub> with A<sub>p</sub> = { a ≥ p : gcd(a, P<sub>&lt;p</sub>) =
          1 } — the p-rough numbers, a <i>wheel</i>, not a list of primes. Below p² every multiplier
          is prime (Lemma 2.3); the first composite multiplier is exactly p². Try p = 11 for the
          <code>observation.md</code> counterexample 121 ∈ A<sub>11</sub>.
        </p>
        <div class="row">
          <label>prime p</label><input type="number" id="ownP" value="11" min="2" />
          <label>show multipliers up to</label
          ><input type="number" id="ownUpto" value="180" min="10" />
          <button id="btnOwn">inspect</button>
        </div>
        <pre id="outOwn" class="dim">—</pre>
      </section>

      <!-- ============================================================= -->
      <section>
        <h2>3 · Algorithm A — exact one-touch orthogonal generator <span class="ref">§3</span></h2>
        <p class="note">
          Stream tree Σ<sub>b</sub> = { b·q : q prime, q ≥ P(b) } (Thm 3.1) with lazy child creation
          via EMIT/SPAWN cursors (§3.2). No marking array, no divisibility, no √ — one multiply and
          one compare per step. The assertion <code>pops == composites</code> is the
          machine-checkable statement of exact orthogonality (Thm 3.2).
        </p>
        <div class="row">
          <label>N</label><input type="number" id="aLimit" value="200000" min="2" />
          <button id="btnA">run Algorithm A</button>
          <button id="btnTrace">trace N = 50 (§3.6)</button>
        </div>
        <div class="grid2">
          <pre id="outA" class="dim">—</pre>
          <pre id="outTrace" class="dim">—</pre>
        </div>
      </section>

      <!-- ============================================================= -->
      <section>
        <h2>
          4 · Algorithm B — wheeled streaming generator <span class="ref">§4 (recommended)</span>
        </h2>
        <p class="note">
          Exact multiplier set A<sub>p</sub> is relaxed to the tabulated Ã<sub>p</sub> = { a ≥ p :
          gcd(a,W)=1 }. Advancement is <code>a += step[a % W]; v = p*a</code> — genuinely O(1) time
          and O(1) state per prime — at the cost of ω<sub>&gt;p<sub>w</sub></sub
          >(m) touches per composite (§4.5). Measured pops are compared against both the exact
          factor-count and the κ<sub>W</sub>·N·(lnln√N − lnln p<sub>w</sub>) estimate.
        </p>
        <div class="row">
          <label>N</label><input type="number" id="bLimit" value="1000000" min="100" />
          <label>w</label><input type="number" id="bW" value="6" min="1" max="7" />
          <button id="btnB">run Algorithm B</button>
          <button id="btnBSweep">sweep w = 1…7</button>
        </div>
        <pre id="outB" class="dim">—</pre>
      </section>

      <!-- ============================================================= -->
      <section>
        <h2>5 · Engineering layer — bucket queue + segments <span class="ref">§5.1, §4.6</span></h2>
        <p class="note">
          Algorithm B with the log factor removed: streams are filed into per-segment buckets,
          drained into a Δ-byte mark array, and re-filed. Stream state at an arbitrary segment start
          X is recomputed in O(1) by a<sub>0</sub> = max(p, next_coprime_ge(⌈X/p⌉)) — the property
          that makes B segment-parallel and A not.
        </p>
        <div class="row">
          <label>N</label><input type="number" id="segLimit" value="10000000" min="1000" />
          <label>w</label><input type="number" id="segW" value="6" min="1" max="7" />
          <label>log₂Δ</label><input type="number" id="segD" value="18" min="10" max="22" />
          <button id="btnSeg">run bucketed B</button>
          <button id="btnCmp">compare vs Eratosthenes</button>
        </div>
        <pre id="outSeg" class="dim">—</pre>
      </section>

      <!-- ============================================================= -->
      <section>
        <h2>6 · Validation suite <span class="ref">every numbered claim</span></h2>
        <p class="note">
          Each line is an independent executable check of a theorem, lemma, corollary or correction
          from the specification.
        </p>
        <div class="row">
          <button class="primary" id="btnTests">run validation suite</button>
          <span id="testBadge"></span>
        </div>
        <pre id="outTests" class="dim">—</pre>
      </section>

      <!-- ============================================================= -->
      <section>
        <h2>
          7 · Measuring S(N) — the real cost of exact orthogonality
          <span class="ref">§3.7, §9.1</span>
        </h2>
        <p class="note">
          S(N) = #{ b ≥ 2 : b·P(b) ≤ N } is the live-stream count of Algorithm A. The heuristic says
          S(N) = N<sup>θ+o(1)</sup>, θ ≈ 0.75 — decisively worse than π(√N). Measure, then fit; do
          not trust the exponent.
        </p>
        <div class="row">
          <label>max N</label><input type="number" id="scaleMax" value="400000" min="10000" />
          <label>points</label><input type="number" id="scalePts" value="8" min="3" max="14" />
          <button id="btnScale">measure</button>
        </div>
        <pre id="outScale" class="dim">—</pre>
        <div id="chart"></div>
      </section>
    </main>

    <script src="./js/experiments-primegen-algorithm.js" type="module"></script>
  </body>
</html>