struct BigInt

template <size_t Bits, bool Signed, typename WordType = uint64_t>

struct BigInt

Defined at line 333 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

Public Members

cpp::array<WordType, WORD_COUNT> val
static const bool SIGNED
static const size_t BITS
static const size_t WORD_SIZE
static const size_t WORD_COUNT

Public Methods

void BigInt<Bits, Signed, WordType> ()

Defined at line 360 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

void BigInt<Bits, Signed, WordType> (const BigInt<Bits, Signed, WordType> & other)

Defined at line 362 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

template <size_t OtherBits, bool OtherSigned, typename OtherWordType>
void BigInt<Bits, Signed, WordType> (const BigInt<OtherBits, OtherSigned, OtherWordType> & other)

Defined at line 365 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

template <size_t N>
void BigInt<Bits, Signed, WordType> (const WordType (&)[N] nums)

Construct a BigInt from a C array.

Defined at line 456 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

void BigInt<Bits, Signed, WordType> (const cpp::array<WordType, WORD_COUNT> & words)

Defined at line 462 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

template <typename T, typename = cpp::enable_if_t<cpp::is_integral_v<T>>>
void BigInt<Bits, Signed, WordType> (T v)

Initialize the first word to |v| and the rest to 0.

Defined at line 469 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> & operator= (const BigInt<Bits, Signed, WordType> & other)

Defined at line 484 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> zero ()

constants

Defined at line 487 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> one ()

Defined at line 488 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> all_ones ()

Defined at line 489 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> min ()

Defined at line 490 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> max ()

Defined at line 496 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

bool is_neg ()

TODO: Reuse the Sign type.

Defined at line 504 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

template <size_t OtherBits, bool OtherSigned, typename OtherWordType>
BigInt<OtherBits, OtherSigned, OtherWordType> operator __fuchsia_libc::BigInt<value-parameter-1-0, value-parameter-1-1, type-parameter-1-2> ()

Defined at line 507 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

template <typename T>
T operator T ()

Defined at line 512 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

template <typename T>
cpp::enable_if_t<cpp::is_integral_v<T> && !cpp::is_same_v<T, bool>, T> to ()

Defined at line 517 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

bool operator bool ()

Defined at line 537 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

bool is_zero ()

Defined at line 539 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

WordType add_overflow (const BigInt<Bits, Signed, WordType> & rhs)

Add 'rhs' to this number and store the result in this number.

Returns the carry value produced by the addition operation.

Defined at line 548 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator+ (const BigInt<Bits, Signed, WordType> & other)

Defined at line 552 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator+ (BigInt<Bits, Signed, WordType> && other)

This will only apply when initializing a variable from constant values, so

it will always use the constexpr version of add_with_carry.

Defined at line 560 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> & operator+= (const BigInt<Bits, Signed, WordType> & other)

Defined at line 566 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

WordType sub_overflow (const BigInt<Bits, Signed, WordType> & rhs)

Subtract 'rhs' to this number and store the result in this number.

Returns the carry value produced by the subtraction operation.

Defined at line 573 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator- (const BigInt<Bits, Signed, WordType> & other)

Defined at line 577 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator- (BigInt<Bits, Signed, WordType> && other)

Defined at line 583 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> & operator-= (const BigInt<Bits, Signed, WordType> & other)

Defined at line 589 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

WordType mul (WordType x)

Multiply this number with x and store the result in this number.

Defined at line 596 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

template <size_t OtherBits>
auto ful_mul (const BigInt<OtherBits, Signed, WordType> & other)

Return the full product.

Defined at line 602 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator* (const BigInt<Bits, Signed, WordType> & other)

Defined at line 609 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> quick_mul_hi (const BigInt<Bits, Signed, WordType> & other)

Fast hi part of the full product. The normal product `operator*` returns

`Bits` least significant bits of the full product, while this function will

approximate `Bits` most significant bits of the full product with errors

bounded by:

0

<

= (a.full_mul(b) >> Bits) - a.quick_mul_hi(b))

<

= WORD_COUNT - 1.

An example usage of this is to quickly (but less accurately) compute the

product of (normalized) mantissas of floating point numbers:

(mant_1, mant_2) -> quick_mul_hi -> normalize leading bit

is much more efficient than:

(mant_1, mant_2) -> ful_mul -> normalize leading bit

-> convert back to same Bits width by shifting/rounding,

especially for higher precisions.

Performance summary:

Number of 64-bit x 64-bit -> 128-bit multiplications performed.

Bits WORD_COUNT ful_mul quick_mul_hi Error bound

128 2 4 3 1

196 3 9 6 2

256 4 16 10 3

512 8 64 36 7

Defined at line 635 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

void pow_n (uint64_t power)

BigInt(x).pow_n(n) computes x ^ n.

Note 0 ^ 0 == 1.

Defined at line 643 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

cpp::optional<BigInt<Bits, Signed, WordType>> div (const BigInt<Bits, Signed, WordType> & divider)

Performs inplace signed / unsigned division. Returns remainder if not

dividing by zero.

For signed numbers it behaves like C++ signed integer division.

That is by truncating the fractionnal part

https://stackoverflow.com/a/3602857

Defined at line 661 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

cpp::optional<BigInt<Bits, Signed, WordType>> div_uint_half_times_pow_2 (multiword::half_width_t<WordType> x, size_t e)

Efficiently perform BigInt / (x * 2^e), where x is a half-word-size

unsigned integer, and return the remainder. The main idea is as follow:

Let q = y / (x * 2^e) be the quotient, and

r = y % (x * 2^e) be the remainder.

First, notice that:

r % (2^e) = y % (2^e),

so we just need to focus on all the bits of y that is >= 2^e.

To speed up the shift-and-add steps, we only use x as the divisor, and

performing 32-bit shiftings instead of bit-by-bit shiftings.

Since the remainder of each division step

<

x

<

2^(WORD_SIZE / 2), the

computation of each step is now properly contained within WordType.

And finally we perform some extra alignment steps for the remaining bits.

Defined at line 687 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator/ (const BigInt<Bits, Signed, WordType> & other)

Defined at line 802 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> & operator/= (const BigInt<Bits, Signed, WordType> & other)

Defined at line 808 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator% (const BigInt<Bits, Signed, WordType> & other)

Defined at line 813 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator%= (const BigInt<Bits, Signed, WordType> & other)

Defined at line 818 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> & operator*= (const BigInt<Bits, Signed, WordType> & other)

Defined at line 823 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> & operator<<= (size_t s)

Defined at line 828 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator<< (size_t s)

Defined at line 833 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> & operator>>= (size_t s)

Defined at line 837 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator>> (size_t s)

Defined at line 842 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator~ ()

Defined at line 866 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator- ()

Defined at line 873 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> & operator++ ()

Defined at line 909 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator++ (int )

Defined at line 914 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> & operator-- ()

Defined at line 920 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

BigInt<Bits, Signed, WordType> operator-- (int )

Defined at line 925 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

const WordType & operator[] (size_t i)

Return the i-th word of the number.

Defined at line 932 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

WordType & operator[] (size_t i)

Return the i-th word of the number.

Defined at line 937 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

bool get_bit (size_t i)

Return the i-th bit of the number.

Defined at line 940 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

void set_bit (size_t i)

Set the i-th bit of the number.

Defined at line 946 of file ../../third_party/llvm-libc/src/src/__support/big_int.h

Friends

template <size_t Bits, bool Signed, typename WordType = uint64_t>
int BigInt (const BigInt<Bits, Signed, WordType> & lhs, const BigInt<Bits, Signed, WordType> & rhs)
template <size_t Bits, bool Signed, typename WordType = uint64_t>
bool BigInt (const BigInt<Bits, Signed, WordType> & lhs, const BigInt<Bits, Signed, WordType> & rhs)
template <size_t Bits, bool Signed, typename WordType = uint64_t>
bool BigInt (const BigInt<Bits, Signed, WordType> & lhs, const BigInt<Bits, Signed, WordType> & rhs)
template <size_t Bits, bool Signed, typename WordType = uint64_t>
bool BigInt (const BigInt<Bits, Signed, WordType> & lhs, const BigInt<Bits, Signed, WordType> & rhs)
template <size_t Bits, bool Signed, typename WordType = uint64_t>
bool BigInt (const BigInt<Bits, Signed, WordType> & lhs, const BigInt<Bits, Signed, WordType> & rhs)
template <size_t Bits, bool Signed, typename WordType = uint64_t>
bool BigInt (const BigInt<Bits, Signed, WordType> & lhs, const BigInt<Bits, Signed, WordType> & rhs)
template <size_t Bits, bool Signed, typename WordType = uint64_t>
bool BigInt (const BigInt<Bits, Signed, WordType> & lhs, const BigInt<Bits, Signed, WordType> & rhs)
template <size_t Bits, bool Signed, typename WordType = uint64_t>
BigInt BigInt (BigInt<Bits, Signed, WordType> & lhs, const BigInt<Bits, Signed, WordType> & rhs)
template <size_t Bits, bool Signed, typename WordType = uint64_t>
BigInt BigInt (const BigInt<Bits, Signed, WordType> & lhs, const BigInt<Bits, Signed, WordType> & rhs)
template <size_t Bits, bool Signed, typename WordType = uint64_t>
BigInt BigInt (BigInt<Bits, Signed, WordType> & lhs, const BigInt<Bits, Signed, WordType> & rhs)
template <size_t Bits, bool Signed, typename WordType = uint64_t>
BigInt BigInt (const BigInt<Bits, Signed, WordType> & lhs, const BigInt<Bits, Signed, WordType> & rhs)
template <size_t Bits, bool Signed, typename WordType = uint64_t>
BigInt BigInt (BigInt<Bits, Signed, WordType> & lhs, const BigInt<Bits, Signed, WordType> & rhs)
template <size_t Bitsbool Signedtypename WordType = uint64_t>
BigInt BigInt (const BigInt<Bits, Signed, WordType> & lhsconst BigInt<Bits, Signed, WordType> & rhs)