bit.div

Unsigned integer division: q = a/b, r = a%b. Jumps to end if b==0. q, a, b, r are bit[:n]. Wasteful in space — prefer hex.div for serious work.

Signature

def div n, a, b, q, r @ Q, R, end { ... }

Defined in bit/div.fj — lines 111–127 (view on GitHub).

Complexity

• Time: n^2(10@+20)

• Space: n^2(11@+22)

See the complexity glossary for what @, w, dw, dbit, n mean.

Source

Click to view the macro body

def div n, a, b, q, r @ Q, R, end {
    .if0 n, b, end
    .zero 2*n, R
    .zero   n, Q

    rep(n, i) .div.div_step n,  a+(n-1-i)*dw,  b,  R+(n-1-i)*dw,  Q+(n-1-i)*dw

    .mov n, r, R
    .mov n, q, Q
    ;end

  R:
    .vec 2*n
  Q:
    .vec n
  end:
}

Depends on

• bit.if0/3

• bit.mov/3

• bit.vec/1

• bit.zero/2

Used by

• bit.idiv

Example uses

• bit.idiv in bit/div.fj

---

← Previous: bit.idiv Next: bit.div.div_step →