Divide and Conquer

Overview

An algorithm technique for dividing a problem into smaller subproblems is called divide and conquer. We will here implement another version of a parallel transform algorithm using divide and conquer. It works as follows: if the input range is smaller than a specified threshold, the range is processed; otherwise, the range is split into two parts:

• The first part is processed on a newly branched task
• The other part is recursively processed at the calling thread

The following illustration shows how the divide and conquer algorithm would recursively transform a range using the following data and parameters:

• Range size: 16
• Source range contains floats from 1.0 to 16.0
• Chunk size: 4
• Transformation function: [](auto x) { return x*x; }