snarkVM
snarkVM copied to clipboard
AleoNet
Faster `sqrt` impl
^This is the pseudocode algorithm for reference.
@ljedrz can you check the correctness of the Rust syntax and API usage (i.e. we use .floor() and .sqrt() among many operators) for edge cases that we have not have contemplated?
Left some suggestions; as long as subtractions and pows don't overflow, I don't see any obvious footguns here. As with any arithmetic implementations, I'd recommend using something like quickcheck to verify that the results match the expectations.
@ljedrz I've managed to squeeze out a lot of optimization, and managed around a 4-10% decrease in time taken to compute square roots (depending on field size, with Fr having the best decrease). Maybe you might find some more optimizations I can apply to shave it down even further.
More generally, the algorithm will become even faster if lookups are added. Since the theoretical improvement applies to both TS and Sarkar, we will see a more significant improvement by applying it here, so I think it may be worthwhile to continue working on this with the intention of merging it in.
For now we've decided to forgo the lookup variant of the Sarkar algorithm as the speedup may not be worth it.