Add Q96 computation in lisk-utils/math

[shuse2]

Description

• Add Q96 computation in @liskhq/lisk-utils/math
  • Class Q(val: number | bigint | Buffer, base = 96)
    • add(n: Q): Q
    • sub(n: Q): Q
    • mul(n: Q): Q
    • div(n: Q): Q
    • muldiv(n: Q, m: Q): Q
    • toInt(operation: roundDown | roundUp): bigint
    • Inv(n: Q): Q
    • toBytes(): Buffer

Acceptance Criteria

• All functions are unit tested
• Create fixture for buffer conversion
• Overflow cases needs to be handled in tests (maybe find standard fixtures)
• Have test for Rounddown when exceeding the Buffer limit

Additional Information

Fixed Point Arithmetic

Definition

We represent a positive real number r as a Qn by the positive integer Qn(r) = floor(r*2^n) (inspired by the Q number format for signed numbers). In this representation, we have n bits of fractional precision. We do not limit the size of r as modern libraries can handle integers of arbitrary size; note that all the Qn conversions assume no loss of significant digits.

Operations on Integers

For an integer a in the Qn format, we define:

• Rounding down: roundDown_n(a) = a >> n

Qn Arithmetic Operations

In the following definition, * is the integer multiplication, // is the integer division (rounded down). Division by zero is not permitted and should raise an error in any implementation.

For two numbers a,b and c in Qn format, we define the following arithmetic operations which all return a Qn:

• Addition: add_n(a, b) = a + b

• Subtraction: sub_n(a,b) = a - b, only defined if a >= b

• Multiplication: mul_n(a, b) = (a * b) >> n

• Division: div_n(a, b) = (a << n) // b

• Multiplication and then division: muldiv_n(a, b, c) = roundDown_n(((a * b) << n) // c)

• Multiplication and then division, rounding up: muldiv_n_RoundUp(a, b, c) = roundUp_n(((a * b) << n) // c)

• Convert to integer rounding down: Q_n_ToInt(a) = roundDown_n(a)

• Convert to integer rounding up: Q_n_ToIntRoundUp(a) = roundUp_n(a)

• Inversion in the decimal precision space: inv_n(a) = div_n(1 << n, a)