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: |
|||
| (6 intermediate revisions by 4 users not shown) | |||
Line 1:
{{
{{WikiProject Mathematics|priority=low}} {{WikiProject Computing }}
== Divide and conquer (February 2011) ==
Line 218 ⟶ 221:
:::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)
| |||