`bit.mul`¶

dst[:n] *= src[:n]
b is the number of 1-bits in src.
@NOTE: this implementation works with both signed and unsigned numbers.
@NOTE: this is faster, yet WASTEFUL in space, compared to the mul_loop macro.
@NOTE: safe when dst and src are the same address (squaring: dst *= dst), unlike mul_loop.
@NOTE: For a faster multiplication see hex.mul (requires hex.init).

Signature¶

def mul n, dst, src @ shifted_src, res, end { ... }

Defined in bit/mul.fj — lines 59–72 (view on GitHub).

Complexity¶

Time: n*b(8@+14) if b==n/2: n^2(4@+7)
Space: n^2(8@+14)

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

Source¶

Click to view the macro body

def mul n, dst, src @ shifted_src, res, end {
    .zero n, res
    .zero n, shifted_src
    .mov n, shifted_src+dw*n, src
    rep(n, i) .mul.mul_add_if n, dst+i*dw, res, shifted_src+(n-i)*dw
    .mov n, dst, res
    ;end

  shifted_src:
    .vec 2*n
  res:
    .vec n
  end:
}

Depends on¶

← Previous: bit.mul_loop Next: bit.mul.mul_add_if →