128-bit TEAL operations

General
1

We are trying to implement AMM (Automated Market Maker) DEX in TEAL.

Not sure how much into the details should I go but the problem that we are facing right now is that, we need to calculate proportion of assets that are already in the pool to the asset being added to the pool and from that we can calculate how much new pool tokens we should mint.

Lets assume that we have 100 pieces of asset X in the pool and this is represented by 1000 pool tokens (PT). When a user adds 10 more token X to the pool, we mint 100 new PT tokens and give it to the user. Simple.

This can be easily calculated from following formula pt = (newX/totalX) * totalPT.

From here comes harder things. Below are my assumptions that could be wrong, so please feel free to correct me.

All 3 variables in this equation could be either small numbers or large one from 1 up to 2^64.

The problem is that to calculate it, we need to either do multiplication or division first. If we do do division first, we could lose precision (1/2=0), we could multiple it by some power of two first (and then divide it back). If we do multiplication first we could face integer overflow.
In both cases we face either integer overflow or loosing lots of precision.

This means that there is no other way than to use mulw operation here? Or maybe I am exaggerating?

Also, after mulw we need to divide two values (low and high) from stack and convert it back to 64-bit? I can imagine this is not super hard and require just few operations.

2

I think you would avoid losing precision by also talking the modulo when performing that initial division, and use that fractional part in the later multiplication.

3

Ok, that make sense but what in case we have such numbers? I am getting either 0 or overflow.

IMG_6743
IMG_67433903Ă—1311 1.08 MB

4

Let’s pretend TEAL only supported u16, so the numbers are small.
I think you’re asking how you should calculate
(2^8/2^9)(2^8+1). Which is (256/513)(258) = 128r384

How can we get 128r384 using only what TEAL has?

I changed the calculation slightly to be a better illustration.
Dividing by 513 makes it more challenging - simple bit shifting won’t
work for the division. I used 258 as the second multiplicand instead
of 257 because otherwise the result is 128r128 which would be
confusing.

First, use mulw for 256*258 to get 66048, which would be returned as:
1 in the high word, and 512 in the low word. How can we divide this
two word representation of 66048 by 513?

Note that if you got a number in the high word that is bigger than
your divisor, you’ve got a problem - your final result doesn’t even
fit in the word size. I suppose something like that could happen in
an AMM if the token values were extremely divergent. Not sure what
you would do. So let’s assume otherwise for now.

The strategy will be to scale the small number in the high word up,
divide it by 513, and then scale it back down in such a way that
during the scale down, we figure out how it contributes tp the low word,
which is the final result.

Pick the largest scale factor k that won’t make the high word
overflow, and is a power of two. We can use k=2^15 because 1 is so
small. Scale up and divide: 1 * 2^15 / 513 = 63r449

So we now have three numbers. 512 in the low word from our original
multiply, 63 after the division by 513 in the high word, and 449 as
the remainder. Now we combine all of those.

The 63 needs to be scaled scaled “down” from the high word, into the
low word, by 15 bits. So it’s going to contribute to our final answer
as 126 (shifting down 15 bits from high into low is the same as
shifting the high up 1 bit and treating it as the low). The 449 also
needs to be scaled into the low word (as 898) but then combined with
the 512 that’s already there (898+512=1410) and divided by
513. 1410/513 = 2r384.

Add the 126 to 2 to get 128. And since the remainder was 384, we have
calculated exactly 128r384. You’ll probably be making a rounding
decision based on the 384 remainder compared to the 513 divisor.

I think perhaps the hardest part of this with TEAL today is the bit
shifting for the scaling by k. You can “shift” by multiplying or
dividing by integer constants. But I can’t think of a good way to
obtain those constants given a calculated integer at run time. That is, if you
want to shift up by 5, how do you calculate that you must multiply by
32? Soon you’ll be able to make the right integer by using a new
opcode bitset. In the mean time, I think you could hack up a kind of
lookup table in a byte-array.

All that being said, I’m sure Algorand is amenable to making this
easier, the question is what is the best way? Should we add divw
which takes its argument as two stack words? That seems easy, and a
smaller conceptual leaps than adding a u128 type (for which people
would probably ask for mulw to get two u128s and we’d have the same
problem!)

I suppose the “good news” is that, at the moment, if you tried to do
this the “simple way” by multiplying first, with * instead of mulw, the
overflow would panic your TEAL, so that txn just wouldn’t happen.

5

I’m not all convinced this always works. The low word could be nearly too big, so when you bring the bits down from the high word, you get addition overflow.

6

Thank you.

This looks like a right way to go, I will give it a try and think what to do with that one overflow. Still it looks like a quite a work to common math/finance problem that eventually most of more advanced smart contracts would end up.

Regarding extra opcodes. Adding divw would definitely help for that one case but I am not sure if it has any broader use cases.

So looks like I would need to build divw “subroutine” and wait for that opcode together with bitset.

7

With divmodw and callsub/retsub released to betanet…

func TestMulDiv(t *testing.T) {
	// Demonstrate a "function" that expects three u64s on stack,
	// and calculates B*C/A. (Following opcode documentaion
	// convention, C is top-of-stack, B is below it, and A is
	// below B.

	muldiv := `
muldiv:
mulw				// multiply B*C. puts TWO u64s on stack
int 0				// high word of C as a double-word
dig 3				// pull C to TOS
divmodw
pop				// pop unneeded remainder low word
pop                             // pop unneeded remainder high word
swap
int 0
==
assert				// ensure high word of quotient was 0
swap				// bring C to surface
pop				// in order to get rid of it
retsub
`
	testAccepts(t, "int 5; int 8; int 10; callsub muldiv; int 16; ==; return;"+muldiv, 4)

	testRejects(t, "int 5; int 8; int 10; callsub muldiv; int 15; ==; return;"+muldiv, 4)

	testAccepts(t, "int 500000000000; int 80000000000; int 100000000000; callsub muldiv; int 16000000000; ==; return;"+muldiv, 4)
}
3 Likes