Mathematic calculations in programming

I'm trying to work on a demonstration about multithreading. I need an example of a computationally-intensive function/method. But at the same time, the code that does the computing should be simple.

For example, I'm looking for a function that maybe does something like calculate the nth digit of pi or e:

function c开发者_运维技巧alculatePiToNthDecimalDigit(digits) {
    var pi = "3.";

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

    return pi;
}

function digitOfPiAtDecimalPlace(decimalPlace) {
    ...
}

Can anyone give me an example of a function that is relatively simple but can be used in succession (e.g. tight loop) to generate a very hard-to-compute (takes a long time) value?

The simplest I can think of is summing a huge list of numbers. Addition is obviously easy, but if the list is huge, that will make it computationally-intensive, and the problem lends itself well to multi-threading.

Real tests come from real problems. How about the numerical integration of a function using a simple formula such as the trapezoidal rule:

Lets try to prove that

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;
}

at which point I get N=2097153 and err=2.1183055309848E-13 after several milliseconds. If you go much higher in accuracy then the error starts to up as round-off errors start to creep in. I think something similar might happen with a calculation for Pi whereas you will reach you machine accuracy within a few milliseconds and beyond that you are really calculating garbage. You could just repeat the integral several times for a longer overall effect.

So you might be ok to show a drop in time from lets say 140 ms down to 90 ms and count it as a victory.

The multiplication of two NxN matrices has complexity proportional to N^3, so it is relatively easy to create a "computationally intensive" task, just by squaring a sufficiently large matrix. For example, as size goes from N=10 to N=100 to N=1000, the number of (scalar) multiplications required by the classic algorithm for matrix multiplication goes from one thousand to one million to one billion.

Also such a task has plenty of opportunities for parallel processing, if your multi-threading demonstration is meant to take advantage of such opportunities. E.g. the same row can be multiplied by more than one column in parallel.