4 ms·
I tried 1/sqrt(9x-6) from .7 to 1e308, and got as one alternative sqrt(-.16666…) It did correctly mark this as 0% accurate, but I’m kinda curious as to where
by bee_rider 3y ago
I tried 1/sqrt(9x-6) from .7 to 1e308, and got as one alternative
sqrt(-.16666…)
It did correctly mark this as 0% accurate, but I’m kinda curious as to where it came from.
It does have a 1.1x speedup apparently. None of the other (more accurate) options provide a speedup. Maybe there aren’t any value options that provide a speedup, but the tool allows increasingly reduced accuracy (down to zero) until it finds a speedup?
- lifthrasiir 3y agoYou can click "derivation" to see the exact process it was derived. It's the first term of a taylor series expansion around x = 0, which is indeed f(0) = 1/sqrt(9*0-6) = sqrt(-1/6). I'm not sure why x was chosen outside of its input domain though. ---- ADDED LATER: I think I have the answer. Herbie seems to always assume x = 0, but there are a fixed set of transformations to get around that fact. Currently it only tries f(x), 1/f(x) and 1/-f(x) [1]. [1] https://github.com/herbie-fp/herbie/blob/b4a4bb4c61749912a64362f254d4eb69a075e50f/src/patch.rkt#L57-L64 https://github.com/herbie-fp/herbie/blob/b4a4bb4c61749912a64... > Maybe there aren’t any value options that provide a speedup, but the tool allows increasingly reduced accuracy (down to zero) until it finds a speedup? AFAIK Herbie works by trying a bunch of transformations to get candidate expressions and evaluate them to get the pareto frontier. So if there is a single constant expression generated, it will always be available as the worst alternative.
- AlotOfReading 3y agoAside from the alternative, there's not much room to optimize that function. 1/sqrt(x) has pretty good approximations (e.g. fast inverse sqrt, reciprocal sqrt instructions) and 9x-6 is just FMA. A quick test with compiler explorer [1] shows 4 instructions, and you could probably do 3 with judicious instruction set choice and/or no regard for performance. Even a lookup table could be slower in practice, depending on what the rest of the program looks like. [1] https://godbolt.org/z/86P86xTvx https://godbolt.org/z/86P86xTvx
- pclmulqdq 3y agoThose are four long instructions, and there's a chance that you could do better within your desired accuracy bounds by using one of the inverse square root instructions and a round of Newton-Raphson iteration.
- bee_rider 3y agoIt does have an FMA command that it can suggest, but it paired it with pow. double code(double x) { return pow(fma(x, 9.0, -6.0), -0.5); } It labeled this as having a slowdown.