fixed_point.hpp

Go to the documentation of this file.

/*
 * Copyright (c) 2020-2024, NVIDIA CORPORATION.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
 
#pragma once
 
#include <cudf/detail/utilities/assert.cuh>
#include <cudf/fixed_point/temporary.hpp>
#include <cudf/types.hpp>
 
#include <cuda/std/limits>
#include <cuda/std/type_traits>
#include <cuda/std/utility>
 
#include <algorithm>
#include <cassert>
#include <cmath>
#include <string>
 
namespace CUDF_EXPORT numeric {
 
enum scale_type : int32_t {};
 
enum class Radix : int32_t { BASE_2 = 2, BASE_10 = 10 };
 
template <typename T>
constexpr inline auto is_supported_representation_type()
{
  return cuda::std::is_same_v<T, int32_t> ||  //
         cuda::std::is_same_v<T, int64_t> ||  //
         cuda::std::is_same_v<T, __int128_t>;
}
  // end of group
 
// Helper functions for `fixed_point` type
namespace detail {
 
template <typename Rep,
          Radix Base,
          typename T,
          typename cuda::std::enable_if_t<(cuda::std::is_same_v<int32_t, T> &&
                                           cuda::std::is_integral_v<Rep>)>* = nullptr>
CUDF_HOST_DEVICE inline constexpr Rep ipow(T exponent)
{
  cudf_assert(exponent >= 0 && "integer exponentiation with negative exponent is not possible.");
 
  if constexpr (Base == numeric::Radix::BASE_2) { return static_cast<Rep>(1) << exponent; }
 
  // Note: Including an array here introduces too much register pressure
  // https://simple.wikipedia.org/wiki/Exponentiation_by_squaring
  // This is the iterative equivalent of the recursive definition (faster)
  // Quick-bench for squaring: http://quick-bench.com/Wg7o7HYQC9FW5M0CO0wQAjSwP_Y
  if (exponent == 0) { return static_cast<Rep>(1); }
  auto extra  = static_cast<Rep>(1);
  auto square = static_cast<Rep>(Base);
  while (exponent > 1) {
    if (exponent & 1) { extra *= square; }
    exponent >>= 1;
    square *= square;
  }
  return square * extra;
}
 
template <typename Rep, Radix Rad, typename T>
CUDF_HOST_DEVICE inline constexpr T right_shift(T const& val, scale_type const& scale)
{
  return val / ipow<Rep, Rad>(static_cast<int32_t>(scale));
}
 
template <typename Rep, Radix Rad, typename T>
CUDF_HOST_DEVICE inline constexpr T left_shift(T const& val, scale_type const& scale)
{
  return val * ipow<Rep, Rad>(static_cast<int32_t>(-scale));
}
 
template <typename Rep, Radix Rad, typename T>
CUDF_HOST_DEVICE inline constexpr T shift(T const& val, scale_type const& scale)
{
  if (scale == 0) { return val; }
  if (scale > 0) { return right_shift<Rep, Rad>(val, scale); }
  return left_shift<Rep, Rad>(val, scale);
}
 
}  // namespace detail
 
template <typename Rep,
          typename cuda::std::enable_if_t<is_supported_representation_type<Rep>()>* = nullptr>
struct scaled_integer {
  Rep value;         
  scale_type scale;  
  CUDF_HOST_DEVICE inline explicit scaled_integer(Rep v, scale_type s) : value{v}, scale{s} {}
};
 
template <typename Rep, Radix Rad>
class fixed_point {
  Rep _value{};
  scale_type _scale;
 
 public:
  using rep                 = Rep;  
  static constexpr auto rad = Rad;  
 
  template <typename T,
            typename cuda::std::enable_if_t<cuda::std::is_integral_v<T> &&
                                            is_supported_representation_type<Rep>()>* = nullptr>
  CUDF_HOST_DEVICE inline explicit fixed_point(T const& value, scale_type const& scale)
    // `value` is cast to `Rep` to avoid overflow in cases where
    // constructing to `Rep` that is wider than `T`
    : _value{detail::shift<Rep, Rad>(static_cast<Rep>(value), scale)}, _scale{scale}
  {
  }
 
  CUDF_HOST_DEVICE inline explicit fixed_point(scaled_integer<Rep> s)
    : _value{s.value}, _scale{s.scale}
  {
  }
 
  template <typename T, typename cuda::std::enable_if_t<cuda::std::is_integral_v<T>>* = nullptr>
  CUDF_HOST_DEVICE inline fixed_point(T const& value)
    : _value{static_cast<Rep>(value)}, _scale{scale_type{0}}
  {
  }
 
  CUDF_HOST_DEVICE inline fixed_point() : _scale{scale_type{0}} {}
 
  template <typename U, typename cuda::std::enable_if_t<cuda::std::is_integral_v<U>>* = nullptr>
  explicit constexpr operator U() const
  {
    // Cast to the larger of the two types (of U and Rep) before converting to Rep because in
    // certain cases casting to U before shifting will result in integer overflow (i.e. if U =
    // int32_t, Rep = int64_t and _value > 2 billion)
    auto const value = std::common_type_t<U, Rep>(_value);
    return static_cast<U>(detail::shift<Rep, Rad>(value, scale_type{-_scale}));
  }
 
  CUDF_HOST_DEVICE inline operator scaled_integer<Rep>() const
  {
    return scaled_integer<Rep>{_value, _scale};
  }
 
  CUDF_HOST_DEVICE [[nodiscard]] inline rep value() const { return _value; }
 
  CUDF_HOST_DEVICE [[nodiscard]] inline scale_type scale() const { return _scale; }
 
  CUDF_HOST_DEVICE inline explicit constexpr operator bool() const
  {
    return static_cast<bool>(_value);
  }
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline fixed_point<Rep1, Rad1>& operator+=(fixed_point<Rep1, Rad1> const& rhs)
  {
    *this = *this + rhs;
    return *this;
  }
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline fixed_point<Rep1, Rad1>& operator*=(fixed_point<Rep1, Rad1> const& rhs)
  {
    *this = *this * rhs;
    return *this;
  }
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline fixed_point<Rep1, Rad1>& operator-=(fixed_point<Rep1, Rad1> const& rhs)
  {
    *this = *this - rhs;
    return *this;
  }
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline fixed_point<Rep1, Rad1>& operator/=(fixed_point<Rep1, Rad1> const& rhs)
  {
    *this = *this / rhs;
    return *this;
  }
 
  CUDF_HOST_DEVICE inline fixed_point<Rep, Rad>& operator++()
  {
    *this = *this + fixed_point<Rep, Rad>{1, scale_type{_scale}};
    return *this;
  }
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline friend fixed_point<Rep1, Rad1> operator+(
    fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline friend fixed_point<Rep1, Rad1> operator-(
    fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline friend fixed_point<Rep1, Rad1> operator*(
    fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline friend fixed_point<Rep1, Rad1> operator/(
    fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline friend fixed_point<Rep1, Rad1> operator%(
    fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline friend bool operator==(fixed_point<Rep1, Rad1> const& lhs,
                                                 fixed_point<Rep1, Rad1> const& rhs);
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline friend bool operator!=(fixed_point<Rep1, Rad1> const& lhs,
                                                 fixed_point<Rep1, Rad1> const& rhs);
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline friend bool operator<=(fixed_point<Rep1, Rad1> const& lhs,
                                                 fixed_point<Rep1, Rad1> const& rhs);
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline friend bool operator>=(fixed_point<Rep1, Rad1> const& lhs,
                                                 fixed_point<Rep1, Rad1> const& rhs);
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline friend bool operator<(fixed_point<Rep1, Rad1> const& lhs,
                                                fixed_point<Rep1, Rad1> const& rhs);
 
  template <typename Rep1, Radix Rad1>
  CUDF_HOST_DEVICE inline friend bool operator>(fixed_point<Rep1, Rad1> const& lhs,
                                                fixed_point<Rep1, Rad1> const& rhs);
 
  CUDF_HOST_DEVICE [[nodiscard]] inline fixed_point<Rep, Rad> rescaled(scale_type scale) const
  {
    if (scale == _scale) { return *this; }
    Rep const value = detail::shift<Rep, Rad>(_value, scale_type{scale - _scale});
    return fixed_point<Rep, Rad>{scaled_integer<Rep>{value, scale}};
  }
 
  explicit operator std::string() const
  {
    if (_scale < 0) {
      auto const av = detail::abs(_value);
      Rep const n   = detail::exp10<Rep>(-_scale);
      Rep const f   = av % n;
      auto const num_zeros =
        std::max(0, (-_scale - static_cast<int32_t>(detail::to_string(f).size())));
      auto const zeros = std::string(num_zeros, '0');
      auto const sign  = _value < 0 ? std::string("-") : std::string();
      return sign + detail::to_string(av / n) + std::string(".") + zeros +
             detail::to_string(av % n);
    }
    auto const zeros = std::string(_scale, '0');
    return detail::to_string(_value) + zeros;
  }
};
 
template <typename Rep, typename T>
CUDF_HOST_DEVICE inline auto addition_overflow(T lhs, T rhs)
{
  return rhs > 0 ? lhs > cuda::std::numeric_limits<Rep>::max() - rhs
                 : lhs < cuda::std::numeric_limits<Rep>::min() - rhs;
}
 
template <typename Rep, typename T>
CUDF_HOST_DEVICE inline auto subtraction_overflow(T lhs, T rhs)
{
  return rhs > 0 ? lhs < cuda::std::numeric_limits<Rep>::min() + rhs
                 : lhs > cuda::std::numeric_limits<Rep>::max() + rhs;
}
 
template <typename Rep, typename T>
CUDF_HOST_DEVICE inline auto division_overflow(T lhs, T rhs)
{
  return lhs == cuda::std::numeric_limits<Rep>::min() && rhs == -1;
}
 
template <typename Rep, typename T>
CUDF_HOST_DEVICE inline auto multiplication_overflow(T lhs, T rhs)
{
  auto const min = cuda::std::numeric_limits<Rep>::min();
  auto const max = cuda::std::numeric_limits<Rep>::max();
  if (rhs > 0) { return lhs > max / rhs || lhs < min / rhs; }
  if (rhs < -1) { return lhs > min / rhs || lhs < max / rhs; }
  return rhs == -1 && lhs == min;
}
 
// PLUS Operation
template <typename Rep1, Radix Rad1>
CUDF_HOST_DEVICE inline fixed_point<Rep1, Rad1> operator+(fixed_point<Rep1, Rad1> const& lhs,
                                                          fixed_point<Rep1, Rad1> const& rhs)
{
  auto const scale = std::min(lhs._scale, rhs._scale);
  auto const sum   = lhs.rescaled(scale)._value + rhs.rescaled(scale)._value;
 
#if defined(__CUDACC_DEBUG__)
 
  assert(!addition_overflow<Rep1>(lhs.rescaled(scale)._value, rhs.rescaled(scale)._value) &&
         "fixed_point overflow");
 
#endif
 
  return fixed_point<Rep1, Rad1>{scaled_integer<Rep1>{sum, scale}};
}
 
// MINUS Operation
template <typename Rep1, Radix Rad1>
CUDF_HOST_DEVICE inline fixed_point<Rep1, Rad1> operator-(fixed_point<Rep1, Rad1> const& lhs,
                                                          fixed_point<Rep1, Rad1> const& rhs)
{
  auto const scale = std::min(lhs._scale, rhs._scale);
  auto const diff  = lhs.rescaled(scale)._value - rhs.rescaled(scale)._value;
 
#if defined(__CUDACC_DEBUG__)
 
  assert(!subtraction_overflow<Rep1>(lhs.rescaled(scale)._value, rhs.rescaled(scale)._value) &&
         "fixed_point overflow");
 
#endif
 
  return fixed_point<Rep1, Rad1>{scaled_integer<Rep1>{diff, scale}};
}
 
// MULTIPLIES Operation
template <typename Rep1, Radix Rad1>
CUDF_HOST_DEVICE inline fixed_point<Rep1, Rad1> operator*(fixed_point<Rep1, Rad1> const& lhs,
                                                          fixed_point<Rep1, Rad1> const& rhs)
{
#if defined(__CUDACC_DEBUG__)
 
  assert(!multiplication_overflow<Rep1>(lhs._value, rhs._value) && "fixed_point overflow");
 
#endif
 
  return fixed_point<Rep1, Rad1>{
    scaled_integer<Rep1>(lhs._value * rhs._value, scale_type{lhs._scale + rhs._scale})};
}
 
// DIVISION Operation
template <typename Rep1, Radix Rad1>
CUDF_HOST_DEVICE inline fixed_point<Rep1, Rad1> operator/(fixed_point<Rep1, Rad1> const& lhs,
                                                          fixed_point<Rep1, Rad1> const& rhs)
{
#if defined(__CUDACC_DEBUG__)
 
  assert(!division_overflow<Rep1>(lhs._value, rhs._value) && "fixed_point overflow");
 
#endif
 
  return fixed_point<Rep1, Rad1>{
    scaled_integer<Rep1>(lhs._value / rhs._value, scale_type{lhs._scale - rhs._scale})};
}
 
// EQUALITY COMPARISON Operation
template <typename Rep1, Radix Rad1>
CUDF_HOST_DEVICE inline bool operator==(fixed_point<Rep1, Rad1> const& lhs,
                                        fixed_point<Rep1, Rad1> const& rhs)
{
  auto const scale = std::min(lhs._scale, rhs._scale);
  return lhs.rescaled(scale)._value == rhs.rescaled(scale)._value;
}
 
// EQUALITY NOT COMPARISON Operation
template <typename Rep1, Radix Rad1>
CUDF_HOST_DEVICE inline bool operator!=(fixed_point<Rep1, Rad1> const& lhs,
                                        fixed_point<Rep1, Rad1> const& rhs)
{
  auto const scale = std::min(lhs._scale, rhs._scale);
  return lhs.rescaled(scale)._value != rhs.rescaled(scale)._value;
}
 
// LESS THAN OR EQUAL TO Operation
template <typename Rep1, Radix Rad1>
CUDF_HOST_DEVICE inline bool operator<=(fixed_point<Rep1, Rad1> const& lhs,
                                        fixed_point<Rep1, Rad1> const& rhs)
{
  auto const scale = std::min(lhs._scale, rhs._scale);
  return lhs.rescaled(scale)._value <= rhs.rescaled(scale)._value;
}
 
// GREATER THAN OR EQUAL TO Operation
template <typename Rep1, Radix Rad1>
CUDF_HOST_DEVICE inline bool operator>=(fixed_point<Rep1, Rad1> const& lhs,
                                        fixed_point<Rep1, Rad1> const& rhs)
{
  auto const scale = std::min(lhs._scale, rhs._scale);
  return lhs.rescaled(scale)._value >= rhs.rescaled(scale)._value;
}
 
// LESS THAN Operation
template <typename Rep1, Radix Rad1>
CUDF_HOST_DEVICE inline bool operator<(fixed_point<Rep1, Rad1> const& lhs,
                                       fixed_point<Rep1, Rad1> const& rhs)
{
  auto const scale = std::min(lhs._scale, rhs._scale);
  return lhs.rescaled(scale)._value < rhs.rescaled(scale)._value;
}
 
// GREATER THAN Operation
template <typename Rep1, Radix Rad1>
CUDF_HOST_DEVICE inline bool operator>(fixed_point<Rep1, Rad1> const& lhs,
                                       fixed_point<Rep1, Rad1> const& rhs)
{
  auto const scale = std::min(lhs._scale, rhs._scale);
  return lhs.rescaled(scale)._value > rhs.rescaled(scale)._value;
}
 
// MODULO OPERATION
template <typename Rep1, Radix Rad1>
CUDF_HOST_DEVICE inline fixed_point<Rep1, Rad1> operator%(fixed_point<Rep1, Rad1> const& lhs,
                                                          fixed_point<Rep1, Rad1> const& rhs)
{
  auto const scale     = std::min(lhs._scale, rhs._scale);
  auto const remainder = lhs.rescaled(scale)._value % rhs.rescaled(scale)._value;
  return fixed_point<Rep1, Rad1>{scaled_integer<Rep1>{remainder, scale}};
}
 
using decimal32  = fixed_point<int32_t, Radix::BASE_10>;     
using decimal64  = fixed_point<int64_t, Radix::BASE_10>;     
using decimal128 = fixed_point<__int128_t, Radix::BASE_10>;  
  // end of group
}  // namespace CUDF_EXPORT numeric