Quick start

When working in your own project with wide-integer, using the uintwide_t.h header is straightforward. Identify the header within its directory. Include this header path to the compiler's set of include paths or in your project. Then simply #include <uintwide_t.h> in the normal C++ way.

Easy application follows via traditional C-style typedef or alias such as uint512_t. An instance of the defined type can be used very much like a built-in integral type.

In the following code, for example, the static uint512_t variable x is initialized with unsigned, integral value 3U. The main subroutine subsequently computes $3^{301}$ with the specialized wide-integer, namespace-specific function pow, which is found via ADL.

The approximate result is

$$3^{301}~{\approx}~4.10674{\times}~10^{143}\text{.}$$

See also the following informative links to Wolfram Alpha(R).

• Query the approximate value of $3^{301}$ with N[3^301]
• Verify the exact value of $3^{301}$ with 3^301

This example, compiled with successful output result, is shown in its entirety in the following short link to godbolt.

In particular,

#include <math/wide_integer/uintwide_t.h>

#include <iostream>

auto main() -> int
{
  using uint512_t = ::math::wide_integer::uintwide_t<512U, std::uint32_t>;

  const uint512_t x { 3U };

  const auto p3 = pow(x, 301);

  // 410674437175765127973978082146264947899391086876012309414440570235106991532497229781400618467066824164751453321793982128440538198297087323698003
  std::cout << "p3: " << p3 << std::endl;

  std::cout << "Cast p3 to double: " << double { p3 } << std::endl;
}

The code sequence above defines the local data type uint512_t with an alias. The first template parameter 512U sets the binary width (or bit count) while the second optional template parameter std::uint32_t sets the internal limb type. The limb type must be unsigned and one of std::uint8_t, std::uint16_t, std::uint32_t or on some systems std::uint64_t. If the second template parameter LimbType is left blank, the default limb type (i.e., uint_defaultlimb_t) is either std::uint32_t or std::uint64_t, with $64$-bit limbs if WIDE_INTEGER_HAS_LIMB_TYPE_UINT64 is defined (see also the relevant docs below).

The complete template signature of the uintwide_t class is shown below.

namespace math::wide_integer {

namespace detail { using size_t = std::uint32_t; }

using detail::size_t;

// Forward declaration of the uintwide_t template class.
template<const size_t Width2,
         typename LimbType      = uint_defaultlimb_t,
         typename AllocatorType = void,
         const bool IsSigned    = false>
class uintwide_t;

// Here, uint_defaultlimb_t is either std::uint32_t or std::uint64_t
// (if WIDE_INTEGER_HAS_LIMB_TYPE_UINT64, see below) is defined.

} // namespace math::wide_integer

uintwide_t also has a third optional template parameter that is used to set the allocator type employed for internal storage of the big integer's data. The default allocator type is void and uintwide_t uses stack allocation with an std::array-like internal representation. Setting the allocator type to an actual allocator such as, for instance, std::allocator<limb_type> activates allocator-based internal storage for uintwide_t. Using allocator-based storage reduces stack consumption and can be especially beneficial for higher digit counts. For low digit counts, the allocator type can simply be left blank (thus defaulting to void) or explicitly be set to void and stack allocation will be used in either case.

If an allocator is supplied with any granularity other than limb_type (in other words LimbType) such as std::allocator<void>, custom_allocator_type<char>, etc., then the uintwide_t class will internally rebind the allocator to the granularity and unsigned-ness of limb_type using rebind_alloc from std::allocator_traits.

The fourth template parameter IsSigned can be set to true to activate a signed integer type. If left blank, the default value of IsSigned is false and the integer type will be unsigned.

Examples

Various interesting and algorithmically challenging examples have been implemented. It is hoped that the examples provide inspiration and guidance on how to use wide-integer.

• example000_numeric_limits.cpp verifies parts of the specializations of std::numeric_limits for (unsigned) uint256_tand (signed) int256_t.
• example000a_builtin_convert.cpp exercises some conversions to/from built-in types/uintwide_t.
• example001_mul_div.cpp performs multiplication and division.
• example001a_div_mod.cpp exercises division and modulus calculations.
• example002_shl_shr.cpp does a few left and right shift operations.
• example003_sqrt.cpp computes a square root.
• example003a_cbrt computes a cube root.
• example004_rootk_pow.cpp computes an integral seventh root and its corresponding power. A negative-valued cube root is also tested.
• example005_powm.cpp tests the power-modulus function powm.
• example005a_pow_factors_of_p99.cpp verifies a beautiful, known prime factorization result from a classic tabulated value.
• example006_gcd.cpp tests several computations of greatest common divisor using the gcd function.
• example007_random_generator.cpp computes some large pseudo-random integers.
• example008_miller_rabin_prime.cpp implements primality testing via Miller-Rabin.
• example008a_miller_rabin_prime.cpp verifies Boost's interpretation of Miller-Rabin primality testing using uintwide_t-based types.
• example008b_solovay_strassen_prime.cpp implements a standalone implementation of Solovay-Strassen primality testing using uintwide_t-based types.
• example009_timed_mul.cpp measures multiplication timings.
• example009a_timed_mul_4_by_4.cpp also measures multiplication timings for the special case of wide integers having four limbs.
• [example009b_timed_mul_8_by_8.cpp](./examples/example009b_timed_mu