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