pervognsen

Von Neumann is credited with a method for generating fair coin flips from repeated tosses of a bent coin with unknown probability p via rejection sampling: In each round, toss the bent coin twice. Map (heads, tails) to heads and (tails, heads) to tails. For (heads, heads) and (tails, tails), repeat the process.

Since (heads, tails) has probability p*(1-p) and (tails, heads) has probability (1-p)*p, this generates the same distribution as a fair coin flip, but the process has a random running time.

1. What is the expected running time in number of rounds?
2. If you forcibly terminate the process after n rounds and return heads/tails arbitrarily, what is the bias?
3. If you're given a bound on p (say you know the bent coin is no more biased than p = 0.9) and a maximum tolerated bias for that generated output, what is the minimum value of n that reduces the bias below that level?

pervognsen

from random import *

def random_bit():
    return randint(0, 1)

def frac_bits(n, d):
    assert n < d
    r = n*2
    while True:
        if r >= d:

pervognsen

def sample(xs, k):
    n = 0
    ys = k * [None]
    for x in xs:
        n += 1
        i = randrange(n) 
        if i < k: ys[i] = x
    return ys

pervognsen

from random import *

# Classical reservoir sampling
def sample1(xs):
    n = 0
    y = None
    for x in xs:
        n += 1
        if randrange(n) == 0: y = x
    return y

pervognsen

def chain_decomposition(graph):
    up = {}
    down = {}
    order = {} # Assumes Python 3.6+ insertion-ordered dictionaries
    def dfs(v):
        order[v] = len(order)
        down[v] = []
        for w in graph[v]:
            if w in up:
                if order[w] < order[v] and up[v] != w:

pervognsen

https://www.cs.cmu.edu/~crary/819-f09/Landin66.pdf

Naur: Regarding indentation, in many ways I am in sympathy with this, but I believe that if it came about that this notation were used for very wide communication and also publication, you would regret it because of the kind of rearrangement of manu- scripts done in printing, for example. You very frequently run into the problem that you have a wide written line and then suddenly you go to the Communications of the ACM and radically, perhaps, you have to compress it. The printer will do this in any way he likes; he is used to having great freedom here and he will foui up your notation.

Landin: I have great experience with this. (Laughter) I think I am probably the only person who has run through three versions of the galley proofs for the Communications of the ACM. However, I think that next time I could do better, and I think it is worth looking into. At any rate, the principle that [have described here is a good deal better than some that one might think

pervognsen

pc = 0
mem = [0] * 2**16

def load(addr):
    if addr < io_base:
        return mem[addr]
    else:
        return io_read(addr)

def store(addr, data):

pervognsen

def funnel_shifter_unit(x, n, dir, shift, arith):
    s = rep(arith & x[-1], len(x)-1) 
    low = when(dir, x[:-1], when(shift, s, x[1:]))
    mid = when(dir, x[-1], x[0])
    high = when(dir, when(shift, s, x[:-1]), x[1:])
    return funnel_shifter(low @ mid @ high, when(dir, n, ~n))

pervognsen

# Everything marked up for tracing
def barrel_shifter(x, n, dir, shift, arith, left_rotator=left_rotator_radix4):
    x, n, dir, shift, arith = trace(x, base=2), trace(n), trace(dir), trace(shift), trace(arith)
    y = left_rotator(when(dir, x[-1] @ x[:-1], x), when(dir, ~n, n))
    mask = bits(~shift | when(dir, ~i >= n, i >= n) for i in range(len(y)))
    mask = trace(mask, 'mask', base=2)
    y = bits(when(mask[i], b, arith & x[-1]) for i, b in enumerate(y))
    y = trace(y, 'y', base=2)
    return y

pervognsen

def funnel_shifter(x, n):
    assert 2 * 2**len(n) - 1 == len(x)
    for i, b in enumerate(n):
        x = when(b, x[2**i:], x[:-2**i])
    return x

def funnel_right_shifter(x, n):
    return funnel_shifter(x @ bit[len(x)-1](0), n)

def funnel_arithmetic_right_shifter(x, n):