Saturday, September 12, 2009

Integration for Programmers

Calculus can be very useful for improving the performance of a function. Here, I’ll demonstrate how integration works using Visual Basic code instead of the Greek used in math class. I chose VB since many people can open Excel, Word or others and try it out for themselves. I have instructions for that as well.

You can watch the real work in a companion video on YouTube.
http://www.youtube.com/watch?v=xXxXxXxXxXx

Background
In calculus 101, you learn integration and differentiation for solving things like acceleration, area and volume. If programmers don’t know the formula for something like that, they know how to get a pretty good answer by writing a loop. If that’s not accurate enough, just loop a lot more. But at some point, such looping becomes exceedingly inefficient. Now just imagine what that was like for Newton when he was trying to predict some future location of a planet. He needed a better method. He and Leibniz separately formalized the rules of Calculus in the 1670s. And it’s the notations of Leibniz that are in use today.

Example
Let’s use a really simple example of the area under a line where the line is defined as the function y = x. This is a diagonal line. The area under it looks like a right triangle that is half of a square. So the formula is:

Area of half a square = x2/2


Now let’s say that we want the area under x between 1 and 3. You don’t need a computer or calculus to figure that out. It’s 4. The formula for that is:

Area = 32/2 – 12/2 = 4

We need a more general formula that can handle any interval like a and b.

Area = b2/2 – a2/2

Let’s pretend we don’t know all that but we do know the formula for summing integers up to N.

1+2+3+...+N = (N2+N)/2

This works great for integers but we don’t know how to use this for areas. So instead we write a loop that cuts the area up into 20 thin slices. Each slice is 1/10 wide by x high. We can calculate the area of each slice and add them together.

.1+.11+.12+...+.28+.29+.3 = 4.2

That’s a little off. So we could try carving it up into 200 slices.

.01+.011+.012+...+.028+.029+.03 = 4.02

Replacement
That’s better but still not exact. Y = X is an overly simple example. But for harder formulas, that’s just how they did it before calculus. Today, mathematicians call this a Riemann Sum. The idea is to keep carving it up into thinner and thinner slices. The problem is you can’t quite go all the way to infinitely thin. Instead the idea is to get the problem down to some fundamental loop that you can replace. In our case, we want to replace:

For i = 1 to N
A = A + i
Next

with

A = (N2+N)/2


Getting Rid of N
You can see just how that’s done in the video. After that, you’re left with all these Ns in the formula. You’ll see that there are ways of getting rid of those too. Hopefully, cancellation gets rid of most of them. For the rest, it helps to imagine those thin slices again. Lots of thin slices means N gets really big. If N is only on the bottom of a fraction, as N approaches infinity, that fraction gets really small. At that point, it’s safe to remove that fraction from the formula and you’re done.

Coding
Here’s the code you’ll start with. To try it, open Microsoft Word or Excel and press Alt + F11. That opens the Visual Basic editor. In the editor, double-click “ThisDocument” or “ThisWorkbook”. Paste in this code and click Run. A box pops up with the answer: 4.0002. That answer’s pretty close since the code loops 10,000 times. This code also works in a VBS file if you’re any good with that.

Sub FunctionVersion01()
a = 1 ' Start of interval
b = 3 ' End of interval
N = 10000 ' Number of slices
DeltaX = (b - a) / N ' Slice width
For i = 1 To N
x = a + i * DeltaX
y = x ' <---------------- Formula! (Slice height)
SliceArea = y * DeltaX
Area = Area + SliceArea
Next
MsgBox Area
End Sub


More Integration
If you think you’ve got it, try the same thing with the formula y = x2. Depending on your loop, you may need some other summation formula with which to replace it. And in most cases, you won’t have to go through this at all. You can just replace the whole thing with the integral.


Indefinite Integrals
Sequential Integer Sums
∫ x dx = x2/2
n
∑ i = (n2+n)/2
i=1
∫ x2 dx = x3/3
n
∑ i2 = (2n3+3n2+n)/6
i=1
∫ x3 dx = x4/4
n
∑ i3 = ((n2+n)/2)2
i=1
∫ 1/x dx = ln(x)

∫ cos(x) dx = sin(x)

∫ ex dx = ex


References
http://en.wikipedia.org/wiki/Summation
http://en.wikipedia.org/wiki/Riemann_sum
http://en.wikipedia.org/wiki/Riemann_integral
http://en.wikipedia.org/wiki/Integral
http://www.youtube.com/watch?v=gFpHHTxsDkI

Wednesday, February 06, 2008

Special Relativity

Special Relativity was discovered by Einstein and published in 1905, his miracle year. That year, he published 4 papers, each one a breakthrough. He got a Nobel Prize for one but it wasn't on special relativity. Still, Special Relativity is what started his fame. It's different from General Relativity, which he came up with 10 years later. General Relativity accounts for gravity and acceleration where Special Relativity leaves them out.

Special Relativity sprang from the strange fact that the speed of light doesn't change no matter how fast you're going. That took a while to figure out since light goes a billion feet per second. But, in 1887, some guys figured out a way to measure slight changes. They used interference patterns. (Michelson–Morley) And guess what happened? Nothing. The speed never changed.

It didn't make sense. It's as if we weren't moving. But we're flying around the sun at 70,000 MPH, that's 100 times the speed of sound. Then again the Earth is spinning and we don't feel a breeze. So they thought maybe we're dragging the light around with us just enough. They called it the Luminiferous Aether theory. (Gotta love it.) But it had plenty of its own issues.

Einstein thought let's just say the speed of light is constant and it's space and time that are squishy. This had all kinds of strange effects. For example, if you see 2 things happen at the same time, a traveler might see them happen at different times. As crazy as that sounds, Einstein just went with it. To demonstrate how that works, Einstein was famous for using thought experiments. A popular one is the light clock. Let's say you could get light to bounce between 2 mirrors a foot apart. And let's say you could see that light and count how many times it bounced. In a second it would bounce a billion times. Now if that clock flew past you at half the speed of light, it would move half a foot forward between each bounce. So the light has farther to travel. And since the speed of light is constant, it would take slightly longer to reach the other side. So it would bounce less often. In this diagram, I put a circle between each foot the light travels. For every 5 feet the the light travels, it only bounces 4 times.

So let's say your good buddy Ashley travels along with the light clock. Would she also see it bounce slower? No. To the traveler, the light still bounces between 2 mirrors a foot apart. So if it bounced any slower, then the speed of light is not constant. Instead, she sees it bounce a billion times a second just as if she and the light clock weren't moving at all. The only way that can work is if time moves slower for the traveler. That's called time dialation.

Relativity
I have some news for you. All of that was thought of before Einstein. (FitzGerald 1889, Lorentz 1892) So what did Einstein add to this? Those predicessors depended on the idea of something not moving. But what is stationary? Are we stationary? Or the Sun or the galaxy? Einstein added the classic idea of relativity. Relativity, as a principle, has been around a long time. (Galileo 1632) A simple example is juggling on a jet. The laws of physics stay the same whether you're flying at 700 MPH or sitting on the tarmac with the engines running. In fact, without looking out the window, it's hard to tell what the plane is doing. Maybe a scale or an altimeter would help but not if you fly really low.

If relativity applies to speeds approching the speed of light, then your friend Ashley can juggle just fine. And short of looking out the window, there's no test she can do to determine her speed. For example, if she shined a flashlight in the direction she's traveling, us Earth bound observers would see the light travel out the front of the ship at the speed of light. Since the traveler is traveling so fast, you might think she sees it leave at half the speed. But no. Because of time dialation, she sees it travel out at the speed of light too. So that experiment won't work.

Now here's where the relativity part comes in. There's no reason why the traveler can't decide that she's the one who's stationary and it's Earth that's flying past at half the speed of light. And who are we to argue. There's no experiment we can do to proove her wrong. For example, if she looks at the light clock sitting next to you here on Earth, she would see it running slowly. Just to be clear here, you see her clock running slowly and she sees your clock running slowly. How can that be?

http://casa.colorado.edu/~ajsh/sr/paradox.html

http://casa.colorado.edu/~ajsh/sr/centre.html

















Monday, January 22, 2007

What's so special about the Algerian War of Independence?

Bush says he's been reading a book given to him by Kissinger called "A Savage War of Peace". [news] It's about the Algerian war of independence in 1954-1962. The book is known for its counter-insurgency strategy. There's a movie as well called "The Battle of Algiers". Parallels have been drawn between Algeria and Iraq since early in the Iraq war.

I'm glad Bush is learning more about this kind of thing but there are some important points that detract from this. For one thing, the Algerian war didn't go well. The author asserts that torture was a major cause of this. The reasoning is that torture turns the people against you and the people are an important part of an insurgency. They provide shelter or at least look the other way.

Another problem is that Iraq is less and less an insurgency and more an more a civil war. You essentially have insurgents on both sides. And finally, insurgents have learned to overcome some problems. A WikiPedia page does a good job of explaining this:
http://en.wikipedia.org/wiki/Counter-insurgency#Tactics


Friday, January 12, 2007

The Life of a Well Traveled Ant

In another post called the Life of a Well Traveled Photon, I explain the expansion of the universe by using one photon as an example. Since then, I keep thinking about a version where the Earth is expanding. In the other post, the photon travels for 12 billion years. Considering the universe is 13.7 billion years old, that photon was travelling for most of that time. It came from a galaxy that was just 3 1/2 billion light years away. But by the time that photon reached us, the galaxy got 29 billion light years away. It just so happens that the second longest interstate in the US, I-80, is 2900 miles long. It runs from New York to San Francisco. I need to replace the photon with something real slow, like an ant. Some big ants go 1 MPH. So, with a little math, you might think the journey takes 4 months. But remember that at the beginning of the journey, I-80 is much shorter. It's only 360 miles long. That's 1/8 the real distance, which matches the redshift Z=7 used in the other post. Not to give the ending away, but the trip takes 1200 hours.

Click the image to see a full sized map. Or maybe you prefer a Google map.

So let's say the Earth is born right on new years. At that time, the Earth is just a dot. But it's expanding quickly. In the first hour, New York and San Francisco go from the same place to 2 miles apart. And the Earth becomes 18 miles around (radius=3mi). Our ant doesn't begin it's journey until 2am January 8, when the Earth is 1 week and 2 hours old. At that time, New York is 360 miles away. In half a day, the ant passes through Sacramento, which is pretty good considering it would normally take 3 or 4 days at 1 MPH. The problem is New York has gotten an additional 25 miles away. At this rate, our ant will never get there. Still, it reached Reno in another day and Salt Lake City by January 13th. By now, our ant has been on the road for 120 hours. And by now, we notice something promising. I-80 has grown in length a steady rate of just over 2 MPH. But our ant has crossed a 1/4 of that road. So the road in front of it is expanding a little slower. Over the past hour, it grew by only 1 1/2 miles. Still, New York has reached 450 miles away and it's still getting farther.

Nine days later, it's January 22nd and the ant has reached Lincoln, Nebraska. That's more than half way. As depressing as it my be to hear that New York is now 507 miles away, our little ant has crossed an important mile stone. New York is finally getting closer. Even though I-80 continues to expand at over 2 MPH, the part in front of it is expanding at less than 1 MPH. So now we know the ant will get to New York. The only problem is the second half will take a lot longer, 5 more weeks. That's more than twice as long as the first half.

Tuesday, December 12, 2006

Hubble Radius Misconseptions

The Hubble Radius is one of those things about the standard cosmology that's commonly missunderstood. The distance keeps growing. So pages like the following are incorrect.

The Universe Adventure - Hubble Distance
(If that doesn't work, try this.)

The Hubble Radius
You might read that the Hubble Radius is what we can see, like it's another way of saying the visible universe. But that's not right. The Hubble Radius is the distance at which the expansion of the universe adds up to the speed of light. An important part of the standard cosmology is: the farther galaxies are away from us the faster they move away from us. It's not acurite but it's pretty consistant on average. A galaxy twice as far moves away twice as fast. So if you go really far, far enough, galaxies must move away at the speed of light. That distance is the Hubble Radius. It surounds us like a bubble. Anything outside of it moves away even faster than the speed of light. To be clear, cosmologists don't like to say "move" since that implies those things are actually moving through their space. And nothing can go faster than light. It's really the space between us is expanding. So instead, they say "recede". So at some point, galaxies must reciede away from us at the speed of light.

The Expanding Radius
The interesting part about the Hubble Radius is that the light beyond that distance can't get closer to us. The space between us is expanding too fast for the light to get any closer. You might think it reasonable to conclude that we can't see anything beyond that hoizon. And this is where the trouble starts. If the radius stayed the same size, that would be true. But it's expanding with the universe. It use to be a lot smaller back when the universe expanded faster. The size of the radius is closely tied the the age of the universe. The radius now is about 14 billion light years. That's close to the age of the universe. And when the universe was younger, the radius was smaller.

Seeing Beyond the Radius
We can see galaxies that are outside the the Hubble Radius and have always been outside. Few galaxies cross from inside to outside the radius (or vice-versa). Any galaxy with a redshift Z of 2 or more is outside the radius and has been outside since the light we see left that galaxy.

Tuesday, December 05, 2006

The Life of a Well Traveled Photon

The farthest object ever discovered is nearly 13 billion light years away. That's not the distance it is now and it's not the distance it was then. It's just the time it took the light to reach us. Astrophysicists call that the Light Travel Time distance. That distance isn't very informative and it's hard to explain why. Truth is they give us the Light Travel Time to avoid any obvious confusion. It's kind of an editorial policy. For example, if I told you that the object is actually 29 billion light years away right now, you might think that's impossible since it would have to go faster than twice the speed of light to get that far away. After all, the universe is only 13.7 billion years old.

Understanding such astronomical distances is an important part of understanding the expansion of the universe and the standard cosmology (Big Bang or Lambda-CDM). Most people, while learning about the expansion, bump into a couple popular analogies used to explain the theory. One involves a balloon and the other, raisin bread. Both models have their flaws. For me, it helps to add a third. I like to imagine one of those photons traveling all that way.

I can't keep myself from making a point about "Faster-Than-Light". Special Relativity and General Relativity are 2 different things. Special Relativity says the speed of light is the limit. But General Relativity says sufficiently distant objects have sufficiently different frames of reference. [Wikipedia] They do not contradict each other. They work together. So don't let Special Relativity keep you from accepting that distant objects can recede from us faster than light.

Let's go over what we know. Really, all we know is the redshift of the object. It's somewhere between 6.6 and 7.1. So let's just say 7. The redshift tells us how much the light has stretched since it started its journey. [wikipedia] From that, we know how much the space between us has expanded. It's now 8 times bigger than when the photon began its journey. (1 + redshift = 8) From the standard cosmology and the theory of General Relativity, we can figure out more. You can even do your own calculations with Ned Wright's Cosmology Calculator. Dr. Wright takes a lot into account that I am no good at. So I use a simpler model. That's cheating, I know, but it's not so bad. The biggest difference is that our photon starts out 12 billion years ago instead of 13. The rest is very much the same. The object is now 29 billion light years away. We see it as it was when it was 3.6 billion light years away. That's 1/8 the distance and fits the redshift. The object has been and still is receding away from us at just over twice the speed of light.

It's reasonable to assume the source object is a galaxy but we can't see it so well. It's very faint, which means the light we see contains few photons. Still enough reach the telescope's spectrometer to make a nice spectrum. Some of those photons started their trip on the ultraviolet or black light side of the visible spectrum, a nice deep purple with a wavelength of 400 nanometers. But by the time those photons reach us, their wavelength has stretched by 8 times to 3200 nanometers (1/20 the width of a human hair) pushing them through the visible spectrum and far into the infrared. Compared to sound, that's 3 octaves. That's like going from middle C to the deepest note on a piano. Visible light doesn't even cover one octave.

Our photon began it's journey by leaving the source object at the speed of light. But, because of the expansion of the universe, the source object is receding away from us at over twice the speed of light. So even though the photon is heading right toward us, it's still moving away faster than the speed of light. On its first birthday, that photon has traveled a light year, which is about 6 trillion miles. Yet it is slightly more than a light year away from the source. That's because the space behind it has expanded by about 200 miles. It's a tiny addition but it's something. Here, I'm assuming the expansion is applied evenly everywhere. But astrophysicists don't think that's the case so close to a galaxy. So forget what I just said.


Three billion years is when our photon gets the farthest away from us. It reaches 5 billion light years away. That's a billion and a half farther than when it started. Plus, it's showing its age. It started off a nice deep purple. But by this time, it's gone through the visible spectrum and well into the infrared.

Three billion years is also when things start to change for our photon. Although it's farther than it has ever been, it's just as far from the source object. That object is now 10 billion light years away from us. Even though 3 billion years have passed, expansion has added to the distance. Plus, by this time, the expansion of the universe has slowed considerably. It expands 1/3 as fast as when the photon began its journey. In fact, it has slowed enough that the space between us and the photon expands at just the speed of light. That means our photon won't get any farther away. For the rest of the trip, it just gets closer.

After an additional 5 billion years, it has reclaimed all the distance it lost and then some. It may be getting a little long in the tooth (and the wavelength) but the expansion isn't enough to keep it from moving toward us at nearly the speed of light. It travels the remaining 3.4 billion light years in 4 billion years. You can see all that in this Space-Time diagram.

This is called a Space-Time diagram but I think it should be called a Distance-Time diagram. Although the photon is shown as a curved line, the photon does not turn. It started off heading straight toward us and kept that heading even when it was getting farther away. The part I should explain is the Hubble Radius Cone. The Hubble Radius is the distance at which the expansion adds up to the speed of light. It surrounds us like a bubble at about 13.7 billion light years away. But when the universe was younger, the bubble was smaller. So in this diagram, it ends up looking like a cone. The bigger the bubble, the slower the expansion. Notice that the cone crosses our photon's path just when it began getting closer.

So now you know that some of the light we see may have taken a strange path and gotten farther away from us before heading toward us.

Monday, December 04, 2006

Iraq War Adds 40% to Deficit

As of November 2006, $350 billion has been spent on the 3.5 year long Iraq war. That’s $100 billion a year. That means the Iraq war has added 40% to the deficit over the same period of time (May 03 through October 06) from $840 billion to $1190 billion. That $350 billion accounts for 73% of the budget approved by congress for the “war on terror”. The rest is for Afghanistan, domestic and some other war related stuff. This does not include a $127 billion request that has not yet gone through congress. All these numbers come from the Congressional Budget Office. The deficit numbers come the Historical Budget Data PDF link right on the home page. I estimate the 2006 deficit to be $250 billion.

http://news.yahoo.com/s/afp/usiraqpoliticsreport
http://cbo.gov/budget/historical.pdf (PDF)