Какие другие математические операторы можно использовать для преобразования алгоритма

Question

Оператор разности (аналогично оператору производной) и оператор суммирования (аналог оператора интегрирования) можно использовать для изменения алгоритма, поскольку они являются обратными.

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

AnПример их использования в программе AC приведен ниже.

Эта программа c демонстрирует три подхода к созданию массива квадратов.

1. Первый подход - простой очевидный подход, y = x*x.
2. Второй подход использует уравнение (difference in y) = (x0 + x1)*(difference in x).
3. Третий подход является обратным и использует уравнение (sum of y) = x(x+1)(2x+1)/6.

Второйподход несколько быстрее, чем первый, хотя я не удосужился оптимизировать его.Я полагаю, что если бы я старался изо всех сил, я мог бы сделать это еще лучше.

Третий подход всегда вдвое медленнее, но это не значит, что основная идея глупа.Я мог бы представить, что для какой-то функции, отличной от y = x*x, этот подход может быть быстрее.Также существует проблема переполнения целых чисел.

Испытание всех этих преобразований было очень интересным, поэтому теперь я хочу знать, какие еще пары математических операторов я мог бы использовать для преобразования алгоритма?

Вот код:

#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

Здесь есть два класса оптимизации: снижение прочности и глазок оптимизации.

Снижение прочности - это обычный термин для замены «дорогих» математических функций более дешевыми функциями - скажем, замена умножения на два поиска в логарифмической таблице , дополнение, а затем обратный логарифмический поиск, чтобы найти конечный результат.

Оптимизация глазка - это обычный термин для замены чего-то вроде умножения на степень два с левыми сдвигами. Некоторые процессоры имеют простые инструкции для этих операций, которые выполняются быстрее, чем обычное целочисленное умножение для конкретного случая умножения на степени двух.

Вы также можете выполнять оптимизацию отдельных алгоритмов. Вы можете написать a * b, но существует много разных способов умножения , и разные алгоритмы работают лучше или хуже в разных условиях. Многие из этих решений принимаются разработчиками микросхем, но целочисленные библиотеки произвольной точности делают свой собственный выбор, основываясь на достоинствах доступных им примитивов.

Answer 2

Когда я пытался скомпилировать ваш код в Ubuntu 10.04, у меня возникла ошибка сегментации сразу после запуска main (), потому что вы объявляете переменные в стеке на много мегабайт. Я смог скомпилировать его после того, как переместил большинство ваших переменных за пределы main, чтобы они стали глобальными переменными.

Тогда я получил эти результаты:

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

Программа работает так быстро, что трудно поверить, что она действительно что-то сделала. Я включил опцию "-O0", чтобы отключить оптимизацию, но возможно, что GCC все еще мог оптимизировать все вычисления. Поэтому я попытался добавить квалификатор «volatile» в ваши массивы, но все равно получил похожие результаты.

Вот где я перестал работать над этим. В заключение, я не знаю, что происходит с вашим кодом, но вполне возможно, что что-то не так.