This repo contains code to generate as well as a specific instance of a normal distribution CDF (cumulative distribution function) implemented in Solidity.
The CDF.cdf function operates on WAD numbers (fixed point numbers with scale 10^18) and achieves
8-digit accuracy (max error
- Setup virtual environment:
uv venv .venv - Install mpmath:
uv pip install mpmath - Run tests:
forge t -vvv --ffi
The core objective was to approximate either
I therefore opted to approximate the error function itself using a rational approximation, finding
tow polynomials
This algorithm was implemented in Python using the arbitrary precision library mpmath:
script/remez/rational.py.
Initially despite correct implementation the algorithm did not work as I was attempting to
approximate to large of a range. I then discovered that not only did the algorithm work well once
you started applying it to smaller ranges, you needed a smaller function to achieve the same
precision. This is how I came to implementing the final algorithm in
script/bounds.py. It takes a set target accuracy and parameter size and
continuously bisects the target range until the desired accuracy is achieved, it then stores the
result in a json file.
The last step of the process is the codifier which takes the list of
functions and produces solidity assembly code to be inserted into the implementation.
While the code was applied to the Normal Distribution CDF with very simple tweaks it could be applied to other functions.
Base-2 Fixed Point Numbers
For the sake of accuracy and getting access to cheaper "division" in the form of bit-shifting
opcodes the input to the function is converted to a base-2 fixed point number when computing
Arithmetic Overflow/Underflow Checks
Thanks to the bounds of the polynomial and the range checks the core erfc function cannot overflow.
However when