For a simple example, lets say you need to add the numbers from 1 to 1,000,000. The obvious way to do this is to go through the list and add each one to the total. This is quite slow. Your processor has some instructions that can work on multiple pieces of data at once, so you can do 1+2, 3+4, 5+6, 7+8 simultaneously, then go back and add those results together.
Your processor also has multiple cores, if you have eight cores you can have core zero working on the numbers up to 125,000, core 1 working on 125,001 to 250,000, etc. So we’re now ~32x faster than the original code, ignoring overhead.
But we can do better. We don’t REALLY care about the process of adding the numbers, what we actually want is the answer at the end. And with a little math we can turn that into something that’s much faster to compute. If you notice that the first number plus the last number is equal to the second number plus the second to last number, and that that pattern holds as you work to the middle, you can turn all those additions into one multiplication. 1,000,001 * 500,000. The code is now hundreds of thousands of times faster, even if you’re only using one core.
If there isn’t a clever trick to make the calculation faster, what you can sometimes do instead is do the calculation once, then keep the result, so you only have to look the answer up in a table.
Latest Answers