`hex.idiv`¶

Signed integer division with configurable remainder convention (rem_opt: 0 = sign(r)==sign(b), Python-style floor division; 1 = sign(r)==sign(a), C-style truncation; 2 = remainder always positive). Jumps to div0 if b==0. q, a are hex[:n]; r, b are hex[:nb].

Signature¶

def idiv n, nb, q, r, a, b, div0, rem_opt @ set_negative_a, test_b, set_negative_b, update_rem_opt_0, update_rem_opt_2, add_b, sub_b, negative_a, negative_b, one_negative, do_div, neg_b_2, neg_ans, end, fix_rem { ... }

Defined in hex/div.fj — lines 86–150 (view on GitHub).

Complexity¶

Time: n^2(2@+8) + n*nb(34@+92) so if nb==n: n^2(36@+100)
Space: n(8.5@+132) + nb(21.5@+309) so if nb==n: n(30@+441)

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

Requires init¶

The following must be initialised before this macro is invoked:

hex.sub.init & hex.cmp.init (or hex.init)

Source¶

Click to view the macro body

def idiv n, nb, q, r, a, b, div0, rem_opt\
        @ set_negative_a, test_b, set_negative_b, update_rem_opt_0, update_rem_opt_2, add_b, sub_b,\
        negative_a, negative_b, one_negative, do_div, neg_b_2, neg_ans, end, fix_rem {
    .if0 nb, b, div0
    stl.comp_if1 ((rem_opt < 0) | (rem_opt > 2)), div0

    bit.zero negative_a
    bit.zero negative_b
    bit.zero one_negative

    .sign n, a, set_negative_a, test_b
  set_negative_a:
    bit.not negative_a
    bit.not one_negative
    .neg n, a
  test_b:
    .sign nb, b, set_negative_b, do_div
  set_negative_b:
    bit.not negative_b
    bit.not one_negative
    .neg nb, b

  do_div:
    .div n, nb, q, r, a, b, div0

    bit.if0 negative_a, neg_b_2
    .neg n, a
    .neg nb, r
  neg_b_2:
    bit.if0 negative_b, neg_ans
    .neg nb, b
  neg_ans:
    bit.if0 one_negative, fix_rem
    .neg n, q

  fix_rem:
    stl.comp_if1 rem_opt == 0, update_rem_opt_0
    stl.comp_if1 rem_opt == 2, update_rem_opt_2
    ;end

  update_rem_opt_0:
    bit.if one_negative, end, add_b

  update_rem_opt_2:
    bit.if0 negative_a, end
    bit.if negative_b, add_b, sub_b

  add_b:
    hex.add nb, r, b
    hex.dec n, q
    ;end

  sub_b:
    hex.sub nb, r, b
    hex.inc n, q
    ;end

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

Depends on¶

← Previous: hex.div