Ideas for Math/Computer Project

[recon]

Hi guys, I'm in need of a topic to do for my math project. What's difficult about the project is that I need to demonstrate the power of mathematics through using the computer. I have no access to supercomputers, so any ideas that would involve a normal home computer would be great. I need to do the project at a high school level, but would be willing to do any project requiring higher skills if it is feasible. Alas, I have no programming skills, and I only have a rudimentary idea of C++ and BASIC from a few years back! If it helps, I do have the mathematica software.

The project is due in 1 month, but I need to inform the teacher of what my topic is going to be about 2 weeks from now.

Thanks in advance!


Edit: My math teacher suggested devising teaching aids, but it sounds dull as hell to me. Perhaps some of you may be able to come up with some fresh ideas. I tried but I can't.

 

[Damned charming :)]

Can you tell the exact question and the level of maths you are at.


you can use microsoft excel to show that
$$\frac{d^2x}{dt^2} =- kx$$
like in the case of a springs
leads to simple harmonic motion.

you can use some logic and the identity
$$\cos(\frac{\theta}{2}) = \sqrt{ \frac{ \cos ( \theta)+1}{2}}$$
to calculate pi using excel.

 

[recon]

Thanks for your reply Damned Charming:) !

I am now in what would be equivalent of the American 10th Grade. I do well in mathematics at school, and am picking up calculus and trigonometry pretty quickly. However, I do not understand the significance of the equations you have written yet. I have a book about logic that is very interesting, but I gave up reading it as I did not have the time. I would be very much interested in looking into your suggestion, so could you please elaborate? Thank you once again.

 

[Damned charming :)]

1) Are you aware of the rate of change of displacement is velocity?
i.e. v = dx/dt
2) Are you aware of the rate of change of velocity is accelation?
i.e a = dv/dt = d^2x/dt^2
3) Are you aware that force is proportional to accelatrion?
4) Are you aware that the force that a spring exerts is proportional to how much you pull.
5) Can you combine these facts to give that if x is the displacemnt on a weight on a spring then

$$\frac{d^2 x}{ dt^2} = -kx$$





After a 2 pages of work you can show that after two pages of work you can show that $$x=A\sin( \sqrt{k} t)$$ however using excel you can quickly get a nice looking sin curve by getting it to take many tiny intervals of time and estimate things using equations 1 to 5.

 

[Chen]

Actually it's:

$$\Sigma F = m\vec a = -k\vec x$$

That gives:

$$\vec a = \frac{d^2\vec x}{dt^2} = -\frac{k}{m}\vec x$$

Which results in:

$$\vec x = A\cos(\omega t)$$

When:

$$\omega = \sqrt\frac{k}{m}$$

 

[Damned charming :)]

@recon Chens comment and my reply to him will have no direct connection to your problem and you can ignore them if you don't follow them.

@Chen
that is indeed what is in a physics textbook, but my treatment is still correct if you treat k as a constant of proportionality. I don't think the thread author is sitting a physics exam anytime soon.

and bye the bye the complete solution is actually
$$x =a cos ( \omega t) + bcos( \omega t) =A sin (\omega t + \phi)$$ where $$\phi$$ is the phase shift.
A phase shift is clearly necessary because the equation

$$x = A cos ( \omega t)$$ then x must be A when t=0.

 

[Chen]

Originally posted by Damned charming :)
A phase shift is clearly necessary because the equation

$$x = A cos ( \omega t)$$ then x must be A when t=0.

Not if you assume that the weight started its movement in one of the amplitudes of its motion, which is how it would work if you were to conduct this experiment in the lab. Whether the system was laid out horizontally or vertically, you would need to give the weight an inital (potential) energy and the best simple way to do that would be to pull the spring, thereby causing the weight to be at the amplitude at $$t = 0$$.

And by the way, Recon, if you need to prove that these formulas are correct as part of the project, just making the graph in Excel is not enough. :)

 

[recon]

Originally posted by Damned charming :)
1) Are you aware of the rate of change of displacement is velocity?
i.e. v = dx/dt

Yes, very throughly.

[2) Are you aware of the rate of change of velocity is accelation?
i.e a = dv/dt = d^2x/dt^2
3) Are you aware that force is proportional to accelatrion?
4) Are you aware that the force that a spring exerts is proportional to how much you pull.
5) Can you combine these facts to give that if x is the displacemnt on a weight on a spring then

$$\frac{d^2 x}{ dt^2} = -kx$$

Actually, yes to all. I see what you mean now.

After a 2 pages of work you can show that after two pages of work you can show that $$x=A\sin( \sqrt{k} t)$$ however using excel you can quickly get a nice looking sin curve by getting it to take many tiny intervals of time and estimate things using equations 1 to 5.

But, here's where you lose me.

 

[recon]

Originally posted by Damned charming :)

you can use some logic and the identity
$$\cos(\frac{\theta}{2}) = \sqrt{ \frac{ \cos ( \theta)+1}{2}}$$
to calculate pi using excel.

Damned charming :), I am really ingratiated to all you've come up with up to this point. But right now, I am really sifting through all the potential topics for my project. I would be glad if you could tell me more about the logic and identity idea above. Is there a webpage you could refer me to for that harmonic motion thingy or for anything else? It sounds exciting and I would love to know more about it.

To Chen and anyone else, keep those ideas coming please. Thanks!

 

[recon]

Originally posted by Chen

And by the way, Recon, if you need to prove that these formulas are correct as part of the project, just making the graph in Excel is not enough. :)

Please explain. What could I do to rectify the situation?

 

[Damned charming :)]

O.K. An actual school teacher liked this example and yours might as well.

For estimating pi you could use a hexagon and find the area. It would be more accurate to use an octogon, and a 100 sided polygon would even be more accurate. To calcuate the area of a polygon you can calculate the area of a triangles (6 in a hexagon, 8 in a octogon etc)
you can use the formula area = 1/2*a*b*sinC = 1/2r^2 sin C. If you want accurate measurements for pi you need to get sin of a small angle. Now if you can find cos of small angles that is easily manipulated to give sin of a small angle. And the identy I mentioned
give
$$cos(15) = \sqrt{ \frac{ cos(30) + 1 }{2}$$
once you have cos(15) you can find cos(7.5) with

$$cos(7.5) = \sqrt{ \frac{ cos(15) + 1 }{2}$$

then you could find cos(3.75) etc etc, you can automate the process and get a very good approximation of pi.







OK I have done the excel file for my calculus question and
I can email it to you if you pm me you email address. (I cannot attach it). As chen points out it is not a proof but it is crude example of numerical integration which is something engineers actually use.
I suppose Chen will point out the following information which is not useful to you. My guess is Chen would want to say " you should you numerically integrate something that you can solve directly, and you should use the Runge Kutta method".

 

[Chen]

Originally posted by recon
Please explain. What could I do to rectify the situation?

You would have to develop the equations and show that the harmonic motion indeed adheres to the formula of $$\vec x$$ that Charming posted.

One of the ways to do that is by comparing the simple harmonic motion to the uniform circular motion:
http://www.physics.gatech.edu/academics/tutorial/phys2121/Java Applets/ntnujava/shm/shm.html
But this doesn't have much to do with computers.

Why don't you try to prove that every map can be colored with just 4 colors? ;)
http://www.cs.uidaho.edu/~casey931/mega-math/gloss/math/4ct.html

 

[Damned charming :)]

@recon
I have sent you an excel file where you use the computer to numerically integrate
$$\frac{d^2x}{dt^2} = -x$$ and you get an x= cos(t) curve.

I like it because computers can't calculate something
like cos(0.92) ( get calculator in rad mode) directly they have to use multiplication and division. My method shows that gets cos(0.92) correct to 3 decimal places and only uses multiplication and addition and can clearly be made more accurate to produce a higly accurate x=cos(t) curve.

It works by assuming x is initially 1, v is 0 (the spring is fully stretched), and acceleration is -1. After 0.001 of a second
new value of x $$\approx$$ oldvalue of x + 0.001 old value of v

new value of v $$\approx$$ old value of v + 0.001 old value of a


new value of a = -new value of x

you start with the original value, use this to get the second value
use the second value to get the third value the third value to get the fourth etc.


Now why the teacher may like because it draws a cos curve only by
using addition and multiplication and you can also go to physics site
and copy and paste the formal proof. You can point out that the computer does many calculations whereas and the formal proof predicts these calculations.

 

[recon]

Originally posted by Damned charming :)

Now why the teacher may like because it draws a cos curve only by
using addition and multiplication and you can also go to physics site
and copy and paste the formal proof. You can point out that the computer does many calculations whereas and the formal proof predicts these calculations.

Thanks for the excel file. I am not an expert of Excel, so I don't know how you generated so many lines. They weren't typed out individually, were they? Also, what physics site are you referring me to above?

 

[Damned charming :)]

In excel you can highlight a pattern, then click on the bottom right
corner of the screen then drag things down and it will continue the pattern. For example you could open excel and type in 2,4,6 in the cells (rectangles) A1,A2,A3. Then you could highlight cells A1,A2,A3
and click and hold the little black square on the bottom corner of cell A3. You must keep holding the mouse button down you can select cells A1,A2,A3,...,A10. If you let the mouse button go cells A1,A2,..A10 will contain the information 2,4,6,8,...,20.
This is fairly common knowledge so if you know anyone good with computers they should be able to help you. You can of course search the web for introduction to excel.
http://www.unt.edu/training/Office2000/Excel2000.pdf seemed ok.




I page that formaly proves that x = cos(t) when k/m = 1 would be
http://www.upei.ca/~physics/polson/course/P112/notes/ch13/ch13.pdf
If you don't like it google search " simple harmonic motion proof" from a different page.

 

[recon]

Originally posted by Damned charming :)
@recon
It works by assuming x is initially 1, v is 0 (the spring is fully stretched), and acceleration is -1. After 0.001 of a second
new value of x $$\approx$$ oldvalue of x + 0.001 old value of v

new value of v $$\approx$$ old value of v + 0.001 old value of a


new value of a = -new value of x

you start with the original value, use this to get the second value
use the second value to get the third value the third value to get the fourth etc.

No, this is the part where I don't understand. I did a google search of generating the cos curve using multiplication and substraction only and found nothing. I want to know a proof or explanation for it.

 

[NateTG]

I think a good project might be to do something involving computational complexity. It's one of a few situations where computers and mathematics typically intersect, but you really want to be aware of Taylor/McLaurin series first.

In a more general sense, computers are excellent numerical tools, but not really that great for mathematics, and it's difficult to understand what "demonstrate the power of mathematics" means.

P.S.

The usual modern method for calculating $$\cos(x)$$ ,where $$x$$ is in radians, is to use the Taylor series:
$$\cos(x)=\sum_{i=0}^\infty\frac{(-1)^ix^{2i}}{(2i)!}$$
with the undstanding that $$0^0$$ is one in this case

 

[recon]

Thanks for your reply NateTG. But it seems to me that the Taylor Series goes on forever without converging (is that the word?) for most values of x. It feels very inconvenient but is that what Damned Charming :) meant when he said 'multiplication and addition only'?

 

[Chen]

Originally posted by recon
Looks like the Taylor Series goes on forever without converging (is that the word?) for most values of x. It feels very inconvenient.

Actually, it does converge. Since X can only be between 0 and 2PI, 2i! grows larger much faster than X^2i, so at some point the series does converge.

 

[matt grime]

The power series converges for all x, and very quickly too.

 

[matt grime]

Originally posted by Chen
Actually, it does converge. Since X can only be between 0 and 2PI, 2i! grows larger much faster than X^2i, so at some point the series does converge.

Why must x only lie between 0 and 2pi? What do you mean by 'at some point ... does converge'? Is the point x, or, do you mean, after some number of terms in the summation it 'suddenly' converges? Neither is accurate: it converges for all points x, meaning given any e>0, there is an N such that the absolute value of the difference between any of the partial sums of p and q terms, for p and q larger than N is at most e.

 

[recon]

Originally posted by NateTG
I think a good project might be to do something involving computational complexity. It's one of a few situations where computers and mathematics typically intersect, but you really want to be aware of Taylor/McLaurin series first.

I just did a bit of googling, and computational complexity seems to involve quite a bit of computing skills which, if you've read my thread-opener, I don't have that much of. What I found interesting about computational complexity is that it is used in analysing Games and Puzzles by analysing the efficiency of algorithms. Are there simple situations where computational complexity can be demonstrated.

 

[NateTG]

Originally posted by recon
I just did a bit of googling, and computational complexity seems to involve quite a bit of computing skills which, if you've read my thread-opener, I don't have that much of. What I found interesting about computational complexity is that it is used in analysing Games and Puzzles by analysing the efficiency of algorithms. Are there simple situations where computational complexity can be demonstrated.

Understanding what computational complexity is does not require much computer sophistication.

A classic example of computational complexity is generation of Finonacci (not sure of spelling) numbers:

Fibonacci numbers are defined as follows:
$$F_0=1$$
$$F_1=1$$
$$F_n=F_{n-1}+F_{n-2}$$

This leads to a naive implementation of the fibbonacci number function:

int fib(int n) {
   if(n<0) {
      fprintf(STDERR,"Unexpected argument to fib\n");
      exit 1;
   }
   if(n<2) {
      return 1;
   }
   return (fib(n-1)+fib(n-2);
}

This is a relatively 'slow' way to generate Fibonacci number, since it generates the n'th Fibonacci number in O(2^n) steps.

A better way to do this is:

int fib(int n) {
   int i=0,j=0,k=1,l=0;
   for(i=0;i<n;i++) {
      l=j+k;
      j=k;
      k=l;
   }
   return k;
}

Which generates the n'th fibonacci number in O(n) steps.

Of course, if you're sophisticated, you can do even better:

int fib(int n) {
   return ( (1.6180339)^n-(-0.6180339)^n)/(2.236067977))
}

or something similar using Binet's formula. For small n, this takes constant time (actually O(log n) or so).

For a wider spectrum of performance, you can use different methods for generating the digits of π

 

[Damned charming :)]

@recon
I will explain a crucial part about my excel program, if you understand it go and show your teacher the program and discuss it.

We can be a bit inaccurate and say. Don't worry the
errors will only occur in the third decimal place.
$$a \approx \frac{ \delta v}{ \delta t} = -x$$

rearranging gives$$\delta v = -x \delta t$$
This is saying the small change in v after a small change in time
is equal to -x * change in time.

So velocity after t+ 0.001 seconds $$\approx$$ velocity
at t seconds -x* 0.001.

so if we know a,x and v at time 0 , we can use thes to get a good estimate of a,x, and v at time 0.001. We can then use the estimates at time 0.001 to estimate the values at time 0.002, and so on and so forth. This is a very very crude form of a useful topic called numerical integration, but it gives you the basic idea that if you know a particles acceration and initial condition you can use a computer to predict were it goes. Obviously our simple example can be done by many other methods but if acceleration is a very difficult function of x and v then our numerical method shows you roughly how an actual computer would predict how the particle moves over time.

 

[recon]

Sorry, I'm just reposting it and recorrecting your [/tex] because I don't understand Latex yet and consequently can't visualise the formula in its [edit: raw] Latex form.

@recon
I will explain a crucial part about my excel program, if you understand it go and show your teacher the program and discuss it.

We can be a bit inaccurate and say. Don't worry the
errors will only occur in the third decimal place.
$$a \approx \frac{ \delta v}{ \delta t} = -x$$

rearranging gives$$\delta v = -x \delta t$$
This is saying the small change in v after a small change in time
is equal to -x * change in time.

So velocity after t+ 0.001 seconds $$approx$$ velocity
at t seconds -x* 0.001.

so if we know a,x and v at time 0 , we can use thes to get a good estimate of a,x, and v at time 0.001. We can then use the estimates at time 0.001 to estimate the values at time 0.002, and so on and so forth. This is a very very crude form of a useful topic called numerical integration, but it gives you the basic idea that if you know a particles acceration and initial condition you can use a computer to predict were it goes. Obviously our simple example can be done by many other methods but if acceleration is a very difficult function of x and v then our numerical method shows you roughly how an actual computer would predict how the particle moves over time.

 

[Damned charming :)]

I made a typo and edited it but something went wrong, the
[tex [\tex] is not supposed to appear. I will fix that post. You
figured it out anyway, note the the approx was supposed
to be the approximately equal to sign $$\approx$$.

 

[recon]

Excel does have a cosine function, and I generate the same graph as you (at least on a large scale)using that. As you say, computers calculate cos(x) indirectly, so how does Microsoft Excel go about doing that? Is it more accurate than our way of doing it? Does it use methods like the ones you said Chen would suggest using earlier, i.e. Range-Kutta? Is that how calculators generate cos(x) as well?

 

[recon]

Originally posted by Damned charming :)
If you want accurate measurements for pi you need to get sin of a small angle. Now if you can find cos of small angles that is easily manipulated to give sin of a small angle. And the identy I mentioned
give
$$cos(15) = \sqrt{ \frac{ cos(30) + 1 }{2}$$
once you have cos(15) you can find cos(7.5) with

$$cos(7.5) = \sqrt{ \frac{ cos(15) + 1 }{2}$$

then you could find cos(3.75) etc etc, you can automate the process and get a very good approximation of pi.

I don't understand the appearance of both sin and cos above. Is it an error on your part or mine. Also, is there a link to the proof that as the x in cos(x) gets smaller, the approximation of pi gets better.

 

[Chen]

Originally posted by recon
I don't understand the appearance of both sin and cos above. Is it an error on your part or mine. Also, is there a link to the proof that as the x in cos(x) gets smaller, the approximation of pi gets better.

I happen to really like Damned's idea of finding Pi like this, so I'll explain it in more detail...

A circle can be visualized as a polygon with infinite sides of equal length. That polygon is made of infinitely many isosceles triangles, who are all the same - an angle $$\theta$$ confined between two legs whose length is R. The area of the circle is the same as the sum of all areas of the triangles, right? So:

$$\pi R^2 = N\frac{1}{2}R^2\sin \theta$$

$$\pi = N\frac{1}{2}\sin \theta$$

The idea is to find the sin of a very small angle, and use it in the equation above to find the value of pi.

N is of course the number of triangles you have in your polygon, and it's given by $$2\pi / \theta$$ ($$\theta$$ should be in radians). But you can't use this, because it assumes you already know the value of pi. So what you need to do is start with an inital angle of 30 degrees (pi/6) and count the number of times you reduce it by half. The inital N is 12, and every time you reduce the angle by half N is doubled.

This is where the identity:

$$\cos(\frac{\theta}{2}) = \sqrt{ \frac{ \cos ( \theta)+1}{2}}$$

Comes into play. You use it to find the cosine of a very very small angle, and from there you can find its sine as well ($$(\sin \alpha)^2 = 1 - (\cos \alpha)^2$$). Now that you have the sine of a very small angle, and you've kept track of N, you can calculate pi.

 

[NateTG]

Of course, there are many more algorthms available for calculating $$\pi$$.

The worst algorthim that I am aware of is one that relies on the fact that the probability that two large numbers have a common factor is $$\frac{6}{\pi^2}$$ and then tries to generate $$\pi$$ by testing radom large numbers:
http://www.cacr.caltech.edu/~roy/upi/

A more accessible, and similarly poor approach for generating $$\pi$$ is to determine what fraction of the points in $$[0,1] \timex [0,1]$$ are in the unit circle by survey methods, and then back-generate $$\pi$$. For two numbers $$x,y$$ chosen with a flat distribution on $$[0,1]$$ the probablity that $$x^2+y^2>1$$ is $$\frac{\pi^2}{4}$$, so you could take that approach to finding $$\pi$$.

 

[Damned charming :)]

Originally posted by recon
Excel does have a cosine function, and I generate the same graph as you (at least on a large scale)using that. As you say, computers calculate cos(x) indirectly, so how does Microsoft Excel go about doing that? Is it more accurate than our way of doing it? Does it use methods like the ones you said Chen would suggest using earlier, i.e. Range-Kutta? Is that how calculators generate cos(x) as well?

Runge-kutta is generally used if you want many points on a curve, and you when have the rate of change initialy but not many inital values on the curve.

To find a single value of cos(x) a calculator would use taylor series.
$$cos(x) = 1 -x^2/2 + x^4/(4*3*2*1) -x^6/(6*5*4*3*2*1)+...$$
The +... means that the series goes on for ever however it can be shown it is enough to use the first few terms. I suppose your project how many of these terms you need. I doubt it is more than 6 in old calculators because they produced an error when you tried to take the cos of 10^20.



The basic idea about how this formula was found is easy understand in laymans terms, a formal proof is obviously more tricky.


It is reasonable to assume that cos(x) is can be represented by a polynomial with infinitely many terms.

So
$$cos(x) = a + bx + cx^2 + dx^3+ ...$$

now how would you find a? well sub in x=0 and you get
$$cos(0) = a + b*0 + c*0^2+...$$
so a = cos(0)=1

to find b differentiate both sides of the polynomial to get
$$-sin(x) = b + 2x+ 3dx^2+...$$
sub in x=0 and get
b= -sin(0) = 0

You can continue to keep finding the coefficents and come up with
$$cos(x) = 1 -x^2/2 + x^4/(4*3*2*1) -x^6/(6*5*4*3*2*1)+...$$

 

[NateTG]

The error term in an alternating series that converges is always less that the last term - if you pair off the following terms, you can see that the total, if it exists, is smaller than the term that was added.

Another usefull thing to note about the Taylor series is that it represents a sequence of improving approximations - first a linear approximation, then a quadratic, cubic, etc..

Regarding calculators:
Considering the number of digits that $$\frac{(10^20)^4}{4!}$$ has, it's harldy surprising that you would get an overflow error. A naive taylor series method for generating the cosine would involve roughly 20 terms to start getting reasonable accuracies.

 

[Chen]

Originally posted by NateTG
... the probablity that $$x^2+y^2>1$$ is $$\frac{\pi^2}{4}$$, so you could take that approach to finding $$\pi$$.

Actually, the probability of that is $$\frac{4 - \pi}{4}$$. Similarly, the probability that $$x^2+y^2 \leq 1$$ is $$\frac{\pi}{4}$$.

 

[NateTG]

Originally posted by Chen
Actually, the probability of that is $$\frac{4 - \pi}{4}$$. Similarly, the probability that $$x^2+y^2 \leq 1$$ is $$\frac{\pi}{4}$$.

Right. One of these days I'll figure out this math thing ;)

 

[Chen]

I used the method to calculate $$\pi$$ on my computer today, the result was 3.1403104. About 0.04% off the real value of it, not so bad I guess considering I took only 5 million random points.