11

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?

2 Answers 2

11

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

8

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.