Decimal impl

Implements interface Decimal.

Summary

Decimal impl	Implements interface Decimal.
Copyright	This program is free software.
Files
C-kern/api/math/float/decimal.h	Header file Decimal.
C-kern/math/float/decimal.c	Implementation file Decimal impl.
Types
struct decimal_frombigint_t	Export decimal_frombigint_t into global namespace.
struct decimal_frombigint_state_t	Export decimal_frombigint_state_t into global namespace.
struct alignedexpandshift_t	Export alignedexpandshift_t into global namespace.
struct decimal_divstate_t	Export decimal_divstate_t into global namespace.
shiftleft10p_f	A function which computes the decimal left shift of digit.
alignedexpandshift_t	Stores an exponent of DIGITSBASE and a reference to a shift-left function.
decimal_frombigint_state_t	Holds the modulo result of a division of a bigint_t.
Variables
big	A preallocated bigint_t.
tabidx	References a divisor in s_decimal_powbase.
decimal_frombigint_t	Type holding state for conversion from bigint_t into decimal_t.
Variables
state	state[0] holds the result of the first division.
decimal_divstate_t	Used in div_decimalhelper to store current state of division computation.
decimal_t
static variables
s_decimal_errtimer	Simulates an error in different functions.
s_decimal_powbase	Tables of powers of pow(10,9) used to convert bigint_t, float, double, into decimal_t.
decimal_powbase
tableindex_decimalpowbase	Returns index into table s_decimal_powbase.
tableindexfromdecsize_decimalpowbase	Returns index into table s_decimal_powbase.
decsize_decimalpowbase	Returns size of decimal_t needed to represent <s_decimal_powbase>[tableindex].
decimal_frombigint_t
helper
DIGITSBASE	The base of a digit in array decimal_t.digits.
BIGINT_MAXSIZE	The number of digits of bigint_t which may be converted to decimal_t without overflow.
power10_decimalhelper	Calculates pow(10, exponent) for 0 <= exponent <= 9.
determinehshiftleft_decimalhelper	Returns shiftleft10p_f for argument decimal_exponent_x.
alignexponent_decimalhelper	Returns the difference between decimal_exponent and the aligned exponent.
allocate_decimalhelper	Does the real allocation / reallocation.
add_decimalhelper	Implements adding of two decimal numbers.
sub_decimalhelper	Implements subtraction of two decimal numbers.
mult_decimalhelper	Multiplies two decimal numbers and returns the positive result.
addsplit_decimalhelper	Implements adding of two positive decimal numbers.
multsplit_decimalhelper	Multiplies two decimal numbers and returns the positive result.
div3by2digits_decimalhelper	Computes ((dividend * DIGITSBASE + nextdigit) / divisor).
submul_decimalhelper	Computes »ldigits[]-=nextdigitrdigits[*]« and corrects nextdigit with -1 if necessary.
div_decimalhelper	Divides two decimal numbers and returns the positive quotient.
divi32_decimalhelper	Divides decimal number by integer and returns the positive quotient.
nrzerobits2nrdigits_decimalhelper	Returns the nr of zero decimal digits calculated from the number of zero bits.
nrzerobits2decsize_decimalhelper	See nrzerobits2nrdigits_decimalhelper.
nrzerodigits2nrbits_decimalhelper	Returns the nr of zero bits calculated from the number of zero decimal digits.
calcfractionsize_decimalhelper	Calculates the number of digits needed to represent a binary fraction.
digit2str_decimalhelper	Writes a decimal representation of digit into string str.
lifetime
query
assign
ternary operations
test
test_example1	Evaluate f(a = 77617, b = 33096)

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

Files

C-kern/api/math/float/decimal.h

Header file Decimal.

C-kern/math/float/decimal.c

Implementation file Decimal impl.

Types

struct decimal_frombigint_t

typedef struct decimal_frombigint_t decimal_frombigint_t

Export decimal_frombigint_t into global namespace.

struct decimal_frombigint_state_t

typedef struct decimal_frombigint_state_t decimal_frombigint_state_t

Export decimal_frombigint_state_t into global namespace.

struct alignedexpandshift_t

typedef struct alignedexpandshift_t alignedexpandshift_t

Export alignedexpandshift_t into global namespace.

struct decimal_divstate_t

typedef struct decimal_divstate_t decimal_divstate_t

Export decimal_divstate_t into global namespace.

shiftleft10p_f

typedef uint32_t (
* shiftleft10p_f
) (/*inout*/uint32_t * shiftcarry, uint32_t shiftdigit)

A function which computes the decimal left shift of digit. The computed return value is:

shiftcarry + (shiftdigit % pow(10,9-x)) * pow(10,x)

Where x is number of decimal digits this function shifts to the left. The processing order for a left shift is from least significant first up to most significant last. Before return parameter shiftcarry is set to:

shiftdigit / pow(10,9-x)

which becomes the next shiftcarry.

alignedexpandshift_t

struct alignedexpandshift_t

Stores an exponent of DIGITSBASE and a reference to a shift-left function. Call this function to shift all decimal digits left starting from least significant digit.

decimal_frombigint_state_t

struct decimal_frombigint_state_t

Holds the modulo result of a division of a bigint_t.

Summary

Variables
big	A preallocated bigint_t.
tabidx	References a divisor in s_decimal_powbase.

Variables

big

bigint_t * big

A preallocated bigint_t. It will hold the modulo result of a division operation. The divisor is referenced with tabidx.

tabidx

unsigned tabidx

References a divisor in s_decimal_powbase.

decimal_frombigint_t

struct decimal_frombigint_t

Type holding state for conversion from bigint_t into decimal_t.

Summary

Variables
state	state[0] holds the result of the first division.

Variables

state

decimal_frombigint_state_t state[7]

state[0] holds the result of the first division.

---------------------------------------------------------------
| state[0] | state[1] | ... | 1 == size_bigint(state[X]->big) |
---------------------------------------------------------------

The division process is repeated until the quotient becomes a number in the range [0 .. DIGITSBASE-1].

decimal_divstate_t

struct decimal_divstate_t

Used in div_decimalhelper to store current state of division computation.

decimal_t

Summary

static variables
s_decimal_errtimer	Simulates an error in different functions.
s_decimal_powbase	Tables of powers of pow(10,9) used to convert bigint_t, float, double, into decimal_t.
decimal_powbase
tableindex_decimalpowbase	Returns index into table s_decimal_powbase.
tableindexfromdecsize_decimalpowbase	Returns index into table s_decimal_powbase.
decsize_decimalpowbase	Returns size of decimal_t needed to represent <s_decimal_powbase>[tableindex].
decimal_frombigint_t
helper
DIGITSBASE	The base of a digit in array decimal_t.digits.
BIGINT_MAXSIZE	The number of digits of bigint_t which may be converted to decimal_t without overflow.
power10_decimalhelper	Calculates pow(10, exponent) for 0 <= exponent <= 9.
determinehshiftleft_decimalhelper	Returns shiftleft10p_f for argument decimal_exponent_x.
alignexponent_decimalhelper	Returns the difference between decimal_exponent and the aligned exponent.
allocate_decimalhelper	Does the real allocation / reallocation.
add_decimalhelper	Implements adding of two decimal numbers.
sub_decimalhelper	Implements subtraction of two decimal numbers.
mult_decimalhelper	Multiplies two decimal numbers and returns the positive result.
addsplit_decimalhelper	Implements adding of two positive decimal numbers.
multsplit_decimalhelper	Multiplies two decimal numbers and returns the positive result.
div3by2digits_decimalhelper	Computes ((dividend * DIGITSBASE + nextdigit) / divisor).
submul_decimalhelper	Computes »ldigits[]-=nextdigitrdigits[*]« and corrects nextdigit with -1 if necessary.
div_decimalhelper	Divides two decimal numbers and returns the positive quotient.
divi32_decimalhelper	Divides decimal number by integer and returns the positive quotient.
nrzerobits2nrdigits_decimalhelper	Returns the nr of zero decimal digits calculated from the number of zero bits.
nrzerobits2decsize_decimalhelper	See nrzerobits2nrdigits_decimalhelper.
nrzerodigits2nrbits_decimalhelper	Returns the nr of zero bits calculated from the number of zero decimal digits.
calcfractionsize_decimalhelper	Calculates the number of digits needed to represent a binary fraction.
digit2str_decimalhelper	Writes a decimal representation of digit into string str.
lifetime
query
assign
ternary operations
test
test_example1	Evaluate f(a = 77617, b = 33096)

static variables

s_decimal_errtimer

static test_errortimer_t s_decimal_errtimer

Simulates an error in different functions.

s_decimal_powbase

static const bigint_t * s_decimal_powbase[7]

Tables of powers of pow(10,9) used to convert bigint_t, float, double, into decimal_t. The entries s_decimal_powbase[i] are calculated as pow(pow(10,9), i+1).

decimal_powbase

tableindex_decimalpowbase

static inline unsigned tableindex_decimalpowbase( uint32_t bigintsize )

Returns index into table s_decimal_powbase. The index is calculated from the size of the bigint_t. Check the returned index if it is < lengthof(s_decimal_powbase). If it is out of range than bigintsize is too big.

Returns

1. bigintsize <= BIGINT_MAXSIZE The highest index ti is returned for which the following is true. size_bigint(s_decimal_powbase[ti)) <= bigintsize 2. bigintsize > BIGINT_MAXSIZE Returns index ti overflowing size of s_decimal_powbase.

tableindexfromdecsize_decimalpowbase

static inline unsigned tableindexfromdecsize_decimalpowbase( uint32_t decsize )

Returns index into table s_decimal_powbase. If the preconditions are not met the returned index is either wrong or out of range.

Preconditions are not checked.

Precondition

1. decsize >= 1 2. decsize <= 64 (64*9 == 576)

decsize_decimalpowbase

static inline unsigned decsize_decimalpowbase( unsigned tableindex )

Returns size of decimal_t needed to represent <s_decimal_powbase>[tableindex].

decimal_frombigint_t

helper

DIGITSBASE

#define DIGITSBASE ( (uint32_t)1000000000 )

The base of a digit in array decimal_t.digits. To calculate the value of a single digit use the formula:

decimal_t * dec = ... ;
double    digit_value[size_decimal(dec)] ;
for (unsigned i = 0; i < size_decimal(dec); ++i)
   digit_value[i] = dec->digits[i] * pow(DIGITSBASE, i) * pow(10, dec->decimal_exponent) ;

BIGINT_MAXSIZE

#define BIGINT_MAXSIZE ( (uint32_t)119 )

The number of digits of bigint_t which may be converted to decimal_t without overflow. A bigint_t number whose size is bigger will overflow for sure. A bigint_t number whose size is smaller will never overflow.

power10_decimalhelper

static inline uint32_t power10_decimalhelper( unsigned exponent )

Calculates pow(10, exponent) for 0 <= exponent <= 9.

determinehshiftleft_decimalhelper

static shiftleft10p_f determinehshiftleft_decimalhelper( uint32_t shiftcount )

Returns shiftleft10p_f for argument decimal_exponent_x. The argument must be a value between 0 and 8. The value 0 calls a function which returns an unshifted number.

alignexponent_decimalhelper

static inline int alignexponent_decimalhelper(
/*out*/uint32_t * exponent_correction,
int32_t decimal_exponent
)

Returns the difference between decimal_exponent and the aligned exponent. If you subtract the returned value in exponent_correction from the decimal exponent you get the aligned exponent.

allocate_decimalhelper

static int allocate_decimalhelper( decimal_t *restrict * dec,
uint32_t size_allocate )

Does the real allocation / reallocation. In case parameter dec does not point to a NULL pointer, it is considered to point to a valid reference to a decimal_t previously allocated by this function. In this case a reallocation is done - if allocate_digits is higher than decimal_t.size_allocated.

add_decimalhelper

static int add_decimalhelper( decimal_t *restrict * result,
const decimal_t * ldec,
const decimal_t * rdec )

Implements adding of two decimal numbers. The sign of the result is determined by parameter ldec. The sign of parameter rdec is not taken into account.

sub_decimalhelper

static int sub_decimalhelper( decimal_t *restrict * result,
const decimal_t * ldec,
const decimal_t * rdec )

Implements subtraction of two decimal numbers. The sign of the result is determined by parameter ldec. The sign of parameter rdec is not taken into account.

mult_decimalhelper

static void mult_decimalhelper( decimal_t * dec,
uint8_t lsize,
const uint32_t * ldigits,
uint8_t rsize,
const uint32_t * rdigits,
int16_t exponent )

Multiplies two decimal numbers and returns the positive result. The numbers are represented with their size and digits array. This allows for splitting the nummbers without allocating a new decimal_t.

(unchecked) Preconditions

1.	result must be allocated with size == (lsize + rsize)
2.	(lsize > 0 && rsize > 0)
3.	lsize <= rsize
4.	ldigits[lsize-1] != 0 && rdigits[rsize-1] != 0

addsplit_decimalhelper

static void addsplit_decimalhelper( decimal_t * restrict result,
uint8_t digitsoffset,
uint8_t lsize,
const uint32_t * ldigits,
uint8_t rsize,
const uint32_t * rdigits )

Implements adding of two positive decimal numbers.

(unchecked) Preconditions

1.	result must be allocated with size >= (lsize + rsize)
2.	(lsize > 0 && rsize > 0)
3.	ldigits[lsize-1] != 0 && rdigits[rsize-1] != 0
4.	Either ldigits[0] != 0 \|\| rdigits[0] != 0 => result->baseexponent == 0 !

multsplit_decimalhelper

static int multsplit_decimalhelper( decimal_t * restrict * result,
uint8_t lsize,
const uint32_t * ldigits,
uint8_t rsize,
const uint32_t * rdigits )

Multiplies two decimal numbers and returns the positive result. The multiplication is done with splitting of numbers to save one multiplication.

(unchecked) Preconditions

1.	result must be allocated with size == (lsize + rsize)
2.	After skipping of trailing zeros: (lsize > 0 && rsize > 0)
3.	(ldigits[lsize-1] != 0 && rdigits[rsize-1] != 0)

div3by2digits_decimalhelper

static void div3by2digits_decimalhelper( decimal_divstate_t * state )

Computes ((dividend * DIGITSBASE + nextdigit) / divisor). The value returned in nextdigit is always in range [1..DIGITSBASE-1] (in case preconditions are met).

Changed values

1. nextdigit contains result of (dividend * DIGITSBASE + nextdigit) / dividend 2. dividend contains result of (dividend * DIGITSBASE + nextdigit) % dividend

(unchecked) Preconditions

1.	divisor < DIGITSBASEDIGITSBASE && dividend < DIGITSBASEDIGITSBASE && nextdigit < DIGITSBASE
2.	divisor > dividend
3.	divisor < (dividend * DIGITSBASE + nextdigit)

submul_decimalhelper

static void submul_decimalhelper( decimal_divstate_t * state )

Computes »ldigits[*]-=nextdigit*rdigits[*]« and corrects nextdigit with -1 if necessary.

Special case (nextdigit == DIGITSBASE-1)

No multiplication is done.

Special case (nextdigit == 1)

No multiplication is done.

(unchecked) Precondition

1.	nextdigit > 0 && nextdigit < DIGITSBASE
2.	ldigits[loffset] == 0 && ldigits[loffset+1] == 0
3.	dividend contains the result of ldigits[“top digits”]-=nextdigit*rdigits[“top digits”]

div_decimalhelper

static int div_decimalhelper( decimal_t *restrict result,
bool isNegSign,
int32_t exponent,
const uint8_t lsize,
uint32_t * const ldigits,
const uint8_t rsize,
const uint32_t * const rdigits,
const uint8_t result_size )

Divides two decimal numbers and returns the positive quotient. The division is done as you have learned in school. The content of ldigits is destroyed.

(unchecked) Preconditions

1.	result must be allocated with result_size && result_size > 0
2.	lsize >= rsize && rsize >= 2
3.	lsize[lsize-1] != 0 && rsize[rsize-1] != 0
4.	exponent must be in range of int16_t

divi32_decimalhelper

static int divi32_decimalhelper( decimal_t *restrict result,
bool isNegSign,
int32_t exponent,
uint8_t lsize,
const uint32_t * ldigits,
uint32_t divisor,
const uint32_t result_size )

Divides decimal number by integer and returns the positive quotient. The division is done as you have learned in school.

(unchecked) Preconditions

1.	result must be allocated with result_size && result_size > 0
2.	lsize > 0 && ldigits[lsize-1] != 0
3.	divisor < DIGITSBASE
4.	exponent must be in range of int16_t

nrzerobits2nrdigits_decimalhelper

static inline uint32_t nrzerobits2nrdigits_decimalhelper(
uint32_t nrleadingzerobits
)

Returns the nr of zero decimal digits calculated from the number of zero bits. The binary number “0b0.0000111111” has 4 zero bits after the binamal point and this function returns the number of zero digits “0.0009” which would translate into the binary number. The returned number is valid for a 64(or bigger) bit mantissa. For smaller mantissa the nr of leading zero decimal digits returned could be too small by one.

Implementation hint

pow(10,294912) needs 32 * 30615 bits to be stored Tested only up to 1080 bits.

nrzerobits2decsize_decimalhelper

static inline uint32_t nrzerobits2decsize_decimalhelper(
uint32_t nrleadingzerobits
)

See nrzerobits2nrdigits_decimalhelper. The difference is that nrzerobits2decsize_decimalhelper returns nrzerobits2nrdigits_decimalhelper divided by <digitsperint_decimal>().

nrzerodigits2nrbits_decimalhelper

static uint32_t nrzerodigits2nrbits_decimalhelper( uint32_t nrleadingzerodigits )

Returns the nr of zero bits calculated from the number of zero decimal digits. The decimal number “0.0000999” has 4 zero digits after the decimal point and this function returns the number of zero bits “0b0.00...001” which would translate into the decimal number. The returned number is valid for a 1 bit mantissa. For bigger mantissa the nr of leading zero bits returned could be too small by one.

Implementation hint

pow(10,294912) needs 32 * 30615 bits to be stored Tested only up to 1080 bits.

calcfractionsize_decimalhelper

static uint32_t calcfractionsize_decimalhelper(
    /*out*/uint32_t * leadingzerosize,
    uint32_t fractionalbits,
    uint32_t nrleadingzerobits
)

Calculates the number of digits needed to represent a binary fraction. The binary fraction 0.00000...0111...1 has fractionalbits digits after the binamal point. This function assumes that all digits are 1 except for the first nrleadingzerobits. After return the parameter leadingzerosize contains the nr of full integer digits which are zero.

digit2str_decimalhelper

static inline void digit2str_decimalhelper( uint8_t * str,
uint32_t digit,
uint8_t digitsize )

Writes a decimal representation of digit into string str. Exactly digitsize least significant digits of digit are written to the string.

lifetime

query

assign

ternary operations

test

test_example1

static int test_example1( void )

Evaluate f(a = 77617, b = 33096)

f = 333.75*pow(b,6) + pow(a,2)*(11*pow(a,2)*pow(b,2) - pow(b,6) - 121*pow(b,4) - 2) + 5.5*pow(b,8) + a

Exact result

f(a = 77617, b = 33096) == 77615.00