Support for wide (128-bit) arithmetic

[jasonpaulos]

Summary

TEAL has the opcodes mulw, addw, and divmodw, which can be used to multiply, add, and divide 64-bit unsigned integers without worrying about possible overflow. They work by using two 64-bit integers to represent a single 128-bit integer on the stack.

PyTeal could expose these opcodes in order to create convenience methods for math operations whose input and output are 64-bit integers, but whose intermediate values might be as large as a 128-bit integer. (By this I mean we could make it easier to express A * B / C where A * B might overflow a 64-bit int, but the final expression will not overflow. If you're looking for ways to directly handle integers larger than 64-bits, consider byteslice arithmetic instead.)

Scope

Create a set of functions which internally use mulw, addw, and divmodw to perform multi-step arithmetic expressions on 64-bit unsigned integers. These could be:

• WideRatio(numeratorFactors: List[Expr], denominatorFactors: List[Expr]) -> Expr: calculate the product of numeratorFactors divided by the product of denominatorFactors, e.g. (N_1 * N_2 * N_3 * ...) / (D_1 * D_2 * D_3 * ...)
• WideSummation(positiveTerms: List[Expr], negativeTerms: List[Expr]) -> Expr: calculate the summation of all positiveTerms minus the summation of all negativeTerms, e.g. (P_1 + P_2 + P_3 + ...) - (N_1 + N_2 + N_3 + ...)

Maybe there's a need for expressions mixing addition and division too, possibly of the form (A + B) / C?

Priority

Not urgent because it's possible to use byteslice arithmetic in place of this (e.g. Btoi(BytesDiv(BytesMul(Itob(Int(1)), Itob(Int(2))), Itob(Int(3)))) expresses 1 * 2 / 3 in a way that's safe from overflow). However, exposing support for divmodw and friends would be more efficient in terms of opcode cost.

[Ungolim]

bumping this; @jasonpaulos, as @cusma says, judging from discord discussions a fair amount of projects would stand to benefit from an official, safe and efficient library leveraging the 128-bit math opcodes

Using byteslice is wasteful

[jasonpaulos]

edit: changed prefix of proposed functions from Safe to Wide

[algoanne]

note: we now have divw that should also be perhaps taken into account here.

[michaeldiamant]

To hopefully minimize confusion, making these changes:

• Open Provide general-purpose wide arithmetic (128-bit) API #246 with an explicit focus on a general-purpose API rather than providing a narrow API supporting limited operations.
• Close this issue because it seems a general-purpose API is more sought after than additional, specific operations. Should the assumption change, let's reopen.

[huybuidac]

@jasonpaulos any info or update about WideSummation

[jasonpaulos]

We will likely prioritize general-purpose wide math support as described in #246 over another specific function like WideSummation.

If you're feeling adventurous, you could check out #236 which is a work in progress PR to add general-purpose wide math. There's not much in the way of documentation or tests, so take that into consideration, but the bottom of pyteal/ast/widemath.py has some comments with example usage.