[Twisted-Python] Reviewer who understands basic numeric algorithms wanted

Laurens Van Houtven lvh at laurensvh.be
Fri Sep 18 08:50:06 EDT 2009


Hello :-)



twisted.positioning has just (read: last night) grown a new module,
called util, which has two functions I needed for statistical
analysis: the error function (erf) and the inverse normal cumulative
distribution function (Phi).

As most of you on this mailing list probably know, code headed for
trunk needs to be reviewed. The reason I need to ask for this
specifically is because the reviewer does not need to know anything
about Twisted, but does need some experience with how numerical
algorithms work -- and that's about the opposite of most Twisted
reviewers ;-)

The default is to attempt to use scipy's implementation (which is
hopefully faster), but otherwise fall back to a pure Python
implementation (which from my tests is still way more than fast
enough).

The implementations rely on Chebyshev polynomial interpolation. The
error function is a pretty simple one, the inverse normal cdf is
slightly harder (three parts: the center is a simple rational, the
'tails' are rationals expressed in a linearizing parameter). There are
two things that make this easier:

1. Other people have done similar things, and said coefficients can be
looked up in other places (I'm not the first person to do the math --
I'm just the first person to implement both in Python with a shared
Horner scheme evaluator, apparently)
2. It can be shown to be accurate by comparing the results at random
points with scipy's reference implementation if we do it for 10**5 or
10**6 points or so -- there's already an automated unit test that does
it for a much smaller number

If you're not 100% sure you're up to it from just seeing the code, I
can also talk you through it and show how I got there :-)

It might be more useful to create a separate ticket for this piece of
code for reviewing purposes, if anyone else feels that's the case I'll
make the ticket.

People who are interested: you can reply to this mail, mail me
personally, or contact me on freenode (nick: lvh).

(Oh, and before someone tells me I'm reinventing the wheel: yes, but
not really -- the only commonly available python implementation is
Scipy, that's *already* used as the default, and we do need something
in case of no scipy (adding a dependency just because of one function
on all of scipy is not exactly good either) and the only other simpler
alternative would be a giant LUT with linear interpolation which would
have been *much* worse near the edges of the interval of invncdf,
which also happen to be the *interesting* bits of that function...)

tia
lvh



More information about the Twisted-Python mailing list