Content deleted Content added
m Maintain {{WPBS}} and vital articles: 2 WikiProject templates. Create {{WPBS}}. Keep majority rating "C" in {{WPBS}}. Remove 2 same ratings as {{WPBS}} in {{Maths rating}}, {{WikiProject Computing}}. Remove 1 deprecated parameter: field. Tag: |
|||
| (12 intermediate revisions by 7 users not shown) | |||
Line 1:
{{
{{WikiProject Mathematics|priority=low}} {{WikiProject Computing }}
== Divide and conquer (February 2011) ==
Line 195 ⟶ 198:
''
What the article don't say is that the 59,049 Karatsuba's multiplications are NOT ''single-digit'' multiplications! (like the traditional algorithm) so they're comparing pears
In order to correctly do comparisons, we need to set a ''standard''. If the standard is '''single-digit multiplications''', then the results in the article change.
Line 202 ⟶ 205:
Only three multiplications, which operate on smaller integers, are used to compute three partial results:
z2 = 12 × 6 = 72
z0 = 345 × 789 = 272205
Line 212 ⟶ 215:
Where is the error in my reasoning, if any? [[Special:Contributions/2806:2F0:93C0:FD4B:E92A:EC7:7FF6:5CF0|2806:2F0:93C0:FD4B:E92A:EC7:7FF6:5CF0]] ([[User talk:2806:2F0:93C0:FD4B:E92A:EC7:7FF6:5CF0|talk]]) 01:46, 14 June 2023 (UTC)
:This is a divide-and-conquer algorithm, so the multiplications in z0 and z1 wouldn't be carried out by the conventional nxn method, but rather by calling Karatsuba recursively for each of z0 and z1. I find the article's example poorly chosen and awkward, so I'm not guaranteeing there's nothing wrong with it; but what you're talking about isn't it. [[User:EEng#s|<b style="color:red;">E</b>]][[User talk:EEng#s|<b style="color:blue;">Eng</b>]] 06:22, 14 June 2023 (UTC)
::I am not talking nor referring to advanced details on the method, but about a single and specific point: the comparison of the number of operations on both the traditional algorithm and Karatsuba algorithm, that the article said that is ''~17.758 times faster'' in the first example...
::The posterior example on Karatsuba method (the one that specify ''"Only three multiplications, which operate on '''smaller integers''' (NOT single-digit integers), are used to compute three partial results"'') uses multiplications over ''three-digits numbers''. For this reason I concluded that the first example, the one that requires 1024*1024 = 1,048,576 single-digit multiplications, would require: 1024/3 = 342*342 three-digits multiplications; that is: 116,964 multiplications.
::In this way, if the traditional algorithm requires 116,964 ('''three-digits''') multiplications and Karatsuba algorithm requires 59,049 ('''three-digits''') multiplications (as the second example clearly indicate), then Karatsuba is just 1.98 times faster (and ''not'' 17.758 times faster as the article said). [[Special:Contributions/2806:2F0:93C0:FD4B:B85C:D1F7:77AB:F805|2806:2F0:93C0:FD4B:B85C:D1F7:77AB:F805]] ([[User talk:2806:2F0:93C0:FD4B:B85C:D1F7:77AB:F805|talk]]) 04:58, 21 June 2023 (UTC)
:::I've removed these quantitative claims because (a) they're way overprecise; and (b) they appear to be [[WP:OR]]. [[User:EEng#s|<b style="color:red;">E</b>]][[User talk:EEng#s|<b style="color:blue;">Eng</b>]] 07:21, 21 June 2023 (UTC)
::::To answer the OP's original question "Where is the error in my reasoning": the error is that the OP is confusing the number of single-digit multiplications at the bottom of the recursion (given for the example of two 1024-digit numbers) with the number of recursive multiplications at the top of the recursion (given for the example of 12345 and 6789 and always three). The top-level recursive multiplications are not single-digit. The multiplications at the bottom level of the recursion would be single-digit in whatever base you are using (which really should be much larger than base-10). —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 07:34, 21 June 2023 (UTC)
:::::As usual, the prof put it best. [[User:EEng#s|<b style="color:red;">E</b>]][[User talk:EEng#s|<b style="color:blue;">Eng</b>]] 07:49, 21 June 2023 (UTC)
== Was Babbage faster? ==
"four multiplications...were known to Charles Babbage," isn't that faster than the "quadratic 'grade school' algorithm" (wherein each digit of a multiplicand is multiplied by each digit of a multiplier and
shifted results are added)? If so, that'd mean the Karatsuba algorithm wasn't the first faster multiplication algorithm. [[Special:Contributions/213.41.102.186|213.41.102.186]] ([[User talk:213.41.102.186|talk]]) 10:17, 15 December 2023 (UTC)
:The great observation of Karatsuba is that 3 multiplications are sufficient where Babbage needed 4 multiplications, and that this leads to an algorithm that is faster (for large factors) than all previously known algorithms. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 11:03, 15 December 2023 (UTC)
::Indeed. But, the four multiplications known to Babbage already beats "grade school," right? [[Special:Contributions/213.41.102.186|213.41.102.186]] ([[User talk:213.41.102.186|talk]]) 15:04, 15 December 2023 (UTC)
:::Why do you think that? BTW, the 4 multiplications are the same as the "quadratic 'grade school' algorithm" with 2-digit numbers in a high radix. — [[User:Vincent Lefèvre|Vincent Lefèvre]] ([[User talk:Vincent Lefèvre|talk]]) 15:35, 15 December 2023 (UTC)
::::Oh, doesn't beat, understood. [[Special:Contributions/213.41.102.186|213.41.102.186]] ([[User talk:213.41.102.186|talk]]) 16:50, 15 December 2023 (UTC)
| |||