http://rapidshare.com/files/437713784/F ... cation.pdf
I would like to discuss some aspects of these notes
First question is, in page 4 what does does it mean by: "The stuff in parenthesis doesn't amount to much (though it is fun to think about how much there is)."
And also, the number of steps for multiplication is 2n^2. i think it should be more. Could anyone please explain this to me?
Thanks in advance.
Academic Question about Cryptography
Academic Question about Cryptography
- Attachments
-
- Fast_multiplication.zip
- (67.51 KiB) Downloaded 469 times
Good day, sir.
This algorithm is also called "long multiplication". So, let's say you want to multiply 2938 (call it "a" number) and 3547 (call it "b" number).
Also, remember that
2938 = 2000 + 900 + 30 + 8
3547 = 3000 + 500 + 40 + 7
Let's take only digits from every number, but remember its position (how many zeros behind the digit), then:
2938 consists of 2, 9, 3, 8 (notation in the article a_4, a_3, a_2, a_1)
3547 — 3, 5, 4, 7 (b_4, b_3, b_2, b_1)
Multiplication part: each digit of one number multiplies on all digit from the second number. It is (n numbers of a) * (n numbers of b). Since we are talking about numbers with the same number of digits, n numbers of a = n numbers of b, so we need n^2 number of steps in multiplication part of algorithm.
Addition part:
First, why "the stuff in parenthesis" doesn't really matter: I don't know. In this example full calculation gives the 10 421 086, and calculation without steps in parentheses — 7 949 536. The difference is 25% — it DOES matter.
Second, you can't get n^2 steps without that steps in parentheses, you'll get something less than n^2. For this step look into columns method of addition and assume you have to remember and add one more number on each step. And still, very first digit of the first multiplication step will be the rightmost in the answer, we have nothing to add to it. So, my opinion, that number of addition steps will be (n^2 - 1) (= 2 + 3 + ... + n + (n - 1) + ... + 2 + 1), then total number of steps
2n^2 - 1
Really hope, this will help you
This algorithm is also called "long multiplication". So, let's say you want to multiply 2938 (call it "a" number) and 3547 (call it "b" number).
Also, remember that
2938 = 2000 + 900 + 30 + 8
3547 = 3000 + 500 + 40 + 7
Let's take only digits from every number, but remember its position (how many zeros behind the digit), then:
2938 consists of 2, 9, 3, 8 (notation in the article a_4, a_3, a_2, a_1)
3547 — 3, 5, 4, 7 (b_4, b_3, b_2, b_1)
Multiplication part: each digit of one number multiplies on all digit from the second number. It is (n numbers of a) * (n numbers of b). Since we are talking about numbers with the same number of digits, n numbers of a = n numbers of b, so we need n^2 number of steps in multiplication part of algorithm.
Addition part:
First, why "the stuff in parenthesis" doesn't really matter: I don't know. In this example full calculation gives the 10 421 086, and calculation without steps in parentheses — 7 949 536. The difference is 25% — it DOES matter.
Second, you can't get n^2 steps without that steps in parentheses, you'll get something less than n^2. For this step look into columns method of addition and assume you have to remember and add one more number on each step. And still, very first digit of the first multiplication step will be the rightmost in the answer, we have nothing to add to it. So, my opinion, that number of addition steps will be (n^2 - 1) (= 2 + 3 + ... + n + (n - 1) + ... + 2 + 1), then total number of steps
2n^2 - 1
Really hope, this will help you
Thank you for your replys
@Flash: I am still not sure what it means but I don't think that's what the author meant
@Cust0dain: Good day to you too sir
Perhaps the extra 1 operation can be attributed to a possible carry over from the extreme last digit? for example, if the last digit was a 9 and had a carry (of say 2), then it would still give out a carry which, although just need to be added to zero, would in fact increase the total number of digits in the final answer
But I am still not sure about this
What are your views?
@Flash: I am still not sure what it means but I don't think that's what the author meant
@Cust0dain: Good day to you too sir
Perhaps the extra 1 operation can be attributed to a possible carry over from the extreme last digit? for example, if the last digit was a 9 and had a carry (of say 2), then it would still give out a carry which, although just need to be added to zero, would in fact increase the total number of digits in the final answer
But I am still not sure about this
What are your views?
I was counting it as last one addition step (2 + 3 + ... + n + (n-1) + ... + 2 + 1)mahaju wrote:... it would still give out a carry which, although just need to be added to zero, would in fact increase the total number of digits in the final answer
Well, I'm looking at it now and thinking what if author count addition of all digits to zero? Like this one last step that we were talking about. Than, without carries, we'll have exctly n^2 steps.
If we count those steps in parentheses, we'll have (in worst case) 2 * (SUM from n=1 to n-1 of n) more steps (1 + 2 + ... + (n - 1) + (n - 1) + ... + 2 + 1), wich, as you can see is n less than n^2.
So, in case of such interpretation of this algorithm, it has (3n^2 - n) steps.