2

There is a version of Strassen's algorithm for integer multiplication that uses a three-way split (division of the n-bit number into 3 parts of n/3 bits) and takes O(n^1.46).

My question is why is this method not generally preferred to the usual one with 2 way split that uses O(n^1.59)? Any ideas or links that can help me understand? (I looked it up online but I couldn't find anything)

Diana
  • 1,417
  • 5
  • 25
  • 48
  • 1
    Strassen's multiplication is for matrces did you mean `Schönhage–Strassen algorithm` ? or modification of `Karatsuba` instead? see this: http://stackoverflow.com/q/18465326/2521214 the last edit5 contains most recent measurements and also the `n` tresholds for each method of multiplication/squaring so you see what did Riko meant by `n` will not be big enough in practical usage ... (unless you are computing some cipher or math proof or up to date PI number) – Spektre Apr 23 '15 at 06:25

1 Answers1

2

That is because in practise the second one will be slower. O notation doesn't always correspond with real running speed.

Example: 

f(n) = 1000*n
g(n) = n*lg(n)

O(f(n)) is better than O(g(n)), making f(n) "faster", while in practise n will never be large enough for us to prefer f(n).

Neithrik
  • 2,002
  • 2
  • 20
  • 33