| * Routines for selecting the k largest or smallest values could use |
| heapsort for speed O(N log k) rather than insertion O(N k). |
| |
| * Sorting of complex arrarys without using additional memory. We try |
| to avoid allocating memory internally in GSL, so internally computing |
| the magnitudes and storing them in a temporary array is undesirable. |
| |
| Obviously a complex array can be sorted using sqrt(x*x + y*y) <=> |
| sqrt(u*u + v*v) (written in a numerically stable way) for every |
| comparison, but this may be unacceptably slow. Maybe not? It is just a |
| constant factor. The square roots could sometimes be avoided by |
| optimization, |
| |
| (x,y) = (MAX(|x|,|y|), MIN(|x|,|y|)) |
| (u,v) = (MAX(|u|,|v|), MIN(|u|,|v|)) |
| |
| if (x < u/sqrt(2)) /* This part is optional optimization */ |
| return -1 |
| if (x > u*sqrt(2)) |
| return +1 |
| |
| if (x == 0 && u == 0) ... |
| if (x == 0) ... |
| if (u == 0) ... |
| |
| t = u*sqrt((1+(v/u)^2)/(1+(y/x)^2)) |
| |
| if (x < t) |
| return -1 |
| if (x > t) |
| return +1 |
| else |
| return 0 |
| |
| but this does depend on the data having sufficient range for the |
| optimization to be worthwhile, otherwise it is an extra cost. |
