Parallel Algorithms: Difference between revisions

Parallel Algorithms (view source)

426 bytes added , 4 February 2020

5,337

edits

@@ Line 57: / Line 57: @@
 ;Outputs
 * Array B containing B(i) = A(1) * ... * A(i)
+;Algorithm
+<math>O(n)</math> work and <math>O(\log n)</math> time
+<pre>
+for i, 1 <= i <= n pardo
+  B(0, i) = A(i)
+  // Summation step up the tree
+  for h=1 to log n
+    B(h, i) = B(h-1, 2i-1) * B(h-1, 2i)
+  // Down the tree
+  for h=log n to 1
+    if i even, i <= n/2^h
+      C(h, i) = C(h+1, i/2)
+    if i == 1
+      C(h, i) = B(h, i)
+    if i odd, 3 <= i <= n/2^h
+      C(h, i) = C(h+1, i/2) + B(h, i)
+return C(0, :)
+</pre>