Improvements to Modelica.Math.Vectors.interpolate

[DagBruck]

I suggest the following fairly simple performance improvements. They should be fully backwards compatible.

1. Special handling of nx=2
   • This is a small change that avoids the entire double iteration to find an index.
   • This case is quite common.
2. Default iLast calculated using linear interpolation.
   • If iLast is not specified by the caller, then we do a linear search from the start. This is very inefficient for all but the smallest tables.
   • Calculating an initial guess value by linear interpolation is a a reasonable alternative.
   • As far as I can tell, there is very little active use of iLast so we often fall back to the inefficient default.
3. Remove assertion x2>x1.
   • The test is not very useful because it just tests the two points where our index search stopped. It does not test the input requirement that x is non-decreasing.
   • The test clutters the code.

I also considered two more extensive changes, but do not propose them.

• Replace the linear search by binary search. This has big potential, but the implementation is complicated because the abscissa may contain several identical values. The documentation even defines what should happen.
• Remove the iLast argument and the return value iNew. This would be a significant simplification, especially because the function would just return a single number, not a pair of numbers, Also, almost nobody seems to use iLast/iNew. This would obviously be a non-compatible change.

[HansOlsson]

Just a minor note regarding binary search: If we decide to implement binary search and keep iLast there is a common doubling up variant that achieves logarithmic complexity in terms distance between the elements (commonly called searching in infinite array).

However, for many common cases interpolation to find the starting point should be good enough.

[DagBruck]

Another issue with interpolate is that the documentation seems self-contradictory. The description of the function argument x says:

Abscissa table vector (strict monotonically increasing values required)

The documentation later says (and it makes sense to me, in order to support a step change):

If x has two or more identical values then interpolation utilizes the x-value with the largest index.

My proposal is to remove "strict" from the former and implement the latter. As a side note, the current implementation is a bit unintuitive.

Modelica.Math.Vectors.interpolate({0, 0, 1, 1}, {0, 0, 0.5, 1}, 1)
User assertion failed: Abscissa table vector values must be increasing
Failed to expand Modelica.Math.Vectors.interpolate({0, 0, 1, 1}, {0, 0, 0.5, 1}, 1, 1).

Modelica.Math.Vectors.interpolate({0, 0, 1, 1, 2}, {0, 0, 0.5, 1, 2}, 1)
 = 1.0, 4