hex.mul

  `for n==b/2: n^2(5.5@+20)`  

res[:n] = a[:n] * b[:n]

b is the minimum of #on-bits in a,b (b&lt;n/2 on average, e.g. b=7 for n=16).

Signature

def mul n, res, a, b @ a_less_1bits, b_less_1bits, loop, after_add, dst, src, a_1bits, b_1bits, end { ... }

Defined in hex/mul.fj — lines 53–87 (view on GitHub).

Complexity

• Time: n^2(3@+7) + n*b(5@+26)

• Space: n(21@+479)

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

Requires init

The following must be initialised before this macro is invoked:

• hex.add.init (or hex.init)

Source

Click to view the macro body

def mul n, res, a, b @ a_less_1bits, b_less_1bits, loop, after_add, dst, src, a_1bits, b_1bits, end {
    .zero n, dst
    .zero n, src
    .zero n, res

    // if a has less 1(on) bits - jump to a_less_1bits. else jump to b_less_1bits
    .count_bits n, a_1bits, a
    .count_bits n, b_1bits, b
    .cmp ((#(n*4))+3)/4, a, b, a_less_1bits, a_less_1bits, b_less_1bits

    a_less_1bits:
    .xor n, dst, b
    .xor n, src, a
    ;loop

    b_less_1bits:
    .xor n, dst, a
    .xor n, src, b


  loop:
    .if0 src, after_add
    .add_mul n, res, dst, src
  after_add:
    .shl_hex n, dst
    .shr_hex n, src
    .if  n, src, end, loop      // can be replaced with #n-sized index decrement and check.


  dst: hex.vec n
  src: hex.vec n
  a_1bits: hex.vec ((#(n*4))+3)/4
  b_1bits: hex.vec ((#(n*4))+3)/4
  end:
}

Depends on

• hex.add_mul/4

• hex.cmp/6

• hex.count_bits

• hex.if/4

• hex.if0/2

• hex.shl_hex/2

• hex.shr_hex/2

• hex.xor/3

• hex.zero/2

---

← Previous: hex.mul10 Next: hex.mul.clear_carry →