wideint is a C++ implementation of wide exact-width integer types.

wideint - wide exact-width integer types

Copyright (c) 2022 Joergen Ibsen

About

wideint is a C++ implementation of wide exact-width integer types.

; constexpr auto p = uint128("9223372036854775337"); constexpr auto q = uint128("4611686018427387847"); // prints 42535295865117305235085505148949129439 std::cout << p * q << '\n'; }">
#include <iostream>
#include "wideint.hpp"

int main() {
	using uint128 = wideint::wuint<4>;

	constexpr auto p = uint128("9223372036854775337");
	constexpr auto q = uint128("4611686018427387847");

	// prints 42535295865117305235085505148949129439
	std::cout << p * q << '\n';
}

While doing Advent of Code to pick up some C++20, I came across a problem where I wanted to do a computation on values larger than what fits in an unsigned long long. The C++ standard library does not include a big integer type yet, so I would either have to use one of the stable, well-tested, highly efficient libraries available, or write my own ad hoc solution, and hopefully learn a few things along the way.

Caveat

wideint is not production quality. It has not been thoroughly tested, and some of the algorithms used may be slow compared to what you would get with one of the established big number libraries. Also, being exact-width and stack-allocated means it is only suitable for bounded computations on relatively small values.

Requirements

wideint requires std::uint32_t and std::uint64_t to be available. It uses some C++20 features which may not be available in all compilers.

Details

A wideint stores its value in a std::array of std::uint32_t. It takes the size of this array as a template argument. So a wuint<3>, for example, stores a 96-bit value, while a wuint<4> stores a 128-bit value.

While it is possible to create a wideint with 32- or 64 bits, use the built-in types std::uint32_t and std::uint64_t instead.

There is no implicit conversion from std::uint32_t or std::string_view to wideint. If you want to initialize a wideint with either, you will have to do so explicitly:

// This does not compile, there is no implicit conversion
// uint128 a = 5;

// Use either of these instead
uint128 b(5);
uint128 c = uint128(5);
auto d = uint128(5);

As special cases, modulus (wuint % uint32_t) and bitwise AND (wuint & uint32_t) with a std::uint32_t on the right return a std::uint32_t instead of a wuint.

Most operations are constexpr.

Signed values

There is a signed wideint type, wideint::wint, which interprets the value it stores as a two's complement representation.

constexpr wint gcd(const wint &x, const wint &y) { auto a = x; auto b = y; while (b != 0) { a = std::exchange(b, a % b); } return abs(a); } int main() { using int128 = wideint::wint<4>; constexpr auto p = int128("-9223372036854775337"); constexpr auto q = int128("4611686018427387847"); constexpr auto r = int128("2305843009213693907"); // prints 2305843009213693907 std::cout << gcd(p * r, q * r) << '\n'; }">
#include <iostream>
#include <utility>
#include "wideint.hpp"

using wideint::wint;

template
      size_t width>

      constexpr wint
       
       gcd(
       const wint
       
         &x, 
        const wint
        
          &y)
{
	
         auto a = x;
	
         auto b = y;

	
         while (b != 
         0) {
		a = 
         std::exchange(b, a % b);
	}

	
         return 
         abs(a);
}


         int 
         main() {
	
         using int128 = wideint::wint<
         4>;

	
         constexpr 
         auto p = 
         int128(
         "-9223372036854775337");
	
         constexpr 
         auto q = 
         int128(
         "4611686018427387847");
	
         constexpr 
         auto r = 
         int128(
         "2305843009213693907");

	
         // prints 2305843009213693907
	std::cout << 
         gcd(p * r, q * r) << 
         '\n';
}
        
       
      
     

Output

There is a to_string() function that converts a wideint to a std::string.

There are operator overloads for stream input and output.

Alternatives

Owner
Similar Resources

A compressed, associative, exact dictionary for k-mers.

SSHash This is a compressed dictionary data structure for k-mers (strings of length k over the DNA alphabet {A,C,G,T}), based on Sparse and Skew Hashi

Nov 24, 2022

IntX is a C++11 port of IntX arbitrary precision Integer library with speed, about O(N * log N) multiplication/division algorithms implementation.

IntX IntX is a C++11 port of IntX arbitrary precision Integer library with speed, about O(N * log N) multiplication/division algorithms implementation

Mar 9, 2022

C implementation of C++ Utility functions Integer Comparison Macros

C implementation of C++ Utility functions Integer Comparison Macros

Oct 31, 2022

Reading, writing, and processing images in a wide variety of file formats, using a format-agnostic API, aimed at VFX applications.

README for OpenImageIO Introduction The primary target audience for OIIO is VFX studios and developers of tools such as renderers, compositors, viewer

Nov 22, 2022

Library of generic and type safe containers in pure C language (C99 or C11) for a wide collection of container (comparable to the C++ STL).

Library of generic and type safe containers in pure C language (C99 or C11) for a wide collection of container (comparable to the C++ STL).

M*LIB: Generic type-safe Container Library for C language Overview M*LIB (M star lib) is a C library enabling to use generic and type safe container i

Nov 21, 2022

XMap is a fast network scanner designed for performing Internet-wide IPv6 & IPv4 network research scanning.

XMap is reimplemented and improved thoroughly from ZMap and is fully compatible with ZMap, armed with the "5 minutes" probing speed and novel scanning techniques. XMap is capable of scanning the 32-bits address space in under 45 minutes.

Nov 23, 2022

"Zero setup" cross-compilation for a wide variety of architectures.

"Zero setup" cross-compilation for a wide variety of architectures. xcross includes compact docker images and a build utility for minimal setup C/C++ cross-compiling, inspired by rust-embedded/cross

Nov 10, 2022

Playbit System interface defines an OS-like computing platform which can be implemented on a wide range of hosts

PlaySys The Playbit System interface PlaySys defines an OS-like computing platform which can be implemented on a wide range of hosts like Linux, BSD,

Nov 12, 2022

This plugin allows Flutter desktop apps to defines system/inapp wide hotkey (i.e. shortcut).

hotkey_manager This plugin allows Flutter desktop apps to defines system/inapp wide hotkey (i.e. shortcut). hotkey_manager Platform Support Quick Star

Nov 30, 2022

Dwm_lut - Apply 3D LUTs to the Windows desktop for system-wide color correction/calibration

About This tool applies 3D LUTs to the Windows desktop by hooking into DWM. It works in both SDR and HDR modes, and uses tetrahedral interpolation on

Nov 24, 2022

An open collection of tools and experiments for rendering wide-gamut scene-linear data into an image for an SDR or HDR display device.

Open Display Transform An open collection of tools and experiments for rendering wide-gamut scene-linear data into an image for an SDR or HDR display

Nov 14, 2022

Video game library manager with support for wide range of 3rd party libraries and game emulation support, providing one unified interface for your games.

Video game library manager with support for wide range of 3rd party libraries and game emulation support, providing one unified interface for your games.

An open source video game library manager and launcher with support for 3rd party libraries like Steam, GOG, Origin, Battle.net and Uplay. Includes game emulation support, providing one unified interface for your games.

Dec 2, 2022

This is a simple UNITEST to test the implementation of the the various container types of the C++ standard template library

ft_container UNITest. This is a simple UNITEST to test the implementation of the the various container types of the C++ standard template library that

Nov 12, 2022

Strong type - C++ implementation of strong types

strong_type C++ implementation of strong types Build Status Linux (gcc-8, clang-8) / OSX Table of contents Table of contents What is this ? A tour of

Sep 27, 2022

MIRACL Cryptographic SDK: Multiprecision Integer and Rational Arithmetic Cryptographic Library is a C software library that is widely regarded by developers as the gold standard open source SDK for elliptic curve cryptography (ECC).

MIRACL What is MIRACL? Multiprecision Integer and Rational Arithmetic Cryptographic Library – the MIRACL Crypto SDK – is a C software library that is

Nov 22, 2022

LibTomMath is a free open source portable number theoretic multiple-precision integer library written entirely in C.

libtommath This is the git repository for LibTomMath, a free open source portable number theoretic multiple-precision integer (MPI) library written en

Nov 23, 2022

Fastest Integer Compression

Fastest Integer Compression

TurboPFor: Fastest Integer Compression TurboPFor: The new synonym for "integer compression" 🆕 (2019.11) ALL functions now available for 64 bits ARMv8

Nov 28, 2022

MIRACL Cryptographic SDK: Multiprecision Integer and Rational Arithmetic Cryptographic Library is a C software library that is widely regarded by developers as the gold standard open source SDK for elliptic curve cryptography (ECC).

MIRACL What is MIRACL? Multiprecision Integer and Rational Arithmetic Cryptographic Library – the MIRACL Crypto SDK – is a C software library that is

Nov 22, 2022

A C++11 large integer library with effective high performance, simplistic in nature and also clean in the eyes.

BigIntegerCPP BigIntegerCPP is a C++11 port of large integer library used in CryptoLib4Pascal. It allows mostly parsing of numbers as strings in diffe

Nov 11, 2022
SCIP - Solving Constraint Integer Programs

SCIP: Solving Constraint Integer Programs Welcome to what is currently one of the fastest academically developed solvers for mixed integer programming

Nov 30, 2022
LRU implementation exercises
LRU implementation exercises

LRU implementation exercises

Jul 3, 2022
Implementation using C in programming lab class when being Teacher Assistant.

C Programming Lab Implementation using C in programming lab class when being Teacher Assistant. The problems are here Problems and Description Week2 w

Aug 16, 2022
Implementation of kcp protocol based on c++11
Implementation of kcp protocol based on c++11

?? kcp-cpp A C++11 header-only kcp library,It has been heavily optimized to support native heartbeat packets and multithreading There are a lot of ins

Oct 25, 2022
Jinja2 C++ (and for C++) almost full-conformance template engine implementation

Jinja2С++ C++ implementation of the Jinja2 Python template engine. This library brings support of powerful Jinja2 template features into the C++ world

Nov 9, 2022
Imu_initialization - Implementation of "An Analytical Solution to the IMU Initialization Problem for Visual-Inertial Systems"

An Analytical Solution to the IMU Initialization Problem for Visual-Inertial Systems Implementation of "An Analytical Solution to the IMU Initializati

Nov 23, 2022
Arbitrary Precision provides C++ long integer types that behave as basic integer types. This library aims to be intuitive and versatile in usage, rather than fast.

Arbitrary Precision (AP) Cross-platform and cross-standard header-only arbitrary precision arithmetic library. Currently it offers integer types that

Sep 28, 2022
A collection of multiple types of lists used during pentesting, collected in one place. List types include usernames, passwords, combos, wordlist and may more..
A collection of multiple types of lists used during pentesting, collected in one place. List types include usernames, passwords, combos, wordlist and may more..

Access list is a collection of multiple types of lists used during pentesting, collected in one place, created by Undercode This list include a collec

Nov 21, 2022
Library that solves the exact cover problem using Dancing Links, also known as DLX.

The DLX Library The DLX library The DLX library solves instances of the exact cover problem, using Dancing Links (Knuth’s Algorithm X). Also included

Nov 7, 2022
a game of packing problems - several thousand of them, to be exact

myriad myriad is a game of packing problems -- several thousand of them, to be exact. install you can compile the game using gcc: gcc -Wall -lncurses

Dec 21, 2021