fixed_point.hpp
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2020-2024, 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/limits>
24 #include <cuda/std/type_traits>
25 #include <cuda/std/utility>
26 
27 #include <algorithm>
28 #include <cassert>
29 #include <cmath>
30 #include <string>
31 
33 namespace numeric {
34 
43 enum scale_type : int32_t {};
44 
54 enum class Radix : int32_t { BASE_2 = 2, BASE_10 = 10 };
55 
62 template <typename T>
63 constexpr inline auto is_supported_representation_type()
64 {
65  return cuda::std::is_same_v<T, int32_t> || //
66  cuda::std::is_same_v<T, int64_t> || //
67  cuda::std::is_same_v<T, __int128_t>;
68 }
69  // end of group
71 
72 // Helper functions for `fixed_point` type
73 namespace detail {
74 
83 template <typename Rep,
84  Radix Base,
85  typename T,
86  typename cuda::std::enable_if_t<(cuda::std::is_same_v<int32_t, T> &&
87  is_supported_representation_type<Rep>())>* = nullptr>
88 CUDF_HOST_DEVICE inline Rep ipow(T exponent)
89 {
90  cudf_assert(exponent >= 0 && "integer exponentiation with negative exponent is not possible.");
91 
92  if constexpr (Base == numeric::Radix::BASE_2) { return static_cast<Rep>(1) << exponent; }
93 
94  // Note: Including an array here introduces too much register pressure
95  // https://simple.wikipedia.org/wiki/Exponentiation_by_squaring
96  // This is the iterative equivalent of the recursive definition (faster)
97  // Quick-bench for squaring: http://quick-bench.com/Wg7o7HYQC9FW5M0CO0wQAjSwP_Y
98  if (exponent == 0) { return static_cast<Rep>(1); }
99  auto extra = static_cast<Rep>(1);
100  auto square = static_cast<Rep>(Base);
101  while (exponent > 1) {
102  if (exponent & 1) { extra *= square; }
103  exponent >>= 1;
104  square *= square;
105  }
106  return square * extra;
107 }
108 
120 template <typename Rep, Radix Rad, typename T>
121 CUDF_HOST_DEVICE inline constexpr T right_shift(T const& val, scale_type const& scale)
122 {
123  return val / ipow<Rep, Rad>(static_cast<int32_t>(scale));
124 }
125 
137 template <typename Rep, Radix Rad, typename T>
138 CUDF_HOST_DEVICE inline constexpr T left_shift(T const& val, scale_type const& scale)
139 {
140  return val * ipow<Rep, Rad>(static_cast<int32_t>(-scale));
141 }
142 
156 template <typename Rep, Radix Rad, typename T>
157 CUDF_HOST_DEVICE inline constexpr T shift(T const& val, scale_type const& scale)
158 {
159  if (scale == 0) { return val; }
160  if (scale > 0) { return right_shift<Rep, Rad>(val, scale); }
161  return left_shift<Rep, Rad>(val, scale);
162 }
163 
164 } // namespace detail
165 
184 template <typename Rep,
185  typename cuda::std::enable_if_t<is_supported_representation_type<Rep>()>* = nullptr>
187  Rep value;
195  CUDF_HOST_DEVICE inline explicit scaled_integer(Rep v, scale_type s) : value{v}, scale{s} {}
196 };
197 
207 template <typename Rep, Radix Rad>
208 class fixed_point {
209  Rep _value{};
210  scale_type _scale;
211 
212  public:
213  using rep = Rep;
214  static constexpr auto rad = Rad;
215 
224  template <typename T,
225  typename cuda::std::enable_if_t<cuda::std::is_integral_v<T> &&
226  is_supported_representation_type<Rep>()>* = nullptr>
227  CUDF_HOST_DEVICE inline explicit fixed_point(T const& value, scale_type const& scale)
228  // `value` is cast to `Rep` to avoid overflow in cases where
229  // constructing to `Rep` that is wider than `T`
230  : _value{detail::shift<Rep, Rad>(static_cast<Rep>(value), scale)}, _scale{scale}
231  {
232  }
233 
240  : _value{s.value}, _scale{s.scale}
241  {
242  }
243 
251  template <typename T, typename cuda::std::enable_if_t<cuda::std::is_integral_v<T>>* = nullptr>
253  : _value{static_cast<Rep>(value)}, _scale{scale_type{0}}
254  {
255  }
256 
261  CUDF_HOST_DEVICE inline fixed_point() : _scale{scale_type{0}} {}
262 
269  template <typename U, typename cuda::std::enable_if_t<cuda::std::is_integral_v<U>>* = nullptr>
270  explicit constexpr operator U() const
271  {
272  // Cast to the larger of the two types (of U and Rep) before converting to Rep because in
273  // certain cases casting to U before shifting will result in integer overflow (i.e. if U =
274  // int32_t, Rep = int64_t and _value > 2 billion)
275  auto const value = std::common_type_t<U, Rep>(_value);
276  return static_cast<U>(detail::shift<Rep, Rad>(value, scale_type{-_scale}));
277  }
278 
284  CUDF_HOST_DEVICE inline operator scaled_integer<Rep>() const
285  {
286  return scaled_integer<Rep>{_value, _scale};
287  }
288 
294  CUDF_HOST_DEVICE [[nodiscard]] inline rep value() const { return _value; }
295 
301  CUDF_HOST_DEVICE [[nodiscard]] inline scale_type scale() const { return _scale; }
302 
308  CUDF_HOST_DEVICE inline explicit constexpr operator bool() const
309  {
310  return static_cast<bool>(_value);
311  }
312 
321  template <typename Rep1, Radix Rad1>
323  {
324  *this = *this + rhs;
325  return *this;
326  }
327 
336  template <typename Rep1, Radix Rad1>
338  {
339  *this = *this * rhs;
340  return *this;
341  }
342 
351  template <typename Rep1, Radix Rad1>
353  {
354  *this = *this - rhs;
355  return *this;
356  }
357 
366  template <typename Rep1, Radix Rad1>
368  {
369  *this = *this / rhs;
370  return *this;
371  }
372 
379  {
380  *this = *this + fixed_point<Rep, Rad>{1, scale_type{_scale}};
381  return *this;
382  }
383 
397  template <typename Rep1, Radix Rad1>
399  fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
400 
414  template <typename Rep1, Radix Rad1>
416  fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
417 
429  template <typename Rep1, Radix Rad1>
431  fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
432 
444  template <typename Rep1, Radix Rad1>
446  fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
447 
461  template <typename Rep1, Radix Rad1>
463  fixed_point<Rep1, Rad1> const& lhs, fixed_point<Rep1, Rad1> const& rhs);
464 
478  template <typename Rep1, Radix Rad1>
479  CUDF_HOST_DEVICE inline friend bool operator==(fixed_point<Rep1, Rad1> const& lhs,
480  fixed_point<Rep1, Rad1> const& rhs);
481 
495  template <typename Rep1, Radix Rad1>
496  CUDF_HOST_DEVICE inline friend bool operator!=(fixed_point<Rep1, Rad1> const& lhs,
497  fixed_point<Rep1, Rad1> const& rhs);
498 
512  template <typename Rep1, Radix Rad1>
513  CUDF_HOST_DEVICE inline friend bool operator<=(fixed_point<Rep1, Rad1> const& lhs,
514  fixed_point<Rep1, Rad1> const& rhs);
515 
529  template <typename Rep1, Radix Rad1>
530  CUDF_HOST_DEVICE inline friend bool operator>=(fixed_point<Rep1, Rad1> const& lhs,
531  fixed_point<Rep1, Rad1> const& rhs);
532 
546  template <typename Rep1, Radix Rad1>
547  CUDF_HOST_DEVICE inline friend bool operator<(fixed_point<Rep1, Rad1> const& lhs,
548  fixed_point<Rep1, Rad1> const& rhs);
549 
563  template <typename Rep1, Radix Rad1>
564  CUDF_HOST_DEVICE inline friend bool operator>(fixed_point<Rep1, Rad1> const& lhs,
565  fixed_point<Rep1, Rad1> const& rhs);
566 
577  {
578  if (scale == _scale) { return *this; }
579  Rep const value = detail::shift<Rep, Rad>(_value, scale_type{scale - _scale});
581  }
582 
586  explicit operator std::string() const
587  {
588  if (_scale < 0) {
589  auto const av = detail::abs(_value);
590  Rep const n = detail::exp10<Rep>(-_scale);
591  Rep const f = av % n;
592  auto const num_zeros =
593  std::max(0, (-_scale - static_cast<int32_t>(detail::to_string(f).size())));
594  auto const zeros = std::string(num_zeros, '0');
595  auto const sign = _value < 0 ? std::string("-") : std::string();
596  return sign + detail::to_string(av / n) + std::string(".") + zeros +
597  detail::to_string(av % n);
598  }
599  auto const zeros = std::string(_scale, '0');
600  return detail::to_string(_value) + zeros;
601  }
602 };
603 
613 template <typename Rep, typename T>
614 CUDF_HOST_DEVICE inline auto addition_overflow(T lhs, T rhs)
615 {
616  return rhs > 0 ? lhs > cuda::std::numeric_limits<Rep>::max() - rhs
617  : lhs < cuda::std::numeric_limits<Rep>::min() - rhs;
618 }
619 
628 template <typename Rep, typename T>
629 CUDF_HOST_DEVICE inline auto subtraction_overflow(T lhs, T rhs)
630 {
631  return rhs > 0 ? lhs < cuda::std::numeric_limits<Rep>::min() + rhs
632  : lhs > cuda::std::numeric_limits<Rep>::max() + rhs;
633 }
634 
643 template <typename Rep, typename T>
644 CUDF_HOST_DEVICE inline auto division_overflow(T lhs, T rhs)
645 {
646  return lhs == cuda::std::numeric_limits<Rep>::min() && rhs == -1;
647 }
648 
657 template <typename Rep, typename T>
658 CUDF_HOST_DEVICE inline auto multiplication_overflow(T lhs, T rhs)
659 {
660  auto const min = cuda::std::numeric_limits<Rep>::min();
661  auto const max = cuda::std::numeric_limits<Rep>::max();
662  if (rhs > 0) { return lhs > max / rhs || lhs < min / rhs; }
663  if (rhs < -1) { return lhs > min / rhs || lhs < max / rhs; }
664  return rhs == -1 && lhs == min;
665 }
666 
667 // PLUS Operation
668 template <typename Rep1, Radix Rad1>
670  fixed_point<Rep1, Rad1> const& rhs)
671 {
672  auto const scale = std::min(lhs._scale, rhs._scale);
673  auto const sum = lhs.rescaled(scale)._value + rhs.rescaled(scale)._value;
674 
675 #if defined(__CUDACC_DEBUG__)
676 
677  assert(!addition_overflow<Rep1>(lhs.rescaled(scale)._value, rhs.rescaled(scale)._value) &&
678  "fixed_point overflow");
679 
680 #endif
681 
682  return fixed_point<Rep1, Rad1>{scaled_integer<Rep1>{sum, scale}};
683 }
684 
685 // MINUS Operation
686 template <typename Rep1, Radix Rad1>
688  fixed_point<Rep1, Rad1> const& rhs)
689 {
690  auto const scale = std::min(lhs._scale, rhs._scale);
691  auto const diff = lhs.rescaled(scale)._value - rhs.rescaled(scale)._value;
692 
693 #if defined(__CUDACC_DEBUG__)
694 
695  assert(!subtraction_overflow<Rep1>(lhs.rescaled(scale)._value, rhs.rescaled(scale)._value) &&
696  "fixed_point overflow");
697 
698 #endif
699 
700  return fixed_point<Rep1, Rad1>{scaled_integer<Rep1>{diff, scale}};
701 }
702 
703 // MULTIPLIES Operation
704 template <typename Rep1, Radix Rad1>
706  fixed_point<Rep1, Rad1> const& rhs)
707 {
708 #if defined(__CUDACC_DEBUG__)
709 
710  assert(!multiplication_overflow<Rep1>(lhs._value, rhs._value) && "fixed_point overflow");
711 
712 #endif
713 
715  scaled_integer<Rep1>(lhs._value * rhs._value, scale_type{lhs._scale + rhs._scale})};
716 }
717 
718 // DIVISION Operation
719 template <typename Rep1, Radix Rad1>
721  fixed_point<Rep1, Rad1> const& rhs)
722 {
723 #if defined(__CUDACC_DEBUG__)
724 
725  assert(!division_overflow<Rep1>(lhs._value, rhs._value) && "fixed_point overflow");
726 
727 #endif
728 
730  scaled_integer<Rep1>(lhs._value / rhs._value, scale_type{lhs._scale - rhs._scale})};
731 }
732 
733 // EQUALITY COMPARISON Operation
734 template <typename Rep1, Radix Rad1>
736  fixed_point<Rep1, Rad1> const& rhs)
737 {
738  auto const scale = std::min(lhs._scale, rhs._scale);
739  return lhs.rescaled(scale)._value == rhs.rescaled(scale)._value;
740 }
741 
742 // EQUALITY NOT COMPARISON Operation
743 template <typename Rep1, Radix Rad1>
745  fixed_point<Rep1, Rad1> const& rhs)
746 {
747  auto const scale = std::min(lhs._scale, rhs._scale);
748  return lhs.rescaled(scale)._value != rhs.rescaled(scale)._value;
749 }
750 
751 // LESS THAN OR EQUAL TO Operation
752 template <typename Rep1, Radix Rad1>
754  fixed_point<Rep1, Rad1> const& rhs)
755 {
756  auto const scale = std::min(lhs._scale, rhs._scale);
757  return lhs.rescaled(scale)._value <= rhs.rescaled(scale)._value;
758 }
759 
760 // GREATER THAN OR EQUAL TO Operation
761 template <typename Rep1, Radix Rad1>
763  fixed_point<Rep1, Rad1> const& rhs)
764 {
765  auto const scale = std::min(lhs._scale, rhs._scale);
766  return lhs.rescaled(scale)._value >= rhs.rescaled(scale)._value;
767 }
768 
769 // LESS THAN Operation
770 template <typename Rep1, Radix Rad1>
772  fixed_point<Rep1, Rad1> const& rhs)
773 {
774  auto const scale = std::min(lhs._scale, rhs._scale);
775  return lhs.rescaled(scale)._value < rhs.rescaled(scale)._value;
776 }
777 
778 // GREATER THAN Operation
779 template <typename Rep1, Radix Rad1>
781  fixed_point<Rep1, Rad1> const& rhs)
782 {
783  auto const scale = std::min(lhs._scale, rhs._scale);
784  return lhs.rescaled(scale)._value > rhs.rescaled(scale)._value;
785 }
786 
787 // MODULO OPERATION
788 template <typename Rep1, Radix Rad1>
790  fixed_point<Rep1, Rad1> const& rhs)
791 {
792  auto const scale = std::min(lhs._scale, rhs._scale);
793  auto const remainder = lhs.rescaled(scale)._value % rhs.rescaled(scale)._value;
794  return fixed_point<Rep1, Rad1>{scaled_integer<Rep1>{remainder, scale}};
795 }
796 
800  // end of group
802 } // namespace 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 friend bool operator!=(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
operator != (for comparing two fixed_point numbers)
CUDF_HOST_DEVICE friend fixed_point< Rep1, Rad1 > operator*(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
operator * (for multiplying two fixed_point numbers)
CUDF_HOST_DEVICE friend bool operator==(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
operator == (for comparing two fixed_point numbers)
CUDF_HOST_DEVICE rep value() const
Method that returns the underlying value of the fixed_point number.
static constexpr auto rad
The base.
CUDF_HOST_DEVICE friend bool operator<(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
operator < (for comparing two fixed_point numbers)
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 friend fixed_point< Rep1, Rad1 > operator/(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
operator / (for dividing two fixed_point numbers)
CUDF_HOST_DEVICE fixed_point< Rep1, Rad1 > & operator+=(fixed_point< Rep1, Rad1 > const &rhs)
operator +=
CUDF_HOST_DEVICE friend fixed_point< Rep1, Rad1 > operator+(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
operator + (for adding two fixed_point numbers)
CUDF_HOST_DEVICE friend bool operator<=(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
operator <= (for comparing two fixed_point numbers)
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 friend fixed_point< Rep1, Rad1 > operator-(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
operator - (for subtracting two fixed_point numbers)
CUDF_HOST_DEVICE friend bool operator>=(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
operator >= (for comparing two fixed_point numbers)
CUDF_HOST_DEVICE fixed_point< Rep1, Rad1 > & operator/=(fixed_point< Rep1, Rad1 > const &rhs)
operator /=
CUDF_HOST_DEVICE friend bool operator>(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
operator > (for comparing two fixed_point numbers)
CUDF_HOST_DEVICE friend fixed_point< Rep1, Rad1 > operator%(fixed_point< Rep1, Rad1 > const &lhs, fixed_point< Rep1, Rad1 > const &rhs)
operator % (for computing the modulo operation of two fixed_point numbers)
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 T right_shift(T const &val, scale_type const &scale)
Function that performs a right shift scale "times" on the val
CUDF_HOST_DEVICE Rep ipow(T exponent)
A function for integer exponentiation by squaring.
Definition: fixed_point.hpp:88
Radix
Scoped enumerator to use when constructing fixed_point
Definition: fixed_point.hpp:54
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:43
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.
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)
constexpr auto is_supported_representation_type()
Returns true if the representation type is supported by fixed_point
Definition: fixed_point.hpp:63
fixed_point and supporting types
Definition: fixed_point.hpp:33
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