NAME

types/bignum.c - A decimal arithmetic library for Perl and Parrot

DESCRIPTION

This code is intended for inclusion in the parrot project, and also for backporting into Perl5 (as a CPAN module). Any patches to this code will likely find their way back to the Mother Ship, as it were.

There is a good deal of scope for improving the speed of this code, modifications are encouraged as long as the extended regression tests continue to pass. Alex Gough, 2002

It was a very inconvenient habit of kittens (Alice had once made the remark) that, whatever you say to them, they always purr. "If they would only purr for `yes,' and mew for `no,' or any rule of that sort," she had said, "so that one could keep up a conversation! But how can you talk with a person if they always say the same thing?"

On this occasion the kitten only purred: and it was impossible to guess whether it meant `yes' or `no'.

When in parrot

When the library is used within parrot, all calls expect an additional first argument of an interpreter, for the purposes of memory allocation, some internal macros do not (getd/setd and CHECK(O|U)FLOW.

If you're being useful and inserting proper rapid fillins, start with the BN_i* methods, but make sure any errors can still be thrown.

Macros

Access digits, macros assume length given.

BN_setd(BIGNUM*, pos, value): Set digit at pos (zero is lsd) to value.
int BN_getd(BIGNUM*, pos): Get value of digit at pos.
CHECK_OVERFLOW(bn, incr, context): If increasing the exponent of bn by incr will cause overflow (as decided by elimit), returns true.
CHECK_UNDERFLOW(bn, decrement, context): If subtracting decrement (a positive number) from the exponent of bn would cause underflow, returns true.

Special Values

am_INF(bn): True if bn is +Infinity or -Infinity.
am_NAN(bn): True if bn is either a quiet or signalling NaN.
am_sNAN(bn): True if bn is a signalling NaN.
am_qNAN(bn): True if bn is a quiet NaN.

Creation and Memory Management Functions

BIGNUM *BN_new(PINTD_ INTVAL length): Create a new BIGNUM. length is number of decimal digits required. The bignumber will be equal to zero.
void BN_grow(PINTD_ BIGNUM *in, INTVAL length): Grows bn so that it can contain length decimal digits, does not modify the value of the bignumber.
void BN_destroy(PINTD_ BIGNUM *bn): Frees all the memory used by the BIGNUM.
BN_CONTEXT *BN_create_context(PINTD_ INTVAL precision): Creates a new context object, with specified precision, other fields are initialised as follows:; The context object can be destroyed with free().
INTVAL BN_set_digit(PINT_ BIGNUM *bn, INTVAL pos, INTVAL value): Sets digit at pos (zero based) to value. Number is grown if digits > allocated space are accessed, but intermediate digits will have undefined values. If pos is beyond digits then digits is also updated.
INTVAL BN_get_digit(PINTD_ BIGNUM *bn, INTVAL pos): Get the value of the decimal digit at pos, returns -1 if pos is out of bounds.
int BN_set_inf(PINTD_ BIGNUM *bn)
int BN_set_qNAN(PINTD_ BIGNUM *bn)
int BN_set_sNAN(PINTD_ BIGNUM *bn): Sets its argument to appropriate value.; Infinity is represented as having zero digits, an undefined exponent and private flags set to BN_inf_FLAGS.; sNAN is represented as having zero digits, an undefined exponent, an undefined sign and both qNAN and sNAN bits set.; qNAN is represented as having zero digits, an undefined exponent and only the qNAN bit set.
int BN_set_verybig(PINTD_ BIGNUM *bn, BN_CONTEXT *context): Used when an operation has overflowed, sets bn according to context->rounding and the sign of bn:
BIGNUM *BN_copy(PINTD_ BIGNUM *one, BIGNUM *two): Copies two into one, returning one for convenience.
BIGNUM *BN_new_from_int(PINTD_ INTVAL value): Create a new bignum from a (signed) integer value (INTVAL) We assume that the implementation limits are somewhat larger than those required to store a single integer into a bignum.
void BN_PRINT_DEBUG (BIGNUM *bn, char *mesg): Dump the bignum for testing, along with a little message.
INTVAL BN_nonfatal(PINTD_ BN_CONTEXT *context, BN_EXCEPTIONS except, char *msg): When an exceptional condition occurs after which execution could continue. If context specifies that death occurs, then so be it.
void BN_exception(PINTD_ BN_EXCEPTIONS exception, char *message): Throw `exception'. Should be accessed via a BN_EXCEPT macro, this version is provided until Parrot exceptions are sorted out properly.
INTVAL BN_to_scientific_string(PINTD_ BIGNUM*bn, char **dest): Converts bn into a scientific representation, stored in dest.
INTVAL BN_to_engineering_string(PINTD_ BIGNUM*bn, char **dest): Converts *bn into a engineering representation, stored in **dest.; These functions return char* strings only, parrot may want to reimplement these so that locales and the like are nicely coped with.; Any reimplementation should be in a seperate file, this section of the main file can be #ifdefed out if this is done.; Memory pointed to by dest is not freed by this function.
INTVAL BN_to_scieng_string(PINTD_ BIGNUM *bn, char **dest, int eng): Does the heavy string handling work, eng defines the conversion to perform.
BIGNUM *BN_from_string(PINTD_ char *s2, BN_CONTEXT *context): Convert a scientific string to a BIGNUM. This function deals entirely with common-or-garden C byte strings, so the library can work anywhere. Another version will be eventually required to cope with the parrot string fun.; This is the Highly Pedantic string conversion. If context has extended as a true value, then the full range of extended number is made available, and any string which does not match the numeric syntax is converted to a quiet NaN.; Does not yet check for exponent overflow.
int BN_strip_lead_zeros(PINTD_ BIGNUM *bn, BN_CONTEXT *context): Removes any zeros before the msd and after the lsd.
int BN_strip_tail_zeros(PINTD_ BIGNUM *bn, BN_CONTEXT *context): Removes trailing zeros and increases the exponent appropriately. Does not remove zeros before the decimal point.
int BN_make_integer(PINTD_ BIGNUM *bn, BN_CONTEXT *context): Convert the number to a plain integer if precision such that this is possible.
int BN_really_zero(PINTD_ BIGNUM *bn, int allow_neg_zero): Sets any number which should be zero to a canonical zero.; To check if a number is equal to zero, use BN_is_zero().
void BN_round(PINTD_ BIGNUM *bn, BN_CONTEXT *context): Rounds *bn according to *context.
int BN_iround (PINTD_ BIGNUM *bn, BN_CONTEXT *context): Rounds victim according to context.; Round assumes that any leading zeros are significant (after an addition operation, for instance).; If precision is positive, the digit string is rounded to have no more than precision digits. If precision is equal to zero, the number is treated as an integer, and any digits after the number's decimal point are removed. If precision is negative, the number is rounded so that there are no more than - precision digits after the decimal point.; eg. for 1.234567E+3 with rounding of ROUND_DOWN
int BN_round_up(PINTD_ BIGNUM *bn, BN_CONTEXT *context): Truncates coefficient of bn to have precision digits, then adds 1 to the last digits and carries until done. Do not call this function with non-positive values of precision.
int BN_round_down(PINT_ BIGNUM *bn, BN_CONTEXT *context): Truncates the coefficient of bn to have precision digits. Do not call this function with non-positive precision.
void BN_round_as_integer(PINTD_ BIGNUM *bn, BN_CONTEXT *context): precision must be less than one. This rounds so that expn is at least precision. Name is slightly misleading.

Arithmetic operations

Operations are performed like this:

Rounding: Both operands are rounded to have no more than context->precision digits.
Computation: The operation is computed.
Rounding of result: The result is then rounded to context->precision digits.
Conversion to zero and integerisation: If the result is equal to zero, it is made exactly zero.; Where the length of the coefficient + the exponent of the result is less than context->precision, the result is converted into an integer.

The general form for all arithmetic operations is:

    void BN_operation(result, one, two, context)

int BN_arith_setup(PINTD_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context, BN_SAVE_PREC *restore): Rounds one and two ready for arithmetic operation.; We assume that an operation might extend the digit buffer with zeros on either side, but not tamper with the actual digits of the number, we can then easily return the number to the correct (but still rounded) representation in _cleanup later; If you can promise that you will not modify the representation of one and two during your operation, then you may pass &restore as a NULL pointer to both setup and cleanup.; If overflow or underflow occurs during rounding, the numbers will be modified to the appropriate representation and will not be restorable.
int BN_arith_cleanup(PINTD_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context, BN_SAVE_PREC *restore): Rounds result, one, two, checks for zeroness and makes integers. Fixes one and two so they don't gain precision by mistake.
int BN_align(PINTD_ BIGNUM *one, BIGNUM *two): Adds zero digits so that decimal points of each number are at the same place.
void BN_add(PINTD_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context): Adds one to two, returning value in result.
int BN_iadd (PINTD_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context): Adds together two aligned big numbers with coefficients of equal length. Returns a result without reference to the signs of its arguments. Cannot cope with special values.
void BN_subtract(PINTD_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context): Subtracts *two from *one, returning value in *result.
int BN_isubtract (PINTD_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context): Subtracts two from one, assumes both numbers have positive aligned coefficients of equal length. Sets sign of result as appropriate. Cannot cope with special values.
void BN_plus(PINTD_ BIGNUM *result, BIGNUM *one, BN_CONTEXT *context): Perform unary + on *one. Does all the rounding and what have you.
void BN_minus(PINTD_ BIGNUM *result, BIGNUM *one, BN_CONTEXT *context): Perform unary - (minus) on *one. Does all the rounding and what have you.
void BN_compare (PINT_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context): Numerically compares *one and *two, storing the result (as a BIGNUM) in *result.
void BN_multiply (PINTD_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context): Multiplies *one and *two, storing the result in *result.
int BN_imultiply (PINTD_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context): Multiplication without the rounding and other set up.
void BN_divide(PINTD_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context): Divide two into one, storing up to precision digits in result. Performs own rounding. We also assume that this function will not be used to produce a BigInt. That is the job of divide_integer().; If you want to divide two integers to produce a float, you must do so with precision greater than the number of significant digits in either operand. If you want the result to be an integer or a numer with a fixed fractional part
void BN_divide_integer (PINTD_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context): Places the integer part of *one divided by *two into *result.
void BN_remainder(PINTD_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context): Places the remainder from divide-integer (above) into *result.
BN_idivide(PINT_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context, BN_DIV_ENUM operation, BIGNUM *rem): Does the heavy work for the various division wossnames.
INTVAL BN_comp (PINTD_ BIGNUM *one, BIGNUM *two, BN_CONTEXT *context): Comparison with no rounding etc.
void BN_power(PINTD_ BIGNUM *result, BIGNUM *bignum, BIGNUM *expn, BN_CONTEXT *context): Calculate result = bignum to the power of *expn;
void BN_rescale(PINTD_ BIGNUM *result, BIGNUM *one, BIGNUM *two, BN_CONTEXT *context): Rescales *one to have an exponent of *two.
INTVAL BN_to_int(PINT_ BIGNUM *bn, BN_CONTEXT *context): Converts the bignum into an integer, raises overflow if an exact representation cannot be created.
INTVAL BN_is_zero(BIGNUM *foo, BN_CONTEXT *context): Returns a boolean value indicating whether *foo is zero.

TODO

Parrot string playing, exception raising

parrotcode: A decimal arithmetic library for Perl and Parrot
Contents \| Big Number Arithmetic