11170 - Cos(NA)

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Tue Feb 20, 2007 11:03 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Feb 20, 2007 2:12 pm

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
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

Re: what was ur approach??

Post by snar » Tue Feb 20, 2007 4:21 pm

sohel wrote: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
Narek Saribekyan

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik » Tue Feb 20, 2007 4:31 pm

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Feb 21, 2007 12:17 am

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
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sat Jun 09, 2007 6:27 am

sclo wrote: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
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sat Jun 09, 2007 7:53 am

little joey wrote: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
New poster
Posts: 10
Joined: Thu Feb 26, 2009 4:03 pm

Re: 11170 - Cos(NA)

Post by wallace » Thu Apr 09, 2009 5:27 pm

how to calculate the coefficient of Chebyshev???

Post Reply

Return to “Volume 111 (11100-11199)”