Skip to content

big integer and big decimal datatype

Jump to bottom Edit New page
bitbegin edited this page Sep 29, 2018 · 19 revisions

Abstract

Red support integer! and float! datatype for basic numerical calculation.

The integer!'s precision range is [- 2^31 ~ 2^31 - 1] or [-2147483648 ~ 2147483647], so it has 9-10 digits precision.

The float! like other language's double datatype, it has 52 bit length for precision, 2^52 = 4503599627370496, so it has 15-16 digits precision. The float!'s precision is high, however, it has restrictions. For example, if we translate 0.1 to float!, the actual value in memory is 0x3FB999999999999A, it mast accurate represents 1.00000000000000005551115123126E-1.

In some cases, this situation is not allowed, for example, in money apps. So if we want a high precision and not lost digits, we should support base10 datatype.

Most languages provide big integer and big decimal datatypes (or libs). For example, in java, there are Biginteger and Bigdecimal to support large precision integer and float. In python, the default integer is biginteger type, and there also exists Decimal to support bigdecimal.

So, we implement bigint! for big integer, and bigdecimal! for big float (in base10)

bigint!

datatype define

bigint!: alias struct! [
	size		[integer!]				;-- size in integer!
	used		[integer!]				;-- used length in integer!
	expo		[integer!]
	prec		[integer!]
]
  • size: for unit buffer size. After field prec, there continues unit buffer.
  • used: the actual datas used length, if it's negative, the bigint! is a negative value.
  • expo: for bigdecimal!
  • prec: for bigdecimal!, and can be used to distinguish with bigdecimal!

data structure

| size | used | expo | prec | unit 1 | unit 2 | ... | unit `used` | ... | unit `size` |

For example, "0" will be saved in memory like this:

| 1 | 1 | 0 | 0 | 0 |

"-1" will be saved in memory like this:

| 1 | -1 | 0 | 0 | 1 |

"0x1122334455667788" will be saved in memory like this:

| 2 | 2 | 0 | 0 | 0x55667788 | 0x11223344 |

"-0x1122334455667788" will be saved in memory like this:

| 2 | -2 | 0 | 0 | 0x55667788 | 0x11223344 |

math calculation

Assumed there exist big1 and big2 for bigint!

add

  1. first set carry flag = 0, position = unit 1
  2. add big1's unit and big2's unit and carry flag (if position overflowed, then break)
  3. if it overflowed, set carry flag = 1, position + 1, then loop 2

sub

  1. first set carry flag = 0, position = unit 1
  2. sub big1's unit and big2's unit and carry flag (if position overflowed, then break)
  3. if it overflowed, set carry flag = 1, position + 1, then loop 2

mul

It's a little complicated to explain this algorithm.

  1. get a unit from big2 data buffer tail (if no data, then break)
  2. use this unit mul big1's every data unit, and add result's buffer data
  3. if overflowed, process carry flag
  4. move result's buffer back one position, continue loop 1

div

It's very complicated to explain this, so i put it's origin web sites here HAC 14.20.

left/right shift

It's like integer! shift, just bit shift.

compare/modulo/load/form ...

  • We also provide compare/zero?*/negative?* and so on functions, these also very useful.
  • modulo is related to rounding mode(it will be explained below). So we implement 10 modes.
  • load-str can get bigint! from string format. For example, base16 "11AA22CC" and base10 "296362700" will produce same bigint!
  • form will translate bigint! to ascii string, then this string can be print out.

rounding mode

#enum ROUNDING! [
	ROUND-UP							;Rounds away from zero
	ROUND-DOWN							;Rounds towards zero
	ROUND-CEIL							;Rounds towards Infinity
	ROUND-FLOOR							;Rounds towards -Infinity
	ROUND-HALF-UP						;Rounds towards nearest neighbour. If equidistant, rounds away from zero
	ROUND-HALF-DOWN						;Rounds towards nearest neighbour. If equidistant, rounds towards zero
	ROUND-HALF-EVEN						;Rounds towards nearest neighbour. If equidistant, rounds towards even neighbour
	ROUND-HALF-ODD						;Rounds towards nearest neighbour. If equidistant, rounds towards odd neighbour
	ROUND-HALF-CEIL						;Rounds towards nearest neighbour. If equidistant, rounds towards Infinity
	ROUND-HALF-FLOOR					;Rounds towards nearest neighbour. If equidistant, rounds towards -Infinity
]

bigdecimal!

In bigint! section, we saw expo and prec for bigdecimal!. There is a main reason to explain.

bigdecimal! also can be defined as single file not depended on bigint!, but we will write many similar codes. To avoid this, prec can be used to distinguish bigint! and bigdecimal!.

For example, add or sub depend on negative sign to call absolute-add or absolute-sub. So, we can define add/sub help function for decimal, then use prec to decide which one to be choosed.

In bigdecimal! module, digits add can be defined like:

	add-raw: func [
		big1				[bigdecimal!]
		big2				[bigdecimal!]
		free?				[logic!]
		return:				[bigdecimal!]
	][
		as bigdecimal! bigint/add as bigint! big1 as bigint! big2 free?
	]

datatype define

bigdecimal!: alias struct! [
	size		[integer!]				;-- size in integer!
	used		[integer!]				;-- used length in integer!
	expo		[integer!]
	prec		[integer!]
]

It's same with bigint!, so we can convert between each other through as

data structure

| size | used | expo | prec | unit 1 | unit 2 | ... | unit `used` | ... | unit `size` |

For example, "0" will be saved in memory like this:

| 1 | 1 | 0 | 20 | 0 |

"-1E100" will be saved in memory like this:

| 1 | -1 | 100 | 20 | 1 |

"1234567890.123456789" will be saved in memory like this:

| 3 | 3 | -9 | 20 | 23456789 | 45678901 | 123 |

"-1234567890.123456789" will be saved in memory like this:

| 3 | -3 | -9 | 20 | 23456789 | 45678901 | 123 |

math calculation

bigdecimal! use 1e8 as base unit, for example, 10 + 99999999 will produce "1" for high unit, 9 for low unit. This "1" high unit like uint32's overflow(carry flag).

So, we need make sure every unit is base 1e8 (< 1e8), and process carry flag, and then we get bigdecimal!'s math calculation

special functions

  • NaN? and INF? like in float!
  • bigdecimal!'s shift is different bigint!. bigdecimal!'s shift one digit is 10x.
  • there are many *-raw functions, and these are just suitable for digits calculation, not considering exponent.
  • rounding mode: as we define digits length (or precision), but the math calculation result maybe exceed this length (default 20 digits), so we need round it to <= digits length. There is definition for ROUNDING! in bigint! section.

Interfaces in Red/System

bigint!

  • set-max-size: max bit length, default 1024
  • alloc*: allocate bigint! header unit buffer
  • free*: free bigint!
  • copy*: copy a bigint!
  • expand*: copy a bigint! and expand this size to a larger one
  • load-int: load a integer value to bigint!
  • load-uint: load an uint32 value to bigint!
  • zero?*: check a value of bigint! if it's zero
  • compare: compare two bigint! value
  • negative?*: check a value of bigint! if it's negative
  • absolute*: get an absolute bigint!
  • shrink: remove head zero units
  • left-shift: left shift
  • right-shift: right shift
  • add: add two bigint! value
  • sub: sub two bigint! value
  • mul: mul two bigint! value
  • div: div two bigint! value (also return remainder)
  • modulo: modulo two bigint! value (depends on rounding-mode)
  • load-bin: load a byte array to bigint!
  • load-str: load a string to bigint!, support 2 ~ 16 radix, but 16 radix is very fast
  • form: form a bigint! value to string, support 2 ~ 16 radix, but 16 radix is very fast

bigdecimal!

  • set-default-prec: set precision, default 20
  • set-exp-min: set min exp, default -1000000000
  • set-exp-max: set max exp, default 1000000000
  • set-rounding-mode: set rounding mode, default ROUND-HALF-UP
  • alloc*: allocate bigdecimal! header unit buffer
  • free*: free bigdecimal!
  • copy*: copy a bigdecimal!
  • expand*: copy a bigdecimal! and expand this size to a larger one
  • load-nan: create a NaN bigdecimal!
  • load-inf: create a INF bigdecimal!
  • NaN?: check a value of bigdecimal! if it's NaN
  • INF?: check a value of bigdecimal! if it's INF
  • load-int: load a integer value to bigdecimal!
  • load-uint: load an uint32 value to bigdecimal!
  • shrink: remove no used tail zero
  • zero?*: check a value of bigdecimal! if it's zero
  • compare: compare two bigdecimal! value
  • load-str: load base10 digit string (only include "0"~"9") to bigdecimal!
  • load-float: load base10 float string (support "." and "E") to bigdecimal!
  • form: format a bigdecimal! value to base10 float string
  • left-shift: left shift
  • right-shift: right shift
  • add: add two bigdecimal! value
  • sub: sub two bigdecimal! value
  • mul: mul two bigdecimal! value
  • div: div two bigdecimal! value
  • remainder: remainder two bigdecimal! value
  • modulo: modulo two bigdecimal! value (depends on rounding-mode)

Examples

There are many examples in "tests/source/runtime/bigint-test.reds" and "tests/source/runtime/bigdecimal-test.reds"

Differences

  • bigint! is for integer calculation, bigdecimal! is for float calculation
  • bigint! is saved in uint32, bigdecimal! is also saved in uint32, but the unit less than 1e8, you can call this base 1e8.
  • bigint! is suitable for base16 data calculation and show, if it shows in base10, the form will cost many div 10 to get base10 string.
  • bigdecimal! is suitable for base10 data calculation and show, as one unit range is 0 ~ 99999999, it's easy to form it in base10 string.
  • bigint!'s precison is limit with bit length (default 1024), bigdecimal!'s precison is limit with digit length (default 20)
  • bigint!'s (default 1024) range is [-2^1024, 2^1024], bigdecimal!'s (default 20 for max digits, -1000000000 for min exp, 1000000000 for max exp) range is [-99999999999999999999E-1000000000, 99999999999999999999E1000000000]
Add a custom footer
Add a custom sidebar
Clone this wiki locally