Content deleted Content added
→Was Babbage faster?: new section |
|||
Line 219:
::::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)
| |||