search

tact-lang / tact

Tact compiler main repository
https://tact-lang.org
MIT License
394 stars 110 forks source link

Port `stdlib.fc` and `mathlib.fc`'s asm functions to Tact's stdlib #770

Open anton-trunov opened 2 months ago

anton-trunov commented 2 months ago

This is going to be very easy after #768 is resolved.

It is partially addressed in these issues:

Gusarich commented 2 months ago

We can't just port them to Tact stdlib and remove the .fc files, because functions defined there are used in code generation, e.g. src/generator/writers/writeStdlib.ts.

anton-trunov commented 2 months ago

That's right. I meant some additional functions that can be used by Tact users.

Gusarich commented 3 weeks ago

@anton-trunov should I implement the sqrt function the same way as it works in mathlib.fc or take a different approach?

anton-trunov commented 3 weeks ago

@Gusarich I haven't checked how sqrt is implemented in mathlib.fc, what are the alternatives you see?

Gusarich commented 3 weeks ago

@anton-trunov we can take this one: https://github.com/TonoxDeFi/open-contracts/blob/ebbb877e5ee6a9e506605c455c44b2b5223956f1/contracts/math/math.func#L26

or even implement a different algorithm. probably makes sense to benchmark these on different ranges of integers to see what is more gas efficient

anton-trunov commented 3 weeks ago

probably makes sense to benchmark these on different ranges of integers to see what is more gas efficient

agreed!

Gusarich commented 5 hours ago

@anton-trunov turns out both of these implementation use the same Newton-Raphson method, but the one from tonox openlib does it in constant time (hardcoded 7 iterations for any input) and also has worse initial approximation, so the mathlib implementation wins on all ranges of numbers in terms of gas, especially after a few minor optimizations.

I looked through some other algorithms for square root finding and seems that Newton-Raphson will be the best for TVM in general, so I suggest to proceed with that (from mathlib).