Talk:Karatsuba algorithm: Difference between revisions

Revision as of 16:01, 14 April 2017

Latest revision as of 11:12, 4 February 2024

(19 intermediate revisions by 10 users not shown)

Line 1:

{{WikiProject banner shell|class=C|

{{maths rating |class=C |importance=low |field=applied}}

{{WikiProject Mathematics|priority=low}}

{{WikiProject Computing |importance=Low |science=y |science-importance=Low |software=y |software-importance=Low}}

}}

== Divide and conquer (February 2011) ==

Line 10 ⟶ 13:

By the way, it's impossible to write that "Karatsuba algorithm is a notable example of "Divide and Conquer" or "Binary Splitting", since just Karatsuba invented this idea, the names "Divide and Conquer", "Binary Splitting" were called much later. Somebody called the Karatsuba idea "Divide and Conquer", so Karatsuba didn't use somebody else' idea, somebody else used the Karatsuba idea. See you the difference? To write "Karatsuba algorithm is a notable example of "Divide and Conquer" means to write that Karatsuba used the method "Divide and Conquer" to create a fast multiplication, but Karatsuba just invented this method (in computational mathematics).[[Special:Contributions/91.79.192.32|91.79.192.32]] ([[User talk:91.79.192.32|talk]]) 14:05, 1 February 2011 (UTC)

The comments above by 91.79.192.32 are utter nonsense and reflect a near complete lack of cognitive competence. Relative timing of the development of concepts and algorithms has no bearing on whether the algorithms are examples of the concepts. -- [[User:Jibal|Jibal]] ([[User talk:Jibal|talk]]) 22:26, 17 January 2020 (UTC)

== Divide and conquer ==

Line 31 ⟶ 36:

''"To equal such different by importance results as the Karatsuba method and von Neumann Sorting means to diminish the advantage of the Karatsuba result."'' — This sentence shows a lot of ignorance. Claiming that a fast sort algorithm is not important is uninformed at best. In fact, most applications depend on sorting rather than on multiplication of long numbers. — [[User:Adrianwn|Adrianwn]] ([[User talk:Adrianwn|talk]]) 08:19, 1 April 2010 (UTC)

The comments above by 83.149.209.253 are utter nonsense and reflect a near complete lack of cognitive competence. -- [[User:Jibal|Jibal]] ([[User talk:Jibal|talk]]) 22:33, 17 January 2020 (UTC)

== Rule of thumb ==

Line 180 ⟶ 187:

== Algorithms are generally invented, not discovered ==

The opening paragraphs states that Karatsuba ''discovered'' this algorithm. Although the principles or properties underlying the algorithm may indeed have been discovered, the algorithm itself would have been ''invented'', unless it was somehow preexistent. I posted this instead of modifying the article directly in case somebody has a justification for the current wording. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/38.104.57.138|38.104.57.138]] ([[User talk:38.104.57.138#top|talk]]) 16:01, 14 April 2017 (UTC)</small> <!--Autosigned by SineBot-->

:Nonsense. This O(n^1.58) algorithm has always existed; therefore it was discovered. On can generally interchange "discovered" and "invented" for algorithms, but the simpler and more fundamental the algorithm, the more "discovered" is appropriate, and the more ad hoc the algorithm, the more "invented" is appropriate. -- [[User:Jibal|Jibal]] ([[User talk:Jibal|talk]]) 22:40, 17 January 2020 (UTC)

== Karatsuba method is not (comparatively) as fast as the article said ==

The description in the article indicate:

''"For example, to multiply two 1024-digit numbers (n = 1024 = 2^10), the traditional algorithm requires (2^10)^2 = 1,048,576 single-digit multiplications, whereas the Karatsuba algorithm requires 3^10 = 59,049 thus being ~17.758 times faster"

''

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 vs apples.

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.

In the example of the product of 12345 and 6789, the traditional algorithm requires 5 digits X 4 digits = 20 single-digit multiplications. The description indicate:

Only three multiplications, which operate on smaller integers, are used to compute three partial results:

z2 = 12 × 6 = 72

z0 = 345 × 789 = 272205

z1 = (12 + 345) × (6 + 789) − z2 − z0 = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

However, 12 × 6 is NOT one multiplication but 2 single-digit multiplications, and 345 × 789 requires 9 single-digit multiplications, and (12 + 345) × (6 + 789) also requires 9 single-digit multiplications, giving a total of 20 multiplications! (not 3).

In this way, Karatsuba's method is not as fast as the article said...

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)