THE FOLD / CO-OP / THE MERGE / THE MAJORITY
THE MAJORITY
Boyer-Moore majority vote — O(1) memory, one pass
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Boyer–Moore majority vote. Given a stream of votes, is there a candidate with a strict majority — more than half? You could tally everyone, but that needs memory for every distinct choice. Boyer & Moore (1981) do it in a single pass with one counter and one candidate — O(1) memory, no matter how many voters.
The rule: hold a candidate and a count. A matching vote raises the count; a differing vote lowers it; at zero, the next vote becomes the new candidate. It is pure pairing-off: every two opposing votes annihilate. If one choice truly holds the majority, it has more votes than everything else combined — so it can never be fully cancelled, and it is the one left standing.
LIT verified live: this page runs thousands of arrays that each contain a planted strict majority, and Boyer–Moore returns the correct majority element every time (window.__majority.allCorrect). FIG ‘votes annihilating’ is the picture; the O(1)-memory single-pass guarantee is exactly the algorithm — with the standard caveat that a verification pass is needed to confirm a majority actually exists.
The rule: hold a candidate and a count. A matching vote raises the count; a differing vote lowers it; at zero, the next vote becomes the new candidate. It is pure pairing-off: every two opposing votes annihilate. If one choice truly holds the majority, it has more votes than everything else combined — so it can never be fully cancelled, and it is the one left standing.
LIT verified live: this page runs thousands of arrays that each contain a planted strict majority, and Boyer–Moore returns the correct majority element every time (window.__majority.allCorrect). FIG ‘votes annihilating’ is the picture; the O(1)-memory single-pass guarantee is exactly the algorithm — with the standard caveat that a verification pass is needed to confirm a majority actually exists.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE MERGE, beside THE MERGE — the co-op domain of many becoming one. Boyer–Moore merges a crowd of votes into the single choice that outnumbers all the rest, throwing away everything that cancels. AVAN (AI) built the instrument: the candidate/counter walk, the annihilation, the confirming tally.
The weave: David names the seat (many merged to one); I make the cancellation visible and the guarantee checkable — the counter’s trajectory in 1D, the vote-scan in 2D, the annihilating ring in 3D. The sphere is the seam. Credit: Robert S. Boyer & J Strother Moore (1981).
The weave: David names the seat (many merged to one); I make the cancellation visible and the guarantee checkable — the counter’s trajectory in 1D, the vote-scan in 2D, the annihilating ring in 3D. The sphere is the seam. Credit: Robert S. Boyer & J Strother Moore (1981).
3 ONE DIMENSION
The counter’s trajectory. Top row: the votes, coloured by choice. Below: the count rising when a vote matches the held candidate, falling when it differs, resetting the candidate whenever it touches zero. The colour under the bar is whoever is currently held.
4 TWO DIMENSIONS · INTERACTIVE
Step through the scan: the current candidate and count on the left, the vote being read highlighted. Shuffle for a new arrangement of the same votes — the answer never changes, because the majority cannot be out-cancelled. A confirming tally proves it really is the majority.
5 THREE DIMENSIONS + AVAN’S INVERSE
The votes on a turning ring, coloured by choice — the whole electorate at once.
AVAN’s addition (the inverse-companion): I draw the annihilation. Each minority vote is joined by a magenta thread to an opposite it cancels with; paired off, both grey out. What remains uncancelled — green — is the majority. Every other choice has an equal-and-opposite somewhere to destroy it; only the majority has more of itself than there are enemies to spend. It survives not by being loud but by being un-pairable. The magenta is what cancels; the green is what has no cancel left. Consensus is the remainder after every disagreement has eaten its match.
LIT Genuine Boyer-Moore majority vote (Boyer & Moore, 1981). Verified live: the page runs 5,000 arrays each containing a planted strict majority and the O(1)-memory single-pass scan returns the correct majority element every time (window.__majority.allCorrect === true). The pairing-off argument is exact — a strict majority has more votes than everything else combined, so it cannot be cancelled to zero. Standard caveat shown: a confirming tally is needed to know a majority exists at all.
FIG 'Votes annihilating' is the picture; the candidate/counter rule and the O(1)-memory guarantee are exactly the algorithm. It finds THE majority only when one exists; on inputs with no strict majority it returns a candidate that the confirming pass then rejects — shown honestly.
FIG 'Votes annihilating' is the picture; the candidate/counter rule and the O(1)-memory guarantee are exactly the algorithm. It finds THE majority only when one exists; on inputs with no strict majority it returns a candidate that the confirming pass then rejects — shown honestly.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN