Математические вычисления в программировании

Question

Я пытаюсь работать над демонстрацией многопоточности.Мне нужен пример вычислительно-интенсивной функции / метода.Но в то же время код, который выполняет вычисления, должен быть простым.

Например, я ищу функцию, которая, возможно, выполняет что-то вроде вычисления n-й цифры числа пи или е:

function calculatePiToNthDecimalDigit(digits) {
    var pi = "3.";

    for (var i = 1; i < digits; i++) {
        pi += digitOfPiAtDecimalPlace(i);
    }

    return pi;
}

function digitOfPiAtDecimalPlace(decimalPlace) {
    ...
}

Может ли кто-нибудь дать мне пример функции, которая относительно проста, но может быть использована последовательно (например, с замкнутым циклом) для генерации очень сложного для вычисления (занимает много времени) значения?

Answer 1

Реальные тесты происходят от реальных проблем. Как насчет численного интегрирования функции с использованием простой формулы, такой как трапециевидное правило :

Давайте попробуем доказать, что , используя C #

void Main(string[] args)
{
    int N = 2097153;
    double two = Integral(0, Math.PI, N);
    double err = (2.0 - two) / 2.0;
    Console.WriteLine("N={0} err={1}", N, err);
}
double f(double x) { return Math.Sin(x); }
double Integral(double a, double b, int N)
{
    double h = (b - a) / N;
    double res = (f(a) + f(b)) / 2;
    for (int j = 1; j < N; j++)
    {
        double x = a + j*h;
        res += f(x);
    }
    return h * res;
}

В этот момент я получаю N=2097153 и err=2.1183055309848E-13 через несколько миллисекунд. Если вы станете намного выше в точности, тогда ошибка начнет увеличиваться, так как ошибки округления начнут появляться. Я думаю, что нечто подобное может произойти с вычислением для Pi, тогда как вы достигнете точности станка в течение нескольких миллисекунд и более того. Вы действительно рассчитываете мусор. Вы можете просто повторить интеграл несколько раз для более длительного общего эффекта.

Так что, возможно, вам будет хорошо показать уменьшение времени, скажем, с 140 мс до 90 мс и считать его победой.

Answer 2

Умножение двух NxN-матриц имеет сложность, пропорциональную N ^ 3, поэтому создать задачу, требующую большого объема вычислений, довольно просто, просто возведя в квадрат достаточно большую матрицу. Например, когда размер изменяется от N = 10 до N = 100 до N = 1000, количество (скалярных) умножений, требуемых классическим алгоритмом умножения матриц, увеличивается от одной тысячи до одного миллиона до одного миллиарда.

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

Answer 3

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