Solidity: Fixed point types

[chriseth]

https://www.pivotaltracker.com/story/show/81779716

TODO:

• [ ] assignment (lvalue and rvalue)
• [ ] conversion (between different fixed types)
• [ ] conversion (between other types)
• [ ] comparison operators (< > =)
• [ ] unary operators (-, --, ++)
• [ ] binary operators (+ - / * )
• [ ] do-we-need-these? binary operators (% **)

[chriseth]

Some notes:

IntegerType::binaryOperatorResult is too tight, this should work but seems not to: uint128(1) + ufixed(2), same with FixedPointType::binaryOperatorResult

also this should work: .5 * uint128(7)

what happens currently with uint(7) / 2? Is it identical to .5 * uint(7)?

add test about signed mod with rational constants (should behave identical to SMOD opcode)

[VoR0220]

signed mod as in a modulus operation with signed rational constants?

[chriseth]

yes - and fixed point

[VoR0220]

alright. I'll get on that. Crafting tests. Working on some fixes. And then it's onto the actual compilation.

[VoR0220]

so couple of things. I got your first one working.

ufixed a = uint128(1) + ufixed(2);

The second two in the examples you laid out, based on how we defined implicit conversion are currently impossible.

0.5 currently converts to ufixed0x8 and that does not convert with a uint128.

uint(7) / 2 stays a uint256 after the division by 2 (it's truncating), and therefore cannot convert to ufixed128x128. And no... 0.5 * uint(7) is not the same as uint(7)/2....one is a ufixed0x8 and the other is dividing by an integer....kind of confusing....I'm thinking we may need to fix this up. Open to all suggestions....the only thing I can think up right now is to create a class atop integer type and fixed point and make it a super class of some kind...

[chriseth]

We decided to rather denote decimal places instead of "number of bits after the comma" to reduce confusion among users. This means that
fixed64x7 is a type of 64 bits and a value x of this type is interpreted as the number x / 10**7.

The type fixed is an alias for fixed128x19. The reason is that this type simplifies multiplication and also allows conversion from int64 without loss of precision / range.

[VoR0220]

@chriseth do we still want to allow users to fully extend the decimal range so that it can be fixed0x32 (I believe that's the full amount that it could take in but may be wrong).

[chriseth]

@VoR0220 note that the 0 is the total amount of bits in the type. The drawback of using decimals is that you cannot force the value to be between 0 and 1 anymore (because that does not fit the decimal range).

[VoR0220]

@chriseth so in other words it HAS to have an integer portion now...That's fine by me. The range and precisions seriously diminishes after 128 bits in fixed point either way.

[VoR0220]

Actually...I think we can. http://academic.evergreen.edu/projects/biophysics/technotes/program/bcd.htm#multiply

[chriseth]

This might be relevant: https://github.com/gnosis/solidity-arithmetic/blob/master/contracts/Arithmetic.sol

[VoR0220]

^Good find.

[axic]

Added a todo list above.

I think a good start could be making the below code compile:

contract C {
  fixed a = 3.14;
  function f(fixed b) {
     a = b;
  }
  function g() returns (fixed) {
    return a;
  }
}

[randomnetcat]

Is this still planned for completion?

[axic]

A good question raised by @meowingtwurtle: should an explicit typecast from fixed point to integer be a reinterpretation of the bits or an actual integer conversion?

Currently typecasting is a mix between the two, but mostly it is an actual conversion and not reinterpretation. One example is function type to address (the address of the external contract) and to bytes4 (the signature of the external function).

I think we should always do an actual conversion, e.g. fixed point to integer is the integer only part. Reinterpretation can always be done via assembly if needed.

In the future it may make sense introducing a notation to separate the two.

[fulldecent]

The test case in this issue could be much improved to illustrate all features that are required to be implemented.

[3sGgpQ8H]

As long as shifts are now available in EVM, probably binary fixed point types should be considered yet again.
Also it would be great to have 128-bit binary fixed point, e.g. 64.64 or 96.32 bit, because they are cheaper to multiply and divide than wider fixed point types.

[chriseth]

I still think it might be dangerous to provide binary fixed point numbers since they are harder to understand. You are right that previously, there was no efficiency difference between the two, though...

[3sGgpQ8H]

Binary fixed point is not harder to understand (actually simpler), than binary floating point, and people usually don't have to understand internal mechanics to use them. I believe many C++ developers think, that by writing 2.99e8 they use decimal floating point, but does this misunderstanding lead to any harm?
As long as one may write area = 3.141592 * radius * radius and get correct answer, it does not matter, whether it is binary or decimal, and whether it is fixed or floating point numbers under the hood.

[chriseth]

People are generally way more used to decimal fixed points - they use them all the time when e.g. using money. They know how rounding works and are aware about the precision limitations. Comparing binary fixed points to floating points does not gain anything, one complex beast is as complex as another one... ;)

[3sGgpQ8H]

People are using decimal fixed point for money in real life, but in computer programs best practice is to always use integer numbers for money and measure money amounts in the smallest units (Wei for Ether, Satoshi for Bitcoin, cent for USD etc). The number of decimals is only considered when converting money amount to/from string.

As long as string conversion is usually performed not in smart contract, but rather in client-side code of DApp, I would not at all consider money amounts as a use case for fixed point numbers in Solidity. What could help here is a "decimals" hint in ABI JSON, that will help Web3 API to properly convert Javascript big number with decimals into/from integer when passing them to/from smart contract.

The real use cases for fixed point numbers in Solidity are calculations of simple and compound interest rates, exchange rates, margin rates, fees, reserve amounts etc.

[chriseth]

I still don't see the point. Interest rates are usually given in percents, not "perbins". All the other things you give are usually displayed in decimal to the user and thus also having decimal fixed points for them in the smart contract would remove confusion.

[3sGgpQ8H]

All numbers are usually displayed in decimals, including numbers such as Pi, e, and √2. This does not make these numbers more decimal that binary. Actually, decimal/binary is just an encoding, not the property of the number.
For percents I didn't get your point. For me, interest rate of 2.45% is neither decimal nor binary, but just fractional.
In Ethereum smart contracts it is usually convenient to store 1-second interest rate, rather than annual. This allows calculating compound interest for arbitrary time interval just by raising 1-second interest rate to the power of number of seconds in the interval (in Ethereum all time intervals always contain integer number of seconds). Such 1-second rates are usually something like 0.000000094% (corresponds to 3% annual rate). For me, both, decimal and binary representation works equally well for such rates.
Mainstream Javascript implementations use binary integers and binary floating point, so at least for Javascript community, binary numbers are more familiar than decimals, in terms of range, precision, and rounding.

[chriseth]

My point is: If you use two decimal places precision, you know that you can always store all integer percentage values without loss of precision. You need 9 decimal places to store 0.000000094% without loss of precision. How many binary places do you need? And is the number representable as a binary fraction at all?

[fulldecent]

JSON uses, and its author champions, floating decimal.

I believe 10EE-18 is popular in Solidity implementations. Here is the implementation in Compound Finance https://github.com/compound-finance/compound-money-market/blob/master/contracts/Exponential.sol

As long as source code is written with decimal literals then fixed point numbers should only be decimal based.

[3sGgpQ8H]

JSON uses, and its author champions, floating decimal.

I would not agree. For JSON, number format is implementation-dependent, but RFC 7159 explicitly says that:

This specification allows implementations to set limits on the range
and precision of numbers accepted. Since software that implements
IEEE 754-2008 binary64 (double precision) numbers [IEEE754] is
generally available and widely used, good interoperability can be
achieved by implementations that expect no more precision or range
than these provide, in the sense that implementations will
approximate JSON numbers within the expected precision. A JSON
number such as 1E400 or 3.141592653589793238462643383279 may indicate
potential interoperability problems, since it suggests that the
software that created it expects receiving software to have greater
capabilities for numeric magnitude and precision than is widely
available.

Also, for this

As long as source code is written with decimal literals then fixed point numbers should only be decimal based.

I would not agree again. Solidity source code is usually written with both decimal and hexadecimal literals used equally often.

It seems that we are mixing three very different cases here:

1. Numbers that are intrinsically integer but are rendered with certain fixed number of decimals. This includes money amounts such as Ether (stored in Wei but rendered in Ether with 18 decimals), Bitcoin (stored in Satoshi, but rendered in Bitcoin with 8 decimals), USD (stored in cents but rendered in USD with 2 decimals), etc. As long as these numbers are stored as integers, they do not need any fraction numbers support from compiler and platform. (Most common case)
2. Real numbers with the more the better range and precision. In mainstream programming languages de-facto standard for such numbers is IEEE 754 double precision floating point numbers that have enough range and precision for most real-life applications. (Quite common case)
3. Fractional numbers with particular decimal precision. Such numbers are often used to meet requirements of formal accounting rules, and usually accompanied with strict rounding rules such as round half to even rule. Mainstream languages usually do not support such numbers natively, but only via libraries. Though, specialized financial-oriented languages may provide core support for such numbers. (Quite rare case)

[chriseth]

Fixed point numbers are not essential, but they are nice to have. You can always use integers and keep a fractional divisor in your head and for that divisor, it is mostly irrelevant whether it is a power of 2 or of 10. IEEE 754 does not really apply here because it specifies floating-point numbers. If you store the exponent dynamically as in floating point numbers, using powers of two makes more sense, but we do not store it dynamically.

In general, I do not think that we should use arguments like "mainstream programming languages use X", but rather "mainstream programming languages use X because of the following advantages".

My impression is that most mainstream programming languages use binary exponents because of the above argument about floating point numbers and because floating point numbers are a feature of their target machine. Both of these issues are not relevant for Solidity.

@fulldecent if I remember correctly, you have been a strong opponent of adding fixed point number types to Solidity in general. Is that still your opinion?

[3sGgpQ8H]

No, one cannot just keep divisor in head, and use integers for fixed point, unless the numbers are intrinsically integers (see my previous comment). Fixed point numbers behave differently when multiplied and divided, for example 2.00 * 3.00 = 6.00, while 200 * 300 = 60000. And, most importantly, they have different overflow behavior. For example, if one uses signed 32-bit integers to represent fixed point numbers with 3 decimals, then 1000.000 * 2000.000 will return 2000000.000 (fits into signed 32-bit), while 1000000 * 2000000 will overflow. Thus one cannot just write something like x * y / 1000 to simulate fixed point multiplication via integers.

[chriseth]

@3sGgpQ8H of course you have to adapt some arithmetic operations, but the point I was making is that fixed point numbers do not need any drastically different ABI encoding or memory representation.

[fulldecent]

@chriseth My biggest argument is that the target machine supports only integers so we should support only integers.

My second biggest argument is that there is not widespread use of Exponent.sol or other userland approaches therefore it is wholly premature to add this feature to the language.

---

I'll change my mind when:

1. Metamask actually uses contract ABIs when presenting transactions to the user;
2. There is/are well-written userland fixed point implementation(s); and
3. Projects that matter (deployed to production and having users) are using the implementation(s)

[3sGgpQ8H]

There is demand for fractional math in Solidity, and non-widespread use of existing libraries as well as lack of high quality full featured libraries is mainly due to the lack of fractional numbers support in Solidity.
While complicated functions, such as exponentiation or logarithm, and probably even basic arithmetic should be left for libraries to allow different implementations to coexist and compete, there are two essential things that only compiler can do:

1. establish common format for fractional numbers, otherwise different libraries will not be able to interop, and
2. support convenient fractional number literals, otherwise code dealing with fractions will be totally unreadable and unmaintainable.

So I think you are mixing cause and effect here.

[fulldecent]

For interop, are you talking about updating the ABI specification? That would be an EIP.

If libraries are not in widespread use then what other workarounds are people using the solve the real world problems that exist?

When I’m in a park or forest sometimes I’ll see a worn out dirt path in the grass. This is a good sign that a lot of people want to walk from one place to another even if there is no official trail.

If programmers demand to have fixed point numbers then they are going to use /something/ today. I have one concrete example, Exponential.sol, used in Compound.Finance. If there are other concrete examples, maybe even one using binary fixed point then it would be helpful to mention them here.

[chriseth]

We have a certain kind of a chicken-and-egg problem here and I think you cannot measure the demand by how many people implement workaround. Quoting an analogy from bicycle lane advocates: You cannot measure the demand for a bridge by the number of people swimming across a river.

One of the advantages of fixed point types supported by the compiler you cannot get by any other means is using operators for arithmetics. BEcause of that, using libraries for fixed point arithmetics is both hard to read and expensive, and I would guess that for most people this weighs heavily against the convenience.

[3sGgpQ8H]

@fulldecent By library interop problem I mean situation when developer wants to use in one contract fractional math functions from several libraries, but cannot do this efficiently, because each library uses its own format for fractional numbers.

[fulldecent]

I do not see a chicken and egg problem here. If smart contract developers want to do something they will do it. They don't just swim across the river, they swim through rock. Nothing about this new feature enables additional programming techniques. Everything is already possible with x / 10**18. Additionally, nothing in this feature is end user-facing; all client software still needs to divide by 10**18 for presentation to the end user.

We have only reviewed one concrete examples in this discussion -- Compound Finance uses 18-zeros decimal fixed point numbers.

At current, there is no interop problem because we have not identified a second piece of software that requires fixed point integers. Presumably there is only one piece of software that cares about fixed point numbers, they solved the problem, case closed.

[3sGgpQ8H]

There is no lack of smart contracts that operate with fraction numbers using various workarounds. Fraction numbers are actually widespread in Ethereum world. What is not widespread, and you correctly mentioned it, is use of fractional math libraries.
The fact that most of such contracts do not go further than y = x * 3 / 100 does not mean that they really want two decimals fixed point math and nothing else. They actually want to calculate 3% of x in the simplest possible way, and would write y = 0.03 * x if this would work correctly in Solidity.
And if this will ever work, most of the people will not care whether there are fixed or floating point, binary or decimal numbers under the hood. As most people don't care about how double data type works internally, as long as it works well for their tasks.

[fulldecent]

We're getting closer here.

Can you please provide references for this unnamed cache of contracts (with actual users) which are operating on fractions and would benefit from these proposed new features?

[3sGgpQ8H]

@fulldecent Sure. As a professional smart contract auditor I see various workarounds for missing fraction numbers in virtually every contract I review, and repetitive issues in naive implementations of such workarounds. As a professional smart contracts developer, I have to implement different sorts of workaround in virtually every contract I develop. Though, my personal experience might be non representative, here are several examples of quite widely used contracts that implement fractional math themselves:

1. EtherDelta 2 uses decimal fixed point for fees abd simple fractions for prices, both implemented in naive, overflow-prone way.
2. ENS Registrar uses naive decimal fixed point for refund ratios.
3. BancorConberter uses binary fixed point.

[axic]

Some relevant discussions:

• https://forum.openzeppelin.com/t/designing-fixed-point-math-in-openzeppelin-contracts/2499
• https://twitter.com/alexberegszaszi/status/1245040879645200384 (check the comments)

[nventuro]

Given the discussions today on the Solidity Summit it might make sense to halt development of the library we had in mind for OpenZeppelin Contracts: the proposed native support greatly aligns with what we had in mind. I guess @MicahZoltu got what he wanted :stuck_out_tongue:

Is there a rough estimate for when we might expect this feature to be released? I'm not sure how much extra work is required on the compiler, given that fixed point types are already supported to a quite large extent.

Also, would explicit casts to and from intM be allowed for fixedMxN?

[axic]

Also, would explicit casts to and from intM be allowed for fixedMxN?

That was the plan, see the top message.

[albertocuestacanada]

[...] here are several examples of quite widely used contracts that implement fractional math themselves [...]:

And here there are another two significant projects that used Fixidity.sol for fixed point math, and deserve something better:

• Celo
• PoolTogether

Synthetix made their own fixed point library, which I personally like a lot. I use a very similar one in an under-the-wraps DeFi startup I'm working for now.

If the point is not proven, I'm sure I can dig through a bunch of DeFi projects and most of them will use so

[albertocuestacanada]

@3sGgpQ8H made some good points that I think deserve better explaining. He told me the same a while ago in the OpenZeppelin thread and I only understood it fully while working in a different project.

When working with fixed point types the most common operation, by far, is this:
uint modified_amount = uint amount * fixed rate

There is really no reason to keep currency amounts in fixed point numbers, except for the reason that I don't think we can have cross-type operations in solidity, so the above usually means:
fixed modified_amount = fixed(uint amount) * fixed rate;

We shouldn't have currency amounts stored in fixed point types, but since we have to multiply them by a fixed point rate, that means you have to cast from uint amount to fixed amount, and then we have to be careful with precision losses due to representation.

My vote would be for a decimal representation, but I don't think it matters much. I'm pretty sure that a binary representation would work fine as well and if it is done right the smart contract developers would be none the wiser.

[albertocuestacanada]

Another comment is about using 18 decimals because that's the convention with ether. I pressed for this myself, @3sGgpQ8H told me I was wrong, and eventually I saw that taking a cue from the decimals used in ether is misleading, as I was told :man_shrugging:

Think about this, you have these two variables:
uint money = 1
uint votes = 1

When you cast them into fixed point, you will want this result:
fixed money = 1.0
uint votes = 1.0

But money is probably in wei, so to be consistent you would need:
fixed money = 0.000000000000000001
fixed votes = 0.00000000000000001

So it doesn't matter how many decimals are in ether, a conversion from uint to fixed can't take them automatically into account.

However, there should be some option to cast from uint to fixed and automatically displace the result, something like this:
fixed money = fixed_18(uint money)

The casting above would convert from uint money = 1 to fixed money = 0.000000000000000001

[albertocuestacanada]

How many decimals to use?

• If there aren't cross type operations then we need cast_and_displace and using 18 decimals is useful because then fixed can hold the same money amounts as uint.
• If there are cross type operations then don't need cast_and_displace, money amounts would have no reason to use the fixed type, and I would use a much larger amount of decimals such as 27 or even 45. That is because most values that belong in a fixed type are in the (2, -2) range (think about it, when have you needed to calculate the 10000000% of something?).

And I'm done! Thanks for listening! :nerd_face:

[chriseth]

Thank you very much for your input, @albertocuestacanada ! This actually leaves me much more worried than before...

Currently, all types and operators in Solidity (except for shifts and exp) work by either implicitly converting the left operand to the type of the right operand or vice-versa and then doing the operation in that type.

Furthermore, implicit conversions can only be done if there is no precision or data loss.

If we keep these concepts, then we can neither have fixed * int -> int nor fixed * int -> fixed. The only thing that can be done is something like fixed256x18 * int128 -> fixed256x18, i.e. the integer types has to fit inside the fixed point type.

What could make sense is - and this has been discussed another issue I currently cannot find - to make the result of the multiplication have a new type that fits both the value and the precision range of the result. I.e. unt64 * ufixed64x4 would have 4 digits precision and the number of bits required to represent the number (2**64-1) * (2**64-1 / 10**4). The benefit of this approach would be that we do not need overflow checks (because nothing ever overflows), but the downsides are that you need explicit type conversions afte almost each operation and the implementation would also be more complicated.

[albertocuestacanada]

Yeah, I thought that cross-type operations would be hard. If we can't have them for uint256 then there is probably no point, as we would have to cast all currency amounts anyway.

If we can't have fixed * int -> int nor fixed * int -> fixed, then we need to store currency amounts in fixed. That means that conversions between int and fixed can't have data loss. I might be wrong but that is probably harder to do with binary representation.

If we are going to store currency amounts in fixed because cross-type conversions are a no-go then I think we would need:

• Decimal representation, with 18 decimals (plus other precisions if desired).
• To be able to choose between two casting behaviours: fixedA(1) == 1.0 and fixedB(1) == 0.00...001

[nventuro]

Wouldn't such an application be better suited for functions in a library? Another related function is div(uint, uint) -> fixed - I'm not sure how such a function would be implemented in terms of operators.

[chriseth]

Do we really need so many integer digits? Wouldn't div(uint, uint) -> fixed be fine by converting the uint to fixed first?

About fixedA(1) == 1.0 and fixedB(1) == 0.00...001: The second could be realized by casting through a bytes32 I would say.

[albertocuestacanada]

Do we really need so many integer digits? Wouldn't div(uint, uint) -> fixed be fine by converting the uint to fixed first?

Yes, converting the uint to fixed would be fine, but as before being able to choose how to convert would be useful.

You would see the operation above when calculating the proportion than a certain token holds in a basket. For example if I have something like a balancer pool that should have a 40% of it's value in Dai, and the other 60% in WEth, you would do P = div(dai.balanceOf(address), weth.balanceOf(address)) to check if you have to rebalance.

If you can use a fixedB(1) == 0.00...001 conversion above, you wouldn't need to worry about overflows. You just do div(fixed(uint), fixed(uint)).

If you must use a fixedA(1) == 1.0 conversion above, you need to know that you convert currency amounts like this: fixed_a = fixed(uint_a) / fixed(10**decimals_a). You also need to require(a < MAX_UINT256 / 10**decimals_a);. A bit cumbersome, and slightly limiting (not much), but can be coded in a library. A lot of gas would be wasted, though.

[albertocuestacanada]

Ah, hold on. @chriseth, did you mean that to do ufixed(1) == 0.00...001, we could do it like ufixed f = fixed(bytes32(uint256 i))?

And then, of course, for ufixed(1) == 1.0 we would do ufixed f = ufixed(uint256 i).

I would like that. You would keep types and casting general and consistent, but there would be a workaround to cast money amounts into fixed units without range issues, loss of precision, or unnecessary operations.

[nventuro]

As long as there is a way to cast (not convert!) to and from integers of the same word size, I think we'll be fine. Simple functions can then make those operations more readable, such as:

function getRate(uint128 a, uint128 b) internal returns (fixed128x18) {
    return fixed128x18(a) / fixed128x18(b);
}

I'd focus on operations within the fixed type (add, sub, mul, div).

[chriseth]

The cast (type conversion / "re-labeling" without changing the underlying data) would go through the respective bytesXX type. Explicit and implicit conversions would not change the numeric value, but the EVM word data:

uint8 x = 1;
fixed128x10 y = x; // implicit conversion, results in a multiplication by 10**10 at EVM-level
bytes16 z = bytes16(y); // explicit conversion to underlying bytes type, results in a left-shift (because bytes are left-aligned)
uint128 t = uint128(z); // explicit conversion, results in right-shift
assert(t == 10**10);

Still, I would be much more confident to see some example code that really benefits from the fixed-point types that are currently planned.

[nventuro]

@asselstine you've used fixed point libraries to compute rates and fractions, perhaps you could shed some light on this?

[albertocuestacanada]

It's late already here, tomorrow I'll write up an analysis of fixed point math use in MakerDAO, that'll be juicy.

[asselstine]

@nventuro I could shed some light on how we've used fixed point math in PoolTogether. I have used @albertocuestacanada's Fixidity.sol and have also rolled my own. Currently:

• Monetary values are stored as uint256.
• Monetary values are multiplied or divided by "mantissas" and returned as uint256. Mantissas are fixed point 18 numbers like Ether. Here is our simple multiply uint by mantissa function:

function multiplyUintByMantissa(uint256 b, uint256 mantissa) internal pure returns (uint256) {
    uint256 result = mantissa.mul(b);
    result = result.div(SCALE);
    return result;
}

It's pretty much like every other library out there.

The discussion between decimal and binary fixed point is a little beyond me.

However, in general I think that having a built-in fixed point type would improve readability for all contracts. Having a common fixed point "language" across all Ethereum projects would be good for the ecosystem, and would mean that people wouldn't have to roll their own or copy-and-paste Compound's Exponential lib.

Another benefit for code quality would be compiler warnings about mixing fixed with non-fixed or perhaps even bad casts. It would extend the helpful strong typing right down to the math.

[chriseth]

@asselstine thanks for the insights! Would you be able to share some code examples about how you would use built-in fixed point types?

[3sGgpQ8H]

function multiplyUintByMantissa(uint256 b, uint256 mantissa) internal pure returns (uint256) {
uint256 result = mantissa.mul(b);
result = result.div(SCALE);
return result;
}

This implementation suffers from what I call “phantom overflow”: it may overflow even when the final result would fit into uint256. For example, multiplication by one or by a number less than one may overflow, which seems absurd to me.

[asselstine]

@3sGgpQ8H Yes, the overflow is a concern. The scaling factor removes a lot of the top-end of the uint256. This is another one of my concerns that I'd love to see some support for, or compiler warnings at the very least.

@chriseth Happy to share some example code!

A good example is the calculateExitFee function.

The function first calculates the "mantissa" based on the user's total token supply:

FixedPoint.calculateMantissa(tickets, totalSupply)

This mantissa represents the fraction of tokens they own out of the supply. This mantissa is then used to calculate a "fair" fee to be paid to the prize. Pretty common use case.

If I were to use fixed point math, it might look something like:

fixed256x18 mantissa = fixed256x18.fraction(balance, totalSupply)
uint256 share = mantissa * total;

As @3sGgpQ8H mentioned, it would be great to have more clarity around overflow and numerical limits. I think this is where it might be useful to learn more heavily on the compiler for numerical safety. I'm not sure off the top of my head what that would look like, however.

[randomnetcat]

I can share some implementation experience. In #3389, we decided to restrict the fixed point types that could be multiplied and divided in order to prevent overflow. I believe the result was that two fixed points could only be multiplied/divided if both of their types were 128 bits wide or less.

[chriseth]

@asselstine what are reasonable bounds on totalSupply? Do you use fractional tokens? How would your math look like given unrestricted precision on both integers and fractions - i.e. what kind of formulas do you use?

[asselstine]

Just want to add that this code has not been audited and is alpha :)

totalSupply is from the standard ERC20 token, so it is a uint256. It would be interesting to limit the minting of tokens so that the supply is less than uint128, as suggested by @random-internet-cat. That would ensure the numbers fit into the fixed point size and mitigate overflow. It does remove a lot of the top-end of the number, though.

Does that answer your question?

[chriseth]

@asselstine thanks for that comment! I would still really like to see more uses of fixed points. I have a hard time reading your code, unfortunately, could you maybe just provide the raw formulas?

[asselstine]

Sure.

First we let:

totalSupply = total # of tickets
balance = users # of tickets
previousPrize = the size of the last prize that was awarded
remainingTime = remaining number of seconds until prize
prizePeriodSeconds = total number of seconds between prizes

Then we calculate the exit fee:

exitFee = (remainingTime / prizePeriodSeconds) * (balance / totalSupply) * previousPrize

[3sGgpQ8H]

I believe the result was that two fixed points could only be multiplied/divided if both of their types were 128 bits wide or less.

For me, forbidding multiplication of wide types makes the whole idea quite useless. I would prefer compiler to automatically apply different strategies for different types and even different values.

For example, when combined bit-widths of both arguments do not exceed 2^256-1, naive approach could be used:

return x * y / scale;

Otherwise, if scale is below 2^128-1, slightly more complicated approach is needed:

if (y == 0) return 0;
else {
    require (x / scale < uint(-1) / y); // Overflow protection, should be improved

    uint xh = x / scale;
    uint xl = x % scale;
    uint yh = y / scale;
    uint yl = y % scale;

    return xh * xh * scale + xh * yl + xl * yh + xl * yl / scale;
}

Probably, scale above 2^128-1 should be just forbidden, but if not, then for higher scales, compiler should use 512-bit intermediate arithmetic, like here: https://medium.com/coinmonks/math-in-solidity-part-3-percents-and-proportions-4db014e080b1#fe5c

[asselstine]

compiler should use 512-bit intermediate arithmetic

I love this idea. It would give us a lot more headroom over scaling the values.

[fulldecent]

512-bit is not something we need to have in the first iteration of this.

[3sGgpQ8H]

Yes, but overflow semantic should not change after the initial release, otherwise it will be a mess.
So, one option would be to limit the maximum number of decimals to be 38, so scale factor will always fit into 128 bits. This way, multiplication could avoid using 512-bit internal logic. However, division will still be a problem. In my opinion, x / 2.0 should never overflow, but naive implementation like x * 1e18 / 2e18 would overflow on large x values. So for division, we probably need some king of wide arithmetic even in initial release.

Another option (the one I would prefer) is to include only literals, assignments, comparisons, ABI encode/decode, and reinterpret casts into the initial release of the feature in compiler, and leave arithmetic and conversion operations to be implemented in libraries, as there is no single “right” implementation for them.