fixed_point.hpp
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2020-2025, NVIDIA CORPORATION.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #include <cudf/detail/utilities/assert.cuh>
20 #include <cudf/fixed_point/temporary.hpp>
21 #include <cudf/types.hpp>
22 
23 #include <cuda/std/functional>
24 #include <cuda/std/limits>
25 #include <cuda/std/type_traits>
26 #include <cuda/std/utility>
27 
28 #include <algorithm>
29 #include <cassert>
30 #include <cmath>
31 #include <string>
32 
34 namespace CUDF_EXPORT numeric {
35 
44 enum scale_type : int32_t {};
45 
55 enum class Radix : int32_t { BASE_2 = 2, BASE_10 = 10 };
56 
63 template <typename T>
65 {
66  return cuda::std::is_same_v<T, int32_t> || //
67  cuda::std::is_same_v<T, int64_t> || //
68  cuda::std::is_same_v<T, __int128_t>;
69 }
70  // end of group
72 
73 // Helper functions for `fixed_point` type
74 namespace detail {
75 
84 template <typename Rep,
85  Radix Base,
86  typename T,
87  typename cuda::std::enable_if_t<(cuda::std::is_same_v<int32_t, T> &&
88  cuda::std::is_integral_v<Rep>)>* = nullptr>
89 CUDF_HOST_DEVICE inline constexpr Rep ipow(T exponent)
90 {
91  cudf_assert(exponent >= 0 && "integer exponentiation with negative exponent is not possible.");
92 
93  if constexpr (Base == numeric::Radix::BASE_2) { return static_cast<Rep>(1) << exponent; }
94 
95  // Note: Including an array here introduces too much register pressure
96  // https://simple.wikipedia.org/wiki/Exponentiation_by_squaring
97  // This is the iterative equivalent of the recursive definition (faster)
98  // Quick-bench for squaring: http://quick-bench.com/Wg7o7HYQC9FW5M0CO0wQAjSwP_Y
99  if (exponent == 0) { return static_cast<Rep>(1); }
100  auto extra = static_cast<Rep>(1);
101  auto square = static_cast<Rep>(Base);
102  while (exponent > 1) {
103  if (exponent & 1) { extra *= square; }
104  exponent >>= 1;
105  square *= square;
106  }
107  return square * extra;
108 }
109 
121 template <typename Rep, Radix Rad, typename T>
122 CUDF_HOST_DEVICE inline constexpr T right_shift(T const& val, scale_type const& scale)
123 {
124  return val / ipow<Rep, Rad>(static_cast<int32_t>(scale));
125 }
126 
138 template <typename Rep, Radix Rad, typename T>
139 CUDF_HOST_DEVICE inline constexpr T left_shift(T const& val, scale_type const& scale)
140 {
141  return val * ipow<Rep, Rad>(static_cast<int32_t>(-scale));
142 }
143 
157 template <typename Rep, Radix Rad, typename T>
158 CUDF_HOST_DEVICE inline constexpr T shift(T const& val, scale_type const& scale)
159 {
160  if (scale == 0) { return val; }
161  if (scale > 0) { return right_shift<Rep, Rad>(val, scale); }
162  return left_shift<Rep, Rad>(val, scale);
163 }
164 
165 } // namespace detail
166 
185 template <typename Rep,
186  typename cuda::std::enable_if_t<is_supported_representation_type<Rep>()>* = nullptr>
188  Rep value;
196  CUDF_HOST_DEVICE inline explicit scaled_integer(Rep v, scale_type s) : value{v}, scale{s} {}
197 };
198 
208 template <typename Rep, Radix Rad>
209 class fixed_point {
210  Rep _value{};
211  scale_type _scale;
212 
213  public:
214  using rep = Rep;
215  static constexpr auto rad = Rad;
216 
225  template <typename T,
226  typename cuda::std::enable_if_t<cuda::std::is_integral_v<T> &&
227  is_supported_representation_type<Rep>()>* = nullptr>
228  CUDF_HOST_DEVICE inline explicit fixed_point(T const& value, scale_type const& scale)
229  // `value` is cast to `Rep` to avoid overflow in cases where
230  // constructing to `Rep` that is wider than `T`
231  : _value{detail::shift<Rep, Rad>(static_cast<Rep>(value), scale)}, _scale{scale}
232  {
233  }
234 
241  : _value{s.value}, _scale{s.scale}
242  {
243  }
244 
252  template <typename T, typename cuda::std::enable_if_t<cuda::std::is_integral_v<T>>* = nullptr>
253  CUDF_HOST_DEVICE inline fixed_point(T const& value)
254  : _value{static_cast<Rep>(value)}, _scale{scale_type{0}}
255  {
256  }
257 
262  CUDF_HOST_DEVICE inline fixed_point() : _scale{scale_type{0}} {}
263 
270  template <typename U, typename cuda::std::enable_if_t<cuda::std::is_integral_v<U>>* = nullptr>
271  CUDF_HOST_DEVICE explicit constexpr operator U() const
272  {
273  // Cast to the larger of the two types (of U and Rep) before converting to Rep because in
274  // certain cases casting to U before shifting will result in integer overflow (i.e. if U =
275  // int32_t, Rep = int64_t and _value > 2 billion)
276  auto const value = cuda::std::common_type_t<U, Rep>(_value);
277  return static_cast<U>(detail::shift<Rep, Rad>(value, scale_type{-_scale}));
278  }
279 
285  CUDF_HOST_DEVICE inline operator scaled_integer<Rep>() const
286  {
287  return scaled_integer<Rep>{_value, _scale};
288  }
289 
295  CUDF_HOST_DEVICE [[nodiscard]] inline rep value() const { return _value; }
296 
302  CUDF_HOST_DEVICE [[nodiscard]] inline scale_type scale() const { return _scale; }
303 
309  CUDF_HOST_DEVICE inline explicit constexpr operator bool() const
310  {
311  return static_cast<bool>(_value);
312  }
313 
322  template <typename Rep1, Radix Rad1>
324  {
325  *this = *this + rhs;
326  return *this;
327  }
328 
337  template <typename Rep1, Radix Rad1>
339  {
340  *this = *this * rhs;
341  return *this;
342  }
343 
352  template <typename Rep1, Radix Rad1>
354  {
355  *this = *this - rhs;
356  return *this;
357  }
358 
367  template <typename Rep1, Radix Rad1>
369  {
370  *this = *this / rhs;
371  return *this;
372  }
373 
380  {
381  *this = *this + fixed_point<Rep, Rad>{1, scale_type{_scale}};
382  return *this;
383  }
384 
398  template <typename Rep1, Radix Rad1>
400  fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
401 
415  template <typename Rep1, Radix Rad1>
417  fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
418 
430  template <typename Rep1, Radix Rad1>
432  fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
433 
445  template <typename Rep1, Radix Rad1>
447  fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
448 
462  template <typename Rep1, Radix Rad1>
464  fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
465 
479  template <typename Rep1, Radix Rad1>
480  CUDF_HOST_DEVICE inline friend bool operator==(fixed_point<Rep1, Rad1> const& lhs,
481  fixed_point<Rep1, Rad1> const& rhs);
482 
496  template <typename Rep1, Radix Rad1>
497  CUDF_HOST_DEVICE inline friend bool operator!=(fixed_point<Rep1, Rad1> const& lhs,
498  fixed_point<Rep1, Rad1> const& rhs);
499 
513  template <typename Rep1, Radix Rad1>
514  CUDF_HOST_DEVICE inline friend bool operator<=(fixed_point<Rep1, Rad1> const& lhs,
515  fixed_point<Rep1, Rad1> const& rhs);
516 
530  template <typename Rep1, Radix Rad1>
531  CUDF_HOST_DEVICE inline friend bool operator>=(fixed_point<Rep1, Rad1> const& lhs,
532  fixed_point<Rep1, Rad1> const& rhs);
533 
547  template <typename Rep1, Radix Rad1>
548  CUDF_HOST_DEVICE inline friend bool operator<(fixed_point<Rep1, Rad1> const& lhs,
549  fixed_point<Rep1, Rad1> const& rhs);
550 
564  template <typename Rep1, Radix Rad1>
565  CUDF_HOST_DEVICE inline friend bool operator>(fixed_point<Rep1, Rad1> const& lhs,
566  fixed_point<Rep1, Rad1> const& rhs);
567 
577  CUDF_HOST_DEVICE [[nodiscard]] inline fixed_point<Rep, Rad> rescaled(scale_type scale) const
578  {
579  if (scale == _scale) { return *this; }
580  Rep const value = detail::shift<Rep, Rad>(_value, scale_type{scale - _scale});
581  return fixed_point<Rep, Rad>{scaled_integer<Rep>{value, scale}};
582  }
583 
587  explicit operator std::string() const
588  {
589  if (_scale < 0) {
590  auto const av = detail::abs(_value);
591  Rep const n = detail::exp10<Rep>(-_scale);
592  Rep const f = av % n;
593  auto const num_zeros =
594  std::max(0, (-_scale - static_cast<int32_t>(detail::to_string(f).size())));
595  auto const zeros = std::string(num_zeros, '0');
596  auto const sign = _value < 0 ? std::string("-") : std::string();
597  return sign + detail::to_string(av / n) + std::string(".") + zeros +
598  detail::to_string(av % n);
599  }
600  auto const zeros = std::string(_scale, '0');
601  return detail::to_string(_value) + zeros;
602  }
603 };
604 
614 template <typename Rep, typename T>
615 CUDF_HOST_DEVICE inline auto addition_overflow(T lhs, T rhs)
616 {
617  return rhs > 0 ? lhs > cuda::std::numeric_limits<Rep>::max() - rhs
618  : lhs < cuda::std::numeric_limits<Rep>::min() - rhs;
619 }
620 
629 template <typename Rep, typename T>
630 CUDF_HOST_DEVICE inline auto subtraction_overflow(T lhs, T rhs)
631 {
632  return rhs > 0 ? lhs < cuda::std::numeric_limits<Rep>::min() + rhs
633  : lhs > cuda::std::numeric_limits<Rep>::max() + rhs;
634 }
635 
644 template <typename Rep, typename T>
645 CUDF_HOST_DEVICE inline auto division_overflow(T lhs, T rhs)
646 {
647  return lhs == cuda::std::numeric_limits<Rep>::min() && rhs == -1;
648 }
649 
658 template <typename Rep, typename T>
659 CUDF_HOST_DEVICE inline auto multiplication_overflow(T lhs, T rhs)
660 {
661  auto const min = cuda::std::numeric_limits<Rep>::min();
662  auto const max = cuda::std::numeric_limits<Rep>::max();
663  if (rhs > 0) { return lhs > max / rhs || lhs < min / rhs; }
664  if (rhs < -1) { return lhs > min / rhs || lhs < max / rhs; }
665  return rhs == -1 && lhs == min;
666 }
667 
668 // PLUS Operation
669 template <typename Rep1, Radix Rad1>
671  fixed_point<Rep1, Rad1> const& rhs)
672 {
673  auto const scale = cuda::std::min(lhs._scale, rhs._scale);
674  auto const sum = lhs.rescaled(scale)._value + rhs.rescaled(scale)._value;
675 
676 #if defined(__CUDACC_DEBUG__)
677 
678  assert(!addition_overflow<Rep1>(lhs.rescaled(scale)._value, rhs.rescaled(scale)._value) &&
679  "fixed_point overflow");
680 
681 #endif
682 
683  return fixed_point<Rep1, Rad1>{scaled_integer<Rep1>{sum, scale}};
684 }
685 
686 // MINUS Operation
687 template <typename Rep1, Radix Rad1>
689  fixed_point<Rep1, Rad1> const& rhs)
690 {
691  auto const scale = cuda::std::min(lhs._scale, rhs._scale);
692  auto const diff = lhs.rescaled(scale)._value - rhs.rescaled(scale)._value;
693 
694 #if defined(__CUDACC_DEBUG__)
695 
696  assert(!subtraction_overflow<Rep1>(lhs.rescaled(scale)._value, rhs.rescaled(scale)._value) &&
697  "fixed_point overflow");
698 
699 #endif
700 
701  return fixed_point<Rep1, Rad1>{scaled_integer<Rep1>{diff, scale}};
702 }
703 
704 // MULTIPLIES Operation
705 template <typename Rep1, Radix Rad1>
707  fixed_point<Rep1, Rad1> const& rhs)
708 {
709 #if defined(__CUDACC_DEBUG__)
710 
711  assert(!multiplication_overflow<Rep1>(lhs._value, rhs._value) && "fixed_point overflow");
712 
713 #endif
714 
716  scaled_integer<Rep1>(lhs._value * rhs._value, scale_type{lhs._scale + rhs._scale})};
717 }
718 
719 // DIVISION Operation
720 template <typename Rep1, Radix Rad1>
722  fixed_point<Rep1, Rad1> const& rhs)
723 {
724 #if defined(__CUDACC_DEBUG__)
725 
726  assert(!division_overflow<Rep1>(lhs._value, rhs._value) && "fixed_point overflow");
727 
728 #endif
729 
731  scaled_integer<Rep1>(lhs._value / rhs._value, scale_type{lhs._scale - rhs._scale})};
732 }
733 
734 // EQUALITY COMPARISON Operation
735 template <typename Rep1, Radix Rad1>
737  fixed_point<Rep1, Rad1> const& rhs)
738 {
739  auto const scale = cuda::std::min(lhs._scale, rhs._scale);
740  return lhs.rescaled(scale)._value == rhs.rescaled(scale)._value;
741 }
742 
743 // EQUALITY NOT COMPARISON Operation
744 template <typename Rep1, Radix Rad1>
746  fixed_point<Rep1, Rad1> const& rhs)
747 {
748  auto const scale = cuda::std::min(lhs._scale, rhs._scale);
749  return lhs.rescaled(scale)._value != rhs.rescaled(scale)._value;
750 }
751 
752 // LESS THAN OR EQUAL TO Operation
753 template <typename Rep1, Radix Rad1>
755  fixed_point<Rep1, Rad1> const& rhs)
756 {
757  auto const scale = cuda::std::min(lhs._scale, rhs._scale);
758  return lhs.rescaled(scale)._value <= rhs.rescaled(scale)._value;
759 }
760 
761 // GREATER THAN OR EQUAL TO Operation
762 template <typename Rep1, Radix Rad1>
764  fixed_point<Rep1, Rad1> const& rhs)
765 {
766  auto const scale = cuda::std::min(lhs._scale, rhs._scale);
767  return lhs.rescaled(scale)._value >= rhs.rescaled(scale)._value;
768 }
769 
770 // LESS THAN Operation
771 template <typename Rep1, Radix Rad1>
773  fixed_point<Rep1, Rad1> const& rhs)
774 {
775  auto const scale = cuda::std::min(lhs._scale, rhs._scale);
776  return lhs.rescaled(scale)._value < rhs.rescaled(scale)._value;
777 }
778 
779 // GREATER THAN Operation
780 template <typename Rep1, Radix Rad1>
782  fixed_point<Rep1, Rad1> const& rhs)
783 {
784  auto const scale = cuda::std::min(lhs._scale, rhs._scale);
785  return lhs.rescaled(scale)._value > rhs.rescaled(scale)._value;
786 }
787 
788 // MODULO OPERATION
789 template <typename Rep1, Radix Rad1>
791  fixed_point<Rep1, Rad1> const& rhs)
792 {
793  auto const scale = cuda::std::min(lhs._scale, rhs._scale);
794  auto const remainder = lhs.rescaled(scale)._value % rhs.rescaled(scale)._value;
795  return fixed_point<Rep1, Rad1>{scaled_integer<Rep1>{remainder, scale}};
796 }
797 
801  // end of group
803 } // namespace CUDF_EXPORT numeric
A type for representing a number with a fixed amount of precision.
CUDF_HOST_DEVICE fixed_point(scaled_integer< Rep > s)
Constructor that will not perform shifting (assumes value already shifted)
CUDF_HOST_DEVICE fixed_point< Rep, Rad > rescaled(scale_type scale) const
Method for creating a fixed_point number with a new scale
CUDF_HOST_DEVICE rep value() const
Method that returns the underlying value of the fixed_point number.
CUDF_HOST_DEVICE fixed_point< Rep1, Rad1 > & operator*=(fixed_point< Rep1, Rad1 > const &rhs)
operator *=
CUDF_HOST_DEVICE scale_type scale() const
Method that returns the scale of the fixed_point number.
CUDF_HOST_DEVICE fixed_point(T const &value)
"Scale-less" constructor that constructs fixed_point number with a specified value and scale of zero
CUDF_HOST_DEVICE fixed_point< Rep1, Rad1 > & operator-=(fixed_point< Rep1, Rad1 > const &rhs)
operator -=
CUDF_HOST_DEVICE fixed_point< Rep1, Rad1 > & operator+=(fixed_point< Rep1, Rad1 > const &rhs)
operator +=
Rep rep
The representation type.
CUDF_HOST_DEVICE fixed_point()
Default constructor that constructs fixed_point number with a value and scale of zero.
CUDF_HOST_DEVICE fixed_point< Rep1, Rad1 > & operator/=(fixed_point< Rep1, Rad1 > const &rhs)
operator /=
CUDF_HOST_DEVICE fixed_point(T const &value, scale_type const &scale)
Constructor that will perform shifting to store value appropriately (from integral types)
CUDF_HOST_DEVICE fixed_point< Rep, Rad > & operator++()
operator ++ (post-increment)
constexpr CUDF_HOST_DEVICE T left_shift(T const &val, scale_type const &scale)
Function that performs a left shift scale "times" on the val
constexpr CUDF_HOST_DEVICE Rep ipow(T exponent)
A function for integer exponentiation by squaring.
Definition: fixed_point.hpp:89
constexpr CUDF_HOST_DEVICE T right_shift(T const &val, scale_type const &scale)
Function that performs a right shift scale "times" on the val
Radix
Scoped enumerator to use when constructing fixed_point
Definition: fixed_point.hpp:55
CUDF_HOST_DEVICE fixed_point< Rep1, Rad1 > operator-(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
CUDF_HOST_DEVICE bool operator>=(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
CUDF_HOST_DEVICE bool operator<=(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
CUDF_HOST_DEVICE bool operator==(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
CUDF_HOST_DEVICE fixed_point< Rep1, Rad1 > operator%(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
CUDF_HOST_DEVICE auto division_overflow(T lhs, T rhs)
Function for identifying integer overflow when dividing.
CUDF_HOST_DEVICE fixed_point< Rep1, Rad1 > operator/(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
scale_type
The scale type for fixed_point.
Definition: fixed_point.hpp:44
CUDF_HOST_DEVICE fixed_point< Rep1, Rad1 > operator*(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
CUDF_HOST_DEVICE bool operator>(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
CUDF_HOST_DEVICE auto addition_overflow(T lhs, T rhs)
Function for identifying integer overflow when adding.
CUDF_HOST_DEVICE fixed_point< Rep1, Rad1 > operator+(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
CUDF_HOST_DEVICE auto multiplication_overflow(T lhs, T rhs)
Function for identifying integer overflow when multiplying.
constexpr CUDF_HOST_DEVICE auto is_supported_representation_type()
Returns true if the representation type is supported by fixed_point
Definition: fixed_point.hpp:64
CUDF_HOST_DEVICE bool operator!=(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
CUDF_HOST_DEVICE auto subtraction_overflow(T lhs, T rhs)
Function for identifying integer overflow when subtracting.
CUDF_HOST_DEVICE bool operator<(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
fixed_point and supporting types
Definition: fixed_point.hpp:34
Helper struct for constructing fixed_point when value is already shifted.
Rep value
The value of the fixed point number.
CUDF_HOST_DEVICE scaled_integer(Rep v, scale_type s)
Constructor for scaled_integer
scale_type scale
The scale of the value.
Type declarations for libcudf.
#define CUDF_HOST_DEVICE
Indicates that the function or method is usable on host and device.
Definition: types.hpp:32