Talk:Karatsuba algorithm

WikiProject Mathematics (Rated C-class, Low-importance)
WikiProject Mathematics
Portal icon Mathematics portal
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Low Importance
 Field: Applied mathematics

Divide and conquer (February 2011)

The Karatsuba algorithm is the first fast computational algorithm, Merge-sort from 1945 --- isn't!!! The note below is written by a person who is not a specialist in this field.91.79.192.32 (talk) 12:59, 1 February 2011 (UTC)

Says who? Please cite a reliable published source. -- X7q (talk) 13:36, 1 February 2011 (UTC)

In his book (D.E.Knuth, The art of computer programming. v.2 Addison-Wesley Publ.Co., 724 pp., Reading (1969).) Donald Knuth wrote (when he described the A.A. Karatsuba method), that "this idea was not known before" and wrote that even people who multiplied numbers very fast in mind and all other sources didn't know this idea. But here you try to prescribe the idea to von Neumann!! It's an absolutely wrong statement, von Neumann didn't know the Karatsuba method and the Karatsuba idea!91.79.192.32 (talk) 13:56, 1 February 2011 (UTC)

He wrote that with regard to multiplication algorithms. I don't see how "the first fast computational algorithm" (not just for multiplication) follows from that. -- X7q (talk) 14:40, 1 February 2011 (UTC)

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).91.79.192.32 (talk) 14:05, 1 February 2011 (UTC)

Divide and conquer

The Karatsuba multiplication algorithm, ... in 1960 ... The Karatsuba algorithm can be considered to be the earliest example of a binary splitting algorithm, or more generally, a divide and conquer algorithm.

I think this is wrong. According to Merge_sort, von Neumann invented Merge Sort in 1945. —Preceding unsigned comment added by 84.74.154.5 (talk) 14:11, 23 July 2008 (UTC)

I think, this is an absurd to compare von Neumann Merge Sort and the Karatsuba fast multiplication algorithm. Only after the Karatsuba algorithm the history of fast algorithms began. Such fast processes like AGM method of Gauss, Newton method etc. become FAST only with application of fast multiplication. Von Neumann or anybody else results can not help here. That is why the Karatsuba algorithm can be considered as the frist FAST algorithm in the history of computations. —Preceding unsigned comment added by 83.149.209.253 (talk) 14:37, 31 March 2010 (UTC)

I read the Divide and Conquer topic now --- what is a dreadful content! I wrote the remarks which I will add also below: "The problem is that here in "Divide and Conquer" topic different algorithms and approaches were mixed, what is absolutely incorrect and bad for readers who are not specialists in the considered subjects.

What relation "Merge Sort" has to fast computational algorithms? Can you increase the efficiency of calculation of, say, sinus of x, applying the von Neumann idea? No. You can not. So it is a great difference between the Karatsuba idea and the von Neumann idea. Using the Karatsuba you obtain a tool for calculation of a great number of functions, intagrals and series much more effectively. Using von Neumann --- you obtain almoust nothing. How it is possible not only to compare these two approaches, but even to "put them in one box"?

Karatsuba didn't use the "divide and Conquer" paradigma to invent his method, he just invented such a general method that permit to increase the efficiency of the computer work. After the Karatsuba invention the name "Divide and Conquer" was introduced, not before. To equal such different by importance results as the Karatsuba method and von Neumann Sorting means to diminish the advantage of the Karatsuba result.

Knuth in his "Art of Computer Programming" is writing that the Karatsuba idea was not known till 1960 (4000 years of calculations and multiplications). Seems, Donald Knuth is not agree with the authors of D&C paradigma, believing that the Karatsuba idea is the same that von Neumann idea." —Preceding unsigned comment added by 83.149.209.253 (talk) 15:13, 31 March 2010 (UTC)

"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. — Adrianwn (talk) 08:19, 1 April 2010 (UTC)

Rule of thumb

None of the references really talked about any "rule of thumb" I moved those references. I doubt this rule of thumb is any close to truth I think there was a mistake, I think in this case n refers to the operands themselves and not to the number of digits (Cause if Karatsuba's algorithm only got faster after such an insane amount of digits it wouldn't have any practical use) Perhaps this claim should be removed or at least fixed to remove this ambiguity not to mention including an actual reference 200.87.23.227 (talk) 17:35, 8 January 2009 (UTC)

In fact the references did. GMP uses 32-bit limbs on 32-bit processors, and 64-bit limbs on 64-bit processors. Thus the 10-limb crossover point mentioned in the GMP reference suggests 320 to 640 bit numbers, that is, numbers above 2^320 or 2^640, respectively. The other reference suggest an 800 to 2000-bit x86 crossover point (for numbers above 2^800 or 2^2000).
CRGreathouse (t | c) 18:43, 8 January 2009 (UTC)

Well, either way the amguity about "n" remains, I will change n to "the operands" —Preceding unsigned comment added by 200.87.23.104 (talk) 17:52, 13 January 2009 (UTC)

Merge from Karatsuba multiplication

Consider merging material from The Karatsuba multiplication, which has some descriptions of variants and some more sources. JackSchmidt (talk) 12:57, 26 February 2009 (UTC)

Calculations in Example

With n=2^10=1024, the formula 3n^(log_2(3)) approx 3n^1.585 evaluates to 177193, not 59049 as claimed in the heading paragraph. Now, I do not know what's wrong, the formula or just the result. Someone might want to look into this issue. Gulliveig (talk) 05:46, 20 July 2009 (UTC)

Good catch. Looks like the original writer forgot the 3 in front — 3 n^{\log_23} evaluates to exactly 3^{11} = 177147, in fact. Shreevatsa (talk) 06:31, 20 July 2009 (UTC)
Sorry, but the original number 59049 was correct. Note that the number of single-digit multiplies is at most 3n^(log_2(3)) for general n, but is less than that for many vaues of n. In particular, when n is exactly a power of two 2k, the count is exactly n^(log_2(3)) = 3k, not 3 × 3k. All the best, --Jorge Stolfi (talk) 22:12, 24 July 2009 (UTC)
Ok, I edited the text to mention this explicitly, to avoid future confusion. Thanks, Shreevatsa (talk) 22:24, 24 July 2009 (UTC)

Actually, i was confused as well. Should we move excerpt from talks to article itself? --178.120.229.169 (talk) 11:49, 22 November 2010 (UTC)

Using B = 10^9

Someone objected to the suggestion of using B = 109 because "multiplication by 109 is not realizable by bit-shifts, so choosing B this way doesn't make sense". Actually multiplication by 109 corresponds to shifting the array of "digits" (each stored in one 32-bit word) by one full word.
This choice of basis for bignum arithmetic may be advantageous when one expects a lot of input/output in decimal. Other similar choices are B = 10000 (each "digit" stored in a 16-bit short word) and B = 100 (each "digit" stored in one byte). The last two choices allow decimal output and input by table look-up, without divisions or multiplications.
All the best, --Jorge Stolfi (talk) 03:02, 12 December 2009 (UTC)

Sounds interesting, you should add that to the article. Adrianwn (talk) 08:15, 12 December 2009 (UTC)


I don˙t understand the point: here we talk not about implementations, but about fast algorithms. Fast algorithms, and this first fast algorithm for multiplication, just been created to be useful not only for computers of today but to any computer in future, without essential changing the algorithm. Today "multiplication by 10N is not realizable by bit-shifts" and tomorrow "multiplication by 10100N is not realizable by bit-shifts", but fast algorithms can not loss or can not obtain any advantage from it: this is the work of implementators, not algorithmists. —Preceding unsigned comment added by 195.29.122.4 (talk) 20:53, 16 June 2010 (UTC)

And what exactly do you want to tell us by that? Furthermore, could you please explain this edit? I reverted a previous, similar edit of yours, because it was unclear and seemed redundant. – Adrianwn (talk) 05:37, 17 June 2010 (UTC)

Original research by 93.118.212.93 (Florin Matei) I (collapsed)

How it has been computed?

This article axiomatic stated that:

z0 = 345 × 789 = 272,205

However, it doesn't explains the algorithm for compute that. Is there the time for applying long multiplication, or just apply Karatsuba algorithm again to that expression? 31.42.239.14 (talk) 21:54, 25 February 2013 (UTC)

Original research by 93.118.212.93 (Florin Matei) II (collapsed)

"Invented by Karatsuba"/"Kolmogorov was very agitated"

The lead of our article claims that this algorithm was "invented by Karatsuba". Given that the original publication was joint with Ofman, is there reliable sourcing (independent of Karatsuba himself) that this algorithm was invented solely by Karatsuba? If so, what was Ofman's contribution? —David Eppstein (talk) 02:24, 5 August 2013 (UTC)

Hi, I believe the history section does a good job on that: invented by Karatzuba during a seminar of Kolmogorov, published two years later by Kolmogorov and Ofman (another student in the seminar I read somewhere?) under the names of Karatsuba and Ofman. I do not believe that minutes of the seminar exist, so the amount and influence of brainstorming is not reconstructable.--LutzL (talk) 14:46, 5 August 2013 (UTC)

The history section is problematic, even if we ignore the plausible claims for Karatsuba, because that section also says "Kolmogorov was very agitated about the discovery; he communicated it at the next meeting of the seminar, which was then terminated." That is an uncharitable depiction that doesn't seem to be recorded in any of the sources. This sentence should either be sourced or removed.

fonte: https://web.archive.org/web/20120121011733/http://en.wikipedia.org/wiki/Talk:Karatsuba_algorithm