bit.div.div_step

One step of bit-level long division: R[0] ^= N; then if R[:n] >= D[:n], do R -= D and toggle Q[0]. The inner loop of bit.div / bit.idiv.

Signature

def div_step n, N, D, R, Q @ do_sub, end { ... }

Defined in bit/div.fj — lines 137–144 (view on GitHub).

Complexity

• Time: n(10@+20)

• Space: n(11@+22)

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

Source

Click to view the macro body

def div_step n, N, D, R, Q @ do_sub, end {
    ..xor R, N
    ..cmp n, R, D, end, do_sub, do_sub
  do_sub:
    ..sub n, R, D
    ..not Q
  end:
}

Depends on

• bit.cmp/6

• bit.not/1

• bit.sub

• bit.xor/2

---

← Previous: bit.div Next: bit.idiv_loop →