Content deleted Content added
Line 187:
: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 with 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)
| |||