37 ms·
Interval arithmetic powers this graphing calculator I made. The user can enter a formula without solving for y, like “y^y = x^x”. I rearrange into “0 = x^x - y
by memalign 2y ago
Interval arithmetic powers this graphing calculator I made.
The user can enter a formula without solving for y, like “y^y = x^x”. I rearrange into “0 = x^x - y^y”. Then I use interval arithmetic to calculate the result interval of “x^x - y^y” for x = the x-axis range of the graph’s view, y = the y-axis range of the graph’s view. If the result interval contains 0 then I have something to draw. I recursively divide the ranges in half and do a binary search until I find very tiny intervals that contain solutions. I draw those as points on the graph.
Example formulas this can handle:
https://memalign.github.io/m/formulagraph/index.html?f1(x,t)=r%20=%203&v1=true&f2(x,t)=y%5Ey%20=%20x%5Ex&v2=true&f3(x,t)=(x+5)%5E2+(y-((x+5)%5E2)%5E(1/3))%5E2%20%3C%201&v3=true&f4(x,t)=r%20=%202*sin(2*theta)&v4=true&f5(x,t)=(x-5)%5E100%20+%20(y+5)%5E100%20%3C=%202&v5=true&f6(x,t)=-(x-floor(x))%20+%205&v6=true&grid=true&coords=0,0,12&paused=true https://memalign.github.io/m/formulagraph/index.html?f1(x,t)...
- kragen 2y agowhen i did this i got better efficiency from ternary search http://canonical.org/~kragen/sw/aspmisc/intervalgraph.html http://canonical.org/~kragen/sw/aspmisc/intervalgraph.html
- moonchild 2y agoyou may find this interesting if you haven't seen it already: https://fredrikj.net/blog/2017/11/new-rigorous-numerical-integration-in-arb/ https://fredrikj.net/blog/2017/11/new-rigorous-numerical-int...
- kragen 2y agoi hadn't, this is fantastic!
- infruset 2y agoIf on top of rigorous, you want them to be formally verified in Coq at the same time as they are computed: https://www.lri.fr/~melquion/doc/18-jar.pdf https://www.lri.fr/~melquion/doc/18-jar.pdf
- kragen 2y agois this the one mentioned in fredrik's post? he links https://www.lri.fr/~melquion/doc/16-itp-article.pdf https://www.lri.fr/~melquion/doc/16-itp-article.pdf which is presumably a different paper by the same author
- infruset 2y agoI think they are the conference and journal versions of the same paper. Hadn't seen it was mentioned in the article, I should have read it more thoroughly!
- thesz 2y agoThen you possibly will find this useful: https://en.wikipedia.org/wiki/Golden-section_search https://en.wikipedia.org/wiki/Golden-section_search
- kragen 2y agothat is an algorithm for a different problem; here we are looking for a zero, not an extremum, and we want to find all the zeroes (in a two-dimensional plane, so there are usually infinitely many zeroes), not just one of them perhaps there is a way to apply it to this problem that is obvious to you but not to me with autodiff we can use a zero-finding algorithm (even one that isn't derivative-free) to find extrema, but i don't know how you'd go about using an extremum-finding algorithm to find zeroes. the first step would seem to be quadrature? but that sounds impractical
- thesz 2y agoThe algoithm itself is about the use of golden ratio for interval search. One can use subdivision, other can use ternary division. And another one can use golden ratio.
- kragen 2y agoas i understand it, the advantage of golden-section search is that, to search for a minimum rather than a zero, you need to in some sense interpolate a parabola rather than a line, so you need three points rather than two, and you'd like them to be somewhat evenly spaced. i don't fully understand why the golden section is better for this than just dividing the interval between the two lowest points in half, but it's definitely an algorithm to solve a different problem