Talk:Prefix sum

TODO: Mention that it is for any associative binary operator, give a better example of the binary tree communication pattern that achieves optimal depth for powers of 2, cite some of Yen-Chun Lin's work on constructing optimal prefix scan circuits, provide the example showing how it can be used as a parallel addition algorithm, show how to do segmented scan, eliminate MPI_Scan from the article and make another page for it if needed, make a page called "prefix scan" and link them together--GrEp (talk) 03:41, 11 December 2009 (UTC)

In the computer arithmetic field, Algorithm 1 is known as Dogge-Stone and Algorithm 2 as Brent-Kung. There is another algorithm Ladner-Fischer that achieves log(n) stages without being work-inefficient.

See CMOS VLSI Design, 4th edition, for diagrams of adders and prefix circuits using all three algorithms, and hybrids between them, as well as citations to the original papers. Davidmoneyharris (talk) 17:48, 17 April 2022 (UTC)

TODO 2:

• Cite: Parallel Computing Using the Prefix Problem, S. Lakshmivarahan and Sudarshan K. Dhall
• Cite papers on power/speed tradeoffs in circuits.
• Add more examples (4 Russians, tree ops, Well Separated Pair Decompositions, Finite State Automata, ...)
• References to transformation semigroup literature; more formal definition.
• Better Python scan, MPI scan examples.
• References to Duane Merrill's GPU work; illustration of the general two pass algorithm.
• It may be worth mentioning that Algorithm 1 uses O(n log n) operations while algorithm 2 uses O(n) operations. The article by Ladner and Fischer gives a construction that is optimal depth, log base 2 on n, and linear size.67.183.116.53 (talk) 00:44, 23 February 2020 (UTC)

--GrEp (talk) 20:59, 29 October 2012 (UTC)

cumsum

Is this "prefix sum" the same as what Matlab calls cumsum, the cumulative sum?[1] Should the CUSUM article have a disambiguation wp:Hatnote linking to this prefix sum article? --DavidCary (talk) 21:40, 3 September 2011 (UTC)

It does indeed look like Matlab's "cumulative sum" is a prefix sum. But all the references to "cumulative sum" that I found in Google books and Google scholar appear to be for the CUSUM technique, which is something different. Since we don't actually have a cumulative sum article or redirect, and since the Matlab operation has a different name than "CUSUM", there seems little scope for confusion and little need for disambiguation. —David Eppstein (talk) 06:05, 4 September 2011 (UTC)

Not a fold

If my functional programming knowledge correctly serves me, the statement in the first section about prefix sum being the fold of addition is incorrect. I believe it is a scan of addition, however wikipedia does not have a page for scan. 128.138.230.183 (talk) 15:14, 31 January 2012 (UTC)

In the https://en.wikipedia.org/wiki/File:Hypercube-construction-4d.png 4D picture one blue edge is missing .