33

How does a computer calculate a sin value? Logically, when I think about it the only apparent way is to put many sin values into memory, and when a sin value needs to be "calculated" it would just pull data from a specific memory address.(ex. sin(x) would pull data from the memory address containing the value of sin(x) )That seems like the only possible way to do it. Or is there a function which can be used to calculate the sin of a value? I'm really trying to ask how a computer calculates sin on a base level. Is there a way to approximate sin values using a different function composed of more "basic" operations, and the ALU would be able to do multiple "basic" operations to approximate the sin value, or is it just pulling values from memory?

zack1544
  • 807
  • 2
  • 13
  • 25
  • 10
    Google "CORDIC". Google "Taylor series". And your thoughts about memory are not clear. – Eugene Sh. Oct 07 '16 at 22:42
  • When I'm talking about the memory method, I'm trying to say, is a computer "programmed" with many hundreds of sin values? When the computer has to do a sin instruction, does it just take some value from memory and spit it back out? Will do the search, thanks for the reply. – zack1544 Oct 07 '16 at 22:48
  • 8
    The "memory" method is an optimization technique, frequently used (the name is "lookup table"). But no, initially the computer doesn't have it. But if you are ever wandering about how computer calculates <placeholder>, google "<placeholder> calculation algorithm". It works better than asking on SE in most cases.. – Eugene Sh. Oct 07 '16 at 22:50
  • 5
    In addition to CORDIC and Taylors', make sure you also look for Chebyshev coupled with non-linear minimax techniques. Taylor bounds average error, while Chebyshev bounds max error and closes in faster, as well. Minimax is needed because constants aren't infinitely precise and neither are operations. And you need to exploit symmetries, like crazy! – jonk Oct 07 '16 at 22:53
  • 3
    Are you aware that there is a series that can be used to calculate sin just as there is for cos, logs, exponents, pi, square roots etc. – Andy aka Oct 07 '16 at 23:20
  • 1
    If the only way to compute it was to fill memory with values, where would you get the values from in the first place? – whatsisname Oct 08 '16 at 01:45
  • @Andyaka I know the one for pi and exponents. I will take a look at the methods to find logs and square roots. Thank you for the insight. – zack1544 Oct 08 '16 at 02:07
  • 2
    Of course you can have content in computer memory "in the first place" - how do you think computers boot? Initial values can be wired into a circuit, built into read only memory cells or the metalization layers of an ic, burned into fuses, stored as trapped charge as well as read from disk, punch tape, or toggle switches - any method usable for software is in principle useful for precomputed tables, too, and in fact many algorithm needs various constants. What is best really has to be decided based on requirements, technology, and even what resources are left over after other needs. – Chris Stratton Oct 08 '16 at 03:40
  • I wonder if anyone uses a linear approximation with a triangle wave at sqrt(2) peak but truncated to 1. (graph) – Tony Stewart EE75 Oct 08 '16 at 03:18
  • @TonyStewart.EEsince'75: The old Intersil 8038 waveform generator chip did that, using several steps of linear approximation. But that's analog. With digital CPUs, GPUs, and pure software, polynomial fits are the most common way. – DarenW Oct 08 '16 at 05:40
  • @TonyStewart.EEsince'75: I hope not, because it has terrible accuracy (just look at the graph). – user253751 Oct 08 '16 at 07:19
  • but yet extreme simplicity – Tony Stewart EE75 Oct 08 '16 at 13:44
  • 2
    @whatsisname Values can be computed using any algorithm (including paper-and-pencil computation) and then be stored to the lookup table during manufacture. – nanofarad Oct 08 '16 at 17:00
  • Might be worth looking at http://stackoverflow.com/questions/2284860/how-does-c-compute-sin-and-other-math-functions. – copper.hat Oct 09 '16 at 04:52
  • @hexafraction: I think you missed the point. – whatsisname Oct 09 '16 at 06:39
  • How does C compute sin() and other math functions?, What algorithms do FPUs use to compute transcendental functions? – phuclv Aug 14 '18 at 10:29

2 Answers2

33

Typically high resolution sin(x) functions would be implemented with a CORDIC (COrdiate Rotation DIgital Computer) algorithm, which can be accomplished with a small number of iterations using only shifts and add/subtract and a small lookup table. The original paper The CORDIC Computing Technique by Jack Volder is from 1959. It also works nicely when implemented with hardware in an FPGA (and a similar algorithm would be implemented in a hardware FPU for those micros that have an FPU).

For lower resolution, for example to create synthesized sine wave for an inverter or motor VFD (Variable Frequency Drive), a lookup table (LUT) with or without interpolation works well. It's only necessary to store the values for one quadrant of the sine wave because of symmetry.

As @Temlib points out, the algorithms used inside modern FPUs use range reduction followed by an evaluation using something like the Remez algorithm to limit the maximum absolute error. More can be found in this Intel paper Formal verification of floating point trigonometric functions.

Spehro Pefhany
  • 397,265
  • 22
  • 337
  • 893
  • 2
    CORDIC is rather for a pure hardware fixed function conversion (its first historical application). For a computer with a FPU, polynomial approximations are faster and more suitable as they reuse existing arithmetic operators instead of a special CORDIC shift-and-add machine. – Grabul Oct 08 '16 at 16:34
  • 1
    @TEMLIB Yes, that's a valid point, I'll add that to the answer. CORDIC was used in the first scientific calculators too, such as the HP-35. – Spehro Pefhany Oct 08 '16 at 16:57
  • To my knowledge, CORDIC had it's first hardware implementation in the HP 9100A desk calculator. It had a printed circuit card about a foot square, covered with diodes, which served as the ROM storing the parameters used by the CORDIC algorithms. – Hot Licks Oct 09 '16 at 01:50
  • @HotLicks - you would be incorrect, CORDIC was developed for and used in an in-flight navigation computer nearly ten years before the HP 9100A. – Chris Stratton Oct 09 '16 at 03:58
  • @ChrisStratton - I stand corrected. – Hot Licks Oct 09 '16 at 12:45
  • Also worth pointing out that some processors have hardware trig. implementations. I only know this because someone found an error in one of the processors a while ago. Secondly, a good resource is to look at the standard C libraries for the implementation. If I remember correctly, completely different algorithms were used depending on the angle size. They were also extremely hardware dependent, which is something you don't often see nowadays with all the layers of abstraction. – user110971 Oct 09 '16 at 15:18
15

Most computer trig libraries are based on polynomial approximations, which gives the best balance between speed an accuracy. For example, a dozen or so multiplication and add/subtract operations is enough to give full single-precision accuracy for sine and cosine.

Dave Tweed
  • 172,781
  • 17
  • 234
  • 402