What's the best way to compute square root in Substrate?

Question

I'm working on a quadratic voting function, and I'm trying to use a function like square root. There is no square root function in sp that I could find. What is the best way to do this?

Answer 1

If you are just after the integer sqrt (which, depending on your use-case, may be enough), you could follow the approach that the democracy pallet does.

In this case it uses integer_sqrt::IntegerSquareRoot under the hood to calculate

let sqrt_voters = tally.turnout.integer_sqrt();
let sqrt_electorate = electorate.integer_sqrt();

Before doing rational compares. The above use is here - https://github.com/paritytech/substrate/blob/676932fb5543d5b316b4e494631d8e48f98b760d/frame/democracy/src/vote_threshold.rs#L81-L106

Answer 2

TLDR:

sp-arithmetic for relatively simple use cases as highlighted in this answer, and substrate-fixed for more advance stuff.

To perform non-deterministic arithmetic like division and square roots, you'll mostly work with fixed-point numbers. One way to easily set them up is to use Substrate-fixed or hack off of the balance type (which is also a fixed point number - specifically a U88F40 in substrate-fixed). With that, you'll have access to wider arithmetic operations (fixed-point division, being the most prevalent). Next, you'll need to find an algorithm for computing the square root of a fixed-point number.

Here are a few links to help in that search:
I found this, but it's written in c and I haven't looked at the paper it's based off of.

I've also found this article but I barely glanced through it.

There's also Wikipedia

I'll try to update this with more info if I find anything interesting. Lastly, to avoid the headache that comes with these algorithms, I'd advise trying to find a workaround somehow that's equivalent to the square root, or remove the square root entirely by restating the formula either with logarithms (whose value is much easier to compute given the right table) or something similar.