bit.idiv_loop

Compact signed integer division (slower than bit.idiv, but uses much less program space): q = a/b, r = a%b with sign(r)==sign(a). Jumps to end if b==0.

Signature

def idiv_loop n, a, b, q, r @ negative_a, negative_b, one_negative, neg_b_1, do_div, neg_b_2, neg_ans, end { ... }

Defined in bit/div.fj — lines 160–193 (view on GitHub).

Complexity

• Time: n^2(18@+18)

• Space: n(37@+58)

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

Source

Click to view the macro body

def idiv_loop n, a, b, q, r @ negative_a, negative_b, one_negative, neg_b_1, do_div, neg_b_2, neg_ans, end {
    .mov negative_a, a+dw*(n-1)
    .mov negative_b, b+dw*(n-1)
    .zero one_negative

    .if0 negative_a, neg_b_1
    .not one_negative
    .neg n, a
  neg_b_1:
    .if0 negative_b, do_div
    .not one_negative
    .neg n, b
  do_div:
    .div_loop n, a, b, q, r

    .if0 negative_a, neg_b_2
    .neg n, a
    .neg n, r
  neg_b_2:
    .if0 negative_b, neg_ans
    .neg n, b
  neg_ans:
    .if0 one_negative, end
    .neg n, q
    ;end

  negative_a:
    .bit
  negative_b:
    .bit
  one_negative:
    .bit
  end:
}

Depends on

• bit.bit/0

• bit.div_loop

• bit.if0/2

• bit.mov/2

• bit.neg

• bit.not/1

• bit.zero/1

---

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