search

algorand / go-algorand

Algorand's official implementation in Go.
https://developer.algorand.org/
Other
1.35k stars 473 forks source link

divw and friends #1967

Closed jannotti closed 3 years ago

jannotti commented 3 years ago

TEAL has addw and mulw but divw is lacking. It's quite hard to implement "long" division properly with the remaining operations in TEAL. Some possibilities

divw: takes two 128 uints, in the form of two pairs of uint64s on the stack. pushes the quotient as two uints. cost ~ 4? modw: same, but gives remainder. cost ~ 4? divmodw: returns both, at lower cost than 8?

Is there a need for subw? I think less so because "long" subtraction is more easily implemented with the rest of TEAL.

Also add the following opcodes: shl, shr, exp, expw, sqrt, log2

krotkiewicz commented 3 years ago

@jannotti do we already have the next network update date? can we have divmodw by then?

I would like to schedule PyTEAL work to take advantage of that new opcode.

jannotti commented 3 years ago

There is the teal v3 update that I think will be on mainnet very soon. v4 will have divmodw (or similar) but is not done yet. So I suspect that will be in the following update. Usually that's a couple months?

On Sat, Mar 27, 2021 at 5:46 AM Konrad Rotkiewicz @.***> wrote:

@jannotti https://github.com/jannotti do we already have the next network update date? can we have divmodw by then?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/algorand/go-algorand/issues/1967#issuecomment-808703432, or unsubscribe https://github.com/notifications/unsubscribe-auth/AADL7T6N3RIKTGM5ZMZPBBDTFWSOZANCNFSM4ZD6ES7Q .

krotkiewicz commented 3 years ago

@jannotti, so basically no chances in adding it to v3?

We are waiting for that one to finish our AMM solution https://github.com/ulamlabs/asaswap

Currently, we are working on an emulation here.

This approach several major disadvantages and probably won't be enough for the final version.

krotkiewicz commented 3 years ago

@jannotti I know I am late but any chance for this in v3? https://github.com/algorand/go-algorand/pull/2041

jannotti commented 3 years ago

Teal 3 left the building a few weeks ago. It's just in the somewhat lengthy process of making its way through betanet, testnet, mainnet upgrade. So nothing else can get in.

Thanks for working on divmodw. I'm afraid I've also written it, so your code might not end up directly merged, but a form of divmodw will certainly make it into v4. It's actually pretty nice to have another implementation to look at, as I might catch a bug by comparing.

krotkiewicz commented 3 years ago

Understand, thanks for a fast reply.

We are currently trying to emulate calculating a proportion (A x B / C). Without that opcode, it looks like a nightmare (it takes 2kb to have full precision).

jannotti commented 3 years ago

We will end up calling this instruction divmodw (though the current PR calls it divw), to make it clear that both results are returned. We may add divw and modw as conveniences to do less popping when you only care about one result. We have not chosen a cost yet, but expect all three to have the same cost, as the same work must be done, so the short forms are only for convenience.