Talk:Divide-and-conquer algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Deleted reference to "Divide and rule (politics and sociology)"[edit]

Inexplicably, this was included in the "See Also" section of this page, though it has not even a metaphorical relationship to these algorithms. I removed it. —Preceding unsigned comment added by Ailun (talk • contribs) 06:10, 6 April 2010 (UTC)[reply]

Usage[edit]

what percentage of people use the divide and copnquer method?

100% of programmers. You cannot get around it. -71.136.79.237


RE: "One commonly argued disadvantage of a divide-and-conquer approach is that recursion is slow"

Surely not. Function calls are fast and tail calls can be branches...!!!!!

You're definitely wrong - on both counts (tail calls only apply to decrease and conquer).

Deleted the "Decrease and Conquer" section[edit]

The article had a section on the "Decrease and Conquer" (D-C) algorithms, defined as Divide and Conquer (D+C) algorithms where each call generates at most one recursive call (i.e., where the problem gets "divided" into at most one sub-problem). I removed that section, since that approach seems rather pointless. D-C algorithms are much easier to implement and understand using either iteration or simple recursion. Besides, most of the discussion about D+C algorithms is irrelevant for D-C algorithms. So, discussing D-C algorithms in the D+C article is like having a section in the matrix multiplication page that tells how one can multiply two real numbers by turning them into 1x1 matrices. The example algorithms that were given (finding the largest of N numbers) just prove the point: when the D-C paradigm can be applied at all, it produces nedlessly complex and inefficient code. All the best, --Jorge Stolfi (talk) 23:28, 24 October 2008 (UTC)[reply]

Decrease and conquer, undead[edit]

The article was recently edited to extend the name "divide end conquer" so as to include some single-branch recursive algorithms, like binary search and Euclid's gcd (the "decrease and conquer" of some authors). Apparently this broader definition f D+C has been adopted by some textbooks, like Cormen's. However, if Euclid qualifies as D+C, then what algorithm does NOT qualify? Every looping algorithm can be trivially rewritten as a single loop (per Bohm&Jacopini) and then as a sngle-branch recursive procedure. So, where would we draw the line? --Jorge Stolfi (talk) 07:19, 11 March 2009 (UTC)[reply]

Deleted "Divide and Marriage before Conquest" section[edit]

The article had a short section on a supposed "Divide and marriage before conquest" paradigm, in which "solutions to the subproblems generated by the recursion are combined to obtain a solution to the original problem", with mergesort cited as one example. Reference given: Public Domain This article incorporates public domain material from Paul E. Black. "Divide and marriage before conquest". Dictionary of Algorithms and Data Structures. NIST.. But that is precisely the definition of the D&C paradigm, isn't it? --Jorge Stolfi (talk) 23:40, 24 October 2008 (UTC)[reply]

Karatsuba is the author of the first fast method[edit]

In the theory of fast computation "divide and conquer" is the name of the first fast method which was found by Anatolii A. Karatsuba in 1960. The published papers of Gauss (including the presented in the cited sources) do not give the grounds to consider Gauss as an author of a fast method. The author of the reference to the Gauss work didn't present the "Gauss FFT-algorithm". It would be preferably to present it, to give the possibility for everybody to calculate the complexity of such a process and to uderstand the difference between fast and "slow" processes. 

The presented definition

"A divide and conquer algorithm works by recursion breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly" doesn't answer to the question, is such a "D&C" fast or not fast. If you subdivide two n-digit integers into two parts etc. and at every step you do calculations with four n/2, n/4 etc. digit integers as a result you have the same complexity of calculations as an ordinary multiplication algorithm, that is n^2. At the same time, such a "slow" process is just defined by the presented above definition of D&C.

The advantage of the Karatsuba method, and also based on the Karatsuba FFT, AGM etc. is the complexity bound for these methods, these are fast methods what has a practical meaning.


Sincerely, Ekatherina Karatsuba http://www.ccas.ru/personal/karatsuba/index_e.htm

http://www.ccas.ru/personal/karatsuba/algen.htm

http://www.ccas.ru/personal/karatsuba/divcen.htm

http://www.ccas.ru/personal/karatsuba/faqen.htm 

—Preceding unsigned comment added by Ekaratsuba (talk • contribs) 15:00, 16 November 2008 (UTC)[reply]
The algorithm that Gauss described is exactly what is now known as the Cooley-Tukey FFT algorithm (named after later re-discoverers), and is indeed an O(n log n) method (even though Gauss did not analyze this aspect, and merely said it was less "tedious"). The original notes by Gauss are available (e.g. I can get them electronically through my library), although they are in Latin (an interesting exercise for those of use who studied Latin in high school). However, a much more accessible reference is the review by Heideman et al. that is cited here. As Heideman et al. review, divide-and-conquer FFT algorithms were actually discovered multiple times by multiple authors prior to Cooley and Tukey (who, however, deserve credit for the first complexity analysis showing the reduction to O(n log n), and the first description of a practical implementation on an electronic computer, and for popularizing the technique). Most of these were essentially the same Cooley-Tukey algorithm, but a quite distinct algorithm [also O(n log n)], the Prime-factor FFT algorithm, was described by Good in 1958.
As also described by the article, von Neumann described a divide-and-conquer sort algorithm in 1945, so the FFT algorithm is not unique in being a divide-and-conquer algorithm prior to 1960.
Nor is this an exhaustive list. I wouldn't be surprised if there were many other examples of divide-an-conquer algorithms in the history of mathematics, which is why (without a solid reference) we need to be very careful about claiming which one is the "first".
Some divide and conquer algorithms are "fast", in the sense that they reduce the complexity compared to a naive approach to the underlying problem—examples of this include FFTs and sorting, so Karatsuba was certainly not the first in this regard as the references prove—but this doesn't seem to be the definition of divide-and-conquer as the term is used in the field.
—Steven G. Johnson (talk) 17:04, 16 November 2008 (UTC)[reply]


I haven't seen the cited paper of Heideman etc., but I have seen works of Gauss. Although I have seen a paper by three american mathematicins who tried to demostrate that the first fast mutiplication algorithm was invented by Gauss. Unfortunately, there are no fast algorithms in the Gauss works. You make a mistake, believing that described algorithms are fast (without use of another fast sub-algorithms). As for sort algorithms, it is impossible to compare then with the computational algorithms. First fast computational algorithm was invented by Russian A.A. Karatsuba, even if you don't like it. Your attempts to disprove this fact with such references to von Neumann look very funny. Why Gauss? Why not Newton (his algorithms are fast if to use fast multiplication)? Why von Neumann? Why not Alexander the Great (of Macedon)? He invented D&C algorithm in politics. The first one! Before von Neumann's sorting algorithm! —Preceding unsigned comment added by Algoritmist (talk • contribs) 12:55, 6 December 2008 (UTC)[reply]

Sorry, you're wrong. As Heideman et al explain, what Gauss described is exactly equivalent what is now called the Cooley-Tukey FFT algorithm, and is indeed a fast algorithm. And if you've seen the work of Gauss in question, you obviously haven't understood it. And as Heideman explains, FFTs were actually rediscovered multiple times in the 19th and early 20th century, so Gauss isn't the only one.
The standard definition of D&C algorithms in computer science includes algorithms for problems such as sorting (see any algorithms textbook); your arbitrary exclusion of Von Neumann as not "computational" is unsupported, and your hyperbole about Alexander the Great is pointless. And we hardly have an exhaustive history here, so there are probably other examples too. In practice, Wikipedia cannot claim that any specific author was the "first" to describe a D&C algorithm without a reputable source — see the WP:V and WP:RS policies.
Your claims about Karatsuba are just going to get reverted if you keep inserting them, since they are clearly refuted by reputable published work. —Steven G. Johnson (talk) 15:48, 6 December 2008 (UTC)[reply]

My claims are true and mathematically correct. I don't know the specialists in fast algorithms that would refute the fact that Karatsuba multiplication is the first fast computational algorithm. The misunderstanding between us (or between me and your textbooks, reputable of course, but written not by specialists in fast algorithms) that there is a difference between the computational complexity of the algorithms of computation of a function with a given accuracy from the "complexity" of sorting algorithms. Von Neumann algorithm couldn't be considered as a fast computational algorithm. His description in Knuth (The art, 1998) is:" Algorithm M (Two-way merge). This algorithm merges nonempty ordered files $x_1 \leq x_2 \leq \dots \leq x_m$ and $y_1 \leq y_2 \leq \dots \leq y_n$ into a single file $z_1 \leq z_2 \leq \dots \leq z_{m+n}$."..."The total amount of work involved in Algorithm M is essentially proportional to $m+n$"... "From hystorical point of view, merge sorting was one of the very first methods proposed for computer sorting; it was suggested by John von Neumann as early as 1945". Here is nothing about the computational complexity of this algorithm or that this is a fast algorithm. How you estimate "the complexity" of the operation which is called in Knuth book "Find smaller"? Do you consider the numbers x_i,y_j as n-digit integers? Or you calculate in realty only the number of steps (passes ?) of sorting algorithms? Anyway, it is impossible to compare these two sorts/kinds of algorithms --- computational, when you compute a given function with a given accuracy and calculate the total number of bit operations sufficient to do such a computation (the complexity) and the sorting algorithms.

About the Karatsuba multiplication is written in Knuth(I cited always the third edition of "The Art of Computer Programming"(from 1998):"Curiously, this idea does not seem to have been discovered before 1962" (Volume 2, page 295). So, Knuth claimes the Karatsuba multiplication was the first fast multiplication algorithm. An you with Heideman claim that this isn't true. Do you think the book of Knuth isn't "reputable" one? —Preceding unsigned comment added by Algoritmist (talk • contribs) 12:11, 10 December 2008 (UTC)[reply]


It is interesting why did you delete the references to webpages of Ekatherina Karatsuba devoted to fast algorithms? Do you afraid that people get another point of view to this problem?

The advantage of Anatoly Karatsuba is that he just invented the method which later was called "Divide and Conquer", not used, not gave an example, but invented! The examples of von Neumann (also Gauss) etc. do not give a possibility to consider somebody of them as an author od the method similar to the Karatsuba method. —Preceding unsigned comment added by Algoritmist (talk • contribs) 12:40, 10 December 2008 (UTC)[reply]

FFTs are fast algorithms to compute the discrete Fourier transform. I never claimed that they are a fast multiplication algorithm predating Karatsuba, but they are a fast D&C algorithm for something else. (FFTs can be used in fast multiplication algorithms, but this was not pointed out until much later.) As for merge sort, if you don't think that is a fast algorithm, you clearly don't understand it, nor do you understand complexity analysis if you think it doesn't apply to sorting. (All you need to know to analyze sorting is that it takes O(1) time to compare or swap two bounded-size elements of an array. And of course one can analyze sorting in other circumstances as well. Google for "sorting" and "complexity". Moreover, whether you can compare the complexity of sorting to the complexity of fast multiplication algorithms is irrelevant here.)
(It is bizarre that you apparently think that textbook authors like Knuth or Cormen/Leiserson/Rivest are "not specialists in fast algorithms". What do you think these people do for a living?)
Perhaps this is the root of your problem: You apparently think that the term "divide and conquer algorithm" (or "fast algorithm") should only be used for fast multiplication algorithms for arbitrary-precision arithmetic. This is not how the term is used, as is amply demonstrated by the references cited already.
(Your self-published web-page is not a reliable source according to Wikipedia's standards. And it seems like a bad idea to send readers to a page by someone who doesn't seem to understand how words like "divide and conquer", "complexity", or "fast algorithm" are used in computer science in English.)
—Steven G. Johnson (talk) 17:17, 10 December 2008 (UTC)[reply]

Who was the author of the name "Divide and Conquer" for certain kind of computational algorithms ?[edit]

I don't know the answer to this question. Anybody knows? Alexander the Great didn't assume a fast computational algorithm. Also von Neumann. But the description of the D&C, described on this webpage above, unites very dofferent algorithms from very different regions of science and life, fast and not fast. Who did such a unification? —Preceding unsigned comment added by Algoritmist (talk • contribs) 13:26, 6 December 2008 (UTC)[reply]

The description on this page is totally standard in computer science; please stop this pointless and misguided campaign. —Steven G. Johnson (talk) 15:49, 6 December 2008 (UTC)[reply]

This subject is incorrect[edit]

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:09, 31 March 2010 (UTC)[reply]

The description on this page is totally standard in computer science; please stop this pointless and misguided campaign. —Steven G. Johnson (talk) 15:49, 6 December 2008 (UTC)[reply]

Proposed move[edit]

The following discussion is an archived discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review. No further edits should be made to this section.

The result of the move request was: moved to Divide and conquer algorithms. -- BrownHairedGirl (talk) • (contribs) 18:50, 3 March 2014 (UTC)[reply]


Divide and conquer algorithm → Divide and conquer (computer science) – "Divide and conquer algorithm" suggests that it's an algorithm, while it's a class of algorithms. I could live with "Divide and conquer (algorithmics)" or "Divide and conquer algorithms" (plural). Thanks. 63.217.82.139 (talk) 06:58, 19 February 2014 (UTC)[reply]

The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page or in a move review. No further edits should be made to this section.

Outline[edit]

Was this really meant to be under "Implementation issues"?
"A stage reaches [what] when either ..."

Picture[edit]

The commons picture File:Array maximum - divide et impera.png nicely illustrates all aspects of a d+c algorithm. However, I hesitate to show it in the article since the problem it solves (finding the maximum value in an array) can better be solved by linear search. Maybe somebody can obtain a similar image, but about a d+c algorithm that is optimal? - Jochen Burghardt (talk) 06:05, 12 April 2017 (UTC)[reply]

Towers of Hanoi is not a divide and conquer algorithm[edit]

Hi, The recursive Towers of Hanoi algorithm which solves the problem by moving n-1 disks to the intermediate peg, the nth disk to the final page, and the n-1 disks from the intermediate peg is a great example of a recursive solution to a puzzling problem. However it is not a divide and conquer algorithm. In divide and conquer algorithms a problem of size n is typically split into m more or less equally sized subproblems (where m is usually 2, but sometimes more), then the subproblems are solved recursively, and their solutions are then combined to get a solution to the original problem. This does not take place in the Towers of Hanoi algorithm. In this algorithm, there are two recursive function calls, but their recursions are on subproblems of size n-1, and not on subproblems of size n/m. This algorithm is better classified as a "reduce by 1" algorithm, and not as a "divide and conquer" algorithm. Saquigley (talk) 07:32, 11 March 2018 (UTC)Sophie Quigley, Professor, Department of Computer Science, Ryerson University[reply]

Picture: remove intermediate levels for "10"[edit]

At the picture illustrating MergeSort algorithm, I assume it would be better to skip some levels with one-element fragment "10" (only one such level should remain, not three equal ones), with repainting corresponding arrows not one level down, but either two arrows two layers down each, or maybe one arrow one layer down, one arrow three layers down. Reason: one-element fragment "10" IS NOT divided into parts, there are NO recursive calls for it. Draft visual presentation of the proposition is [1]https://docs.google.com/drawings/d/1vO5Zg2Q6KI8ACnFCbfs4h4lwC9_foV2PJlu5ZgX0NXc IlyaCk (talk) 07:37, 9 December 2023 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Divide-and-conquer_algorithm&oldid=1194846636"