Example Worked Example: Balanced Parallel Sum Depth
example formalized

Worked Example: Balanced Parallel Sum Depth

A divide-and-conquer list sum built from par (Parallel Composition in CostM), where cost is combined by so that .cost measures parallel depth, not total work. Splitting the list in half and summing the halves in parallel gives a logarithmic depth, $$ (\operatorname{parSum}\,xs).\mathrm{cost} \;\le\; \lceil \log_2 |xs| \rceil, $$ i.e. parSum_cost_le_clog (Nat.clog 2 xs.length). The coarser linear bound parSum_cost_le_length is also provided. This is the depth-side counterpart of the additive-work examples: the same algorithm under + would cost O(n), but under the independent branches overlap and only the tree height counts.

Lean declarations

  • ParSum.parSum : List ℕ → CostM ℕ ℕ — the balanced parallel sum.
  • ParSum.parSum_cost_le_clog — the ⌈log₂ n⌉ depth bound.
  • ParSum.parSum_cost_le_length — the coarser linear bound.

References

Also in