bit.div_loop

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

Signature

def div_loop n, a, b, q, r @ loop, do_sub, loop_end, after_loop, A, Q, R, i, end { ... }

Defined in bit/div.fj — lines 207–243 (view on GitHub).

Complexity

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

  • Space: n(25@+22)

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

Source

Click to view the macro body

def div_loop n, a, b, q, r @ loop, do_sub, loop_end, after_loop, A, Q, R, i, end {
    .if0 n, b, end
    .zero n, R
    .zero n, Q
    .mov n, A, a
    .zero n, i
    .not i+(n-1)*dw

  loop:
    .if0 n, i, after_loop                //Comp: n(@+2)
    .shl n, R                            //Comp: n(2@-1)
    .xor R, A+(n-1)*dw
    .cmp n, R, b, loop_end, do_sub, do_sub   //Comp: n(2@+4)  (Space=n(3@+6))
  do_sub:
    .sub n, R, b                         //Comp: n(8@+16)
    .xor n, Q, i                         //Comp: n(@-1)
  loop_end:
    .shr n, i                            //Comp: n(2@-1)
    .shl n, A                            //Comp: n(2@-1)
    ;loop

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

  A:
    .vec n
  R:
    .vec n
  Q:
    .vec n
  i:
    .vec n

  end:
}

Depends on

Used by

Example uses

← Previous: bit.idiv_loop