Tiberius Posted April 25, 2012 Share Posted April 25, 2012 I was looking up the fastest multiplication algorithms on Wikipedia. Karatsuba showed up [O(N1.585)], Strassen showed up[O(N log N log log N)], all with respectable big O scores, but a friend recently told me of an algorithm that seems to work in linear time (wrt to the number of digits in the numbers). I can't seem to find it on Google, so I'll just describe it here with an example: Suppose you have two numbers 141 and 45 and we want to multiply them. We keep dividing the first number by 2 until it becomes 1 (integer division), and keep multiplying the 2nd number the same number of times. 141 45 70 90 35 180 17 360 8 720 4 1440 2 2880 1 5760 Now, we look at the LHS and add up all the terms that correspond to ODD terms on the left: 45+180+360+5760=6345 which is 141*45 Now as far as I could tell, there is a linear relationship between the number of iterations of division before you get down to 1 and the number of digits. (You end up adding 3 or 4 iterations per digit increase because multiplying by 10 is multiplying by 1010 in binary). The relationship is something like K=3.322N +0.5, where N is the number of digits and K is the number of iterations. ( I wasn't too sure of a mathematical approach to the relation between K and N, so I plotted K vs N for N=1 to 600 and found that a linear relationship existed) So in the worst case, for an N digit number, one has to do K multiplications by 2 and K divisions by 2. During the process, one has to do at max (if all LHS terms are odd) K additions as well. [Multiplying/Dividing a number by two is a constant time operation right ? Just a simple bit-shift ?] So shouldn't the overall run-time be O(2K+K) =O(9.966N+1.5) = O(N) ? Am I missing something here ? Can I consider division by 2 as a constant time operation as well ? I assumed it was because bit-shifting seems like something that would be classified as constant time, just as adding zero's in Karatsuba's algorithm was considered a constant time operation. Is there something wrong with the relationship between K and N ? Will it deviate for higher values on N ? (I couldn't really go beyond 600, nor could I derive a formal mathematical relationship). Link to comment Share on other sites More sharing options...
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!Register a new account
Already have an account? Sign in here.Sign In Now