parrotcode: Big Numbers  
Contents  Documentation 
docs/pdds/pdd14_bignum.pod  Big Numbers
This document describes the big number library, the functionality it provides and some internal details of interest to people making use of the library. Some of the areas in which the big number library meet with the rest of Parrot are also discussed.
The big number library provides Parrot with both a collection of (nearly) infinite precision numeric types and an implementation of an extended decimal arithmetic (EDA).
There are benefits in using the big number library to provide both values of effectively unlimited precision and a defined arithmetic, complete with rounding and exceptional conditions, for values which are otherwise easily represented using standard lowlevel types. Both require the same range of operations but differ in the environment under which those operations occur. The effort required to produce a library which implements a decimal arithmetic is not much greater than that needed to provide a base2 big number library. It is true that some tradeoff in both space and speed is made but given the nature of dynamic languages, this should not present too great a burden.
The bignumber library provides the following data types to Parrot:
The library implements these different forms of number using the same internal representation, and differentiates between them only when performing rounding operations. A number has the following abstract form:
[ sign, string of digits, exponent ]
If sign is zero, the number is positive, if equal to one, the number is negative. The number has the value
sign, string of digits * 10 ** exponent
A big integer must always have a nonnegative exponent, a big float may have any exponent and a float with a fixed fractional part will have an exponent greater than a given (negative) number. These limits are not attached to a numeric value, but instead are enforced by giving any operation involving the numbers a context.
In general, Parrot functions will not need to care about what the bignum objects are or do, they should merely be used as arguments to big number functions, the objects will be managed by Parrot's garbage collection in a similar manner to strings.
Additionally the library provides special values, which represent the result of otherwise undefined operations (division by zero, for instance). +Infinity, Infinity and both quiet and signalling Not a Number (NaN) are available. In general, the result of an operation with at least one argument which is NaN will be NaN, if the argument is a signalling NaN, an exception will also be raised. See the EDA for full details.
All operations occur within a defined context. This tells the operations how they should be treating their arguments, what sort of rounding to perform and what to do if information is lost through rounding.
The context provides the environment in which an operation occurs, in particular the following options are available:
It is therefore the current context which determines which numeric type is being considered during a particular operation, this makes it easy to upgrade from one numeric form to another, and also allows for considerable codereuse within the library.
The following exception classes are defined:
The rounding part of the context defines the rounding algorithm to be used, the following are provided (examples assume a precision of 5):
[0, 1234567, 10] => [0, 12345, 12]
[0, 1234567, 10] => [0, 12346, 12]
[0, 1234549, 10] => [0, 12345, 12]
[0, 9999950, 10] => [0, 10000, 13]
The following operations are provided by the library, they function exactly as those described in the Standard Decimal Arithmetic (SDA) (see references below) with some extension to cope with integer and fixed fractional part numbers. Only the deviations are outlined here.
In all cases, the sequence of rounding and promotion to zero outlined by the SDA are followed, even where the context implies integer operations.
A one to one conversion between the abstract representation above and a string is provided by the library, and acts as defined by the standard decimal arithmetic. Other conversation operations may also be implemented, and these may not provide one to one mapping.
A pedantic error checking conversion is available within the library, but only works with native strings. Versions which work with Parrot strings will also be provided, although in a separate file to the rest of the library (they will share a common private header file).
Functions are provided which implement the arithmetic, conversion, creation and destruction of big numbers by dealing with otherwise opaque big number objects.
A big number is represented by the following structure, this is capable of being allocated, tracked and destroyed by the Parrot garbage collection system.
typedef struct {
BN_NIB* buffer; /* string of nibbles */
UINTVAL nibs; /* nibs allocated, in sizeof(BN_NIB) */
UINTVAL flags; /* private flags store: 001 Inf, 010 qNAN, 110 sNAN */
INTVAL digits; /* digits used */
int sign; /* sign of number, 0=> positive or zero, 1 => negative */
INTVAL expn; /* exponent of number */
} parrot_bignum_t;
Within the library, individual decimal digits can be accessed using macros, outside the library, access must be made via exported functions. BN_NIB is likely to be a UINTVAL, but this is not essential.
Special values are represented by setting digits to zero and setting appropriate private flags, using internal macros. Infinity has one flag field, NaN another flag field and sNaN a third. In general the flags should not be examined directly, even within the module.
typedef struct {
INTVAL precision; /* number of digs to retain */
BN_ROUNDING rounding; /* rounding type to perform */
BOOLVAL extended; /* do we use extended or base semantics? */
unsigned char flags; /* records possible errors */
unsigned char traps; /* throw errors or not? */
} parrot_bignum_context;
BN_ROUNDING is an enumeration of the possible rounding types as described above. traps is a bitmask of exception traps, 0 implies that a trap is disabled and 1 implies it is enabled. flags is a bitmask which records exceptional conditions and has the same fields at flags.
It is expected that language level types implement big floats using a global floating point context which is tagged onto an interpreter structure (and can thus be modified by called the right opcodes). That big integers and fixedfraction number are provided by creating a context with an appropriate precision whenever a call into the library is made.
When an exceptional condition is raised by the module, control is passed to BN_nonfatal()
, this examines the error which has occurred and the current context to determine which class of error has occurred. If the corresponding trap handler is not enabled, the context's flags are updated and control is returned to the bignumber library, otherwise the exception becomes fatal. How this mechanism interacts with Parrot's own is yet to be decided.
The possible exceptions are detailed in the extended decimal arithmetic.
The Standard Decimal Arithmetic provides a collection of tests for both its base and extended behaviour. Initially it is hoped that this library can pass all base tests, with extended tests to be included at a later date as it is extended to cope with values such as +Inf.
Fill in the remaining functions from the EDA, verify that the test suite still passes, integrate the library into the rest of Parrot, provide PMC types and suitable opcodes. Conversion to and from Parrot strings, conversion to and from floating point types, sprintf output of bignumbers.
IBM's Standard Decimal Arithmetic, with tests http://www2.hursley.ibm.com/decimal/
Perl's Math::Big* modules.
Maintainer: Alex Gough (alex@earth.li)
Class: Internals
PDD Number: 14
Version: $Id$
Status: Informational
Last Modified: $Id$
PDD Format: 1
Language: English
