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.