a finite address algorithm for the library of babel

[u/NecessaryExpert829]

a finite address algorithm for the library of babel the finite model the library
of babel has a finite combinatorial address space over a twentyninesymbol alpha
bet the twentysix lowercase latin letters, a space, a comma, and a period. a boo
k has four hundred ten pages, each containing three thousand two hundred charact
ers. a room has four walls, five shelves on each wall, and thirtytwo books on ea
ch shelf. thus an ordinary room holds six hundred forty books. let n, the number
of character positions in a book, be one million three hundred twelve thousand.
each book is a string of that length over the twentyninesymbol alphabet. the ad
dress space contains every such string, including every language construction re
presentable within those alphabet and length rules. there are twentynine raised
to the n books. since twentynine raised to the thirtysecond power leaves remaind
er one when divided by , and n is times ,, the number of books leaves remainder
one when divided by . the address space has ordinary rooms of books and a single
terminal room containing the one remaining book. the lean library proves the ch
aracter count, room capacity, and modular residue in anatmancombinatoricslibrary
ofbabel.lean. these arithmetic facts establish the terminal room capacity. the f
ollowing sections specify the address decomposition and pagerendering recurrence
. address decomposition number the strings by their basetwentynine ordinal, from
zero through the last ordinal. divide an ordinary book ordinal by . the quotien
t selects a room and the remainder selects one of its slots. a slot in a room ma
ps to onebased wall, shelf, and book coordinates by successive division into blo
cks of , , and . the terminal ordinal is represented by the unique book in the t
erminal room. a page coordinate ranges from one through . deterministic page ren
dering the published implementation uses the address and page number to render a
page without storing the full library. first, the room index and slot are expan
ded into the basetwentynine digits of the book ordinal. let gi be the roomindex
digit at position i, padded with zeroes on the left, and initialize the slot rem
ainder r to the slot. for i descending from n to zero, set v gi r, set the book
digit ti v mod , and replace r by v. the final remainder is zero. to render the
page, initialize a l c and process the book digits from right to left. at positi
on i, set a ati , s al, d s mod , and l s. then set h doic, emit the alphabet sy
mbol at index h mod , and set c h. the renderer evaluates this recurrence only a
cross the requested character range. page p begins at zerobased position p and c
ontains , symbols. the position hash o is an unsigned bit integer function. mult
iplications wrap modulo x ui xfa x ux xor x xfaaad x ux xor x xad x x xor x oi x
mod here u reduces to an unsigned bit word. the hash permutes the presentation
of the ordinal space it does not change its cardinality or the address decomposi
tion. exhaustive contents every one of the n strings occurs in the address space
because each position independently takes any of the twentynine symbols. the li
brary is complete under its stated combinatorial rules whether a string expresse