3 ms·

What do you mean by an O(log(n)) algorithm for multiplication ? The naive approach takes O(n^2) and O(nlog(n)) is extremely state of the art and is unlikely to

• Jtsummers 5y ago
  See page 17 of [0]. Here the big-O is about the value of one of the parameters to multiply(n,m) (say the first), not the number of bits in the values. In the naive multiplication algorithm you have repeated addition which gives you a O(n) algorithm, but you can also do the half & double approach (similar to fast exponentiation) which gives you a O(log n) algorithm. [0] https://www.fm2gp.com/slides/FM2GP_Course_Slides_Pt1.pdf https://www.fm2gp.com/slides/FM2GP_Course_Slides_Pt1.pdf