xbtm 0.1.0

XbTm (X-base Target Mapping) is a tool and DSL for generating canonical, entropy-efficient mappings from an x-way random source to an m-way target choice.

xbtm is a DSL for deterministically exploring and visualizing ways to emulate a uniform random generator with target outcomes using one with base outcomes.

DSL format

A complete program combines a header and a body with a colon.

X{base}T{target}:{body}

base and target are natural numbers. When target is at least 2, base must also be at least 2. When target is 1, base may be 1 because there is no outcome to choose between.

Every body starts at the ordinary state 1.

X2T5:1>2>4>8=5|3>6=5|(1)

States and termination

• n: An ordinary, newly visited state n, written as a natural number.
• (n): A reference state that returns to the previously visited state n. A reference state terminates the body.
• !: A termination marker indicating that the current ordinary state exactly equals target. The implementation represents it as an operator token for convenience.

Thus, a body starts at an ordinary state, repeats transitions, and ends with either a reference state or !.

Transitions

There are two kinds of transition.

Expand: >

old_state>next_state

expand multiplies the current state by base.

next_state = old_state * base

Split: =

old_state=pxq|r
old_state=p|r        # when q == 1

split divides the current state using target.

p = target
q = old_state // target
r = old_state % target
old_state = p * q + r

Here, p and q describe the split, and r is the next state. When q is 1, x1 is omitted. If the next state r was already visited, it is written as (r) and the body ends.

When the split has no remainder, it ends with |! instead of creating state 0.

old_state=pxq|!

For the full DSL rules, see the DSL specification.

Installation

pip install xbtm

Python usage

from xbtm import Program, generate

program = generate(2, 5)

print(program.text)
print(program.get_trials())

same_program = Program.parse("X2T5:1>2>4>8=5|3>6=5|(1)")

Examples

X2T8:1>2>4>8!
X7T8:1>7>49=8x6|(1)
X1T1:1!
X4T2:1>4=2x2|!