Hard maths problem to benchmark with

Red Alert

I'm tricking around with MATLAB, C and Fortran and a bit of Python while I'm at it for a finite element solver I'm writing. I'm aware of the relative performance differences between MATLAB and the rest of them so MATLAB would be pretty much for prototyping.

Also in the case of Fortran where I have some legacy code already I'm trying to benchmark the GNU compiler particularly when it comes to vectorization against the Intel ones for our purposes.

I'm just wondering if anyone knows or has a good 'hard to solve' maths problem that makes good use of vectorization/loops and generally shows up a slow or fast implementation.

Plan seems to be to code it in Fortran at the minute btw.

Cantab.

Red Alert wrote: »

I'm tricking around with MATLAB, C and Fortran and a bit of Python while I'm at it for a finite element solver I'm writing. I'm aware of the relative performance differences between MATLAB and the rest of them so MATLAB would be pretty much for prototyping.

Also in the case of Fortran where I have some legacy code already I'm trying to benchmark the GNU compiler particularly when it comes to vectorization against the Intel ones for our purposes.

I'm just wondering if anyone knows or has a good 'hard to solve' maths problem that makes good use of vectorization/loops and generally shows up a slow or fast implementation.

Plan seems to be to code it in Fortran at the minute btw.

I know a couple of guys in the Trinity Mech. Eng. Dept. did some work on this. They were basically implementing FEM algorithms on FPGAs instead of on a desktop. You could do a search on the stuff they came up with. Also, I'm sure they're not the only people in the world to have done such stuff.

Martyr

I'm just wondering if anyone knows or has a good 'hard to solve' maths problem that makes good use of vectorization/loops and generally shows up a slow or fast implementation.

generating large prime numbers is a CPU intensive process.
RSA,ECDSA all generate these for encryption.

Red Alert

Cheers, I'll give both of those ideas a shot.

ianhobo

On a desktop, generating RSA or key pairs, or any other "normal everyday" encryption stuff should complete relatively fast - as in a matter of second.
For a real challenge and test , go with the prime numbers!
There are prizes out there offering over a million dollars in reward if you can calculate the next one!! good luck

Cantab.

ianhobo wrote: »

On a desktop, generating RSA or key pairs, or any other "normal everyday" encryption stuff should complete relatively fast - as in a matter of second.
For a real challenge and test , go with the prime numbers!
There are prizes out there offering over a million dollars in reward if you can calculate the next one!! good luck

Yeah, but you'd need a few thousand high performance clusters with customised architectures, and a team of computer scientists/mathematicians to compete against the top prime number search groups. Plus, I'd say there are a lot of publications out there that Joe Punter in his back bedroom wouldn't have access to.

ianhobo

ha ha ha indeed
I meant it more as to have a lofty goal
I think the next unknown prime is only the 44th or 45th
The last one was found by a home distributed computer program, like the seti@home, or folding@home, so I don't think the chances of an individual and/or non-mathematician finding the next prime realistic

bonkey

ianhobo wrote: »

I think the next unknown prime is only the 44th or 45th

Close.

The largest known prime is the 44th known Mersenne Prime.

Not quite the same thing.

The last one was found by a home distributed computer program, like the seti@home, or folding@home,

It was found by the "Great Internet Mersenne Prime Search", or GIMPS.

markf909

The Fast Fourier Transform shows up quite a lot in benchmark apps.

May be worth a look.

Hobart

ianhobo wrote: »

ha ha ha indeed
I meant it more as to have a lofty goal
I think the next unknown prime is only the 44th or 45th
The last one was found by a home distributed computer program, like the seti@home, or folding@home, so I don't think the chances of an individual and/or non-mathematician finding the next prime realistic

Surely if you find the next unknown prime, it then becomes defunct? I think the whole finding the "unknown" of something would be useless, as once you know it, it ceases to be unknown .

What about looking for the smallest unknown prime number?

Michael Collins

You could always try an NP-hard problem, and see what the relative times are for getting the optimal solution from the various codes.

The only thing is each different coding system will have its own advantages and disadvantages. Like MATLAB for instance is useless with loops, but if you replace your loops with matrix operations (this can be done easily enough for most loops), this is where MATLAB will shine. Or similarly, maybe C would be excellent at solving one implementation of an FFT type problem, but inefficient at finite element type maths.

So my suggestion would be to code up maybe a mini version of a FEA solver in each platform, and check the performace. This way you're comparing like with like, and the figure of merit is very relevent to your problem.

Martyr

On a desktop, generating RSA or key pairs, or any other "normal everyday" encryption stuff should complete relatively fast - as in a matter of second.

well..it all depends on the keysize, obviously 4096 bits won't be created in a second on a normal everyday desktop, will it?