Author: chromatic Date: Wed Dec 10 00:58:53 2008 New Revision: 33751 Modified: trunk/docs/pdds/draft/pdd14_numbers.pod
Log: [PDD] Reviewed Numbers PDD; minor edits to formatting and phrasing. Sadly, IBM's Standard Decimal Arithmetic Standard is no longer available from IBM's site. It's unclear how to include this within Parrot as it stands anyway. This PDD needs more thinking in the next few days. Modified: trunk/docs/pdds/draft/pdd14_numbers.pod ============================================================================== --- trunk/docs/pdds/draft/pdd14_numbers.pod (original) +++ trunk/docs/pdds/draft/pdd14_numbers.pod Wed Dec 10 00:58:53 2008 @@ -1,4 +1,4 @@ -# Copyright (C) 2001-2004, The Perl Foundation. +# Copyright (C) 2001-2008, The Perl Foundation. # $Id$ =head1 NAME @@ -34,7 +34,6 @@ integer may be autoboxed as an C<Integer> PMC, or as an HLL type mapped to C<Integer>. - =head2 Floating-point data types Parrot provides a native floating-point data type, generally known as a "Num". @@ -50,13 +49,12 @@ method call, a native float may be autoboxed as a C<Float> PMC, or as an HLL type mapped to C<Float>. - =head2 Integer PMC The C<Integer> PMC is a high-level integer type, providing the features of a integer data type appropriate for use in a high-level language. Some languages -may be able to use Parrot's C<Integer> directly as their integer data type, -others may subclass C<Integer> to add their own functionality, and others may +may be able to use Parrot's C<Integer> directly as their integer data type. +Others may subclass C<Integer> to add their own functionality, and others may implement their own high-level integer data type. The C<Integer> PMC has a single attribute, the integer value. @@ -65,20 +63,20 @@ =over 4 -=item init() +=item C<init()> -Initialize the C<Integer> to 0. +Initializes the C<Integer> to 0. -=item set_pmc(PMC *value) and set_integer_same(PMC* value) +=item C<set_pmc(PMC *value)> and C<set_integer_same(PMC *value)> -Set the C<Integer> to the integer value of the PMC argument. +Sets the C<Integer> to the integer value of the PMC argument. -=item set_integer_native(INTVAL value) +=item C<set_integer_native(INTVAL value)> Set the C<Integer> to the passed-in integer value. -=item set_number_native(FLOATVAL value), set_bool(INTVAL value), - set_bigint_int(INTVAL value), set_string_native(STRING *value) +=item C<set_number_native(FLOATVAL value)>, C<set_bool(INTVAL value)>, + C<set_bigint_int(INTVAL value)>, C<set_string_native(STRING *value)> Morphs the C<Integer> PMC to a C<Float>, C<Boolean>, C<BigInt>, or C<String> PMC, and sets the value from the passed in value. @@ -86,99 +84,104 @@ {{NOTE: the morphing behavior is currently under consideration and may be rejected.}} -=item get_integer() +=item C<get_integer()> Retrieves the integer value of the C<Integer>. -=item get_bool() +=item C<get_bool()> Returns the boolean value of the C<Integer> (false if 0, true otherwise). -=item get_number() +=item C<get_number()> Returns the integer value of the C<Integer> as a floating-point number. -=item get_bignum() +=item C<get_bignum()> Returns the integer value of the C<Integer> in a new C<BigInt> PMC. -=item get_string() and get_repr() +{{ NOTE: this vtable entry may be deprecated }} + +=item C<get_string()> and C<get_repr()> Returns the integer value of the C<Integer> as a string. -=item [add|subtract|multiply|divide|floor_divide|modulus|pow]_int(INTVAL b, - PMC *dest) +=item C<[add|subtract|multiply|divide|floor_divide|modulus|pow]_int(INTVAL b, + PMC *dest)> -Add/subtract/multiply/divide/modulus/exponent an integer value with the -C<Integer> PMC, and return the result as a new PMC (the C<dest> parameter is -unused). Overflow of the native integer storage auto-promotes the result PMC -to a C<BigInt>. - -=item i_[add|subtract|multiply|divide|floor_divide|modulus|pow]_int(INTVAL b) - -Add/subtract/multiply/divide/modulus/exponent an integer value with the -C<Integer> PMC, and set the C<Integer> to the resulting value. Overflow of the -native integer storage auto-promotes the C<Integer> to a C<BigInt>. +Adds/subtracts/multiplies/divides/moduluses/exponents an integer value with +the C<Integer> PMC, and returns the result as a new PMC. (The C<dest> +parameter is unused). Overflow of the native integer storage auto-promotes the +result PMC to a C<BigInt>. Note that these are multidispatched. + +=item C<i_[add|subtract|multiply|divide|floor_divide|modulus|pow]_int(INTVAL + b)> + +Adds/subtracts/multiplies/divides/moduluses/exponents an integer value with +the C<Integer> PMC, and sets the C<Integer> to the resulting value. Overflow +of the native integer storage auto-promotes the C<Integer> to a C<BigInt>. +Note that these are multidispatched. {{NOTE: there is some discussion of having this promotion of storage happen purely internally (perhaps by swapping vtables), rather than converting to a different PMC type.}} -=item - i_[add|subtract|multiply|divide|floor_divide|modulus|pow]_float(INTVAL b) +=item C<i_[add|subtract|multiply|divide|floor_divide|modulus|pow]_float(INTVAL + b)> -Add/subtract/multiply/divide/modulus/exponent an integer value with the -C<Integer> PMC, and set the C<Integer> to the resulting value, morphing it -to a C<Float>. +Add/subtract/multiply/divide/modulus/exponent an integer value with the the +C<Integer> PMC, and set the C<Integer> to the resulting value, morphing it to +a C<Float>. Note that these are multidispatched. -=item increment() +=item C<increment()> -Add 1 to the value of the integer. +Adds 1 to the value of the integer. This may autopromote the PMC to a +C<BigInt>. -=item decrement() +=item C<decrement()> -Subtract 1 from the value of the integer. +Subtracts 1 from the value of the integer. This may autopromote the PMC to a +C<BigInt>. -=item absolute() +=item C<absolute()> -Return an C<Integer> PMC set to the absolute value of the current C<Integer>. +Returns an C<Integer> PMC set to the absolute value of the current C<Integer>. -=item i_absolute() +=item C<i_absolute()> -Set the C<Integer> to the absolute value of itself. +Sets the C<Integer> to the absolute value of itself. -=item freeze() +=item C<freeze()> -Freeze the C<Integer> PMC for storage. +Freezes the C<Integer> PMC for storage. -=item thaw() +=item C<thaw()> -Thaw the C<Integer> PMC from storage. +Thaws the C<Integer> PMC from storage. =back =head3 Integer Multis -Many of the math vtable functions are defined instead as multiple dispatch -functions. +Many of the math vtable functions are defined as multiple dispatch functions. =over 4 -=item [add|subtract|multiply|divide|floor_divide|modulus|pow](PMC *value, - PMC *dest) +=item C<[add|subtract|multiply|divide|floor_divide|modulus|pow](PMC *value, + PMC *dest)> -Perform the addition/subtraction/multiplication/division/modulus/exponent -operation, and return a new PMC containing the resulting value. Multiple +Performs the addition/subtraction/multiplication/division/modulus/exponent +operation, and returns a new PMC containing the resulting value. Multiple dispatch variants are defined for C<Integer>, C<Complex>, C<BigInt>, C<String>, and C<DEFAULT>. Overflow of the native integer storage auto-promotes the result PMC to a C<BigInt>. -=item i_[add|subtract|multiply|divide|floor_divide|modulus|pow](PMC *value) +=item C<i_[add|subtract|multiply|divide|floor_divide|modulus|pow](PMC *value)> -Perform the addition/subtraction/multiplication/division/modulus/exponent +Performs the addition/subtraction/multiplication/division/modulus/exponent operation, morphing the C<Integer> to the passed in type, and setting it to the result. Multiple dispatch variants are defined for C<Integer>, C<Complex>, C<BigInt>, and C<DEFAULT>. @@ -186,23 +189,23 @@ Overflow of the native integer storage auto-promotes the C<Integer> to a C<BigInt>. -=item is_equal(PMC *value) +=item C<is_equal(PMC *value)> -Compare the C<Integer> to the passed in PMC, return true (1) if they are +Compares the C<Integer> to the passed in PMC, returning true (1) if they are equal, and false (0) otherwise. Multiple dispatch variants are defined for -C<BigInt> and C<DEFAULT>. {{NOTE: Presumably the C<String>, C<Integer>, -and C<Float> cases are all covered by C<DEFAULT>.}} +C<BigInt> and C<DEFAULT>. {{NOTE: Presumably the C<String>, C<Integer>, and +C<Float> cases are all covered by C<DEFAULT>.}} -=item cmp(PMC *value) +=item C<cmp(PMC *value)> -Compare the C<Integer> to the passed in PMC, return 1 if C<Integer> is +Compares the C<Integer> to the passed in PMC, returning 1 if C<Integer> is greater, -1 if the PMC is greater, and 0 if they are equal. Multiple dispatch variants are defined for C<String>, C<Float>, and C<DEFAULT>. {{NOTE: Presumably the C<Integer> and C<BigInt> cases are covered by C<DEFAULT>.}} -=item cmp_num(PMC *value) +=item C<cmp_num(PMC *value)> -Compare the C<Integer> to the passed in PMC, return 1 if C<Integer> is +Compares the C<Integer> to the passed in PMC, returning 1 if C<Integer> is greater, -1 if the PMC is greater, and 0 if they are equal. Multiple dispatch variants are defined for C<String>, C<Float>, and C<DEFAULT>. {{NOTE: Presumably the C<Integer> and C<BigInt> cases are covered by C<DEFAULT>.}} @@ -213,10 +216,10 @@ =over 4 -=item get_as_base(INTVAL base) +=item C<get_as_base(INTVAL base)> -Convert the decimal integer to another base (anything from base 2 to base 36). -Return the result as a string. +Converts the decimal integer to another base (anything from base 2 to base +36), returning the result as a STRING. =back @@ -237,8 +240,8 @@ 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 base-2 big number library. -It is true that some trade-off in both space and speed is made but given the -nature of dynamic languages, this should not present too great a burden. +There is a trade-off in both space and speed, but given the nature of dynamic +languages, this should not present too great a burden. =head2 Numeric types provided @@ -261,42 +264,43 @@ =back -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: +The library implements these different forms of numbers 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 +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 non-negative exponent, a big float may have -any exponent and a float with a fixed fractional part will have an exponent +A big integer must always have a non-negative 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 I<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 +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. =head2 Special Values -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. +Additionally the library provides special values which represent the result of +otherwise undefined operations (division by zero, for instance). Positive and +negative infinity (C<Inf> or C<+Inf> and C<-Inf>, respectively) and both quiet +and signalling Not a Number (C<NaN>) are available. In general, the result of +an operation with at least one argument which is C<NaN> will be C<NaN>. If the +argument is a signalling C<NaN>, an exception will also be raised. See the +EDA for full details. =head2 Context 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. +they should treat their arguments, what sort of rounding to perform, and what +to do if rounding loses information. The context provides the environment in which an operation occurs, in particular the following options are available: @@ -305,49 +309,48 @@ =item precision -A positive I<precision> indicates that big floats are to be used, these cannot -have more than I<precision> digits in their coefficient before or after any -operation. Arguments to operations with more than I<precision> digits will be -truncated and rounded appropriately and results of operations will not have -more than I<precision> digits in their coefficients, with any extra digits -accumulated during the calculation of the operation being truncated and -rounded as required. - -A I<precision> of zero indicates that integer operations are to be performed. -Arguments to operations are rounded so that they have no fractional part, and -the result of all operations will be rounded to be integers. - -A negative value of I<precision> indicates that a fixed number of fractional -digits are to be provided, with arguments and results being truncated after -those digits. +A positive I<precision> requires the use of big floats. These cannot have more +than I<precision> digits in their coefficient before or after any operation. +Arguments to operations with more than I<precision> digits will be truncated +and rounded appropriately. Results of operations will not have more than +I<precision> digits in their coefficients, with any extra digits accumulated +during the calculation of the operation being truncated and rounded as +required. + +A I<precision> of zero requires the use of integer operations. Arguments to +operations are rounded so that they have no fractional part, and the result of +all operations will be rounded to be integers. + +A negative value of I<precision> requires the use of a fixed number of +fractional digits, with arguments and results being truncated after those +digits. -With non-positive values of I<precision> the total number of digits in the +With non-positive values of I<precision>, the total number of digits in the coefficient is limited only by available memory. =item rounding -The rounding part of the context defines the rounding algorithm which is to be -applied when truncating digits from a number's coefficient. The available -rounding forms are outlined below. +The rounding part of the context defines the rounding algorithm to apply when +truncating digits from a number's coefficient. The available rounding forms +are outlined below. =item traps and flags -The I<traps> part of the context defines how exceptions are raised by the -library. Seven distinct classes of error can occur, if the corresponding trap -is set (enabled) then an exception is raised by the library (and dispatched to -Parrot) otherwise execution continues with the exception class being recorded -in flags. For more details see the extended decimal arithmetic standard. +The I<traps> part of the context defines how the library raises exceptions. +Seven distinct classes of error can occur. If the corresponding trap is set +(enabled), the library raises an exception. Otherwise, execution continues +with the exception class recorded in flags. For more details, see the +extended decimal arithmetic standard. =back -It is therefore the current I<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 code-reuse -within the library. +The current I<context> determines the numeric type during a particular +operation. This makes it easy to upgrade from one numeric form to another and +also allows for considerable code-reuse within the library. =head2 Exception Classes -The following exception classes are defined: +The following exception classes are available: =over 4 @@ -367,9 +370,9 @@ =item Invalid Operation -An invalid operation was attempted, for instance a sNaN was provided as an -argument to a function. This also covers recoverable errors like 0/0, which -signals Invalid Operation and can return NaN. +An invalid operation was attempted, for instance when C<NaN> is present as an +argument to a function. This also covers recoverable errors such as 0/0, +which signals Invalid Operation and can return C<NaN>. =item Overflow @@ -387,8 +390,8 @@ =head2 Rounding -The rounding part of the context defines the rounding algorithm to be used, -the following are provided (examples assume a precision of 5): +The rounding part of the context defines the rounding algorithm to used. The +following contexts are available (examples assume a precision of 5): =over 4 @@ -401,8 +404,8 @@ =item Round half up -The first lost digit is examined, if this is in the range 0-4, the coefficient -is truncated directly, if in the range 5-9, one is added to the final digit of +The first lost digit is examined. If this is in the range 0-4, the coefficient +is truncated directly. If in the range 5-9, one is added to the final digit of the coefficient. If this leads to a coefficient with more than I<precision> digits, the number is rounded again, removing the trailing zero. This is essentially rounding to nearest. @@ -413,35 +416,35 @@ =item Round half even -The first lost digit is examined, if it lies in the range 0-4, the coefficient -is truncated directly, if in the range 6-9, the coefficient is rounded up. If -the first lost digit is equal to 5, and the remaining lost digits in the +The first lost digit is examined. If it lies in the range 0-4, the coefficient +is truncated directly. If in the range 6-9, the coefficient is rounded up. If +the first lost digit is equal to 5 and the remaining lost digits in the coefficient are non-zero, the number is also rounded up. If the lost digits are equal to exactly half, the number is rounded up if the least significant retained digit is odd, and rounded down if it is even. =item Round Floor -If the digits to be discarded are non zero, and the number is negative, the +If the digits to be discarded are non zero and the number is negative, the coefficient is rounded up, otherwise it remains the same. -This is rounding towards -Infinity. +This is rounding towards C<-Inf>. =item Round Ceiling If the digits to be discarded are non zero, and the number is positive, the coefficient is rounded up, otherwise it remains the same. -This is rounding towards +Infinity. +This is rounding towards C<Inf>. =back =head2 Operations -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. +The library provides the following operations. They function exactly as those +described in the Standard Decimal Arithmetic (SDA), 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. @@ -454,15 +457,16 @@ =item Division -Under integer conditions, division is halted once the first fractional digit -is calculated, with the result then being rounded to an integer and returned. -Under fixed-fraction conditions, one more digit than needed is calculated, -with the coefficient then being rounded and returned. +Under integer conditions, division halts once the first fractional digit is +calculated, with the result rounded to an integer and returned. Under +fixed-fraction conditions, one more digit than needed is calculated, with the +coefficient then rounded and returned. If a floating point value is required, or if inexact division by a very small number is attempted, it may be wise to follow big float arithmetic to limit the number of digits returned. It is safe to chose a precision at least as -big the largest number of digits of either argument to the division function. +large as the largest number of digits of either argument to the division +function. =item Integer division, Remainder @@ -476,9 +480,9 @@ =item Comparison -Comparison returns a big number which is equal to 1, 0 or -1 if the first -argument is larger, equal to or smaller than the second. An alternative form -which returns an INTVAL is also provided. +Comparison returns a big number which is equal to 1, 0, or -1 if the first +argument is larger, equal to, or smaller than the second. An alternate form +returns an INTVAL. =item Rescale @@ -492,13 +496,13 @@ 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. +arithmetic. Other conversation operations may also be implemented; 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). +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). =head1 IMPLEMENTATION @@ -508,56 +512,54 @@ =head2 Big number representation -A big number is represented by the following structure, this is capable of -being allocated, tracked and destroyed by the Parrot garbage collection -system. +A big number is represented by the following structure, capable of being +allocated, tracked, and destroyed by the Parrot garbage collection system. typedef struct { - BN_NIB* buffer; /* string of nibbles */ + 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 */ + INTVAL digits; /* digits used */ + INTVAL expn; /* exponent of number */ + int sign; /* sign of number, 0 => positive or zero, 1 => negative */ } 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 +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 I<digits> to zero and setting appropriate private I<flags>, using internal macros. Infinity has one flag -field, NaN another flag field and sNaN a third. In general the flags should +field, NaN another flag field, and sNaN a third. In general the flags should not be examined directly, even within the module. =head2 Context 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? */ + 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; I<BN_ROUNDING> is an enumeration of the possible rounding types as described -above. I<traps> is a bitmask of exception traps, 0 implies that a trap is +earlier. I<traps> is a bitmask of exception traps. 0 implies that a trap is disabled and 1 implies it is enabled. I<flags> is a bitmask which records exceptional conditions and has the same fields at I<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 -fixed-fraction number are provided by creating a context with an appropriate -precision whenever a call into the library is made. +Language level types should implement big floats using a global floating point +context available in an interpreter structure (and accessible). Big integers +and fixed-fraction number are provided by creating a context with an +appropriate precision whenever a call into the library is made. =head2 Exceptional Conditions -When an exceptional condition is raised by the module, control is passed to -C<BN_nonfatal()>, this examines the error which has occurred and the current +When the module raises an exceptional condition, control passes to +C<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 +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. @@ -565,9 +567,7 @@ =head1 Tests The Standard Decimal Arithmetic provides a collection of tests for both its -base and extended behavior. 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. +base and extended behavior. =head1 TODO @@ -582,8 +582,8 @@ =head1 REFERENCES -IBM's Standard Decimal Arithmetic, with tests -L<http://www2.hursley.ibm.com/decimal/> +IBM's Standard Decimal Arithmetic, with tests (sadly, link appears to have +disappeared) The Perl modules Math::BigInt and Math::BigFloat.