Skip to content

feat(Schonhage): batch native sparse queries with one shared preparation #2310

Open

Description

@edemaine

Next native batch milestone toward #1394, on top of #2214. Owner/session codex-root-3sum-20261102, branch work/three-sum-native-box-batch-20261102 in the preserved root-prime-selection worktree. Supplier branches remain untouched.

Implement a fixed standard WordRAM controller over an ordinary list of wanted output codes for one encoded tile. Construct geometry and retained values once, then reuse the actual sparse query kernel for each requested code. Preserve order and duplicates, charge actual query loads/result stores/loop control, and prove total cost preparation + sum of sparse query charges + linear batch overhead. Read source arrays, directory and retained values from real memory; derive all intermediate fits from original address/magnitude bounds. Include empty and repeated queries, signed cancellation, dirty scratch and frames, and an initialized same-state execution client.

This is an original native batching controller. Existing finite box partition, table construction and sparse kernel are reused unchanged. It does not yet construct the wanted list from matrix entries, schedule all tiles, prove Corollary26/ET savings or reach 1.9992; those remain #1394. No curated abstract change is expected. Require scoped strict checks, meaningful clients, independent correctness/API/resource review and full six-gate coverage before integration. AI assistance: OpenAI Codex.

Activity

  1. self-assigned this
    on Nov 2, 2026
  2. edemaine commented on Nov 2, 2026

    @edemaine
    CollaboratorAuthor

    Milestone published as #2312; awaiting hosted full validation, coordinator review and integration. The PR owns the final change, exact-source independent approval and validation evidence. It supplies actual initialized one-table batching, ordered signed answers, charged sparse/linear work and original-input width/prefix bounds. Empty, repeated, distinct-code, signed/cancellation and dirty-memory clients are checked.

    Owner/session codex-root-3sum-20261102 retains this handoff on branch work/three-sum-native-box-batch-20261102; this issue stays open until integration. Native wanted-list construction, all-tile shared geometry, improved complete thin-product/ET composition and the ordinary-3SUM 1.9992 endpoint remain #1394.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions