What are a few time-consuming operations in C?

Question

I'm looking to write a quick benchmark program that can be compiled and run on various machines. Rather than using commercially/open-sourceally available options, I'd rather have my own to play around with threading and algorithm optimization techniques.

I have a couple that I use already, which include recursively calculating the nth number of the Fibonacci sequence, and of seeding/rand()ing a few thousand times.

Are there any other algorithms that are relatively simple, but at the same time computationally-intensive (and possibly math-related)?

(Note that these operations will be implemented in the C language.)

Answer 1

The Ackermann function is usually a fun one, but don't give it very large inputs if you want it to finish in your lifetime.

Answer 2

Inverting big matrices.

Answer 3

Finding prime numbers is considered quite time-consuming.

Answer 4

You could calc big primes or factorizing integers.

Answer 5

This does a lot of addition:

int c = 0; 
for (int n = 0; n < INT_MAX; n++)
    for (int m = 0; m < INT_MAX; m++)
        c++;

std::cout << c;

Answer 6

Take a look at the NAS Parallel Benchmarks. These were originally written by NASA in Fortran for supercomputers using MPI (and are still available that way), but there are also C, Java, and OpenMP implementations available now.

Most of these are very computationally intensive, as they're intended to be representative of numerical algorithms used in scientific computing.

Answer 7

Fractals

(at various resolutions) Some fractal source in C (without opengl)

Answer 8

I know you said you wanted to make your own, but perhaps you could draw upon existing benchmarks for inspiration. The Computer language benchmark game has run many programming languages through a a set of benchmarks. Perhaps you can get some ideas looking at their benchmarks.

Some quick ideas of the top of my head:

• Matrix multiplication: mulitplying 2 large matrices is relatively computationally intensive, though you will have to take caching into account

• Generating prime numbers

• Integer factorization

• Numerical methods for solving ODEs - Runge-kutta for example

Answer 9

Checkout the benchmarks from the language shootout: http://shootout.alioth.debian.org/

However: benchmarks are only benchmarks and don't necessarily tell you a lot about the real world and can, on the contrary, be misleading.

Answer 10

Try to calculate thousands or millions pi digits. There are quite a few formulas for that task.

Answer 11

If you want to try parallelism, do lots of matrix math. The size of your matrix you can use will be limited by memory, but you can do as many iterations as you want.

This will stress the SIMD instructions that modern CPUs come with.

Answer 12

You have some really nice ones in project euler, those are all math related and can be time consuming as you want using higher values.

Answer 13

You could try a tsort (Turbo Sort) with a very large input set. I understand this to be a common operation.

Answer 14

Heuristics for NP-Complete problems are a fun way to get some CPU intensive code. You could code a "solution" :) for one of Karps NP-Complete problems.