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

# 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:

``` elimit   = BN_HARD_EXPN_LIMIT ( defined during configure)
rounding = ROUND_HALF_UP
extended = 1
flags    = 0
traps    = Division by zero, invalid operation, overflow, underflow
and rounded are enabled.
Lost digits and inexact are disabled.```
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`:

``` ROUND_HALF_UP, ROUND_HALF_EVEN => sign Infinity
ROUND_DOWN => sign, largest finite number in given precision (or Inf, if
infinite precision is specified)
ROUND_CEILING => same as round down, if sign is 1, +Inf otherwise
ROUND_FLOOR => same as round down, if sign is 0, -Inf otherwise```
`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 `#ifdef`ed 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`

```    precision:  4 =>  1.234E+3      1234
precision:  6 =>  1.234567E+3   1234.56
precision:  9 =>  1.234567E+3   1234.567
precision:  0 =>  1234          1234
precision: -1 =>  1.2345E+3     1234.5
precision: -9 =>  1.234567E+3   1234.567```
`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`.

```    result = 1  => one > two
result = -1 => two > one
result = 0  => one == two```
`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 