BigInteger

Defines interface for arbitrary precision integers.

Summary
BigIntegerDefines interface for arbitrary precision integers.
CopyrightThis program is free software.
Files
C-kern/api/math/int/bigint.hHeader file BigInteger.
C-kern/math/int/bigint.cImplementation file BigInteger impl.
Types
struct bigint_tExport bigint_t.
struct bigint_fixed_tExport bigint_fixed_t.
Functions
test
unittest_math_int_bigintegerTests interface of bigint_t.
bigint_tBig integer object type.
allocated_digitsThe number of allocated digits.
sign_and_used_digitsThe absolute value of this number is the number of valid digits.
exponentThe exponent with base »2 raised to 32«.
digitsThe values of digits.
lifetime
new_bigintAllocates a new big integer object.
newcopy_bigintMakes a copy from a big integer object.
delete_bigintFrees any allocated memory and sets (*big) to 0.
query
cmp_bigintCompares two big integers and returns -1,0 or +1.
cmpmagnitude_bigintCompares magnitude of two big integers and returns -1,0 or +1.
bitsperdigit_bigintReturns the number of bits used to represent one digit.
exponent_bigintThe number of trailing zero digits which are not explicitly stored.
firstdigit_bigintReturns most significant digit of the number.
isnegative_bigintReturns true if big is negative else false.
iszero_bigintReturns true in case big has value 0 else false.
nrdigits_bigintReturns the number of stored digits (32 bit words) of the big integer.
nrdigitsmax_bigintReturns the maximum number of supported digits stored in a big integer.
size_bigintReturns the sum of exponent_bigint and nrdigits_bigint.
sign_bigintReturns -1, 0 or +1 if big is negative, zero or positive.
todouble_bigintConverts a big integer value into a double.
assign
clear_bigintSets the value to 0.
copy_bigintCopies the value from copyfrom to big.
setfromint32_bigintSets the value of big to the value of the provided parameter.
setfromuint32_bigintSets the value of big to the positive value of the provided parameter .
setfromuint64_bigintSets the value of big to the positive value of the provided parameter .
setfromdouble_bigintSets the value of big to the integer value of the provided parameter.
setbigfirst_bigintSets the value of big integer from an array of integers.
setlittlefirst_bigintSets the value of big integer from an array of integers.
unary operations
clearfirstdigit_bigintSets the first digit to 0 and decrements the number of digits.
negate_bigintInverts the sign of the number.
removetrailingzero_bigintRemoves all trailing digits which are 0.
setnegative_bigintChanges the sign to be negative.
setpositive_bigintChanges the sign to be positive.
binary operations
shiftleft_bigintMultiplies the number by pow(2, shift_count).
shiftright_bigintDivides the number by pow(2, shift_count).
ternary operations
add_bigintAdds the last two parameters and returns the sum in the first.
sub_bigintSubtracts the third from the 2nd parameter and returns the difference in the first.
div_bigintDivides dividend lbig by divisor rbig.
divmod_bigintDivides lbig by rbig and computes lbig modulo rbig.
divmodui32_bigintDivides lbig by divisor of type uint32_t and computes modulo.
divui32_bigintDivides lbig by divisor of type uint32_t.
mod_bigintComputes lbig modulo rbig.
mult_bigintMultiplies two big integers and returns the result.
multui32_bigintMultiplies the big integer with a 32 bit unsigned int.
bigint_fixed_tSame as bigint_t with a fixed size.
lifetime
bigint_fixed_INITInitializes a static object of type bigint_fixed_t.
generic
bigint_fixed_DECLAREDeclares type <bigint_fixedNR_t>.
inline implementation
Macros
bitsperdigit_bigintImplements bigint_t.bitsperdigit_bigint.
div_bigintImplements bigint_t.div_bigint.
divui32_bigintImplements bigint_t.divui32_bigint.
exponent_bigintImplements bigint_t.exponent_bigint.
firstdigit_bigintImplements bigint_t.firstdigit_bigint.
isnegative_bigintImplements bigint_t.isnegative_bigint.
iszero_bigintImplements bigint_t.iszero_bigint.
mod_bigintImplements bigint_t.mod_bigint.
negate_bigintImplements bigint_t.negate_bigint.
nrdigits_bigintImplements bigint_t.nrdigits_bigint.
nrdigitsmax_bigintImplements bigint_t.nrdigitsmax_bigint.
setnegative_bigintImplements bigint_t.setnegative_bigint.
Functions
setpositive_bigintImplements bigint_t.setpositive_bigint.
Macros
sign_bigintImplements bigint_t.sign_bigint.
size_bigintImplements bigint_t.size_bigint.

Copyright

This program is free software.  You can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.

Author

© 2012 Jörg Seebohn

Files

C-kern/api/math/int/bigint.h

Header file BigInteger.

C-kern/math/int/bigint.c

Implementation file BigInteger impl.

Types

struct bigint_t

typedef struct bigint_t bigint_t

Export bigint_t.  Arbitrary precision integer.

struct bigint_fixed_t

typedef struct bigint_fixed_t bigint_fixed_t

Export bigint_fixed_t.  Fixed precision integer.

Functions

Summary
test
unittest_math_int_bigintegerTests interface of bigint_t.

test

unittest_math_int_biginteger

int unittest_math_int_biginteger(void)

Tests interface of bigint_t.

bigint_t

struct bigint_t

Big integer object type.  Supports arbitrary precision integer arithmetic.  Only basic arithmetic operations are supported.

Result of an operation

The result parameter of an operation is reallocated in case the preallocated size is not big enough and if it is of type pointer to pointer to bigint_t.  In case of an error the result parameter will be either left untouched, contains the correct result, or it will be cleared.  Clearing the result is necessary if it is computed digit by digit and an error occurs before the last digit could be computed.

Returned Error Codes

EOVERFLOWIf an operation needs more digits than nrdigitsmax_bigint to represent the result accurately or if the value of bigint_t->exponent does not fit into 16 bit this error is returned.
ENOMEMEvery operation which produces more decimal digits than preallocted needs to reallocate the resulting bigint_t.  If this reallocation fails ENOMEM is returned and the result is not changed.
Summary
allocated_digitsThe number of allocated digits.
sign_and_used_digitsThe absolute value of this number is the number of valid digits.
exponentThe exponent with base »2 raised to 32«.
digitsThe values of digits.
lifetime
new_bigintAllocates a new big integer object.
newcopy_bigintMakes a copy from a big integer object.
delete_bigintFrees any allocated memory and sets (*big) to 0.
query
cmp_bigintCompares two big integers and returns -1,0 or +1.
cmpmagnitude_bigintCompares magnitude of two big integers and returns -1,0 or +1.
bitsperdigit_bigintReturns the number of bits used to represent one digit.
exponent_bigintThe number of trailing zero digits which are not explicitly stored.
firstdigit_bigintReturns most significant digit of the number.
isnegative_bigintReturns true if big is negative else false.
iszero_bigintReturns true in case big has value 0 else false.
nrdigits_bigintReturns the number of stored digits (32 bit words) of the big integer.
nrdigitsmax_bigintReturns the maximum number of supported digits stored in a big integer.
size_bigintReturns the sum of exponent_bigint and nrdigits_bigint.
sign_bigintReturns -1, 0 or +1 if big is negative, zero or positive.
todouble_bigintConverts a big integer value into a double.
assign
clear_bigintSets the value to 0.
copy_bigintCopies the value from copyfrom to big.
setfromint32_bigintSets the value of big to the value of the provided parameter.
setfromuint32_bigintSets the value of big to the positive value of the provided parameter .
setfromuint64_bigintSets the value of big to the positive value of the provided parameter .
setfromdouble_bigintSets the value of big to the integer value of the provided parameter.
setbigfirst_bigintSets the value of big integer from an array of integers.
setlittlefirst_bigintSets the value of big integer from an array of integers.
unary operations
clearfirstdigit_bigintSets the first digit to 0 and decrements the number of digits.
negate_bigintInverts the sign of the number.
removetrailingzero_bigintRemoves all trailing digits which are 0.
setnegative_bigintChanges the sign to be negative.
setpositive_bigintChanges the sign to be positive.
binary operations
shiftleft_bigintMultiplies the number by pow(2, shift_count).
shiftright_bigintDivides the number by pow(2, shift_count).
ternary operations
add_bigintAdds the last two parameters and returns the sum in the first.
sub_bigintSubtracts the third from the 2nd parameter and returns the difference in the first.
div_bigintDivides dividend lbig by divisor rbig.
divmod_bigintDivides lbig by rbig and computes lbig modulo rbig.
divmodui32_bigintDivides lbig by divisor of type uint32_t and computes modulo.
divui32_bigintDivides lbig by divisor of type uint32_t.
mod_bigintComputes lbig modulo rbig.
mult_bigintMultiplies two big integers and returns the result.
multui32_bigintMultiplies the big integer with a 32 bit unsigned int.

allocated_digits

uint16_t allocated_digits

The number of allocated digits.  The number of elements of the digits array.

sign_and_used_digits

int16_t sign_and_used_digits

The absolute value of this number is the number of valid digits.  If this value is 0 the value of bigint_t is 0.  The sign of sign_and_used_digits encodes the sign of this big integer.

exponent

uint16_t exponent

The exponent with base »2 raised to 32«.  The exponent gives the number of digits the number has to be shifted left (multiplied).  After the shift the value of the lowest exponent digits are zero.  The exponent is an optimization to save storage for numbers with a lot of trailing zeros (after conversions from double to bigint).

digits

The values of digits.  Only the first abs(sign_and_used_digits) digits are valid.  The array is of size allocated_digits.  Every digit encodes the value

(digit[digit_pos] << (32 * (digit_pos + exponent)))

lifetime

new_bigint

int new_bigint(/*out*/bigint_t **big,
uint32_t nrdigits)

Allocates a new big integer object.  The new big integer has at least 128 bits (4 digits) or nrdigits which one is higher.  The big integer value is initialized to zero.  The maximum supported value of nrdigits can be obtained with a call to nrdigitsmax_bigint.

newcopy_bigint

int newcopy_bigint(/*out*/bigint_t **big,
const bigint_t *copyfrom)

Makes a copy from a big integer object.  The newly allocated big integer is returned in parameter big.  It has the same value as the number supplied in the second parameter copyfrom.

delete_bigint

int delete_bigint(bigint_t **big)

Frees any allocated memory and sets (*big) to 0.

query

cmp_bigint

int cmp_bigint(const bigint_t *lbig,
const bigint_t *rbig)

Compares two big integers and returns -1,0 or +1.

Returns

-1lbig is lower than rbig
0both numbers are equal
+1lbig is greater than rbig

cmpmagnitude_bigint

int cmpmagnitude_bigint(const bigint_t *lbig,
const bigint_t *rbig)

Compares magnitude of two big integers and returns -1,0 or +1.  This function is the same as cmp_bigint except that the sign of both numbers is considered to be positive.

Returns

-1Absolute value of lbig is lower than absolute value of rbig
0Both absolute values are equal
+1Absolute value of lbig is greater than absolute value of rbig

bitsperdigit_bigint

uint8_t bitsperdigit_bigint(void)

Returns the number of bits used to represent one digit.  The value should be either 32 or 64 depending on the type of architecture.

exponent_bigint

uint16_t exponent_bigint(const bigint_t *big)

The number of trailing zero digits which are not explicitly stored.  If the number is 0 then the exponent must also be 0.

firstdigit_bigint

uint32_t firstdigit_bigint(const bigint_t *big)

Returns most significant digit of the number.  If big is zero the returned value is 0 else it is always number greater zero.

isnegative_bigint

bool isnegative_bigint(const bigint_t *big)

Returns true if big is negative else false.

iszero_bigint

bool iszero_bigint(const bigint_t *big)

Returns true in case big has value 0 else false.

nrdigits_bigint

uint16_t nrdigits_bigint(const bigint_t *big)

Returns the number of stored digits (32 bit words) of the big integer.  The value of a single digit is determined by

digit[digit_pos] << (32 * (digit_pos + exponent_bigint(big)))

nrdigitsmax_bigint

uint16_t nrdigitsmax_bigint(void)

Returns the maximum number of supported digits stored in a big integer.

size_bigint

uint32_t size_bigint(const bigint_t *big)

Returns the sum of exponent_bigint and nrdigits_bigint.  This sum must be smaller or equal to INT16_MAX in case a number is divided with a call to divmodui32_bigint.

sign_bigint

int sign_bigint(const bigint_t *big)

Returns -1, 0 or +1 if big is negative, zero or positive.

todouble_bigint

double todouble_bigint(const bigint_t *big)

Converts a big integer value into a double.  The value +/- INFINITY is returned if big cannot be represented by a double.  Only the first (highest value) 53 bits are used (if double is IEEE 754 conformant) for the mantissa and their offset encoded as exponent.  The other bits are discarded and the precision is lost.  Only if all bits except for the first 53 bits are zero no precision is lost.

Rounding mode

The default rounding mode of uint64_t -> long double is used, which is architecture dependent.  On x84 fpu the uint64_t is converted into long double without loss and then rounded according to the current rounding mode of the fpu.

assign

clear_bigint

void clear_bigint(bigint_t *big)

Sets the value to 0.

copy_bigint

int copy_bigint(bigint_t *restrict *big,
const bigint_t * restrict copyfrom)

Copies the value from copyfrom to big.  If big is not big enough it is reallocated.  In case the reallocation fails ENOMEM is returned.

setfromint32_bigint

void setfromint32_bigint(bigint_t *big,
int32_t value)

Sets the value of big to the value of the provided parameter.

setfromuint32_bigint

void setfromuint32_bigint(bigint_t *big,
uint32_t value)

Sets the value of big to the positive value of the provided parameter .

setfromuint64_bigint

void setfromuint64_bigint(bigint_t *big,
uint64_t value)

Sets the value of big to the positive value of the provided parameter .

setfromdouble_bigint

int setfromdouble_bigint(bigint_t *big,
double value)

Sets the value of big to the integer value of the provided parameter.  The fractional part is discarded.  If the integer part is zero the value is set to 0.  In case parameter value is NAN or INFINITY the error EINVAL is returned.  The assigned bigint_t must have at least 3 allocated integer digits.

setbigfirst_bigint

int setbigfirst_bigint(bigint_t * restrict *big,
int sign,
uint16_t size,
const uint32_t numbers[size],
uint16_t exponent)

Sets the value of big integer from an array of integers.  The integer numbers[0] is considered the most significant digit and numbers[size-1] the least significant digit of the integer value.  If parameter exponent is set to a value > 0 it is considered the number of trailing zero digits which are not explicitly stored in the numbers array.  The parameter sign should be set to either +1 or -1.

setlittlefirst_bigint

int setlittlefirst_bigint(bigint_t * restrict *big,
int sign,
uint16_t size,
const uint32_t numbers[size],
uint16_t exponent)

Sets the value of big integer from an array of integers.  The integer numbers[size-1] is considered the most significant digit and numbers[0] the least significant digit of the integer value.  If parameter exponent is set to a value > 0 it is considered the number of trailing zero digits which are not explicitly stored in the numbers array.  The parameter sign should be set to either +1 or -1.

unary operations

clearfirstdigit_bigint

void clearfirstdigit_bigint(bigint_t *big)

Sets the first digit to 0 and decrements the number of digits.  A zero number is not changed.  If the next digit is also 0 the number of digits is decremented again until a digit is found which is not null.  If all remaining digits are 0 big is set to 0.

negate_bigint

void negate_bigint(bigint_t *big)

Inverts the sign of the number.  A positive signed number becomes negative.  A negative one positive and zero keeps zero.

removetrailingzero_bigint

void removetrailingzero_bigint(bigint_t *big)

Removes all trailing digits which are 0.  This optimization removes the least sign. digit and increments the exponent by one until the least significant digit is not 0 or the exponent reached its maximum value.

setnegative_bigint

void setnegative_bigint(bigint_t *big)

Changes the sign to be negative.  If the sign is zero or already negative nothing is changed.

setpositive_bigint

void setpositive_bigint(bigint_t *big)

Changes the sign to be positive.  If the sign is already positive nothing is changed.

binary operations

shiftleft_bigint

int shiftleft_bigint(bigint_t **result,
uint32_t shift_count)

Multiplies the number by pow(2, shift_count).  Shifting one position left is the same as multiplying by two.  If shift_count is a multiple of bitsperdigit_bigint then only bigint_t.exponent is incremented.  If the exponent overflows EOVERFLOW is returned.

shiftright_bigint

int shiftright_bigint(bigint_t **result,
uint32_t shift_count)

Divides the number by pow(2, shift_count).  Shifting one position right is the same as dividing by two.  If shift_count is a multiple of bitsperdigit_bigint then only bigint_t.exponent is decremented until it becomes 0.  The shift_count least significant bits get lost.  If result is smaller than pow(2, shift_count) the value 0 is returned.

ternary operations

add_bigint

int add_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const bigint_t *rbig)

Adds the last two parameters and returns the sum in the first.  See bigint_t for a discussion of the result parameter.

sub_bigint

int sub_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const bigint_t *rbig)

Subtracts the third from the 2nd parameter and returns the difference in the first.  See bigint_t for a discussion of the result parameter.

div_bigint

int div_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const bigint_t *rbig)

Divides dividend lbig by divisor rbig.  See bigint_t for a discussion of the result parameter.

divmod_bigint

int divmod_bigint(bigint_t *restrict *divresult,
bigint_t *restrict *modresult,
const bigint_t *lbig,
const bigint_t *rbig)

Divides lbig by rbig and computes lbig modulo rbig.  See bigint_t for a discussion of the result parameter.

divmodui32_bigint

int divmodui32_bigint(bigint_t *restrict *divresult,
bigint_t *restrict *modresult,
const bigint_t *lbig,
const uint32_t divisor)

Divides lbig by divisor of type uint32_t and computes modulo.  See bigint_t for a discussion of the result parameter.

divui32_bigint

int divui32_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const uint32_t divisor)

Divides lbig by divisor of type uint32_t.  See bigint_t for a discussion of the result parameter.

mod_bigint

int mod_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const bigint_t *rbig)

Computes lbig modulo rbig.  See bigint_t for a discussion of the result parameter.

mult_bigint

int mult_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const bigint_t *rbig)

Multiplies two big integers and returns the result.  See bigint_t for a discussion of the result parameter.

multui32_bigint

int multui32_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const uint32_t factor)

Multiplies the big integer with a 32 bit unsigned int.  See bigint_t for a discussion of the result parameter.

bigint_fixed_t

struct bigint_fixed_t

Same as bigint_t with a fixed size.  Use this type for static storage and initialization.  Use bigint_fixed_DECLARE to declare a bigint_t type of fixed size.

Summary
lifetime
bigint_fixed_INITInitializes a static object of type bigint_fixed_t.
generic
bigint_fixed_DECLAREDeclares type <bigint_fixedNR_t>.

lifetime

bigint_fixed_INIT

#define bigint_fixed_INIT(nrdigits,
exponent,
...) { 0, nrdigits, exponent, { __VA_ARGS__ } }

Initializes a static object of type bigint_fixed_t.

Parameters

nrdigitsThe magnitude of nrdigits gives the number of 32 bit digits of the whole number.  The sign of nrdigits is the sign of the big integer value.
exponentThe exponent of type uint16_t whose value describes the number of trailing zero digits which are not stored explicitly in the big integer.
...A list of 32-bit digits with nrdigits elements.  The least significant digit comes first.  The last digit is the most significant one.

Example

static bigint_fixed_DECLARE(4) s_bigint4 =
       bigint_fixed_INIT(-4, 0, 1, 2, 3, 4 } ;

This example defines a 128 bit integer with the value -0x00000004000000030000000200000001.

generic

bigint_fixed_DECLARE

#define bigint_fixed_DECLARE(
   nrdigits
) struct CONCAT(CONCAT(bigint_fixed, nrdigits),_t){ uint16_t allocated_digits ; int16_t sign_and_used_digits ; uint16_t exponent ; uint32_t digits[nrdigits] ; }

Declares type <bigint_fixedNR_t>.  Replace NR with the value of the parameter nrdigits.  Use the declared type to reserve and initilize static storage for objects of type bigint_t.  The parameter nrdigits gives the number of preallocated digits.

inline implementation

Summary
Macros
bitsperdigit_bigintImplements bigint_t.bitsperdigit_bigint.
div_bigintImplements bigint_t.div_bigint.
divui32_bigintImplements bigint_t.divui32_bigint.
exponent_bigintImplements bigint_t.exponent_bigint.
firstdigit_bigintImplements bigint_t.firstdigit_bigint.
isnegative_bigintImplements bigint_t.isnegative_bigint.
iszero_bigintImplements bigint_t.iszero_bigint.
mod_bigintImplements bigint_t.mod_bigint.
negate_bigintImplements bigint_t.negate_bigint.
nrdigits_bigintImplements bigint_t.nrdigits_bigint.
nrdigitsmax_bigintImplements bigint_t.nrdigitsmax_bigint.
setnegative_bigintImplements bigint_t.setnegative_bigint.
Functions
setpositive_bigintImplements bigint_t.setpositive_bigint.
Macros
sign_bigintImplements bigint_t.sign_bigint.
size_bigintImplements bigint_t.size_bigint.

Macros

bitsperdigit_bigint

#define bitsperdigit_bigint() ((uint8_t)bitsof(((bigint_t*)0)->digits[0]))

Implements bigint_t.bitsperdigit_bigint.

div_bigint

#define div_bigint(result,
lbig,
rbig) (divmod_bigint(result, 0, lbig, rbig))

Implements bigint_t.div_bigint.

divui32_bigint

#define divui32_bigint(result,
lbig,
divisor) (divmodui32_bigint(result, 0, lbig, divisor))

Implements bigint_t.divui32_bigint.

exponent_bigint

#define exponent_bigint(big) ((big)->exponent)

Implements bigint_t.exponent_bigint.

firstdigit_bigint

#define firstdigit_bigint(
   big
) ((big)->sign_and_used_digits ? big->digits[nrdigits_bigint(big)-1] : 0)

Implements bigint_t.firstdigit_bigint.

isnegative_bigint

Implements bigint_t.isnegative_bigint.

iszero_bigint

#define iszero_bigint(big) (0 == (big)->sign_and_used_digits)

Implements bigint_t.iszero_bigint.

mod_bigint

#define mod_bigint(result,
lbig,
rbig) (divmod_bigint(0, result, lbig, rbig))

Implements bigint_t.mod_bigint.

negate_bigint

#define negate_bigint(
   big
) do { (big)->sign_and_used_digits = (int16_t) ( - (big)->sign_and_used_digits) ; } while (0)

Implements bigint_t.negate_bigint.

nrdigits_bigint

#define nrdigits_bigint(
   big
) ((uint16_t)( (big)->sign_and_used_digits < 0 ? - (big)->sign_and_used_digits : (big)->sign_and_used_digits ))

Implements bigint_t.nrdigits_bigint.

nrdigitsmax_bigint

#define nrdigitsmax_bigint() (0x7fff)

Implements bigint_t.nrdigitsmax_bigint.

setnegative_bigint

#define setnegative_bigint(
   big
) do { (big)->sign_and_used_digits = (int16_t) ( (big)->sign_and_used_digits < 0 ? (big)->sign_and_used_digits : - (big)->sign_and_used_digits ) ; } while (0)

Implements bigint_t.setnegative_bigint.

Functions

setpositive_bigint

#define setpositive_bigint(big) do

Implements bigint_t.setpositive_bigint.

Macros

sign_bigint

Implements bigint_t.sign_bigint.

size_bigint

#define size_bigint(
   big
) ((uint32_t)exponent_bigint(big) + (uint32_t)nrdigits_bigint(big))

Implements bigint_t.size_bigint.

Defines interface for arbitrary precision integers.
Implements BigInteger.
typedef struct bigint_t bigint_t
Export bigint_t.
struct bigint_t
Big integer object type.
typedef struct bigint_fixed_t bigint_fixed_t
Export bigint_fixed_t.
struct bigint_fixed_t
Same as bigint_t with a fixed size.
int unittest_math_int_biginteger(void)
Tests interface of bigint_t.
uint16_t allocated_digits
The number of allocated digits.
int16_t sign_and_used_digits
The absolute value of this number is the number of valid digits.
uint16_t exponent
The exponent with base »2 raised to 32«.
int new_bigint(/*out*/bigint_t **big,
uint32_t nrdigits)
Allocates a new big integer object.
int newcopy_bigint(/*out*/bigint_t **big,
const bigint_t *copyfrom)
Makes a copy from a big integer object.
int delete_bigint(bigint_t **big)
Frees any allocated memory and sets (*big) to 0.
int cmp_bigint(const bigint_t *lbig,
const bigint_t *rbig)
Compares two big integers and returns -1,0 or +1.
int cmpmagnitude_bigint(const bigint_t *lbig,
const bigint_t *rbig)
Compares magnitude of two big integers and returns -1,0 or +1.
uint8_t bitsperdigit_bigint(void)
Returns the number of bits used to represent one digit.
uint16_t exponent_bigint(const bigint_t *big)
The number of trailing zero digits which are not explicitly stored.
uint32_t firstdigit_bigint(const bigint_t *big)
Returns most significant digit of the number.
bool isnegative_bigint(const bigint_t *big)
Returns true if big is negative else false.
bool iszero_bigint(const bigint_t *big)
Returns true in case big has value 0 else false.
uint16_t nrdigits_bigint(const bigint_t *big)
Returns the number of stored digits (32 bit words) of the big integer.
uint16_t nrdigitsmax_bigint(void)
Returns the maximum number of supported digits stored in a big integer.
uint32_t size_bigint(const bigint_t *big)
Returns the sum of exponent_bigint and nrdigits_bigint.
int sign_bigint(const bigint_t *big)
Returns -1, 0 or +1 if big is negative, zero or positive.
double todouble_bigint(const bigint_t *big)
Converts a big integer value into a double.
void clear_bigint(bigint_t *big)
Sets the value to 0.
int copy_bigint(bigint_t *restrict *big,
const bigint_t * restrict copyfrom)
Copies the value from copyfrom to big.
void setfromint32_bigint(bigint_t *big,
int32_t value)
Sets the value of big to the value of the provided parameter.
void setfromuint32_bigint(bigint_t *big,
uint32_t value)
Sets the value of big to the positive value of the provided parameter .
void setfromuint64_bigint(bigint_t *big,
uint64_t value)
Sets the value of big to the positive value of the provided parameter .
int setfromdouble_bigint(bigint_t *big,
double value)
Sets the value of big to the integer value of the provided parameter.
int setbigfirst_bigint(bigint_t * restrict *big,
int sign,
uint16_t size,
const uint32_t numbers[size],
uint16_t exponent)
Sets the value of big integer from an array of integers.
int setlittlefirst_bigint(bigint_t * restrict *big,
int sign,
uint16_t size,
const uint32_t numbers[size],
uint16_t exponent)
Sets the value of big integer from an array of integers.
void clearfirstdigit_bigint(bigint_t *big)
Sets the first digit to 0 and decrements the number of digits.
void negate_bigint(bigint_t *big)
Inverts the sign of the number.
void removetrailingzero_bigint(bigint_t *big)
Removes all trailing digits which are 0.
void setnegative_bigint(bigint_t *big)
Changes the sign to be negative.
void setpositive_bigint(bigint_t *big)
Changes the sign to be positive.
int shiftleft_bigint(bigint_t **result,
uint32_t shift_count)
Multiplies the number by pow(2, shift_count).
int shiftright_bigint(bigint_t **result,
uint32_t shift_count)
Divides the number by pow(2, shift_count).
int add_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const bigint_t *rbig)
Adds the last two parameters and returns the sum in the first.
int sub_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const bigint_t *rbig)
Subtracts the third from the 2nd parameter and returns the difference in the first.
int div_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const bigint_t *rbig)
Divides dividend lbig by divisor rbig.
int divmod_bigint(bigint_t *restrict *divresult,
bigint_t *restrict *modresult,
const bigint_t *lbig,
const bigint_t *rbig)
Divides lbig by rbig and computes lbig modulo rbig.
int divmodui32_bigint(bigint_t *restrict *divresult,
bigint_t *restrict *modresult,
const bigint_t *lbig,
const uint32_t divisor)
Divides lbig by divisor of type uint32_t and computes modulo.
int divui32_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const uint32_t divisor)
Divides lbig by divisor of type uint32_t.
int mod_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const bigint_t *rbig)
Computes lbig modulo rbig.
int mult_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const bigint_t *rbig)
Multiplies two big integers and returns the result.
int multui32_bigint(bigint_t *restrict *result,
const bigint_t *lbig,
const uint32_t factor)
Multiplies the big integer with a 32 bit unsigned int.
#define bigint_fixed_INIT(nrdigits,
exponent,
...) { 0, nrdigits, exponent, { __VA_ARGS__ } }
Initializes a static object of type bigint_fixed_t.
#define bigint_fixed_DECLARE(
   nrdigits
) struct CONCAT(CONCAT(bigint_fixed, nrdigits),_t){ uint16_t allocated_digits ; int16_t sign_and_used_digits ; uint16_t exponent ; uint32_t digits[nrdigits] ; }
Declares type bigint_fixedNR_t.
#define bitsperdigit_bigint() ((uint8_t)bitsof(((bigint_t*)0)->digits[0]))
Implements bigint_t.bitsperdigit_bigint.
#define div_bigint(result,
lbig,
rbig) (divmod_bigint(result, 0, lbig, rbig))
Implements bigint_t.div_bigint.
#define divui32_bigint(result,
lbig,
divisor) (divmodui32_bigint(result, 0, lbig, divisor))
Implements bigint_t.divui32_bigint.
#define exponent_bigint(big) ((big)->exponent)
Implements bigint_t.exponent_bigint.
#define firstdigit_bigint(
   big
) ((big)->sign_and_used_digits ? big->digits[nrdigits_bigint(big)-1] : 0)
Implements bigint_t.firstdigit_bigint.
#define iszero_bigint(big) (0 == (big)->sign_and_used_digits)
Implements bigint_t.iszero_bigint.
#define mod_bigint(result,
lbig,
rbig) (divmod_bigint(0, result, lbig, rbig))
Implements bigint_t.mod_bigint.
#define negate_bigint(
   big
) do { (big)->sign_and_used_digits = (int16_t) ( - (big)->sign_and_used_digits) ; } while (0)
Implements bigint_t.negate_bigint.
#define nrdigits_bigint(
   big
) ((uint16_t)( (big)->sign_and_used_digits < 0 ? - (big)->sign_and_used_digits : (big)->sign_and_used_digits ))
Implements bigint_t.nrdigits_bigint.
#define nrdigitsmax_bigint() (0x7fff)
Implements bigint_t.nrdigitsmax_bigint.
#define setnegative_bigint(
   big
) do { (big)->sign_and_used_digits = (int16_t) ( (big)->sign_and_used_digits < 0 ? (big)->sign_and_used_digits : - (big)->sign_and_used_digits ) ; } while (0)
Implements bigint_t.setnegative_bigint.
#define setpositive_bigint(big) do
Implements bigint_t.setpositive_bigint.
#define size_bigint(
   big
) ((uint32_t)exponent_bigint(big) + (uint32_t)nrdigits_bigint(big))
Implements bigint_t.size_bigint.
The values of digits.
Close