Skip to main content

Posts

Showing posts with the label parallelism analogies

Welcome to a magical world...

A magical world where clever algorithms meet elegant multitasking models! Suppose you were given the following open-ended problem: Given an array of n bits , perform a negation operation on each of the bits. The most obvious brute force approach would be to go from index 0  to index n-1  and invert the  i th  bit on the way. Well, this works in a clean way and is the simplest formulation which delivers correct results. Nice! Now suppose you have an array of about a million digits; our algorithm directs us to go through each of the elements serially, one by one, giving each bit a feeling of self-importance! (The CPU dedicates few clock cycles exclusively on accessing, processing and finally writing out the result). Can we make this faster? Can we use the fact that an operation on the  i th  bit is independent of  the operation on the ( i+1) th  bit (or any other bit in general)? Of course we can! Imagine a switchbo...