You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The current implementation of mul_wide uses schoolbook multiplication, which has complexity of the order of O(n*m) where n, m are the number of limbs in the operands.
Perhaps we should switch to an asymptotically better algorithm like karatsuba multiplication. If so I would be happy to work on this.
The text was updated successfully, but these errors were encountered:
Yes indeed, it's listed as a TODO and we'd be happy to switch to Karatsuba (see also #1).
There are a few other algorithms I've seen that also may be potentially faster than Karatsuba, although I don't have references to them offhand and Karatsuba is a perfectly reasonable starting place.
The current implementation of mul_wide uses schoolbook multiplication, which has complexity of the order of O(n*m) where n, m are the number of limbs in the operands.
Perhaps we should switch to an asymptotically better algorithm like karatsuba multiplication. If so I would be happy to work on this.
The text was updated successfully, but these errors were encountered: