bit.idiv

Signed integer division: q = a/b, r = a%b with sign(r)==sign(a). Jumps to end if b==0. q, a, b, r are bit[:n]. Wasteful in space — prefer hex.idiv for serious work.

Signature

def idiv 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 64–97 (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 idiv 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 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

• bit.if0/2

• bit.mov/2

• bit.neg

• bit.not/1

• bit.zero/1

---

← Previous: bit.div10.cmp_sub_10 Next: bit.div →