Porting everything from Coretran to stdlib

[leonfoks]

Based of @certik rundown of his fortran-utils!

I think Coretran has some useful stuff that could go into stdlib.
Here is what's in Coretran at the moment. I will list from more to less important.
Important, None of my routines handle arbitrary defined types. I.e. I can't sort an array of Joe's custom made classes.

Random

I have implemented the Xorshift128+ algorithm that lets you jump the state of the PRNG. I need to switch to Xoroshiro128+/* because I read that it's more robust. Most languages provide a Mersenne Twister generator, but its not good for parallel applications. My PRNG is OO and thread safe since a local state is used on each thread.

• Random number generator.
• Distributions to generate random numbers from. Normal, Gamma, Weibull etc. This is not a complete section.

Dynamic Arrays

I think these are akin to C++ vectors? OO.
Memory starts low, as entries are added, memory is reallocated only when its full and increases by a set factor. Similarly, if entries are removed the memory is only reallocated once it is 25% full.
Overloaded for r32, r64, i32, i64.

• dynamic_array
• arg_dynamic_array

Searching

These will be fundamental when it comes to developing other functions within the stdlib if we want fast algorithms.

• Brute force search, this is needed for small arrays and is faster than Binary for less than like 16 values.
• Binary Search
• Interval Search

Sorting (#98)

• I have an introspection sort that primarily uses a Quicksort with a Median of 3 pivot. Quicksort goes N^2 for already sorted listed (or nearly sorted) so I swing off into a heap sort at the point at which the quicksort would be slower. These two are unstable sorts. I have a merge sort as well with an extra O(N) memory is stability is required. On average this is O(nlogn). Handles tail recursion by switching to an insertion sort when we are less than 16 values.
  I think a TimSort is better than a quicksort from what I gather but I could never implement it. And from Sparse matrix support #38 a quicksort wont be great for sparse things.

Spatial

• K-Dimensional KdTree. OO with both a KdTree class, and KdTreeSearch to make searches thread safe. At each iteration the tree is split at the median along the dimension with the highest variance which keeps it balanced. (Hence why I needed a quick median algorithm.)

Geometry

I implemented Shewchuk's algorithms for exactly computing whether a point is inside the a) circumcircle of a triangle or b) the circumsphere of a tetrahedron. I was going to use this to write a Delaunay triangulation and/or Voronoi mesh. Shewchuk's algorithms use the naive determinant of a matrix, and add terms if needed until the computation is exact. It handles floating point round-off error.

• Robust predicates for fast adaptive floating point arithmetic.

Maths

• Median. I use an on average O(n) quickselect to find median values.

• cumsum. Should this be a Kahan summation?

• cumprod

• std

• mean

• etc!

• Types (Already in stdlib_experimental_kinds.f90)
  My entire library is built around these so its easy at least to switch those out.