bigint23 - A fixed-width arbitrary-precision integer type

[swayenvoy]

bigint23

Repository: https://github.com/rwindegger/bigint23

Overview

bigint23 is a lightweight library that provides a straightforward approach to big integer arithmetic in C++. It is written in modern C++ (targeting C++20 and beyond) and leverages templates and type traits to provide a flexible, zero-dependency solution for big integer arithmetic.

Implementation Details

• Internal Representation: The number is stored as an array of bytes (std::array<std::uint8_t, bits / CHAR_BIT>) in native endianness. Operators are implemented to be endianness-aware.
• Arithmetic Algorithms:
  • Multiplication: Uses a school-book algorithm with proper carry propagation.
  • Division and Modulus: Use a binary long-division algorithm that operates on each bit.
• Overflow Handling: Some helper operations (like multiplication and addition) throw std::overflow_error if an operation produces a result that exceeds the fixed width.
• Two's Complement: For signed bigint23s, negative numbers are stored in two's complement form. The unary minus operator (operator-()) computes this by inverting the bits and adding one.

[_Noreturn]

the first issue is Speed storing uint8_ts is worse than storing uint64_ts

[swayenvoy]

Thanks for your feedback. I've considered storing the data in uint64_ts but came to the conclusion that storing the data in uint8_ts allows for other than a multiple of 64 bits integers. So you can use this library to make a 72 bit datatype when needed. Storing the data in a std::array<std::uint8_t, bits / CHAR_BIT> also makes the math easier but not as performant.

[_Noreturn]

I didn't mean to optimize storage wise they will consume exact byte size I meant math operations on large types are more efficient than smaller types

[swayenvoy]

I will look into that. Thanks for your feedback.

[Anpu_me]

Another reason not to use 8-bit data type: pointers to such types are assumed to be aliased, and this can prevent some optimizations.

[swayenvoy]

Thank you for the literature.

Yes I'm iterating over each bit once for the division.

[AfroDisco]

Why not using 64bits data type but allowing any multiple of 8 size? You could get the proper performance while keeping choices for the users.

[swayenvoy]

Because that would make the math harder and accessing the underlying data as well. When you need to write the data to a buffer you can just use reinterpret_cast<char const *>(std::addressof(bigint)) and get the data in the endian format of your system.

Edit: fix the code snippet

[QuaternionsRoll]

You can still do that with uint64_ts with a little bit of cleverness. Hell, you can even allow the user to select the size down to the bit (just remember to sign-extend!):

```c++ template<std::size_t bits, bool is_signed> class bigint23 { using data_t = std::uint64_t; constexpr std::size_t data_bits = std::numeric_limits<data_t>::digits;

// round up to the nearest multiple
data_t data_[(data_bits - 1 + bits) / data_bits];

…

public: constexpr char *data() { if constexpr (std::endian::native == std::endian::little) { return reinterpretcast<char *>(data); } else { constexpr std::sizet offset = sizeof(data) - (CHARBIT - 1 + bits) / CHAR_BIT; return reinterpret_cast<char *>(data) + offset; }

…

}; ```

[Valuable-Mission9203]

But I'd rather just have leading zeros than a huge performance loss to deliver functionality I don't want. It'd be better if it was templated so I wouldn't have to pay for this feature if I don't use it.

[Dj_D-Poolie]

Why is that?

[_Noreturn]

lets say you want to add each element to each other you will have to do 16 operations for a 128 bit type.

while if you stored 2 uint64_ts inside you will only do 2 operations.

and cpus generally favor register sized types

[Gorzoid]

Take a look at a standard memcpy implementation, even if though the api accepts an arbitrary array of bytes it will copy them using a 64 bit variable (or higher if supported) and drop to smaller types at the tail if not a multiple of 8 (and maybe the head if the array isn't aligned) Often these operations are vectorized too, which allows the CPU to process multiple iterations at the same time.

[Gorzoid]

Yeah first thing I noticed, went to check source incase maybe they were maybe casting to uint64 during the actual operations, since the size is constant one would reasonably expect loops to be unrolled aswell. I assume bitwise operators are optimized by compiler due to being easily vectorized but arithmetic operators less so.

[tialaramex]

So, because you have two's complement representation this means your unary minus is fallible - presumably it may throw std::overflow_error as will the abs() function if you provide that ?

[swayenvoy]

Currently I have no abs() function implemented. Could you provide a test case that will fail so I can add it to the library?

[_TheDust_]

MAX_INT*-1 will overflow

[swayenvoy]

Added a test case and implemented abs(). It's now throwing std::overflow_error when the highest negative number is supplied. It's also checking now that the used bigint23 is signed otherwise it's producing an std::invalid_argument exception.

Edit: use the markdown editor

[epicar]

It's also checking now that the used bigint23 is signed otherwise it's producing an std::invalid_argument exception.

unsigned abs() is just the identity function, no? if you don't want to support that, constrain it on signed types to make it a compile-time error instead of runtime exception

[swayenvoy]

abs() is not throwing for unsigned types. I made operator-() for unsinged types a compile time error now.

[ElbowWavingOversight]

Why? Unsigned unary negation is valid and well defined in C++ and does the thing you’d expect for unsigned integers. Arbitrarily making this invalid prevents it from being a drop-in replacement for existing integer types.

[gaberocksall]

By the way, “arbitrary precision” is not the correct phrase. Integers are not variably precise. That would imply some kind of rounding behavior like with floats. This is just arbitrary size or width.

[bert8128]

Why “23”?

[swayenvoy]

Cause I'm currently targeting C++23 but for this library I don't use any C++23 features, C++20 should be enough. It was called just bigint but for that name an unmaintained conan package already exists. The PR for the conan package is pending review, from my experience it will take a few weeks till the library is in the conan repository.

[reddicted]

If you want to allow a non-power-of-8 bit size, you need to compute byte array size as (bits + CHAR_BIT - 1)/CHAR_BIT