https://www.righto.com/2026/09/8087-tangent-cordic.html
I hope you're not tired of the 8087, because I have another article about Intel's floating-point chip.1 In 1980, Intel introduced the 8087, making floating-point operations much faster in the IBM PC and other systems. In this article, I look at the algorithm behind the chip's tangent instruction. One popular approach for trigonometric functions is an algorithm called CORDIC. Another approach is a polynomial approximation. The 8087 combined the two to obtain both high accuracy and high performance. The 8087 provided an enormous speedup over the 8086 microprocessor, computing a tangent in 90 microseconds rather than 13,000 microseconds.2
By examining the circuitry and microcode of the 8087, I can explain the algorithm behind the tangent instruction, called FPTAN. To explore the 8087's circuitry, I popped the lid off a chip with a chisel and created a high-resolution image with a microscope.
(Score: 2, Insightful) by shrewdsheep on Monday September 28, @08:51AM (6 children)
exponential time algorithms. Everything can be solved by lookup tables in constant time!
Thanks, interesting read.
(Score: 4, Informative) by weirsbaski on Monday September 28, @05:33PM (3 children)
That first sentence doesn't follow from the second sentence. Just because lookup tables can be awesomely good doesn't mean that exponential-time algorithms don't also exist.
(And I'll leave to the reader to decide whether lookup tables might be impractical for the problem anyway, depending on the size of the tables required).
(Score: 0) by Anonymous Coward on Tuesday September 29, @02:01AM (2 children)
I haven't thought this through, but I'm wondering if a moderate sized LUT + calculations would be a workable compromise?
(Score: 3, Informative) by weirsbaski on Tuesday September 29, @04:36AM
I've seen something similar implemented on real silicon in the past (fast approximations for reciprocal and reciprocal-square-root), IIRC they looked up values in two lookup tables in parallel (a "bipartite table"), and added the results together to get the approximation. Don't know how widespread this method is though.
(Score: 3, Insightful) by lars_stefan_axelsson on Tuesday September 29, @12:12PM
Yes, that's whole field in numerical analysis. You can do it a couple of ways but one is to use piecewise polynomials instead of a polynomial of untractable degree: https://www.sciencedirect.com/topics/computer-science/polynomial-approximation [sciencedirect.com].
You can also start with a lookup and then do interpolation, or even more formal error correction: https://www.ijera.com/special_issue/NLTSETE&S/ECE/ECE-PP-001%20-%200107.pdf [ijera.com]. This paper is even with hardware implementation in mind. LUT plus small polynomial for interpolation exactly like you propose.
Stefan Axelsson
(Score: 4, Informative) by bzipitidoo on Monday September 28, @09:02PM (1 child)
The assumption that lookups are constant time is one of those little inaccurate simplifications that infest Computer Science's introduction to algorithms. An enormous random access physical memory device requires polynomial time, not constant time. Basically, think of filling in the entire solar system with some kind of "cosmic" RAM. To access memory on the other side of the solar system beyond the orbit of Saturn would take a while, hours at the least, what with such a device being far too big for lightspeed to traverse in a fraction of a second. Its capacity to retrieve items using no more than n units of time is only n^3 times however much data can be crammed into a unit of volume.
(Score: 0) by Anonymous Coward on Thursday October 01, @07:02AM
Just budget an infinite amount of setup time to arrange everything.
BTW if something is in a superposition could it in theory have all the results? You just need to coincidentally be in the right multiverse to always have the right results at the right time... 🤣