bit.mul_loop¶
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 slower, yet it saves space, compared to the mul macro.
@Assumes: dst and src are NOT the same address (aliasing makes this macro loop forever).
For squaring (dst==src) use the mul macro, which handles aliasing safely.
@NOTE: For a faster multiplication see hex.mul (requires hex.init).
Signature¶
def mul_loop n, dst, src @ start, after_add, src_copy, res, end { ... }
Defined in bit/mul.fj — lines 27–48 (view on GitHub).
Complexity¶
Time:
n^2(6@+2) + n*b(8@+14) if b==n/2: n^2(10@+9)Space:
n(21@+11)
See the complexity glossary for what @, w, dw, dbit, n mean.
Source¶
Click to view the macro body
def mul_loop n, dst, src @ start, after_add, src_copy, res, end {
.zero n, res
.mov n, src_copy, src
start:
.if0 src, after_add
.add n, res, dst //Comp: n(8@+14)
after_add:
.shl n, dst //Comp: n(2@-1)
.shr n, src //Comp: n(2@-1)
.if0 n, dst, end //Comp: n(@+2)
.if0 n, src, end //Comp: n(@+2)
;start
src_copy:
.vec n
res:
.vec n
end:
.mov n, src, src_copy
.mov n, dst, res
}