41–50 of 68 posts
Earlier quoted context omitted.
It may be, especially when it comes to unnecessary cache. But I think `atan` is almost a brute force. Lookup is nothing comparing to that. Sin/cos must be borders of sqrt(x²+y²). It is also cached indeed.
What do you mean brute force? We can compute these things using iteration or polynomial approximations (sufficient for 64 bit).
Earlier quoted context omitted.
On modern machines, looking things up can be slower than recomputing it, when the computation is simple. This is because the memory is much slower than the CPU, which means you can often compute something many times over before the answer from memory arrives.
Unless your lookup table is small enough to only use a portion of your L1 cache and you're calling it so much that the lookup table is never evicted :)
L1D caches have also gotten bigger -- as big as 128KB. A Deflate/zlib implementation, for instance, can use a brute force full 32K entry LUT for the 15-bit Huffman decoding on some chips, no longer needing the fast small table.
Earlier quoted context omitted.
The compiler can substitute the value how it sees fit. It's like #define, but type-safe and scoped. Maybe it's folded into expressions, propagated through constant expressions, or used it in contexts that require compile-time constants (template parameters, array sizes, static_assert, other constexpr expressions). I mean, not in this case of pi/2, where it's more about announcing semantics, but in general those are t…
It can do this with const too or even a normal variable that just happens to not vary.
If you just want the optimizer to be able to constant-fold a value, then yes, either of those will work.
If you want to be able to use the value in the other contexts the parent mentioned that require constant expressions as a language rule, then you generally need constexpr. As an exception, non-constexpr variable values can be used if they’re const (not ‘happens to not vary’) and have integer or enum type (no floats, structs, pointers, etc.). This exception exists for legacy reasons and there’s no particular reason to rely on it unless you’re aiming for compatibility with older versions of C++ or C.
Even if you don’t need to use a variable in those contexts, constexpr evaluation is different from optimizer constant evaluation, and generally better if you can use it. In particular, the optimizer will give up if an expression is too hard to evaluate (depending on implementation-specific heuristics), whereas constexpr will either succeed or give an error (depending only on language rules). It’s also a completely separate code path in the compiler. There are some cases where optimizer constant evaluation can do things constexpr can’t, but most of those have been removed or ameliorated in recent C++ standards.
So it’s often an improvement to tag anything you want to be evaluated at compile time as constexpr, and rarely worse. However, if an expression is so trivial that it’s obvious the optimizer will be able to evaluate it, and you don’t need it in contexts that require a constant expression, then there’s no concrete benefit either way and it becomes a matter of taste. Personally, I wouldn’t tag this particular pi/2 variable constexpr or const, because it does satisfy those criteria and I personally prefer brevity. But I understand why some people prefer a rule of “always constexpr if possible”, either because they like the explicitness or because it’s a simpler rule.
Earlier quoted context omitted.
> Sin/cos must be borders of sqrt(x²+y²). It is also cached indeed This doesn't make a ton of sense.
In what way do you think a sin function is computed? It is something that computed and cached in my opinion. I think it is stored like sintable[deg]. The degree is index.
In some way vaguely like this: https://github.com/jeremybarnes/cephes/blob/master/cmath/sin...
> I think it is stored like sintable[deg]. The degree is index.
I can think of a few reasons why this is a bad idea.
1. Why would you use degrees? Pretty much everybody uses and wants radians.
2. What are you going to do about fractional degrees? Some sort of interpretation, right?
3. There's only so much cache available, are you willing to spend multiple kilobytes of it every time you want to calculate a sine? If you're imagining doing this in hardware, there are only so many transistors available, are you willing to spend that many thousands of them?
4. If you're keeping a sine table, why not keep one half the size, and then add a cosine table of equal size. That way you can use double and sum angle formulae to get the original range back and pick up cosine along the way. Reflection formulae let you cut it down even further.
There's a certain train of thought that leads from (2).
a. I'm going to be interpreting values anyway
b. How few support points can I get away with?
c. Are there better choices than evenly spaced points?
d. Wait, do I want to limit myself to polynomials?
Following it you get answers "b: just a handful" and "c: oh yeah!" and "d: you can if you want but you don't have to". Then if you do a bunch of thinking you end up with something very much like what everybody else in these two threads have been talking about.
For reference, the coefficients given are [1.5707288, -0.2121144, 0.0742610, -0.0187293]: if we optimize P(x) = (π/2 - arcsin(x))/sqrt(1-x) ourselves, we can extend them to double precision as [1.5707288189560218, -0.21211524058527342, 0.0742623449400704, -0.018729868776598532]. Increasing the precision reduces the max error, at x = 0, by 0.028%.
Adjusting our error function to optimize the absolute error of arcsin(x) = π/2 - P(x)*sqrt(1-x) on [0,1], we get the coefficients [1.5707583404833712, -0.2128751841625164, 0.07689738736091772, -0.02089203710669022]. The max error is reduced by 44%, from 6.75e-5 to 3.80e-5. If we plot the error function [0], we see that the new max error is achieved at five points, x = 0, 0.105, 0.386, 0.730, 0.967.
(Alternatively, adjusting our error function to optimize the relative error of arcsin(x), we get the coefficients [1.5707963267948966, -0.21441792645252514, 0.08365774237116316, -0.02732304481232744]. The max absolute error is 2.24e-4, but the max relative error is now 0.0181%, even in the vicinity of the root at x = 0. Though we'd almost certainly want to use a different formula to avoid catastrophic cancellation.)
So it goes to show, we can nearly double our accuracy, without modifying the code, just by optimizing for the right error metric.
Earlier quoted context omitted.
On modern machines, looking things up can be slower than recomputing it, when the computation is simple. This is because the memory is much slower than the CPU, which means you can often compute something many times over before the answer from memory arrives.
Unless your lookup table is small enough to only use a portion of your L1 cache and you're calling it so much that the lookup table is never evicted :)
I haven't kept up with C++ in a few years - what does constexpr do for local variables? constexpr double a0 = 1.5707288;
It is required to be evaluated at compile time, and it's const. An optimizing compiler might see through a non-constexpr declaration like 'double a0 = ...' or it might not. Constexpr is somewhat more explicit, especially with more complicated initializer expressions.
Earlier quoted context omitted.
In what way do you think a sin function is computed? It is something that computed and cached in my opinion. I think it is stored like sintable[deg]. The degree is index.
> In what way do you think a sin function is computed? In some way vaguely like this: https://github.com/jeremybarnes/cephes/blob/master/cmath/sin... > I think it is stored like sintable[deg]. The degree is index. I can think of a few reasons why this is a bad idea. 1. Why would you use degrees? Pretty much everybody uses and wants radians. 2. What are you going to do about fractional degrees? Some sort of interpreta…
I try to understand how Math.sin works. There is Math.cos. It is sin +90 degrees. So not all of them is something that completes a big puzzle.
Earlier quoted context omitted.
The compiler can substitute the value how it sees fit. It's like #define, but type-safe and scoped. Maybe it's folded into expressions, propagated through constant expressions, or used it in contexts that require compile-time constants (template parameters, array sizes, static_assert, other constexpr expressions). I mean, not in this case of pi/2, where it's more about announcing semantics, but in general those are t…
I'd like something like this in C or C++ quite honestly. Something like a struct that I can say "this struct is global to the whole program and everyone can see it, but once this function exits those values are locked in". Maybe something like that one function is allowed to unlock and update it, but nowhere else. Think in terms of storing a bunch of precomputed coefficients that are based on the samplerate of a syst…