# DMSD Horizon Edition v0.6
## Cross-Algorithm Competition and Crossover Policy

**日期：** 2026-09-30  
**狀態：** COMPLETE  
**環境：** 與 v0.5 相同的 calibration runtime  
**目標：** 對同一 Task Family 放入多個實作，建立 measured winner regions、crossover、memory Pareto 與 algorithm-selection policy。

---

# 1. 從單一 Horizon 變成 Algorithm Competition

v0.5 已經有：

\[
T_{Q,A,E}(n).
\]

v0.6 不再只問：

> 演算法 \(A\) 能算到多遠？

而問：

\[
\boxed{
A^*(n,E,B)
=
\arg\min_A
T_{Q,A,E}(n)
}
\]

subject to：

\[
\boxed{
\text{resource admission}.
}
\]

也就是：

> 在這個 size、這個 runtime、這個 memory / implementation 條件下，到底該用哪個 algorithm？

---

# 2. Competition 不能只看 Big-O

兩個 algorithms 即使：

\[
O(n)
\]

相同，

也可能因：

- interpreter overhead；
- vectorization；
- memory layout；
- native runtime；
- startup cost；

產生 crossover。

反過來：

\[
O(n^2)
\]

與：

\[
O(n^{1.6})
\]

的 theoretical crossover，
也不代表 implementation crossover 在相同位置。

所以 v0.6 只把：

\[
\boxed{
\text{measured crossover}
}
\]

和：

\[
\boxed{
\text{structural crossover}
}
\]

分開保存。

---

# 3. Competition A — Exact Prime Count by Sieve

同一 task：

\[
\pi(N)
\]

使用三個 exact implementations：

```text
full_bytearray
odd_only_bytearray
segmented_64k
```

全部輸出完全一致。

---

# 4. Sieve Correctness

測量：

\[
N=
10^5,
3\times10^5,
10^6,
3\times10^6,
10^7.
\]

三個 algorithms 每個 \(N\)：

```text
prime count identical
```

並確認：

\[
\boxed{
\pi(10^6)=78,498.
}
\]

上一輪 benchmark harness 還曾抓到 odd-only 偶數上界多 materialize \(N+1\) 的 bug，
因此 v0.6 把 cross-algorithm semantic agreement 正式列為必備 gate。

---

# 5. Sieve Time Winner

在全部 measured \(N\)：

\[
\boxed{
\texttt{odd\_only\_bytearray}
}
\]

都是最快。

例如：

## \(N=10^7\)

full：

\[
0.06749\text{ s}
\]

odd-only：

\[
\boxed{0.02694\text{ s}}
\]

segmented：

\[
0.08512\text{ s}.
\]

所以 measured time objective 下：

\[
\boxed{
A^*=\text{odd-only}.
}
\]

---

# 6. 但 Segmented 仍然不是輸家

因為 memory 完全不同。

## \(N=10^7\)

full primary array：

\[
\sim10\text{ MB}
\]

odd-only：

\[
\sim5\text{ MB}
\]

segmented 64K：

\[
\boxed{
\sim69\text{ KB}
}
\]

級 primary working storage，
另加 base primes 到：

\[
\sqrt N.
\]

因此從 \(N\ge3\times10^5\) 開始，
measured time-memory Pareto 前沿通常同時保留：

```text
odd_only_bytearray
segmented_64k
```

一個偏 time，
一個偏 memory。

---

# 7. Full Bytearray 被支配

在本 measured range：

```text
full_bytearray
```

相對 odd-only：

- 更慢；
- primary array 約兩倍大。

所以：

\[
\boxed{
\texttt{full\_bytearray}
}
\]

在 registered time-memory objectives 下被 odd-only 支配。

它仍可以保留為：

```text
simple reference implementation
```

但不應被 policy selector 選成 Pareto winner。

---

# 8. Sieve Policy

因此不是：

> segmented 一定比較好。

而是：

```text
if odd-only resident state fits memory:
    choose odd-only for time
else:
    choose segmented for memory / streaming
```

這就是：

\[
\boxed{
\text{resource-conditioned algorithm selection}.
}
\]

---

# 9. Competition B — Dense GEMM

同一 task：

\[
C=AB.
\]

比較：

```text
python_naive
numpy_openblas
```

測量：

\[
n=2\rightarrow48.
\]

---

# 10. GEMM 沒有 Measured Crossover

即使：

\[
n=2,
\]

NumPy/OpenBLAS median：

\[
0.986\ \mu s
\]

Python naive：

\[
1.684\ \mu s.
\]

之後差距快速擴大。

例如：

\[
n=48
\]

NumPy：

\[
5.53\ \mu s
\]

Python：

\[
5.26\text{ ms}.
\]

約：

\[
\boxed{
950\times
}
\]

差距。

所以本 runtime 的 measured region：

\[
\boxed{
A^*_{\rm GEMM}
=
\text{NumPy/OpenBLAS}
}
\]

從最小測量點就成立。

---

# 11. 「沒有 Crossover」本身也是結果

Cross-algorithm system 不應強迫每對 algorithms 都產生 crossover。

合法結果包括：

```text
A dominates measured range
B dominates measured range
measured crossover
memory-conditioned split
no decision outside calibration range
```

所以：

\[
\boxed{
\text{No crossover observed}
}
\]

本身就是可登記 state。

---

# 12. Competition C — Exact Big Integer Multiplication

這次定義相同 semantic task：

```text
15-bit limb arrays
→ exact product limb arrays
```

比較：

```text
schoolbook_limbs
karatsuba_limbs
cpython_native_bridge
```

native bridge：

```text
limbs → Python int → built-in multiply → limbs
```

所以它甚至包含 conversion cost。

---

# 13. Native Runtime 全區間領先

測量：

\[
2\rightarrow512
\]

limbs，

約：

\[
30
\rightarrow7680
\]

input bits。

CPython native bridge 在每個 measured point 都最快。

例如：

## 512 limbs

schoolbook：

\[
20.13\text{ ms}
\]

Karatsuba：

\[
9.46\text{ ms}
\]

CPython native bridge：

\[
\boxed{
1.92\text{ ms}
}
\]

即使算入 representation conversion，
native runtime 仍大幅領先。

---

# 14. 自製演算法族內部仍有 Crossover

忽略 native runtime，
只比較：

```text
schoolbook
karatsuba
```

小尺寸因 Python overhead 會多次交錯。

所以 v0.6 不把第一個 noisy sign-change 當 crossover。

改用：

> **Stable Crossover**

定義：

> 從某 measured size 起，Karatsuba 至少快 10%，且所有更大 measured points 都維持。

得到：

\[
\boxed{
256\text{ limbs}
}
\]

約：

\[
\boxed{
3840\text{ bits}.
}
\]

---

# 15. Stable Crossover 比 First Crossing 更實用

raw measured ratio 因 tiny timings / recursion overhead，
在小尺寸會交錯。

因此：

\[
\boxed{
\text{first sign change}
\neq
\text{stable regime transition}.
}
\]

這條規則很適合未來：

- GPU kernel；
- distributed algorithm；
- compression；
- proof system；

的 crossover policy。

---

# 16. Competition D — Certificate Verification

同一 certificate：

\[
(a_i,b_i,c_i)
\]

驗：

\[
a_ib_i\bmod(2^{31}-1)=c_i.
\]

比較：

```text
Python scalar loop
NumPy vectorized batch
```

---

# 17. 真正的 Scalar → Vector Crossover

### 10 relations

scalar：

\[
0.592\ \mu s
\]

vectorized：

\[
3.451\ \mu s.
\]

scalar 約：

\[
5.8\times
\]

更快。

---

## 30 relations

scalar：

\[
1.283\ \mu s
\]

vectorized：

\[
3.520\ \mu s.
\]

scalar 仍快。

---

## 100 relations

scalar：

\[
3.843\ \mu s
\]

vectorized：

\[
3.674\ \mu s.
\]

vectorized 首次略勝。

用相鄰 measured log-ratio 插值：

\[
\boxed{
C^*\approx95\text{ relations}.
}
\]

---

# 18. 大 Certificate 的 Vectorization Gain

### 300,000 relations

scalar：

\[
13.40\text{ ms}
\]

vectorized：

\[
1.489\text{ ms}.
\]

speedup：

\[
\boxed{
\sim9.0\times.
}
\]

所以 selector 可以登記：

```text
C < ~95:
    scalar
C >= ~95:
    vectorized
```

但這個 95 是：

\[
\boxed{
\text{this-runtime measured crossover}.
}
\]

不是 universal NumPy law。

---

# 19. Crossover Object

v0.6 正式定義：

\[
\boxed{
\chi(A,B,Q,E)
}
\]

包含：

```text
task
environment
algorithms
measured bracket
interpolation method
estimated crossover
stability rule
confidence / trust state
```

因此不能只存一個：

```text
x = 95
```

卻忘記它屬於什麼 runtime。

---

# 20. Winner Region

Algorithm selector 不再是一個單一名字。

而是：

\[
\boxed{
\Pi_Q(x,R,E)
\rightarrow A.
}
\]

其中：

- \(x\)：problem size；
- \(R\)：resource state；
- \(E\)：environment。

例如 sieve：

\[
\Pi_{\rm sieve}
=
\begin{cases}
\text{odd-only}, & \text{memory admitted}\\
\text{segmented}, & \text{streaming / memory constrained}
\end{cases}
\]

---

# 21. Time Winner 不等於 Global Winner

這輪最清楚的例子就是 sieve。

如果只看：

\[
T_A(N),
\]

odd-only 贏。

如果加入：

\[
M_A(N),
\]

segmented 回到 Pareto frontier。

所以一般 algorithm selection 必須是：

\[
\boxed{
\min_A
(
T,
M,
IO,
E,
\text{availability}
)
}
\]

的 task-specific policy。

---

# 22. Resource Gate 可以創造新的 Crossover

目前 runtime memory cap 約：

\[
4\text{ GiB}.
\]

只看 primary bytearray：

full rough ceiling：

\[
N\lesssim4.29\times10^9.
\]

odd-only rough ceiling：

\[
N\lesssim8.59\times10^9.
\]

這還沒扣：

- Python/runtime；
- base primes；
- OS；
- allocator；

所以只是 rough theoretical gate。

但 segmented primary state 不隨 \(N\) 線性長大。

因此即使 time curve 沒交叉：

\[
\boxed{
\text{memory admission}
}
\]

也會迫使 algorithm crossover。

---

# 23. Cross-Algorithm Competition States

v0.6 暫定：

```text
MEASURED_WINNER
MEASURED_CROSSOVER
STABLE_CROSSOVER
PARETO_SPLIT
DOMINATED
NO_CROSSOVER_OBSERVED
OUTSIDE_CALIBRATION
RESOURCE_FORCED_SWITCH
```

比一句：

> A 比 B 快

完整很多。

---

# 24. Algorithm Selector

本包產生：

```text
algorithm_selector.json
```

它不是 production optimizer，
而是 v0.6 的 reference selector registry。

目前已能表達：

- size threshold；
- memory condition；
- implementation availability；
- measured dominance；
- stable crossover；
- Pareto choice。

---

# 25. Cross-Algorithm Validation

本輪 correctness / replay gates：

- 三種 sieve 每個 measured \(N\) 結果一致；
- \(\pi(10^6)=78,498\)；
- bigint 三 competitors semantic outputs 在 benchmark 階段逐點一致；
- certificate positive / corrupted-negative 兩 implementations 都一致；
- winner table 逐點 replay min-time；
- certificate crossover estimate 落在 measured 30–100 bracket。

全部：

```text
PASS
```

---

# 26. 這一輪最重要的四個結果

### Prime Count

\[
\boxed{
\text{odd-only = measured time winner}
}
\]

\[
\boxed{
\text{segmented = memory Pareto winner}
}
\]

### GEMM

\[
\boxed{
\text{OpenBLAS dominates measured range}
}
\]

### Bigint

\[
\boxed{
\text{CPython native dominates measured range}
}
\]

custom family：

\[
\boxed{
\text{Karatsuba stable crossover}\approx3840\text{ bits}
}
\]

### Certificate

\[
\boxed{
\text{scalar→vector crossover}\approx95\text{ relations}.
}
\]

---

# 27. Horizon Edition 現在可以自動問：

對 scale \(x\)：

1. 這是什麼 task？
2. 有哪些 algorithm plugins？
3. 哪些在 calibration range？
4. 哪些通過 resource gate？
5. time winner 是誰？
6. memory winner 是誰？
7. 是否存在 measured crossover？
8. 是否只能 extrapolate？
9. 是否要切到另一個 algorithm family？

這就是：

\[
\boxed{
\text{Algorithm-Aware Horizon}.
}
\]

---

# 28. 下一步

最自然是：

# Horizon Edition v0.7 — Algorithm Portfolio / Auto-Router

目前 selector 還是 deterministic rules。

下一輪可以讓 runtime 對：

\[
(Q,x,R,E)
\]

自動：

1. 過濾 inadmissible algorithms；
2. 讀 calibration surface；
3. 找 Pareto set；
4. 根據 objective 選：
   - fastest；
   - lowest memory；
   - lowest energy；
   - highest confidence；
5. 若接近 crossover：
   - 執行 local microbenchmark；
   - 更新 calibration；
   - 再決策。

也就是：

\[
\boxed{
\text{Static Crossover Map}
\rightarrow
\text{Adaptive Algorithm Router}.
}
\]

---

# 29. 結論

v0.6 把 Horizon Edition 從：

\[
\text{Algorithm Plugin}
\]

推到：

\[
\boxed{
\text{Algorithm Competition}.
}
\]

因此真正的 compute horizon 不再由一條 algorithm curve 決定，

而是：

\[
\boxed{
H_Q
=
\sup_x
\left[
\exists A:
A\text{ admitted and affordable at }x
\right].
}
\]

也就是：

> **隨尺度變大，runtime 可以換演算法。**

---

```text
DMSD Horizon Edition v0.6: COMPLETE
Tasks competed: 4
Measured crossover: ENABLED
Pareto time-memory split: ENABLED
Algorithm selector registry: GENERATED

Next:
v0.7 — Algorithm Portfolio / Auto-Router
```