template <size_t Bits, bool Signed, typename WordType = uint64_t>struct BigInt
Defined at line 334 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
Public Members
cpp::array<WordType, WORD_COUNT> valstatic const bool SIGNEDstatic const size_t BITSstatic const size_t WORD_SIZEstatic const size_t WORD_COUNTPublic Methods
void BigInt<Bits, Signed, WordType> ()Defined at line 361 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 363 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 366 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 457 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 463 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 470 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 485 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> zero ()constants
Defined at line 488 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> one ()Defined at line 489 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> all_ones ()Defined at line 490 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> min ()Defined at line 491 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> max ()Defined at line 497 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
bool is_neg ()TODO: Reuse the Sign type.
Defined at line 505 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 508 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
template <typename T>
T operator T ()Defined at line 513 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 518 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
bool operator bool ()Defined at line 538 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
bool is_zero ()Defined at line 540 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 549 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 553 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 561 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 567 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 574 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 578 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 584 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 590 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 597 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 603 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 610 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 636 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 644 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 662 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 688 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 803 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 809 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 814 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 819 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 824 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> & operator<<= (size_t s)Defined at line 829 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> operator<< (size_t s)Defined at line 834 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> & operator>>= (size_t s)Defined at line 838 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> operator>> (size_t s)Defined at line 843 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> operator~ ()Defined at line 867 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> operator- ()Defined at line 874 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> & operator++ ()Defined at line 910 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> operator++ (int )Defined at line 915 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> & operator-- ()Defined at line 921 of file ../../third_party/llvm-libc/src/src/__support/big_int.h
BigInt<Bits, Signed, WordType> operator-- (int )Defined at line 926 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 933 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 938 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 941 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 947 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)