11170 - Cos(NA)

[krijger]

I used cos(a+b)=cos(a)*cos(b)-sin(a)*sin(b) to write cos(NA) in terms of cos((N-1)A), cos(A), sin((N-1)A) and sin(A). Then I expanded the sin((N-1)A) using sin(a+b)=sin(a)*cos(b)+cos(A)+sin(b) into terms of sin((N-2)A), sin(A), cos((N-2)A) and cos(A). Then there appears a term sin^2(A)*X which can be rewritten as (1-cos^2(A))*X and then there is still one sin-term remaining (of type sin((N-2)A). This one can be eliminated by writing cos((N-1)A) in terms of cos((N-2)A), cos(A), sin((N-2)A) and sin(A), solving for sin((N-2)A) and substituting into the previous formula. After that, if you work out the details all other sin-terms will vanish, and you'll be left with an expression in cos((N-1)A), cos((N-2)A) and cos(A).

[mf]

I've observed that sin(na) can be always represented as sin(na) = Q(cos a) sin a, for some polynomial Q(x),
and used this fact with formulas for sin(a+b) and cos(a+b) to find for each n polynomials P_n(x) and Q_n(x) such that cos(na) = P_n(cos a), sin(na) = Q_n(cos a) sin a.

[snar]

During the real time contest, I tried this approach:
1] cos(mx) = cos(m/2x + m/2x) =cos^2(m/2x)-sin^2(m/2x)->for even m
sin^2(nx) = 1 - cos^2(nx).

So for even m, I could eliminate sin(). But for odd values of m, I couldn't get rid of sin(). After opening my A'Level Pure Maths book and a bit of googling, I found that cos(nx) can be expressed in terms of cos(n-1) and cos(n-2).

How did you guys do it?

This formula also can solve the probem, the difference is this one doesn't use previous solutions. However, this is much slower.

cos(NA)=Re exp(iNA)=Re exp(iA)^N=Re (cos(A)+i*sin(A))^N

Then I use Newton's Binomial to calculate Re (cos(A)+i*sin(A))^N, by taking only even powers.

Best regards

[Erik]

Hi,

it is also possible to express sin((N-1)A) as derivation of cos((N-1)A). This introduces another sin(A) when derivating the polynomial in cos(A) for cos((N-1)A).
Thus the sin(A)^2 begomes (1-cos(A)^2). This way only the last polynomial is needed.

Cu, Erik

[sclo]

Here's one more way:
cos(a+b) = cos(a)cos(b) - sin(a)sin(b)
cos(a-b) = cos(a)cos(b) + sin(a)sin(b)

so cos(a+b)+cos(a-b) = 2 cos(a)cos(b).
Now let a = (N-1)A, b = A, and you get the formula
cos(NA) = 2cos((N-1)A) * cos(A) - cos((N-2)A) and it is clear that cos(NA) is a polynomial of degree N in cos(A).

[yiuyuho]

Here's one more way:
cos(a+b) = cos(a)cos(b) - sin(a)sin(b)
cos(a-b) = cos(a)cos(b) + sin(a)sin(b)

so cos(a+b)+cos(a-b) = 2 cos(a)cos(b).
Now let a = (N-1)A, b = A, and you get the formula
cos(NA) = 2cos((N-1)A) * cos(A) - cos((N-2)A) and it is clear that cos(NA) is a polynomial of degree N in cos(A).

That is an excellent method, simple yet to the point!

Thanks for posting!

[yiuyuho]

I replaced llabs() with a handmade function and got your code accepted, ....

So the abs(long long) doesn't work on UVa? That's really weird! I've used it for other problems but for this one I had to hand make abs or I get WA. I guess I was just lucky in all my previous problems.......

[wallace]

how to calculate the coefficient of Chebyshev???