4 ms·
CORDIC is how it's usually done in hardware (and FPGAs). https://en.wikipedia.org/wiki/CORDIC https://en.wikipedia.org/wiki/CORDIC
by vardump 3y ago
CORDIC is how it's usually done in hardware (and FPGAs).
https://en.wikipedia.org/wiki/CORDIC https://en.wikipedia.org/wiki/CORDIC
- adgjlsfhk1 3y agono it's not. cordic has awful convergence of 1 bit per iteration. pretty much everyone uses power series.
- f1shy 3y agoThat is 64 iterations for a double, that is nothing!
- adgjlsfhk1 3y ago53, but that's still a lot more than the 5th degree polynomial that you need.
- rcxdude 3y agoyeah, but 52 adds can be a lot cheaper than a few multiplies, if you're making them out of shift registers and logic gates (or LUT). in a CPU or GPU, who cares, moving around the data is 100x more expensive than the ALU operation.
- Const-me 3y ago> in a CPU or GPU, who cares, moving around the data is 100x more expensive than the ALU operation Moving data is indeed expensive, but there’s another reason to not care. Modern CPUs take same time to add or multiply floats. For example, the computer I’m using, with AMD Zen3 CPU cores, takes 3 cycles to add or multiply numbers, which applies to both 32- and 64-bit flavors of floats. See addps, mulps, addpd, mulpd SSE instructions in that table: https://www.uops.info/table.html https://www.uops.info/table.html
- adgjlsfhk1 3y ago> moving around the data is 100x more expensive than the ALU operation. This is exactly the problem with CORDIC. 52 dependent adds requires moving data from a register to the ALU and back 52 times.
- rcxdude 3y agoIt's the problem with CORDIC in that context, yes!
- ajross 3y agoActually pretty much everyone implements double precision sin/cos using the same (IIRC) pair of 6th order polynomials. The same SunPro code exists unchnaged in essentially every C library everywehre. It's just a fitted curve, no fancy series definition beyond what appears in the output coefficients. One for the "mostly linear" segment where the line crosses the origin and another for the "mostly parabolic" peak of the curve.
- perihelions 3y agoCORDIC is pretty obsolete, AFAIK. Its advantage is that its hardware requirements are absolutely tiny: two (?) accumulator registers, and hardware adders and shift-ers—I think that's all. No multiplication needed, in particular. Very convenient if you're building things from discrete transistors, like the some of those earlier scientific calculators! (Also has a nice property, apparently, that CORDIC-like routines exist for a bunch of special functions and they're very similar to each other. Does anyone have a good resource for learning the details of those algorithms? They sound elegant).
- pclmulqdq 3y agoCORDIC still is used in tiny microcontrollers (smaller than Cortex-M0) and in FPGAs when you are very resource-constrained. Restricting the domain and using Chebyshev/Remez is the way to go pretty much everywhere.
- f1shy 3y agoMultiplication is pretty much needed in cordic! And is far from obsolete! It works perfectly fine, and dont have any of the problems said in the article.
- perihelions 3y agoIt uses multiplication by powers of two, which is a floating-point bit shift.
- kevin_thibedeau 3y agoCORDIC doesn't use multipliers. That's the whole appeal for low performance hardware since it's all shifts and adds. It can still be useful on more capable platforms when you want sin and cos in one operation since there is no extra cost.
- dilyevsky 3y agoI think still used out of necessity when hw floating point not available (like fpgas)
- 3y ago
- bigbillheck 3y agoWhy would you ever use CORDIC if you had any other option?
- vardump 3y agoIt's great for hardware implementations, because it's simple and you get good/excellent accuracy. I wouldn't be surprised if that's still how modern x86-64 CPUs compute sin, cos, etc. That said, last time I had to do that in software, I used Taylor series. Might not have been an optimal solution. EDIT: AMD's Zen 4 takes 50-200 cycles (latency) to compute sine. I think that strongly suggests AMD uses CORDIC. https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf page 130. Same for Intel, Tiger Lake (Intel gen 11) has 60-120 cycles of latency. Page 353. I'd guess usually ~50 cycles for Zen 4 (and ~60 for Intel) for float32, float64/float80 datatype. Denormals might also cost more cycles.
- bigbillheck 3y agoThey switched away from CORDIC at one point: https://www.intel.com/content/www/us/en/developer/articles/technical/the-difference-between-x87-instructions-and-mathematical-functions.html?wapkw=fsin https://www.intel.com/content/www/us/en/developer/articles/t... (there doesn't seem to actually be a linked article there, just the summary)
- vardump 3y agoPretty weird Intel's sine computation latency hasn't changed all that much over the years. Latencies have been pretty similar for 20 years. EDIT: That's a paper for a software library, not the CPU's internal implementation. Which is probably still done with CORDIC.
- bigbillheck 3y ago> EDIT: That's a paper for a software library, not the CPU's internal implementation. Unless you're seeing something I'm not, it's talking about x87, which hasn't been anything other than 'internal' since they stopped selling the 80486sx.