Craig Request

[mpharrigan]

Craig says [sent via chat; preserving here]:

This is an example of something I wish didn't suck to write. Q# would hide all the structure behind long method names, but python can't do things like infer the uncomputation and talk about information not leaking.

def compute_mod_inv(R_0: int, R_1: int, n: int) -> int:
    f: MutableIntSlice = alloc_quint(len=n + 1, val=bitReverse(R_0, n + 1))
    g: MutableIntSlice = alloc_quint(len=n + 1, val=bitReverse(R_1, n))
    v: MutableIntSlice = alloc_quint(len=n + 1, val=0)
    r: MutableIntSlice = alloc_quint(len=n + 1, val=1)
    delta: MutableIntSlice = alloc_quint(len=math.floor(math.log2(n) + 2), val=1)
    mask: MutableIntSlice = alloc_quint(len=n - 1, val=-1)

    for _ in range(2*n - 1):
        v <<= 1
        if delta.signed_val() > 0 and g[0]:
            v, r = r, v
        if v[0]:
            f, g = g, f

        g[1:] ^= f[1:] & mask & broadcast(g[0])
        mask.inplace_right_shift(
            amount=delta.signed_val() >= 0 and (delta == 0 or g[0] == 0),
            expected_bottom_bit=True,
        )

        delta ^= broadcast(v[0])
        delta += v[0] + 1

        r ^= v & broadcast(g[0])
        g.inplace_left_rotate()

    assert mask == 0
    result = bitReverse(int(v), n)

    for _ in range(2*n - 1)[::-1]:
        g.inplace_right_rotate()
        r ^= v & broadcast(g[0])

        delta -= v[0] + 1
        delta ^= broadcast(v[0])

        mask.inplace_left_shift(
            amount=delta.signed_val() >= 0 and (delta == 0 or g[0] == 0),
            expected_top_bit=False,
            new_bottom_bit=True,
        )

        g[1:] ^= f[1:] & mask & broadcast(g[0])

        if v[0]:
            f, g = g, f
        if delta.signed_val() > 0 and g[0]:
            v, r = r, v

        v >>= 1

    assert f == bitReverse(R_0, n + 1)
    assert g == bitReverse(R_1, n)
    assert v == 0
    assert r == 1
    assert mask.signed_val() == -1
    assert delta == 1

    return result

"I wrote that as part of trying to verify https://arxiv.org/abs/2303.06570"

[mpharrigan]

More from craig: https://gist.github.com/Strilanc/d08dc245a9661fb9f61359b5f756d9e0

[mpharrigan]

https://arxiv.org/abs/1706.07884 has a lovely resource flowchart

[tanujkhattar]

Yup, and AFAIR from my discussion with Craig , there was no particular automated tool used to construct this figure (except specifying the nodes and edges manually).

Would be nice to create a flowchart like this automatically using Bloqs.