Support for rational numbers #54

New Issue

2019-04-08T22:57:56+09:00

zxq9 commented

2019-04-08 22:57:56 +09:00

(Migrated from gitlab.com)

Created by: radrow

Rational numbers are essential to clearly represent ratios and proportions, which appear commonly in lots of models and computations. Sophia does not support any kind of numbers other than integrals and I think it could be changed.

How does it look now

While developing some kind of basic bonding curve contract I had to specify reserve_ratio. This is the very first place I really faced lack of fractions – I was forced to define max_reserve_ratio, and set reserve ratio as "the value that divided by max_reserve_ratio will produce actual reserve ratio". This leads to quite ridiculous consequences, because then in Bancor formula I need to take something to the power of that ratio, which requires defining more and more operations on these implicit rationals and pushes all this work to the user. Take a look at this solidity code taken from https://github.com/relevant-community/contracts/blob/bondingCurves/contracts/BancorFormula.sol :

    /**
        General Description:
            Determine a value of precision.
            Calculate an integer approximation of (_baseN / _baseD) ^ (_expN / _expD) * 2 ^ precision.
            Return the result along with the precision used.

        Detailed Description:
            Instead of calculating "base ^ exp", we calculate "e ^ (ln(base) * exp)".
            The value of "ln(base)" is represented with an integer slightly smaller than "ln(base) * 2 ^ precision".
            The larger "precision" is, the more accurately this value represents the real value.
            However, the larger "precision" is, the more bits are required in order to store this value.
            And the exponentiation function, which takes "x" and calculates "e ^ x", is limited to a maximum exponent (maximum value of "x").
            This maximum exponent depends on the "precision" used, and it is given by "maxExpArray[precision] >> (MAX_PRECISION - precision)".
            Hence we need to determine the highest precision which can be used for the given input, before calling the exponentiation function.
            This allows us to compute "base ^ exp" with maximum accuracy and without exceeding 256 bits in any of the intermediate computations.
    */
    function power(uint256 _baseN, uint256 _baseD, uint32 _expN, uint32 _expD) internal constant returns (uint256, uint8) {
        uint256 lnBaseTimesExp = ln(_baseN, _baseD) * _expN / _expD;
        uint8 precision = findPositionInMaxExpArray(lnBaseTimesExp);
        return (fixedExp(lnBaseTimesExp >> (MAX_PRECISION - precision), precision), precision);
    }

Note all these workarounds. The programmer needs to pass nominators and denominators separately to define actually very principal operations. This leads to a lot of unneeded bloat of code and creates a lot of opportunities to introduce bugs.

How do I see it

For a start, handling rationals may be done by a library. Rational number is literally a pair of integers. We may call it either Frac, Ratio, Fractional or Rational. It is important to point to the user that they are not system floats. However, the language may actually help us here – taking an idea from OCaml we may include new operators: (+.) : frac -> frac -> frac, (-.), (/.), (*.), because just like in OCaml we have only Hindley-Milner typesystem that won't allow more fancy polymorphism that would allow use of traditional +-like operators. Sample usage:

let a = frac(1, 6)  //  1/6
let b = a *. Int.to_frac(3)  // 1/2 – fractions should be kept in simplified version
let c = b.nom + b.den  // 1 + 2 = 3 – nom and den should be exposed to let users define their own stuff easier

Some operations will preserve rational body and there is nothing to bother here. There is however some problem with functions that may exit rationals, like sqrt, or exponentiation in general as their results can have infinite numerical representation and they will need to be approximated. On the other hand we are not introducing new issue – Sophia programmers still need to deal with it. There is no way to bypass it, but we may make this a bit nicer.

From my point of view it would be very handy to have approximation tools in some library that would perform it for user, but that is a different talk.

What would I expect / naming propositions

Contruction:

// Build fractional from nominator and denominator
frac : int -> int -> frac
// Conversion from int
Frac.from_int / Int.to_frac : int -> frac

Rounding:

Frac.round : frac -> int
Frac.floor : frac -> int
Frac.ceil : frac -> int

Operations:

Frac.add / (+.) : frac -> frac -> frac
Frac.sub / (-.) : frac -> frac -> frac
Frac.div / (/.) : frac -> frac -> frac
Frac.mul / (*.) : frac -> frac -> frac
// negation
Frac.neg : frac -> frac
// invertion
Frac.inv : frac -> frac

Beside that we can later provide some functions that approximate operations on real numbers, like

Frac.exp : frac -> frac -> frac -> frac
Frac.exp(base, exponent, maximum_error)

*Created by: radrow* Rational numbers are essential to clearly represent ratios and proportions, which appear commonly in lots of models and computations. Sophia does not support any kind of numbers other than integrals and I think it could be changed. ### How does it look now While developing some kind of basic bonding curve contract I had to specify `reserve_ratio`. This is the very first place I really faced lack of fractions – I was forced to define `max_reserve_ratio`, and set reserve ratio as "the value that divided by `max_reserve_ratio` will produce actual reserve ratio". This leads to quite ridiculous consequences, because then in Bancor formula I need to take something to the power of that ratio, which requires defining more and more operations on these implicit rationals and pushes all this work to the user. Take a look at this solidity code taken from https://github.com/relevant-community/contracts/blob/bondingCurves/contracts/BancorFormula.sol : ``` /** General Description: Determine a value of precision. Calculate an integer approximation of (_baseN / _baseD) ^ (_expN / _expD) * 2 ^ precision. Return the result along with the precision used. Detailed Description: Instead of calculating "base ^ exp", we calculate "e ^ (ln(base) * exp)". The value of "ln(base)" is represented with an integer slightly smaller than "ln(base) * 2 ^ precision". The larger "precision" is, the more accurately this value represents the real value. However, the larger "precision" is, the more bits are required in order to store this value. And the exponentiation function, which takes "x" and calculates "e ^ x", is limited to a maximum exponent (maximum value of "x"). This maximum exponent depends on the "precision" used, and it is given by "maxExpArray[precision] >> (MAX_PRECISION - precision)". Hence we need to determine the highest precision which can be used for the given input, before calling the exponentiation function. This allows us to compute "base ^ exp" with maximum accuracy and without exceeding 256 bits in any of the intermediate computations. */ function power(uint256 _baseN, uint256 _baseD, uint32 _expN, uint32 _expD) internal constant returns (uint256, uint8) { uint256 lnBaseTimesExp = ln(_baseN, _baseD) * _expN / _expD; uint8 precision = findPositionInMaxExpArray(lnBaseTimesExp); return (fixedExp(lnBaseTimesExp >> (MAX_PRECISION - precision), precision), precision); } ``` Note all these workarounds. The programmer needs to pass nominators and denominators separately to define actually very principal operations. This leads to a lot of unneeded bloat of code and creates a lot of opportunities to introduce bugs. ### How do I see it For a start, handling rationals may be done by a library. Rational number is literally a pair of integers. We may call it either `Frac`, `Ratio`, `Fractional` or `Rational`. It is important to point to the user that they are not system floats. However, the language may actually help us here – taking an idea from OCaml we may include new operators: `(+.) : frac -> frac -> frac`, `(-.)`, `(/.)`, `(*.)`, because just like in OCaml we have only Hindley-Milner typesystem that won't allow more fancy polymorphism that would allow use of traditional `+`-like operators. Sample usage: ``` let a = frac(1, 6) // 1/6 let b = a *. Int.to_frac(3) // 1/2 – fractions should be kept in simplified version let c = b.nom + b.den // 1 + 2 = 3 – nom and den should be exposed to let users define their own stuff easier ``` Some operations will preserve rational body and there is nothing to bother here. There is however some problem with functions that may exit rationals, like `sqrt`, or exponentiation in general as their results can have infinite numerical representation and they will need to be approximated. On the other hand we are not introducing new issue – Sophia programmers still need to deal with it. There is no way to bypass it, but we may make this a bit nicer. From my point of view it would be very handy to have approximation tools in some library that would perform it for user, but that is a different talk. ### What would I expect / naming propositions Contruction: ``` // Build fractional from nominator and denominator frac : int -> int -> frac // Conversion from int Frac.from_int / Int.to_frac : int -> frac ``` Rounding: ``` Frac.round : frac -> int Frac.floor : frac -> int Frac.ceil : frac -> int ``` Operations: ``` Frac.add / (+.) : frac -> frac -> frac Frac.sub / (-.) : frac -> frac -> frac Frac.div / (/.) : frac -> frac -> frac Frac.mul / (*.) : frac -> frac -> frac // negation Frac.neg : frac -> frac // invertion Frac.inv : frac -> frac ``` Beside that we can later provide some functions that approximate operations on real numbers, like ``` Frac.exp : frac -> frac -> frac -> frac Frac.exp(base, exponent, maximum_error) ```

zxq9 commented

2019-04-08 23:16:42 +09:00

(Migrated from gitlab.com)

Created by: UlfNorell

If you define

record frac = {nom : int, den : int}

you can implement everything except the infix operators as a library.

*Created by: UlfNorell* If you define ``` record frac = {nom : int, den : int} ``` you can implement everything except the infix operators as a library.

zxq9 commented

2019-04-08 23:23:32 +09:00

(Migrated from gitlab.com)

Created by: radrow

Of course, but my idea is to have an official and unified implementation for this that would be shipped with the language

*Created by: radrow* Of course, but my idea is to have an official and unified implementation for this that would be shipped with the language

zxq9 commented

2019-04-08 23:30:05 +09:00

(Migrated from gitlab.com)

Created by: UlfNorell

Right, this is something that could go in a standard library of some kind.

Reading this

Note all these workarounds. The programmer needs to pass nominators and denominators separately to define actually very principal operations. This leads to a lot of unneeded bloat of code and creates a lot of opportunities to introduce bugs.

it sounded like you were saying this is how you have to do it in Sophia at the moment, and I wanted to make it clear that this is not at all true.

*Created by: UlfNorell* Right, this is something that could go in a standard library of some kind. Reading this > Note all these workarounds. The programmer needs to pass nominators and denominators separately to define actually very principal operations. This leads to a lot of unneeded bloat of code and creates a lot of opportunities to introduce bugs. it sounded like you were saying this is how you have to do it in Sophia at the moment, and I wanted to make it clear that this is not at all true.

zxq9 commented

2019-12-10 02:24:35 +09:00

(Migrated from gitlab.com)

Created by: thepiwo

This would be working well as standard library, now that they are integrated overall

*Created by: thepiwo* This would be working well as standard library, now that they are integrated overall

zxq9 commented

2019-12-11 22:34:40 +09:00

(Migrated from gitlab.com)

Created by: radrow

Right @thepiwo , actually behind your backs I was working on this. I will finish it after I'm back

*Created by: radrow* Right @thepiwo , actually behind your backs I was working on this. I will finish it after I'm back

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: QPQ-AG/sophia#54