Recursive Sine Approximation

For a quick smaller post today, we'll look at an approximation for the sine of an angle. (As always, SICP is the inspiration, and the Scheme solution for the relevant Exercise 1.15 can be found here.)

We saw in the last post that we could approximate the tangent function using Lambert's continued fraction representation. We can find a similar idea of an approximation for the sine function by using the following trigonometric identity:

So the plan is to implement that idea with some Scala code. We'll quickly look at the efficiency of the implementation, and then use it to compute a few examples. Easy.

The Implementation

This is a recursive trigonometric identity, so the most straight-forward implementation is a recursive function. Then the main idea of our algorithm is follows:

• Check whether x is "sufficiently small" (we'll need to decide what this means.)
• If x is sufficiently small, return x. It's a good enough approximation.
• Otherwise, recursively compute sin(x) according to the identity above.

So when is x sufficiently small? We'll need to have an inequality to test against, ie. |x|< m
for some number m close to zero (ie. m=0.1, m=0.01, etc). We do have a tradeoff here though. 

The smaller the value of m, the more accurate our result ought to be. But we're also doing that many more recursive calls. This would normally be bad enough (the more calls we make, the longer it'll take to get an answer!) but it's made even worse by the nature of the trigonometric expression.

 

For instance, suppose we've managed to recursively calculate a value for sin at some point in the computation. Then as we wind up the recursive calls, we're dividing that value by 3, then cubing it, then multiplying it by scalars and performing a subtraction. Because of this, we can't possibly implement this in a tail-recursive way. So we're guaranteed an extra stack frame for every call we make, and we'll blow the stack if we're not careful!

On the other hand, as far as recursive algorithms go we've actually got a pretty efficient one here (as you'll see). So we won't worry about this too much more, and we'll simply take m=0.01. This value should work to give us a decent approximation.

Finally, as it is written in SICP, we'd do well to isolate that function of sin(x/3) in its own separate lambda expression. This saves us having to do 2 recursive calls for each calculation, which would be truly inefficient.

So with all that said, the code is implemented as a Scala function:

Let's quickly check out the efficiency of the code.

Suppose we want to calculate sin(a) for some number a. The order of growth in time and space for this algorithm is directly tied to the number of recursive calls we need to make; and the number of recursive calls we need to make is directly tied to the number of divisions by 3 we need to make to get the absolute value less than 0.01.

That is, if k represents the number of calls we make, then we require that:
   k > log₃(a / 0.01).
In fact, k should be exactly the integer ceiling of this number.

So from those old log laws that we've all long forgotten about, we have that
log₃(a / 0.01) = log₃(a) – log₃(0.01). Here log₃(0.01) is a constant, so in terms of Big-O notation we can ignore it. So our order of growth when computing sin(a) is O(log₃(a)) for time and space. That's quite nice, as far as recursive algorithms go!

Some Example Calculations

We can test out some sine calculations here, comparing our sin() function to the Math.sin() function of the Java.lang.Math class.

     sin(2)
     //> res0: Double = 0.9092880296631185

     Math.sin(2)
     //> res1: Double = 0.9092974268256817

     sin(Math.PI)
     //> res2: Double = -9.724044563785839E-6

     Math.sin(Math.PI)
     //> res3: Double = 1.2246467991473532E-16

     sin(Math.PI / 2)
     //> res4: Double = 0.999999999940162

     Math.sin(Math.PI / 2)
     //> res5: Double = 1.0

So as you can see, we have a pretty decent approximation to the sine function here.