Divide-and-conquer algorithm: Difference between revisions

Revision as of 05:12, 25 January 2020

Revision as of 02:18, 9 March 2020

Line 1:

In [[computer science]], '''divide and conquer''' is an [[algorithm design paradigm]] based on multi-branched [[recursion]]. A divide-and-conquer [[algorithm]] works by recursively 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. The solutions to the sub-problems are then combined to give a solution to the original problem.

This divide-and-conquer technique is the basis of efficient algorithms for all kinds of problems, such as [[sorting algorithm|sorting]] (e.g., [[quicksort]], [[merge sort]]), [[multiplication algorithm|multiplying large numbers]] (e.g. the [[Karatsuba algorithm]]), finding the [[Closest pair of points problem|closest pair of points]], [[syntactic analysis]] (e.g., [[top-down parser]]s), and computing the [[discrete Fourier transform]] ([[fast Fourier transform|FFT]]).<ref>{{cite book |last1=Blahut |first1=Richard |title=Fast Algorithms for Signal Processing |publisher=Cambridge University Press |isbn=978-0-511-77637-3 |pages=139-143139–143}}</ref>

Understanding and designing divide-and-conquer algorithms is a complex skill that requires a good understanding of the nature of the underlying problem to be solved. As when proving a [[theorem]] by [[Mathematical induction|induction]], it is often necessary to replace the original problem with a more general or complicated problem in order to initialize the recursion, and there is no systematic method for finding the proper generalization.{{Clarify|date=October 2017}} These divide-and-conquer complications are seen when optimizing the calculation of a [[Fibonacci number#Matrix form|Fibonacci number with efficient double recursion]].{{Why|date=October 2017}}{{Citation needed|date=October 2017}}

Line 23:

An early example of a divide-and-conquer algorithm with multiple subproblems is [[Carl Friedrich Gauss|Gauss]]'s 1805 description of what is now called the [[Cooley–Tukey FFT algorithm|Cooley–Tukey fast Fourier transform]] (FFT) algorithm,<ref name=Heideman84>Heideman, M. T., D. H. Johnson, and C. S. Burrus, "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.4791&rep=rep1&type=pdf Gauss and the history of the fast Fourier transform]", IEEE ASSP Magazine, 1, (4), 14–21 (1984).</ref> although he did not [[analysis of algorithms|analyze its operation count]] quantitatively, and FFTs did not become widespread until they were rediscovered over a century later.

An early two-subproblem D&C algorithm that was specifically developed for computers and properly analyzed is the [[merge sort]] algorithm, invented by [[John von Neumann]] in 1945.<ref>{{ cite book | last=Knuth | first=Donald | authorlink=Donald Knuth | year=1998 | title=[[The Art of Computer Programming]]: Volume 3 Sorting and Searching | page=159 | isbn=0-201-89685-0 }}</ref>

Another notable example is the [[Karatsuba algorithm|algorithm]] invented by [[Anatolii Alexeevitch Karatsuba|Anatolii A. Karatsuba]] in 1960<ref>{{cite journal| last=Karatsuba | first=Anatolii A. | authorlink=Anatolii Alexeevitch Karatsuba |author2=Yuri P. Ofman |authorlink2=Yuri Petrovich Ofman | year=1962 | title=Умножение многозначных чисел на автоматах | journal=[[Doklady Akademii Nauk SSSR]] | volume=146 | pages=293–294}} Translated in {{cite journal| title=Multiplication of Multidigit Numbers on Automata | journal=Soviet Physics Doklady | volume=7 | year=1963 | pages=595–596 |url={{Google books|MrkOAAAAIAAJ|plainurl=true}} }}</ref> that could multiply two ''n''-digit numbers in <math>O(n^{\log_2 3})</math> operations (in [[Big O notation]]). This algorithm disproved [[Andrey Kolmogorov]]'s 1956 conjecture that <math>\Omega(n^2)</math> operations would be required for that task.

Line 44:

=== Memory access ===

Divide-and-conquer algorithms naturally tend to make efficient use of [[memory cache]]s. The reason is that once a sub-problem is small enough, it and all its sub-problems can, in principle, be solved within the cache, without accessing the slower main memory. An algorithm designed to exploit the cache in this way is called ''[[cache-oblivious algorithm|cache-oblivious]]'', because it does not contain the cache size as an explicit parameter.<ref name="cahob">{{cite journal | author = M. Frigo |author2=C. E. Leiserson |author3=H. Prokop | title = Cache-oblivious algorithms | journal = Proc. 40th Symp. onOn the Foundations of Computer Science |pages=285–297 | year = 1999|url=https://dspace.mit.edu/bitstream/handle/1721.1/80568/43558192-MIT.pdf;sequence=2|doi=10.1109/SFFCS.1999.814600 |isbn=0-7695-0409-4 }}</ref>

Moreover, D&C algorithms can be designed for important algorithms (e.g., sorting, FFTs, and matrix multiplication) to be ''optimal'' cache-oblivious algorithms–they use the cache in a probably optimal way, in an asymptotic sense, regardless of the cache size. In contrast, the traditional approach to exploiting the cache is ''blocking'', as in [[loop nest optimization]], where the problem is explicitly divided into chunks of the appropriate size—this can also use the cache optimally, but only when the algorithm is tuned for the specific cache size(s) of a particular machine.

Line 74:

Thus, for example, many library implementations of quicksort will switch to a simple loop-based [[insertion sort]] (or similar) algorithm once the number of items to be sorted is sufficiently small. Note that, if the empty list were the only base case, sorting a list with ''n'' entries would entail maximally ''n'' quicksort calls that would do nothing but return immediately. Increasing the base cases to lists of size 2 or less will eliminate most of those do-nothing calls, and more generally a base case larger than 2 is typically used to reduce the fraction of time spent in function-call overhead or stack manipulation.

Alternatively, one can employ large base cases that still use a divide-and-conquer algorithm, but implement the algorithm for predetermined set of fixed sizes where the algorithm can be completely [[loop unwinding|unrolled]] into code that has no recursion, loops, or [[Conditional (programming)|conditionals]] (related to the technique of [[partial evaluation]]). For example, this approach is used in some efficient FFT implementations, where the base cases are unrolled implementations of divide-and-conquer FFT algorithms for a set of fixed sizes.<ref name="fftw">{{cite journal | author = Frigo, M. |author2=Johnson, S. G. | url = http://www.fftw.org/fftw-paper-ieee.pdf | title = The design and implementation of FFTW3 | journal = Proceedings of the IEEE | volume = 93 | issue = 2 |date=February 2005 | pages = 216–231 | doi = 10.1109/JPROC.2004.840301|citeseerx=10.1.1.66.3097 }}</ref> [[Source-code generation]] methods may be used to produce the large number of separate base cases desirable to implement this strategy efficiently.<ref name="fftw"/>

The generalized version of this idea is known as recursion "unrolling" or "coarsening", and various techniques have been proposed for automating the procedure of enlarging the base case.<ref>Radu Rugina and Martin Rinard, "[http://people.csail.mit.edu/rinard/paper/lcpc00.pdf Recursion unrolling for divide and conquer programs]" in ''Languages and Compilers for Parallel Computing'', chapter 3, pp. 34–48. ''Lecture Notes in Computer Science'' vol. 2017 (Berlin: Springer, 2001).</ref>