big_integer.hpp File Reference

#include "config.h"
#include <cmath>
#include <cstdint>

Include dependency graph for big_integer.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	BigInteger

Macros
#define	BIG_INTEGER_WORD_BITS   64U
#define	BIG_INTEGER_WORD_POWER   6U
#define	BIG_INTEGER_WORD   uint64_t
#define	BIG_INTEGER_HALF_WORD   uint32_t
#define	BIG_INTEGER_HALF_WORD_MASK   0xFFFFFFFFULL
#define	BIG_INTEGER_HALF_WORD_MASK_NOT   0xFFFFFFFF00000000ULL

Typedefs
typedef struct BigInteger	BigInteger

Functions
void	bi_set_0 (BigInteger *p)
BigInteger	bi_copy (const BigInteger &in)
void	bi_copy_ip (const BigInteger &in, BigInteger *out)
int	bi_compare (const BigInteger &left, const BigInteger &right)
int	bi_compare_0 (const BigInteger &left)
int	bi_compare_1 (const BigInteger &left)
BigInteger	operator+ (const BigInteger &left, const BigInteger &right)
void	bi_add_ip (BigInteger *left, const BigInteger &right)
BigInteger	operator- (const BigInteger &left, const BigInteger &right)
void	bi_sub_ip (BigInteger *left, const BigInteger &right)
void	bi_increment (BigInteger *pBigInt, const BIG_INTEGER_WORD &value)
void	bi_decrement (BigInteger *pBigInt, const BIG_INTEGER_WORD &value)
BigInteger	bi_load (BIG_INTEGER_WORD *a)
BigInteger	bi_lshift_word (const BigInteger &left, BIG_INTEGER_WORD rightMult)
void	bi_lshift_word_ip (BigInteger *left, BIG_INTEGER_WORD rightMult)
BigInteger	bi_rshift_word (const BigInteger &left, const BIG_INTEGER_WORD &rightMult)
void	bi_rshift_word_ip (BigInteger *left, const BIG_INTEGER_WORD &rightMult)
BigInteger	operator<< (const BigInteger &left, BIG_INTEGER_WORD right)
void	bi_lshift_ip (BigInteger *left, BIG_INTEGER_WORD right)
BigInteger	operator>> (const BigInteger &left, BIG_INTEGER_WORD right)
void	bi_rshift_ip (BigInteger *left, BIG_INTEGER_WORD right)
int	bi_log2 (const BigInteger &n)
int	bi_and_1 (const BigInteger &left)
BigInteger	operator& (const BigInteger &left, const BigInteger &right)
void	bi_and_ip (BigInteger *left, const BigInteger &right)
BigInteger	operator| (const BigInteger &left, const BigInteger &right)
void	bi_or_ip (BigInteger *left, const BigInteger &right)
BigInteger	operator^ (const BigInteger &left, const BigInteger &right)
void	bi_xor_ip (BigInteger *left, const BigInteger &right)
BigInteger	operator~ (const BigInteger &left)
void	bi_not_ip (BigInteger *left)
double	bi_to_double (const BigInteger &in)
bool	operator== (const BigInteger &left, const BigInteger &right)
bool	operator< (const BigInteger &left, const BigInteger &right)
bool	operator<= (const BigInteger &left, const BigInteger &right)
bool	operator> (const BigInteger &left, const BigInteger &right)
bool	operator>= (const BigInteger &left, const BigInteger &right)
BigInteger	operator++ (BigInteger &a)
BigInteger	operator-- (BigInteger &a)
BigInteger	operator* (const BigInteger &left, BIG_INTEGER_HALF_WORD right)
	"Schoolbook multiplication" (on half words) Complexity - O(x^2) More...
BigInteger	operator* (const BigInteger &left, const BigInteger &right)
	"Schoolbook multiplication" (on half words) Complexity - O(x^2) More...
void	bi_div_mod_small (const BigInteger &left, BIG_INTEGER_HALF_WORD right, BigInteger *quotient, BIG_INTEGER_HALF_WORD *rmndr)
	"Schoolbook division" (on half words) Complexity - O(x^2) More...
void	bi_div_mod (const BigInteger &left, const BigInteger &right, BigInteger *quotient, BigInteger *rmndr)
	Adapted from Qrack! (The fundamental algorithm was discovered before.) Complexity - O(log) More...

Variables
constexpr size_t	BIG_INTEGER_BITS = (1 << QBCAPPOW)
constexpr int	BIG_INTEGER_WORD_SIZE = BIG_INTEGER_BITS / BIG_INTEGER_WORD_BITS
constexpr size_t	BIG_INTEGER_HALF_WORD_BITS = BIG_INTEGER_WORD_BITS >> 1U
constexpr int	BIG_INTEGER_HALF_WORD_SIZE = BIG_INTEGER_WORD_SIZE << 1U
constexpr int	BIG_INTEGER_MAX_WORD_INDEX = BIG_INTEGER_WORD_SIZE - 1U

Macro Definition Documentation

BIG_INTEGER_HALF_WORD

#define BIG_INTEGER_HALF_WORD   uint32_t

BIG_INTEGER_HALF_WORD_MASK

#define BIG_INTEGER_HALF_WORD_MASK   0xFFFFFFFFULL

BIG_INTEGER_HALF_WORD_MASK_NOT

#define BIG_INTEGER_HALF_WORD_MASK_NOT   0xFFFFFFFF00000000ULL

BIG_INTEGER_WORD

#define BIG_INTEGER_WORD   uint64_t

BIG_INTEGER_WORD_BITS

#define BIG_INTEGER_WORD_BITS   64U

BIG_INTEGER_WORD_POWER

#define BIG_INTEGER_WORD_POWER   6U

Typedef Documentation

BigInteger

typedef struct BigInteger BigInteger

Function Documentation

bi_add_ip()

void bi_add_ip ( BigInteger *  left, const BigInteger &  right  )

inline

bi_and_1()

int bi_and_1 ( const BigInteger &  left )

inline

bi_and_ip()

void bi_and_ip ( BigInteger *  left, const BigInteger &  right  )

inline

bi_compare()

int bi_compare ( const BigInteger &  left, const BigInteger &  right  )

inline

bi_compare_0()

int bi_compare_0 ( const BigInteger &  left )

inline

bi_compare_1()

int bi_compare_1 ( const BigInteger &  left )

inline

bi_copy()

BigInteger bi_copy ( const BigInteger &  in )

inline

bi_copy_ip()

void bi_copy_ip ( const BigInteger &  in, BigInteger *  out  )

inline

bi_decrement()

void bi_decrement ( BigInteger *  pBigInt, const BIG_INTEGER_WORD &  value  )

inline

bi_div_mod()

void bi_div_mod	(	const BigInteger &	left,
		const BigInteger &	right,
		BigInteger *	quotient,
		BigInteger *	rmndr
	)

Adapted from Qrack! (The fundamental algorithm was discovered before.) Complexity - O(log)

bi_div_mod_small()

void bi_div_mod_small	(	const BigInteger &	left,
		BIG_INTEGER_HALF_WORD	right,
		BigInteger *	quotient,
		BIG_INTEGER_HALF_WORD *	rmndr
	)

"Schoolbook division" (on half words) Complexity - O(x^2)

bi_increment()

void bi_increment ( BigInteger *  pBigInt, const BIG_INTEGER_WORD &  value  )

inline

bi_load()

BigInteger bi_load ( BIG_INTEGER_WORD *  a )

inline

bi_log2()

int bi_log2 ( const BigInteger &  n )

inline

bi_lshift_ip()

void bi_lshift_ip ( BigInteger *  left, BIG_INTEGER_WORD  right  )

inline

bi_lshift_word()

BigInteger bi_lshift_word ( const BigInteger &  left, BIG_INTEGER_WORD  rightMult  )

inline

bi_lshift_word_ip()

void bi_lshift_word_ip ( BigInteger *  left, BIG_INTEGER_WORD  rightMult  )

inline

bi_not_ip()

void bi_not_ip ( BigInteger *  left )

inline

bi_or_ip()

void bi_or_ip ( BigInteger *  left, const BigInteger &  right  )

inline

bi_rshift_ip()

void bi_rshift_ip ( BigInteger *  left, BIG_INTEGER_WORD  right  )

inline

bi_rshift_word()

BigInteger bi_rshift_word ( const BigInteger &  left, const BIG_INTEGER_WORD &  rightMult  )

inline

bi_rshift_word_ip()

void bi_rshift_word_ip ( BigInteger *  left, const BIG_INTEGER_WORD &  rightMult  )

inline

bi_set_0()

void bi_set_0 ( BigInteger *  p )

inline

bi_sub_ip()

void bi_sub_ip ( BigInteger *  left, const BigInteger &  right  )

inline

bi_to_double()

double bi_to_double ( const BigInteger &  in )

inline

bi_xor_ip()

void bi_xor_ip ( BigInteger *  left, const BigInteger &  right  )

inline

operator&()

BigInteger operator& ( const BigInteger &  left, const BigInteger &  right  )

inline

operator*() [1/2]

BigInteger operator*	(	const BigInteger &	left,
		BIG_INTEGER_HALF_WORD	right
	)

"Schoolbook multiplication" (on half words) Complexity - O(x^2)

operator*() [2/2]

BigInteger operator*	(	const BigInteger &	left,
		const BigInteger &	right
	)

"Schoolbook multiplication" (on half words) Complexity - O(x^2)

operator+()

BigInteger operator+ ( const BigInteger &  left, const BigInteger &  right  )

inline

operator++()

BigInteger operator++ ( BigInteger &  a )

inline

operator-()

BigInteger operator- ( const BigInteger &  left, const BigInteger &  right  )

inline

operator--()

BigInteger operator-- ( BigInteger &  a )

inline

operator<()

bool operator< ( const BigInteger &  left, const BigInteger &  right  )

inline

operator<<()

BigInteger operator<< ( const BigInteger &  left, BIG_INTEGER_WORD  right  )

inline

operator<=()

bool operator<= ( const BigInteger &  left, const BigInteger &  right  )

inline

operator==()

bool operator== ( const BigInteger &  left, const BigInteger &  right  )

inline

operator>()

bool operator> ( const BigInteger &  left, const BigInteger &  right  )

inline

operator>=()

bool operator>= ( const BigInteger &  left, const BigInteger &  right  )

inline

operator>>()

BigInteger operator>> ( const BigInteger &  left, BIG_INTEGER_WORD  right  )

inline

operator^()

BigInteger operator^ ( const BigInteger &  left, const BigInteger &  right  )

inline

operator|()

BigInteger operator| ( const BigInteger &  left, const BigInteger &  right  )

inline

operator~()

BigInteger operator~ ( const BigInteger &  left )

inline

Variable Documentation

BIG_INTEGER_BITS

constexpr size_t BIG_INTEGER_BITS = (1 << QBCAPPOW)

constexpr

BIG_INTEGER_HALF_WORD_BITS

constexpr size_t BIG_INTEGER_HALF_WORD_BITS = BIG_INTEGER_WORD_BITS >> 1U

constexpr

BIG_INTEGER_HALF_WORD_SIZE

constexpr int BIG_INTEGER_HALF_WORD_SIZE = BIG_INTEGER_WORD_SIZE << 1U

constexpr

BIG_INTEGER_MAX_WORD_INDEX

constexpr int BIG_INTEGER_MAX_WORD_INDEX = BIG_INTEGER_WORD_SIZE - 1U

constexpr

BIG_INTEGER_WORD_SIZE

constexpr int BIG_INTEGER_WORD_SIZE = BIG_INTEGER_BITS / BIG_INTEGER_WORD_BITS

constexpr