Implement std::midpoint for floating point types

[mclow.lists]

Summary

finish up the implementation of std::midpoint - add the floating point implementation.
Add a new header file in test/support for doing FP testing.

Set the feature test macros; even though we don't do lerp yet - that's coming next.

[mclow.lists]

For some reason; the tests didn't get included.

[EricWF]

Can you update utils/generate_feature_test_macro_components.py and re-running it?

libcxx/include/numeric

573

Can you update the #endif to comment what it's closing?

libcxx/include/version

58

These changes should be made by updating utils/generate_feature_test_macro_components.py and re-running it.

[zoecarver]

libcxx/include/numeric

148

Is there any overlap between cmath and numeric which might confuse the compiler?

libcxx/include/version

226

nit: every other line has a space between # and define.

[zoecarver]

libcxx/test/std/numerics/numeric.ops/numeric.ops.midpoint/midpoint.float.pass.cpp

40

Another nit: maybe use ASSERT_SAME_TYPE?

[mclow.lists]

Updated the <version> header using the tool.
Fixed the check to use ASSERT_SAME_TYPE and ASSERT_NOEXCEPT

[mclow.lists]

libcxx/include/numeric

148

I don't think so. I played around a bit; ran the whole test suite.

[zoecarver]

LGTM :)

libcxx/include/numeric

148

Okay, nevermind then.

[EricWF]

This LGTM.

libcxx/include/numeric

568

I'm not sure it matters, but I would prefer if the calls to abs and isnormal were qualified.

libcxx/test/support/fp_compare.h

40

Should 100.0 be cast to T to avoid promotion?

[mclow.lists]

Committed as revision 359184

libcxx/test/support/fp_compare.h

40

Done.

[a_Tom]

libcxx/include/numeric

559

Shouldn't this function be constexpr?

[zoecarver]

libcxx/include/numeric

564

Also, maybe use _LIBCPP_CONSTEXPR.

[mclow.lists]

libcxx/include/numeric

564

We don't use _LIBCPP_CONSTEXPR in new code - code that requires C++20 (for example), because we assume that modern compilers support constexpr. _LIBCPP_CONSTEXPR is mostly useful for things that should be constexpr, but either (a) have to exist in C++03/11, or (b) for supporting compilers that have incomplete implementations of constexpr.

I am aware that we are not 100% consistent on this.

[mclow.lists]

libcxx/include/numeric

559

Yes, it should - and it is now.

libcxx/docs/FeatureTestMacroTable.rst

     ------------------------------------------------- -----------------
     ``__cpp_lib_generic_unordered_lookup``            *unimplemented*  
     ------------------------------------------------- -----------------
+    ``__cpp_lib_interpolate``                         ``201902L``      
+    ------------------------------------------------- -----------------
     ``__cpp_lib_is_constant_evaluated``               *unimplemented*  
     ------------------------------------------------- -----------------
     ``__cpp_lib_list_remove_return_type``             *unimplemented*  

libcxx/include/numeric

 #include <iterator>
 #include <limits> // for numeric_limits
 #include <functional>
+#include <cmath> // for isnormal
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

 {
     return __a + _VSTD::midpoint(ptrdiff_t(0), __b - __a);
 }
+
+
+template <typename _Tp>
+int __sign(_Tp __val) {
+    return (_Tp(0) < __val) - (__val < _Tp(0));
+}
+
+template <class _Fp>
+_LIBCPP_INLINE_VISIBILITY constexpr
+enable_if_t<is_floating_point_v<_Fp>, _Fp>
+midpoint(_Fp __a, _Fp __b) noexcept
+{
+    return isnormal(__a) && isnormal(__b) 
+       && ((__sign(__a) != __sign(__b)) || ((numeric_limits<_Fp>::max() - abs(__a)) < abs(__b)))
+             ?  __a / 2 + __b / 2
+             : (__a + __b) / 2;
+}
 #endif
 
 _LIBCPP_END_NAMESPACE_STD

libcxx/include/version

 __cpp_lib_incomplete_container_elements                 201505L <forward_list> <list> <vector>
 __cpp_lib_integer_sequence                              201304L <utility>
 __cpp_lib_integral_constant_callable                    201304L <type_traits>
+__cpp_lib_interpolate                                   201902L <numeric>
 __cpp_lib_invoke                                        201411L <functional>
 __cpp_lib_is_aggregate                                  201703L <type_traits>
 __cpp_lib_is_constant_evaluated                         201811L <type_traits>

 // # define __cpp_lib_destroying_delete                    201806L
 # define __cpp_lib_erase_if                             201811L
 // # define __cpp_lib_generic_unordered_lookup             201811L
+# define __cpp_lib_interpolate                          201902L
 // # define __cpp_lib_is_constant_evaluated                201811L
 // # define __cpp_lib_list_remove_return_type              201806L
 // # define __cpp_lib_ranges                               201811L

libcxx/test/std/language.support/support.limits/support.limits.general/numeric.version.pass.cpp

 
 /*  Constant                        Value
     __cpp_lib_gcd_lcm               201606L [C++17]
+    __cpp_lib_interpolate           201902L [C++2a]
     __cpp_lib_parallel_algorithm    201603L [C++17]
 */
 

 #   error "__cpp_lib_gcd_lcm should not be defined before c++17"
 # endif
 
+# ifdef __cpp_lib_interpolate
+#   error "__cpp_lib_interpolate should not be defined before c++2a"
+# endif
+
 # ifdef __cpp_lib_parallel_algorithm
 #   error "__cpp_lib_parallel_algorithm should not be defined before c++17"
 # endif

 #   error "__cpp_lib_gcd_lcm should not be defined before c++17"
 # endif
 
+# ifdef __cpp_lib_interpolate
+#   error "__cpp_lib_interpolate should not be defined before c++2a"
+# endif
+
 # ifdef __cpp_lib_parallel_algorithm
 #   error "__cpp_lib_parallel_algorithm should not be defined before c++17"
 # endif

 #   error "__cpp_lib_gcd_lcm should have the value 201606L in c++17"
 # endif
 
+# ifdef __cpp_lib_interpolate
+#   error "__cpp_lib_interpolate should not be defined before c++2a"
+# endif
+
 # if !defined(_LIBCPP_VERSION)
 #   ifndef __cpp_lib_parallel_algorithm
 #     error "__cpp_lib_parallel_algorithm should be defined in c++17"

 #   error "__cpp_lib_gcd_lcm should have the value 201606L in c++2a"
 # endif
 
+# ifndef __cpp_lib_interpolate
+#   error "__cpp_lib_interpolate should be defined in c++2a"
+# endif
+# if __cpp_lib_interpolate != 201902L
+#   error "__cpp_lib_interpolate should have the value 201902L in c++2a"
+# endif
+
 # if !defined(_LIBCPP_VERSION)
 #   ifndef __cpp_lib_parallel_algorithm
 #     error "__cpp_lib_parallel_algorithm should be defined in c++2a"

libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp

     __cpp_lib_incomplete_container_elements        201505L [C++17]
     __cpp_lib_integer_sequence                     201304L [C++14]
     __cpp_lib_integral_constant_callable           201304L [C++14]
+    __cpp_lib_interpolate                          201902L [C++2a]
     __cpp_lib_invoke                               201411L [C++17]
     __cpp_lib_is_aggregate                         201703L [C++17]
     __cpp_lib_is_constant_evaluated                201811L [C++2a]

 #   error "__cpp_lib_integral_constant_callable should not be defined before c++14"
 # endif
 
+# ifdef __cpp_lib_interpolate
+#   error "__cpp_lib_interpolate should not be defined before c++2a"
+# endif
+
 # ifdef __cpp_lib_invoke
 #   error "__cpp_lib_invoke should not be defined before c++17"
 # endif

 #   error "__cpp_lib_integral_constant_callable should have the value 201304L in c++14"
 # endif
 
+# ifdef __cpp_lib_interpolate
+#   error "__cpp_lib_interpolate should not be defined before c++2a"
+# endif
+
 # ifdef __cpp_lib_invoke
 #   error "__cpp_lib_invoke should not be defined before c++17"
 # endif

 #   error "__cpp_lib_integral_constant_callable should have the value 201304L in c++17"
 # endif
 
+# ifdef __cpp_lib_interpolate
+#   error "__cpp_lib_interpolate should not be defined before c++2a"
+# endif
+
 # ifndef __cpp_lib_invoke
 #   error "__cpp_lib_invoke should be defined in c++17"
 # endif

 #   error "__cpp_lib_integral_constant_callable should have the value 201304L in c++2a"
 # endif
 
+# ifndef __cpp_lib_interpolate
+#   error "__cpp_lib_interpolate should be defined in c++2a"
+# endif
+# if __cpp_lib_interpolate != 201902L
+#   error "__cpp_lib_interpolate should have the value 201902L in c++2a"
+# endif
+
 # ifndef __cpp_lib_invoke
 #   error "__cpp_lib_invoke should be defined in c++2a"
 # endif

libcxx/test/std/numerics/numeric.ops/numeric.ops.midpoint/midpoint.float.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+// <numeric>
+
+// template <class _Float>
+// _Tp midpoint(_Float __a, _Float __b) noexcept
+//
+
+#include <numeric>
+#include <cassert>
+
+#include "test_macros.h"
+#include "fp_compare.h"
+
+//  Totally arbitrary picks for precision
+template <typename T>
+constexpr T fp_error_pct();
+
+template <>
+constexpr float fp_error_pct<float>() { return 1.0e-4f; }
+
+template <>
+constexpr double fp_error_pct<double>() { return 1.0e-12; }
+
+template <>
+constexpr long double fp_error_pct<long double>() { return 1.0e-13l; }
+
+
+template <typename T>
+void fp_test()
+{
+    ASSERT_SAME_TYPE(T, decltype(std::midpoint(T(), T())));
+    ASSERT_NOEXCEPT(             std::midpoint(T(), T()));
+
+    constexpr T maxV = std::numeric_limits<T>::max();
+    constexpr T minV = std::numeric_limits<T>::min();
+    
+//  Things that can be compared exactly
+    assert((std::midpoint(T(0), T(0)) == T(0)));
+    assert((std::midpoint(T(2), T(4)) == T(3)));
+    assert((std::midpoint(T(4), T(2)) == T(3)));
+    assert((std::midpoint(T(3), T(4)) == T(3.5)));
+    assert((std::midpoint(T(0), T(0.4)) == T(0.2)));
+
+//  Things that can't be compared exactly
+    constexpr T pct = fp_error_pct<T>();
+    assert((fptest_close_pct(std::midpoint(T( 1.3), T(11.4)), T( 6.35),    pct)));
+    assert((fptest_close_pct(std::midpoint(T(11.33), T(31.45)), T(21.39),  pct)));
+    assert((fptest_close_pct(std::midpoint(T(-1.3), T(11.4)), T( 5.05),    pct)));
+    assert((fptest_close_pct(std::midpoint(T(11.4), T(-1.3)), T( 5.05),    pct)));
+    assert((fptest_close_pct(std::midpoint(T(0.1),  T(0.4)),  T(0.25),     pct)));
+
+    assert((fptest_close_pct(std::midpoint(T(11.2345), T(14.5432)), T(12.88885),  pct)));
+    
+//  From e to pi
+    assert((fptest_close_pct(std::midpoint(T(2.71828182845904523536028747135266249775724709369995),
+                                      T(3.14159265358979323846264338327950288419716939937510)),
+                                      T(2.92993724102441923691146542731608269097720824653752),  pct)));
+
+    assert((fptest_close_pct(std::midpoint(maxV, T(0)), maxV/2, pct)));
+    assert((fptest_close_pct(std::midpoint(T(0), maxV), maxV/2, pct)));
+    assert((fptest_close_pct(std::midpoint(minV, T(0)), minV/2, pct)));
+    assert((fptest_close_pct(std::midpoint(T(0), minV), minV/2, pct)));
+    assert((fptest_close_pct(std::midpoint(maxV, maxV), maxV,   pct)));
+    assert((fptest_close_pct(std::midpoint(minV, minV), minV,   pct)));
+
+//  Denormalized values
+//  TODO
+
+//  Check two values "close to each other"
+    T d1 = 3.14;
+    T d0 = std::nexttoward(d1, T(2));
+    T d2 = std::nexttoward(d1, T(5));
+    assert(d0 < d1);  // sanity checking
+    assert(d1 < d2);  // sanity checking
+
+//  Since there's nothing in between, the midpoint has to be one or the other
+    T res;
+    res = std::midpoint(d0, d1);
+    assert(res == d0 || res == d1);
+    assert(d0 <= res);
+    assert(res <= d1);
+    res = std::midpoint(d1, d0);
+    assert(res == d0 || res == d1);
+    assert(d0 <= res);
+    assert(res <= d1);
+
+    res = std::midpoint(d1, d2);
+    assert(res == d1 || res == d2);
+    assert(d1 <= res);
+    assert(res <= d2);
+    res = std::midpoint(d2, d1);
+    assert(res == d1 || res == d2);
+    assert(d1 <= res);
+    assert(res <= d2);
+}
+
+
+int main (int, char**)
+{
+    fp_test<float>();
+    fp_test<double>();
+    fp_test<long double>();
+
+    return 0;
+}

libcxx/test/support/fp_compare.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#ifndef SUPPORT_FP_COMPARE_H
+#define SUPPORT_FP_COMPARE_H
+
+#include <cmath>      // for std::abs
+#include <algorithm>  // for std::max
+#include <cassert>
+
+// See https://www.boost.org/doc/libs/1_70_0/libs/test/doc/html/boost_test/testing_tools/extended_comparison/floating_point/floating_points_comparison_theory.html
+
+template<typename T>
+bool fptest_close(T val, T expected, T eps)
+{
+  constexpr T zero = T(0);
+  assert(eps >= zero);
+
+//  Handle the zero cases
+  if (eps      == zero) return val == expected;
+  if (val      == zero) return std::abs(expected) <= eps;
+  if (expected == zero) return std::abs(val)      <= eps;
+
+  return std::abs(val - expected) < eps
+      && std::abs(val - expected)/std::abs(val) < eps;
+}
+
+template<typename T>
+bool fptest_close_pct(T val, T expected, T percent)
+{
+  constexpr T zero = T(0);
+  assert(percent >= zero);
+
+//  Handle the zero cases
+  if (percent == zero) return val == expected;
+  T eps = (percent / 100.0) * std::max(std::abs(val), std::abs(expected));
+
+  return fptest_close(val, expected, eps);
+}
+
+
+#endif // SUPPORT_FP_COMPARE_H

libcxx/utils/generate_feature_test_macro_components.py

    "depends": "!defined(_LIBCPP_HAS_NO_THREADS)",
    "internal_depends": "!defined(_LIBCPP_HAS_NO_THREADS)",
    },
+  {"name": "__cpp_lib_interpolate",
+   "values": {
+     "c++2a": 201902L,
+   },
+   "headers": ["numeric"],
+   },
 ]], key=lambda tc: tc["name"])
 
 def get_std_dialects():