Andrew Que Sites list Photos
Projects Contact
Main

June 09, 2013

North-west trip day 8

Salish Sea looking toward Vancouver Island

Salish Sea looking toward Vancouver Island

  After the first and only night on my trip I didn't sleep in the trunk of my car, it was back to the road.  I decided I didn't have the patients to visit the aquarium—too much of a shift from all the things I had ready seen.  So I decided to go to the north-west coast—as far as possible.  I set out for Neah Bay, WA.  All my maps showed that I could make it to a point a little more north west than this, but upon arrival I found all the roads claimed their were dead ends.  After my lesson in Wyoming, I decided it was better to listen to the signs then try and see if they were wrong.  So I made it to 124.62521° W, and there is only about 2 miles of west left after that.
   I did get to see the Salish Sea and Puget Sound, both of which make their way to the Pacific Ocean.  I could also see Vancouver Island, although there was no travel to Canada this trip.
   Then it was time to meander down the coast.  Found my way back to Hwy 101 and started south, finally stopping in Aberdeen, Washington for the night.

June 08, 2013

North-west trip day 7

Columbia River

Columbia River

   A week on the road, it was time to work my way to Seattle.  I didn't have much planned after this point in the trip, so it was more or less stop at whatever looked interesting.
   I entered Washington state in the morning, and it wasn't at all what I had expected.  The eastern part of the state is dry and hot.  My first stop was near Vantage, Washington at a look out area that had a great view of the Columbia River and the Vantage Bridge.  After I crossed the river, I stopped at Ginkgo Petrified Forest State Park and walked the paths to see some petrified trees.  Unfortunately, they were all caged off, presumably to prevent vandalism.  It didn't make for good pictures but it was interesting to see.  I didn't walk for long.  The temperature was 90°F (32°C) and I don't function in heat like that.
   After a couple hours of driving, I was back in the mountains and the temperature was again becoming tolerable.  I reached Seattle and started south to Tacoma to visit some friends.  Lance and Tara took me to a good Indian restaurant, shared some good local beer and put me up for the night.

June 07, 2013

North-west trip day 6

   I visited the Montana Natural History Center in Missoula in the morning, and then started north.  I took a beautiful drive along the eastern show of Flathead Lake.  On the recommendation of a friend, I stopped at the House Of Mystery near Columbia Fall, Montana.  She was right about it being an interesting optical illusion, but I ended up quite motion sick afterward.  I went to find the Hungry Horse Dam, but ended up sleeping for an hour to fight off the motion sickness first. 
   The Hungry Horse Dam is by far the largest I have ever seen.  At 564 feet tall, it's massive and has a generating capacity of 428 megawatts.  That's a lot of clean power.  For comparison, the power plant on the east side of Madison is a 100 megawatt facility.
   I continued north and entered Glacier National Park by West Glacier.  I had never seen a glacier, and it was on the list of things to do.  I'm still not sure I saw one as the main road through the park was closed about halfway.  There was no reason given for the closure, but I assume rock fall or something of that nature.  Reguardless, the park was magnificent.  A large part of the park had burned in a fire in 2003, and remnants were visible in patches all over.  It is interesting to see how quickly life returns after an event like that.
   Just as I reached the turn around at Glacier Park, a thunderstorm rolled in.  It dropped very little rain and didn't last too long.  I didn't much feel like hiking anyway, so I didn't feel bad about it.  I returned the way I had come and started my way west.
   I wanted to stop near the eastern state line of Idaho, but couldn't find anything until I reached Post Fall near the western edge.  An other truck stop for the evening.

June 06, 2013

North-west trip day 5

Old Faithful

Old Faithful

   I woke up around 9:00 am refreshed and ready to go.  Sleeping in a volcano for the night was one of my better ideas and I decided after this point in the trip not to rush things.  As I was getting up, Old Faithful was erupting.  Being a predictable geyser, I knew I had around 90 minutes before it happened again.  So I walked the grounds looking at the springs, vents and other geysers.  Then it was time to see my first geyser eruption.  Within one minute of the predicted time, Old Faithful began an other display.  It is impressive to consider that between 4 and 8 thousand gallons of water had just been ejected at times 100 feet into the air.  The amount of energy needed for that single event is on the order of 1.9e8 joules (52.7 kilowatt hours)—enough power to run my computer wide open for 6 months.  That amount of energy, every 90 minutes for just one geyser of many on this unique geological hot-spot.  The engineer in me is very impressed.
   After playing with geysers and reading everything worthwhile in the visitor center, it was time to move on.  I took a slow drive through Yellowstone, often pulling over to lets others pass and to take pictures.  When I was finially out of the park, it was time to make my way north. 
   My next stop was Berkeley Pit in Butte, Montana.  It is both am engineering marvel and an ecological disaster.  Over a mile wide, the pit is slowly filling with highly acidic water full of dissolved heavy metals.  The water threatens to spill into the ground water supply, but the display at the visitor center talks very positive about efforts underway to take care of this issue.  Interesting lesson in just because we can (and did), should we?
   While in Butte, I decided to find a car wash.  Every time I leaned against my muddy car I get some on me.  I don't think I had ever washed any of my vehicles before this.  My next scheduled stops were in Missoula, MT, but I arrived too late to do either.  So I decided to pick up some camping gear and do laundry.  While I had a good supply of socks and boxers, I was low on shirts.  And my pants were muddy from my car.  I also picked up a foam pad to place my sleeping bag on, and a propane burner.  I thought I would make more use of the propane burner for cooking, but I only ended up using it that first night to cook some soup.  It did a good job, but I didn't feel like soup the remainder of the trip.
   I found an other truck stop for the evening in a place called Bonner, Montana.  They lady at the truck stop told me it was pronounced "bon-er" (bon like in bonfire).  That's probably how they said it, but I know a boner when I see one.  Clean laundry, soup for dinner, and a new sleeping pad, it was time for bed.

June 05, 2013

North-west trip day 4

Hot Springs State Park

Hot Springs State Park

   It had now been 4 days since I had bathed, and it was time to take advantage of trucker facilities.  Although a truck stop shower is rather overpriced it does get the job done.  Now it was time to take my newly mudded car to Thermopolis, WY.  My first stop was somewhere along Hwy 16 while crossing the Big Horn Mountains.  The reason: snow.  It was 37°F (2.8°C), and the altitude was over 9,000 feet.  For me, it is a real treat to see snow in June. 
  My next stop was the Wyoming Dinosaur Museum in Thermopolis, WY  While the building just looks like a metal shed in randomly sitting on the edge of town, it is by far the best dinosaur exhibit I have ever seen.  It ran chronologically starting just before the Cambrian Explosion and worked it's way to modern mammals.  The layout and information was fantastic and I must have spent at least an hour reading every placard.  Their collection of fossils was also impressive, several of which I had seen in pictures before.  The last part of the exhibit was the large dinosaur skeletons.  It's hard to appreciate the size of a supersaurus without standing next one it's skeleton.
   After getting a good education on evolutionary history, it was off to Hot Springs State Park.  This is the first time I had ever seen a hot spring.  I was expecting a stronger smell, but it was not the case.  There was a distinct sulpher smell in the air, but it wasn't overpowering.  The runoff from the hot spring created some interesting mineral deposits.  I was surprised at how clear the water was in the spring itself.  An other nice first.
   From Thermopolis it was off to Yellowstone National Park.  I had planned to visit Old Faithful first, but had setup the GPS with an incorrect destination.  As I entered Yellowstone the first thing I encountered were several bison grazing by the side of the road.  I have seen bison before, but never wondering around in the wild.  They seemed to care little about my car, which after all was only slightly larger than they were.  After that first encounter, I saw several more herds of them throughout my drive.  But it was the first group I saw the closest.  Something special about seeing the largest land animal in North America whose ancestors were the among the Pleistocene Megafauna, now all extinct.
   Yellow Stone is beautiful, but I had hopped to see a geyser before the end of the evening so I was rushing a bit.  Even so, I still pulled over several times to look around.  I reached Mammoth Hot Springs and soon figured out I had the wrong location.  Old Faithful was about an hour away, and the sun would be gone by then.  Most of the rest areas I passed said no over night camping, which I assumed applied to people sleeping in their trunk as I was.  There were also no truck stops anywhere near me.  I had planned to see Old Faithful and leave the park.  Now my plans had been thwarted.  However, an idea dawned on me.  Old Faithful has a large lodge.  The park was full of people, and the lodge parking lot was probably like most of the other parking lots—full of cars.  No one would notice if I parked there overnight.
   So I spent the last of the daylight hours walking and photographing Mammoth Hot Springs.  I think it was worth my time as it was much larger than the hot springs in Thermopolis.  I set out for Old Faithful as the sun was pretty much gone.  During this part of the drive, I passed two canines walking by the road.  They were either wolfs or coyotes, but I am not sure which.  The with the second canine, I stopped in the road to watch him pass.  While he looked at me, he didn't seem in the least bit concerned with my presents.  Beautiful animal though.  It was too dark to even bother trying to get a shot.  I also encountered an owl who swooped down in front of my car as I drove by.  I'm not sure I have ever seen an owl in the wild.  So wild canines and owls—an other first I was pleased to have.
   As the evening progressed, I pulled over an attempted to photograph the stars.  My tripod was dead, so I just set my camera on the roof of my car.  That would have worked, but it was so dark I could find no light point to set my focus.  The goal was to see if I couldn't photograph the Milky Way.  I may have done it, but all my shots were blurry.
   I at last arrived at Old Faithful and found a nice parking spot where Eve was surrounded by cars and tour buses.  I brushed my teeth, crawled in the truck and slept soundly at an altitude of 7,300 feet in a volcanic caldera.  A day of many firsts.

June 04, 2013

North-west trip day 3

Joe, myself, and Brenna

Joe, myself, and Brenna

   Most of today was spent in the Black Hills.  I started with the Crazy Horse Monument and arrived just in time to see a rock blast.  Most of my time was spent reading about the native American peoples detailed in the exhibits at the visitor center.
   After Crazy Horse, I set out of Jewel Cave and two Australian hitch hikers.  They were also going to Jewel Cave so we decided to all go together.  We did two tours.  One was a basic introductory tour just in one of the main chamber of the cave, and the other was a more in depth loop.  The tour is only a tinny portion of the total cave, of which they believe the 160+ miles currently mapped is about 5% of the total cave.  I think I want to get more into caving after this tour.  I like the dark and small spaces very much, and the challenges of exploring sound like the kind of challenges I like.
   I dropped my hitch hiking friend in Sturgis, SD and continued onto my last destination for the evening: Devils Tower.  I arrived near sunset and in hindsight I should have found a place to sleep so I could have spent more time to enjoy it.  After a few pictures I set out to learn a valuable lessons about Wyoming roads and the GPS I was using: just because the GPS says to turn on a road doesn't necessary mean it is a road, or one a 2004 Toyota Corolla should attempt to drive.  At one point I turned onto a "road" that was nothing more than two ruts going through tall grass.  There was several large mud puddles that required the gathering of speed in order to get through them.  Eve transformed from a suburban front-wheel drive family car into a 4x4 mudding truck.  Getting stuck wasn't an option.  I was in the middle of nowhere, with no cell phone service, after sunset.  But Eve again proved she is just as good as any truck and saw me through it.  After we got on the paved road, Eve was a filthy mess.  I decided backtracking wasn't so bad when out west.
   I eventually found a Flying-J truck stop in Gillette, WY to sleep for the evening.

June 03, 2013

North-west trip day 2

   The day started a little latter than expected as I slept quite well.  I first stopped at the Sioux Falls and picked up groceries and ice.  This trip I wanted to eat better than in road trips past, so I borrowed Xiphos' cooler so I could keep perishable food.  This turned out to be a great plan as I ended up eating from the cooler the entire trip.
   My next stop was the Corn Palace in Mitchell, SD.  I didn't spend a lot of time there, but it was interesting to see murals made of corn husks.  While in Mitchell I also got an oil change.  Then it was back to driving.
   I arrived in the Badlands around 7:00 pm, and I really wasn't prepared for what I was about to see.  There was nothing I could compare it to—the ground went from being flat and then just dropped a couple hundred feet.  I spent the rest of the evening driving around Badlands National Park and stopped at every pullover point.
   It is one thing to see places like this in pictures, but it is quite an other to expense the vast size of these eroded formations in person.  It was a nice birthday present.  Of the 684 pictures I took, I kept 108.  None of them can really present the feeling of standing there.
   The evening ended at a rest area near Tilford, SD.

June 02, 2013

The trip begins

Ben and Amber

Ben and Amber

   This evening I set out on my trip out west.  I have several destinations in mind and plan to greatly reduce the list of states I have yet to see.  Among the destinations are the Rockey Mountains, which I have never been.  I wanted to make it to South Dakota but didn't leave in time to make it that far.  I reached a rest area in Blue Earth, Minnesota and stopped for the night.

June 01, 2013

Computing Cosine with BC Math

When implementing sine and cosine for the bcmath version of my Gauss-Newton class, I used the Maclaurin series. Unfortunately, this ends up being slow to converge for numbers close to π. The slow convergence had required setting the bcmath scale to twice the current value in order to get accurate calculations. This made the performance of the function very slow.

I wrote about using some algebraic tricks to speed the convergence of natural log and the exponential function, and I began to think about ways I could do this with my trigonometric functions. I had investigated trying to use a modified series:

It would have allowed me to do this:

So I could just multiply the series result by the exponential of the input. However, the series just seemed like a mess and I didn't get very far with it.

My next line of thought was to see if I could use the Taylor series speed up the convergence. I had done this in the past using a look-up table for some known points to quickly calculate the Taylor series for the exponential function. Here is the general expression for the Taylor series of a given function:

In this algorithm f(n) is the nth derivative of the function f( x ). The variable b is some point we pick. What b allows us to do is pick a point close to x and compute the series starting there. The Maclaurin series is just a Taylor series where b is always zero. However, using the Taylor series with the value of b closer to x than x is to zero will result in the Taylor series converging faster than the Maclaurin series.

So let us apply the Taylor series for cosine with any b:

Keep in mind that cos(n) is the nth derivative of cosine—not the power—as we are using Lagrange's notation. At first it doesn't look like this will be too useful. Now we need cosine, all it's derivatives, and those values calculated for some b. However, this is where the properties of sine become useful. Recall the following about the sine function:

In addition, there are some special points were we get an exact real number for these trigonometric functions.

So we have four values that can be used for b and we know how the derivatives will change. Time to put this together.

Here is the PHP implementation:

/*
 * Computes cosine of x.
 * @author Andrew Que.
 * @license Public domain.
 */
function bccos$x$isSine false )
{
  
// Cosine and sine repeat in intervals of 2*pi >= x >= -2*pi.  So reduce
  // input down to this range.
  // To do this, get the whole number of how many times two pi divides into the
  // value.  Then subtract off the whole number part times two pi.  This is a
  // modulus remainder, but bcmod only returns the integer part of the
  // remainder.
  
$twoPi bcmulbcpi(), );
  
$mod bcdiv$x$twoPi );
  list( 
$whole$fractional ) = explode'.'$mod );
  
$x bcsub$xbcmul$whole$twoPi ) );

  
$correction bcpi();

  
// Modify the scale for additional accuracy.
  // Done after the interval has been reduced to avoid rounds errors with pi.
  
$scale bcGetScale();
  
bcscale$scale );

  
//-----------------------------------
  // The Taylor series for cosine is as follows:
  //      inf
  //      ---
  //      \    d^n         (x - b)^n
  //      /    ---- cos(x) ---------
  //      ---  dx^n           n!
  //      n=0
  // We use the Taylor series to compute cosine.  We could use the Maclaurin
  // series, but this converges slowly at points close to pi.  So we center
  // on one of four points: 0, pi/2, pi, and 3/2 pi.  This is done because the
  // nth derivative is easy to compute at these points: it simply alternates
  // between 1, 0 and -1.  Where it starts depends on what value the input is
  // closest to.
  //-----------------------------------

  // First, figure out which point the input value is closest to.
  // NOTE: Regular numbers used here, not BC numbers.  No reason to be that
  // that accurate yet.
  
$taylorIndex 0;
  
$taylorPoint pi() * 7/4;
  
$halfPi pi() / 2;
  while ( 
$taylorPoint >= $x )
  {
    
$taylorPoint -= $halfPi;
    
$taylorIndex += 1;
  }

  
// Figure out what point we are starting.
  // Now the value is needed as a BC number.
  
$taylorPoint $taylorIndex 2;
  
$taylorPoint bcmul$taylorPointbcpi() );

  
// The index for what the nth derivative will be.
  // Note that $taylorIndex is subtracted by one in order to iterate it.  This
  // is the same as adding 3 and doing a modulus by 4.
  
$taylorIndex %= 4;

  
// To do sine rather than cosine, simply add one to the starting index.
  
if ( $isSine )
    
$taylorIndex = ( $taylorIndex ) % 4;

  
// This is a look-up table for the derivatives.
  
$taylorIndexMap = array( 10, -1);

  
// Setup the series variables.
  
$x bcsub$x$taylorPoint );
  
$power 1;
  
$newResult 0;
  
$result = -1// <- Something not equal to $newResult
  
$n 0;
  
$fact 1;
  while ( 
bccomp$newResult$result ) )
  {
    
// Get the nth derivative of the Taylor point.
    
$derivative $taylorIndexMap$taylorIndex ];

    
// Don't bother doing any addition of derivative is zero.
    
if ( != $derivative )
    {
      
$result $newResult;

      if ( -
== $derivative )
        
$accumulator bcneg$power );
      else
        
$accumulator $power;

      
$accumulator bcdiv$accumulator$fact );
      
$newResult   bcadd$result$accumulator );
    }

    
$n += 1;
    
$power bcmul$power$x );
    
$fact bcmul$fact$n );
    
$taylorIndex = ( $taylorIndex ) % 4;
  }

  
// Cut off the last few used to account for accumulated error--they are
  // incorrect anyway.
  
$result bcround$result$scale );

  
bcscale$scale );

  return 
$result;

}

/*
 * Computes cosine of x.
 * @author Andrew Que.
 * @license Public domain.
 */
function bcsin$x )
{
  return 
bccos$xtrue );
}

/*
 * Return the BC math scale.
 *
 * This function will return the last value passed to bcscale.
 *
 * @author Andrew Que.
 * @license Public domain.
 */
function bcGetScale()
{
  return 
strlenbcadd0) ) - 2;
}

/*
 * Rounds a value to the number of places requested.
 * @author Andrew Que.
 * @license Public domain.
 */
function bcRound$value$places )
{
  
// Round result by adding 5x10^(-places).
  
if ( -== bccomp$value"0" ) )
    
$value bcadd$value"-0." str_pad""$places"0" ) . "5" );
  else
    
$value bcadd$value"0." str_pad""$places"0" ) . "5" );

  
// Split number into the whole and fractional parts.
  
list( $integer$fractional ) = explode"."$value );

  
// If are result uses all the digits, cut off the last few used to account
  // for rounding error--they are incorrect anyway.
  
if ( strlen$fractional ) > $places )
  {
    
$fractional substr$fractional0$places );
    
$value $integer "." $fractional;
  }

  return 
$value;
}

/*
 * Negate value.
 * @author Andrew Que.
 * @license Public domain.
 */
function bcneg$value )
{
  
// Already negative?
  
if ( '-' == $value] )
    
$value substr$value);
  else
    
$value "-$value";

  return 
$value;
}

/*
 * Computes constant pi.
 *
 * Implementation uses Spigot algorithms.  Should converge rapidly.
 * Verified to 1000 decimal places.
 *
 * @author Andrew Que.
 * @license Public domain.
 */
function bcpi$desiredScale )
{
  
// Cache value of Pi so it is not recalculated if the scale isn't changed.
  
static $pi NAN;
  static 
$piScale 0;

  
// Turn up the scale for the duration of this function to avoid rounding
  // error.
  
$scale bcGetScale();

  
// Has the scale increased?
  
if ( ( $scale $piScale )
    || ( 
$desiredScale $piScale ) )
  {
    
$piScale max$desiredScale$scale );

    
// $$$FUTURE - Arbitrary.  Test and determine what is actually needed.
    
bcscale$piScale );

    
$index 0;
    
$newResult 0;
    
$result    = -1;
    while ( 
bccomp$newResult$result ) )
    {
      
$result $newResult;

      
$accumulator =                      bcdiv4, ( $index ) );
      
$accumulator bcsub$accumulatorbcdiv2, ( $index ) ) );
      
$accumulator bcsub$accumulatorbcdiv1, ( $index ) ) );
      
$accumulator bcsub$accumulatorbcdiv1, ( $index ) ) );
      
$accumulator bcmul$accumulatorbcdiv1bcpow16$index ) ) );

      
$newResult bcadd$newResult$accumulator );
      
$index += 1;
    }

    
// If are result uses all the digits, cut off the last few used to account
    // for rounding error--they are incorrect anyway.
    
if ( strlen$result ) > $piScale )
      
$result substr$result0$piScale );

    
bcscale$scale );

    
$pi $result;
  }

  return 
$pi;
}

The very first step is to get the input into a suitable range. This can be done quickly using the modulo operation which represents how much is left over after an integer division has been preformed.

This is used to put the input into the ±2π range. All trigonometric functions repeat themselves in this period, so it makes sense simply to narrow the input down to this range.

Then the closest b point must be chosen. This is done starting at 7/4 π and dropping by π/2 increments if the current value is greater than the input value. The 7/4 π = 2π – π/4 because we are looking for a cutoff point midway between 2π and 3/2 π. Subtracting by π/2 each time because our b points are separated by π/2. The number of subtractions are counted. In this way, b can be calculated. If n subtractions were made, then b = 2π – πn/2 = π(2 – n/2).

The next part is the derivative table.

The cells in the columns represent the function of the in the top row where x is the value in the row's left most column. Notice how the values simply shift to the left on each subsequent row, and the table repeats every 4 rows. So the number of subtractions used above to calculate b can be used as a starting index into this table.

Now the summation loop itself. Recall the Taylor series summation:

We know that cos(n)( b ) is just the one of the values from the derivative table. Calculating n! in the loop is also easy, because an! = an * an-1 where a0 = 1. The same kind of trick can be used for (xb)n. Here pn = (x - b) * pn-1. That makes the loop itself small and simple.

The very last trick employed in the code is for computing sine. Cosine and sine are 90º out of phase. Simply by starting at the next location in the derivative table, the exact same code for cosine can be used for sine.

I found an interesting side-effect that took a while to trace down. The resolution for the cosine operation is increased to account for rounding error during the function. This can result in it's own rounding error. The easiest example is cos( 2/3 π ). The correct answer is -0.5. However, we can not exactly calculate Pi to an infinite number of places. So the function is always passed some approximate of Pi which results in something like cos( 2/3 * 3.14159 ) = -0.499998467···. For a more accurate representation of Pi, the more decimal places until the calculation stops being 9. For cos( 2/3 * 3.1415926535 ) = -0.4999999999481578···. But the answer will only ever equal -0.5 when exactly 2/3 Pi is used. The only way I found to get around this is to per-calculate Pi to greater precision then necessary, and that does get rid of the round errors. By using 10 decimal digits of Pi, we can expect 9 digits of cosine. Then rounding after 9 digits results in cos( 2/3 * 3.1415926535 ) = -0.5 and that is what we're looking for.

Tests show that the average speed improvement of almost 240 times using the Taylor series method over the straight Maclaurin series. The function is now as fast as the others I implemented. I have to give a shout out to my calculus professor, Dr. Stredulinsky who taught me Taylor series, and an other to my discrete math and differential equations professor Dr. Fuller. These two professors have really made a difference in my understanding of mathematics. I didn't just learn the subjects to pass a test—I understood the subjects enough to apply them here.

1 comment has been made.

From Pluvius

Platteville, WI

June 03, 2013 at 10:37 AM

Interesting, keep the mind sharp and some fast "fun" with PHP. BTW - happy birthday! Indulge in some sushi today.