4

I'd like to write good statements in terms of speed and accuracy. If I remember correctly this line: b=(a+1)*a produces a better program than this: b=(a^2+a).

This is just an example, might be wrong but doesn't matter now, the question is: Where I can find a compendium of good practices for scientific computing?

Björn Pollex
  • 75,346
  • 28
  • 201
  • 283
MarcoS
  • 160
  • 7
  • 1
    I would target readability. Optimalisation is only and point when you have evidence it is not good enough. Compiler do a lot for you :) – RvdK Jan 24 '12 at 12:41
  • 2
    Unfortunately, one need to consider numerical stabiliy next to readability, in that case the readable version should be in the comments. – Bort Jan 24 '12 at 12:45
  • 1
    `a^2` and `a*a` are _not_ the same thing. – Lightness Races in Orbit Jan 24 '12 at 12:49
  • 1
    Regarding accuracy, the most important thing is a [good understanding of floating-point arithmetic](http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html) – Mike Seymour Jan 24 '12 at 12:51
  • @LightnessRacesinOrbit do you mind explaining that? I innocently thought they were the same – MarcoS Jan 24 '12 at 12:53
  • 1
    @MarcoS: The former is an XOR operation; the latter is a multiplication yielding an exponent operation, the equivalent of `std::pow(a, 2)`. In C++, that is. Your question is tagged `c++`. – Lightness Races in Orbit Jan 24 '12 at 12:56
  • +1 for what Mike Seymour said. For instance, when computing a summation, did you know that it can be more accurate to add numbers in ascending order of size? Is it more accurate to do pow(sqrt(x),3) or sqrt(pow(x, 3)) or x * sqrt(x)? Why? Knowing enough about how floating point numbers and standard functions work to answer these questions would put you leagues ahead of most in terms of being able to understand accuracy and error. – Patrick87 Jan 24 '12 at 15:31
  • Have a look also at Accuracy and Stability of Numerical Algorithms, by Nicholas J. Higham – Jommy Dec 18 '19 at 12:19

5 Answers5

5

You can look at Numerical Recipes in C. I am not sure if it introduces or teaches you optimization, but it is a very popular book as far as scientific computing in C goes. There may even be a book for C++.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
Sriram
  • 10,298
  • 21
  • 83
  • 136
  • 2
    the most recent edition is for C++. http://www.amazon.com/Numerical-Recipes-3rd-Scientific-Computing/dp/0521880688/ref=sr_1_1?ie=UTF8&qid=1327417693&sr=8-1 – ev-br Jan 24 '12 at 15:08
  • @Zhenya: Excellent! I have been looking for something like this for the longest time. – Samaursa Jan 24 '12 at 15:16
  • 1
    Numerical Recipes is a wonderful book, one of my favorites, but its main focus is stuff like linear algebra on computers, algorithms like FFT, writing special functions, solving ordinary and partial differential equations, etc. Pick it up, but don't think it's a book about your question. – duffymo Jan 24 '12 at 23:29
3

What you are doing here is called premature optimization, and it is the root of many evils. What you should be doing is, writing your programs, then profile them, and try to optimize the critical parts. A full compendium on optimization-techniques for scientific computing will likely be a very thick book, so you need to narrow down your problem before searching for solutions.

Community
  • 1
  • 1
Björn Pollex
  • 75,346
  • 28
  • 201
  • 283
  • 2
    -1 you seem to have missed the point here - most of the practices are to do with the accuracy part of the 'speed and accuracy', and it not a premature optimisation to ensure that a program produces correct results. – Pete Kirkham Jan 24 '12 at 12:57
  • Indeed. Premature optimisation is one thing; avoiding careful initial design in lieu of producing a _correct_ program (i.e. using the _appropriate_ data structures and yielding accurate/correct mathematical outputs) is quite another. There's a balance to be made. I'm not entirely sure as to which side of the line this question falls, mind you. – Lightness Races in Orbit Jan 24 '12 at 13:05
  • 1
    +1 @LightnessRacesinOrbit I agree with what you write above. When it comes to numerical stability etc it's a good idea to keep things as simple as possible until it is shown that complications are required. The key is most often to not even try to code things yourself but rely on numerical experts who already provide almost anything you would ever want. e.g. answer by @ Sriram – Johan Lundberg Jan 24 '12 at 13:26
1

One useful technique is to make all your functions templates on the datum type, then run the algorithm with a interval arithmetic type instead of a floating point type. This gives you an upper bound on the accuracy of the result for a given set of inputs without having to do extensive numerical analysis.

It's also important to have an idea of the expected magnitudes of your results and any intermediates, so you can tell quickly if something is wrong.

Pete Kirkham
  • 48,893
  • 5
  • 92
  • 171
0

Having a look around https://scicomp.stackexchange.com/ or even asking around there may greatly benefit you.

Best of luck!

Community
  • 1
  • 1
Zéychin
  • 4,135
  • 2
  • 28
  • 27
0

This isn't the usual "premature optimization" discussion. It's not about performance; it's accuracy that's the issue. I agree with the OP - it's very much worth paying attention to.

The biggest thing to watch for is accumulation of rounding error.

You should sort arrays into ascending order prior to adding them if you can:

http://www.ibiblio.org/pub/languages/fortran/ch4-9.html

You might find this help:

http://www.codeproject.com/Articles/25294/Avoiding-Overflow-Underflow-and-Loss-of-Precision

You need to read What Every Computer Scientist Should Know About Floating Point Arithmetic

duffymo
  • 305,152
  • 44
  • 369
  • 561