-3

I am wondering if Math.sin(), Math.cos() are O(1), and how is it translated to the compiler.

We can create a match table for it.

Or we can create a not so detailed match table and use a linear formula to calculate the value.

Or we can break it down.

I guess in any sense Math.sin() is sorta O(1) as the input is bounded, but how exactly is it done in the compiler and how complex it is?

Pyromonk
  • 684
  • 1
  • 12
  • 27
Shen Huang
  • 11
  • 4
  • it looks like a dupe: https://stackoverflow.com/questions/2284860/how-does-c-compute-sin-and-other-math-functions – Nina Scholz Jan 05 '18 at 22:10
  • 3
    It is `O(1)` (for *some* value of `C`), because it is has a [small] finite limit on instructions - even with Taylor expansion, eg. This doesn't mean every call is guaranteed to take the same amount of time (or not), but that's [not relevant to strict `O(1)` classification](https://en.wikipedia.org/wiki/Big_O_notation). – user2864740 Jan 05 '18 at 22:13
  • Javascript is an interpreted language. There is no compiler. – Pyromonk Jan 05 '18 at 22:22
  • @Pyromonk There often is a compiler. See, e.g., https://hacks.mozilla.org/2017/02/a-crash-course-in-just-in-time-jit-compilers/ – r3mainer Jan 05 '18 at 23:04
  • I have found the C library, where I think they uses a Taylor's expansion to do so but it is O(1) time. However I am not exactly sure how JS does it. Also there is actually a difference in a lookup table and Taylor's expansion. In order to optimize the code sometimes a lookup table that calculated certain values of it might be more efficient. – Shen Huang Jan 05 '18 at 23:36
  • @squeamishossifrage, yes, [you are right](https://softwareengineering.stackexchange.com/questions/138521/is-javascript-interpreted-by-design). My knowledge was out of date. Thank you. In most cases it goes through an interpreter first still. – Pyromonk Jan 05 '18 at 23:56
  • 3
    O(1) with respect to what? – Oliver Charlesworth Jan 06 '18 at 00:29

1 Answers1

1

It might be impossible to give a definite answer, so I will try to provide you with as much information as I can instead.

The Math object implementations can differ between browsers and operating systems ("Note that many math functions have a precision that's implementation-dependent. This means that different browsers can give a different result, and even the same JS engine on a different OS or architecture can give different results.[1]").

There are a few major ways in which a sine function can be implemented:

Complexity will depend on implementation. As far as I know, CORDIC algorithm is more common.

Pyromonk
  • 684
  • 1
  • 12
  • 27