What other mathematical operators can be used to transform the algorithm

Question

The difference operator (similar to the derivative operator) and the sum operator (similar to the integration operator) can be used to change the algorithm, since they are inverse.

Sum of (difference of y) = y Difference of (sum of y) = y 

The following is an example of their use in program c.

This c-program demonstrates three approaches to creating an array of squares.

• The first approach is a simple obvious approach, y = x*x .
• The second approach uses the equation (difference in y) = (x0 + x1)*(difference in x) .
• The third approach is the reverse and uses the equation (sum of y) = x(x+1)(2x+1)/6 .

The second approach is consistently a little faster than the first, although I did not bother to optimize it. I believe that if I tried harder, I could do it even better.

The third approach is consistently twice as slow, but this does not mean that the main idea is stupid. I could imagine that for some function other than y = x*x , this approach could be faster. There is also a problem with integer overflow.

The awakening of all these transformations was very interesting, so now I want to know what other pairs of mathematical operators I could use to transform the algorithm?

Here is the code:

 #include <stdio.h> #include <time.h> #define tries 201 #define loops 100000 void printAllIn(unsigned int array[tries]){ unsigned int index; for (index = 0; index < tries; ++index) printf("%u\n", array[index]); } int main (int argc, const char * argv[]) { /* Goal, Calculate an array of squares from 0 20 as fast as possible */ long unsigned int obvious[tries]; long unsigned int sum_of_differences[tries]; long unsigned int difference_of_sums[tries]; clock_t time_of_obvious1; clock_t time_of_obvious0; clock_t time_of_sum_of_differences1; clock_t time_of_sum_of_differences0; clock_t time_of_difference_of_sums1; clock_t time_of_difference_of_sums0; long unsigned int j; long unsigned int index; long unsigned int sum1; long unsigned int sum0; long signed int signed_index; time_of_obvious0 = clock(); for (j = 0; j < loops; ++j) for (index = 0; index < tries; ++index) obvious[index] = index*index; time_of_obvious1 = clock(); time_of_sum_of_differences0 = clock(); for (j = 0; j < loops; ++j) for (index = 1, sum_of_differences[0] = 0; index < tries; ++index) sum_of_differences[index] = sum_of_differences[index-1] + 2 * index - 1; time_of_sum_of_differences1 = clock(); time_of_difference_of_sums0 = clock(); for (j = 0; j < loops; ++j) for (signed_index = 0, sum0 = 0; signed_index < tries; ++signed_index) { sum1 = signed_index*(signed_index+1)*(2*signed_index+1); difference_of_sums[signed_index] = (sum1 - sum0)/6; sum0 = sum1; } time_of_difference_of_sums1 = clock(); // printAllIn(obvious); printf( "The obvious approach y = x*x took, %f seconds\n", ((double)(time_of_obvious1 - time_of_obvious0))/CLOCKS_PER_SEC ); // printAllIn(sum_of_differences); printf( "The sum of differences approach y1 = y0 + 2x - 1 took, %f seconds\n", ((double)(time_of_sum_of_differences1 - time_of_sum_of_differences0))/CLOCKS_PER_SEC ); // printAllIn(difference_of_sums); printf( "The difference of sums approach y = sum1 - sum0, sum = (x - 1)x(2(x - 1) + 1)/6 took, %f seconds\n", (double)(time_of_difference_of_sums1 - time_of_difference_of_sums0)/CLOCKS_PER_SEC ); return 0; } 

Answer 1

There are two classes of optimizations: strength reduction and peephole .

Strength reduction is a common term for replacing “expensive” mathematical functions with cheaper functions — for example, replacing multiplication with two searches for logarithm tables , adding and then searching for the inverse logarithm to find the final result.

Head-eye optimization is a common term for replacing something like multiplying by the power of two with left shifts. Some processors have simple instructions for these operations, which are faster than general integer multiplication for a particular case of multiplication by powers of two.

You can also optimize individual algorithms. You can write a * b , but there are many different ways to do the multiplication , and different algorithms work better or worse in different conditions. Many of these decisions are made by chip developers, but entire libraries with arbitrary precision make their own decisions based on the advantages of the primitives available to them.

Answer 2

When I tried to compile your code on Ubuntu 10.04, I got a segmentation error when main () is running because you are declaring many megabytes of variables on the stack. I was able to compile it after I moved most of your variables outside of main to make them global.

Then I got the following results:

 The obvious approach y = x*x took, 0.000000 seconds The sum of differences approach y1 = y0 + 2x - 1 took, 0.020000 seconds The difference of sums approach y = sum1 - sum0, sum = (x - 1)x(2(x - 1) + 1)/6 took, 0.000000 seconds 

The program runs so fast that it’s hard for her to believe that she really did something. I turned on the "-O0" option to disable the optimization, but it is possible that GCC could still optimize all the calculations. Therefore, I tried to add a “volatile” qualifier to your arrays, but still got similar results.

Where I stopped working on this. In conclusion, I do not know what is happening with your code, but it is possible that something is wrong.