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

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?

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

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.

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.

• TLDR: `sp-arithmetic` for relatively simple use cases, and `substrate-fixed` for more advance stuff. Commented Mar 25, 2022 at 5:50