Andrew Que Sites list Photos
Projects Contact
Main

July 25, 2010

Analysis of a Weighted Random Algorithm

I was envisioning a project where I could use my Banded Inverse Root Nonuniform Scatter (from here on BIRNS) equation. In this project I need control over not just the random band, but the scatter. Specifically, I want to know how many of the numbers (percentage) would be within a certain range.

Graphing the full BIRNS function is difficult because it has two inputs. However, the two inputs is just to make it symmetrical—we can get rid of half the function and assume the histogram will be a mirror image in the opposite direction.

The input into the random function is α which has a range from 0 <= α < 1. The question being asked is a frequency question: how many numbers lay between a given range. Unlike a normal histogram our range isn't even increment. For example, a normal histogram is usually sometime like a point representing the number of values between 0 and .1, .1 and .2, .2 and .3, ext. Our ranges are like this: 0 to .1, 0. to .2, 0 to .3, ext.

The trimmed down function to be analyzed is . In order to get percentages we need to normalize the function for the input range. We obtain this through finding the minimum and maximum values for the function. While the function isn't linear, it is always either increasing or decreasing in value. Thus, we can just use the end points for the min and max values. , , . In order to normalize this function we have to subtract off the minimum, and then divide by the range (Δy) which looks like this: . So when we expand our function becomes , and will make the range 0 <f(x) ≤ 1.

S is our scatter coefficient with a range S ≠ 1, 0 < S < ∞. If we to graph the function, S ≈ 1 will be almost linear, S > 1 will slope more and more steeply downward, and 0 < S < 1 will slope more and more steeply upward.

In the above graph, S ≈ 1 and the function is linear. Note that S can not be 1 or it will produce a divide-by-zero condition. However, we can analyze what the function does as S approaches 1 to see why this function becomes linear. For this, we can look at the limit of the function as S approaches 1: . The result of 1 – x is exactly what the graph looks like.

Here with S = 16 we can see a sharp downward trend the gradually tapers off as x approaches 1. Again, we can see this relationship be using a limit: . Thus larger values of S lead to a function that produces numbers weighted toward 0. This is why it worked so well for BIRNS which aimed to distribute the majority of the results close to the linear function. The larger value of S the closer to the the linear function because the output of f(x) was used as the random addition to the linear function. If that output was a usually a small number then there is usually not much deviation from the linear function.

And here the reverse with S = 1/16 we can see a gradual tapper that becomes more and more sharp as x approaches 1. Again, the limit will show us what happens: . Thus smaller fractional values of S lead to a function that produces numbers weighted toward 1. Input of fractional values will not work in the BIRNS example, but they will work in the partial function.

All of this is useful for the function I wish to design. I can have random number weighted toward 0 or 1, and if need be, not weighted and almost uniformly random. So how do we know what the output will look like? For this, I'm going to produce a plot of two frequency graphs. One is a standard histogram, and the other is a sum if frequencies.

Here we see a frequency plot. The blue is a histogram, and the red a frequency sum. Blue uses the scale on the right side, and the red the scale on the left. How you read the data is as follows. The blue line is the occurrence of values, with the value being on the horizontal axis, and the occurrence on the vertical. For example, number close to 10% make up about 30% of the the function's output. The red graph is the point of this article. It has to be read from left to right and indicate the percentage the horizontal values, starting at 0, represent. For example, 45% of the results will be between 0 and 10%, and over 75% of the number are between 0 and 30%. 90% of the number are at or below an input of 50%. And this is exactly what I would need to know.

   On the drive back to Wisconsin I started listening to a lecture series on major world religions.  I wasn't sure how this series was going to be presented, and I had fears I would only be given the more mundane details about how they spread and who was pushing for it.  I was very pleased to find out that was not the case.  Right now I am getting information on Christianity, how it began, how it was presented, how it has changed and information about the groups and denominations who practice the faith.  The series will also cover Islam, Judaism, and various Chines and Indian religions (of which I assume Buddhism and Hinduism are covered).
   People might find at first think I wouldn't enjoy a study of religion on the grounds I am an atheist.  This is not the case.  I am very interested in how religion works, and why so many (I'd say a majority) hold religious views of some form.  I am not an atheist who advocates the annihilation of religion.  I'd rather study what, how and why religious beliefs occur in every major culture even when they are/were isolated from the rest of the world, because knowing something about religious ultimatly is reveiling something of the human character—and that makes up part of all of us.
   Pictured is Jen who I took out for dinner before she moves out of state.

July 23, 2010

River Back on the Rise

   The river is back on the rise and again threatens to move into Burwood.  All the rain as of late has really pushed up the waters.  The river is expected to climb over an other foot which may put it up over the road Skyview at the end of our street.  Time to keep an eye on the hydrograph.
   Pictured is Vinny who in all of the heat decided she wasn't giving up her perch on top of Noah's car despite the fact he was about to drive away.

July 22, 2010

12-year Old Code

   I had planned on writing about a clever programming trick I thought up, but after implementation the trick didn't work.  About a third of the articles I want to write end up with this fate.  An other third are unfinished.  And the remaining third I've written and they exist somewhere on this rather unsorted site.
   I decided to take a trip to the past.  I know my code from my early days of programming was scary.  But I had not looked at anything from my the days after I learned to program and was actually adequate.  I found some code (finished no less!) I had written in 1998, and you know what?  It wasn't that bad.  I could follow it easily, and it was neatly broken into units.  It could have used some more comments, and at the time I still used C++ was a glorified C with object.  Not bad for code that is now over 12 years old.
   This was DOS code and compiled only with the a Borland compiler.  I used DOSBox to run it, but I'm not sure I'd remember how to compile it.  I now use the GNU compiler suite for most of my programming work.  The Unix style make file system still leaves me feeling like there has to be a better way.  But this code reminded me of something I really miss about Borland C: the ease of inline assembly.  You could move in and out of variables, access registers directly, and there was even a trick you could do to make the compiler generate 386 instructions for 32-bit operations.  GNU C's inline assembly is painful to say the least.  Most of the time I just make an external assembly file and call the functions rather then try to work with the inline assembly setup.
   My contract here in Cedar Rapids (now down to 3 weeks and a day...not that I'm counting or anything) has put me back in practice with my assembly skills.  I'm actually fairly proficient with PowerPC assembly, and I can work ARM assembly without too much trouble.  I do enjoy diving into assembly from time to time.  Seems like most of the people in my current group as well as my last group really shied away from assembly—sometimes to the point of doing things a little strangely in order to avoid having to work in assembly.  So  I've found a little nitch—something I can do, don't mind doing, and that others don't like.  And for a contractor that's a good place to be.
Jenna

Jenna

   As a child of the 1980s, the cartoon He-Man was among my childhood afternoon rituals.  Although I recall that I watched it regularly I wasn't able to recall a single episode.  Since this cartoon clearly occupied a portion of my life I decided to investigate just what it was I watched as a child. 
   I've watched about 9 episodes so far.  I wasn't expecting the show to be good, but I was surprised at the lack of anything consistent.  From episode to episode we have no idea what powers the characters have.  What was used last episode might not be used/work in the next--aside from Adam transforming into He-Man.  No wonder the stories didn't stick in my head—they didn't make any sense.  Watching the show reminds me of the 1936 version of Flash Gordon.  Both have an extremely underdeveloped universe with characters that seem only to have a couple of overly obvious characteristics.  He-man/Flash Gordon: charismatic, and good.  Skeletor/Ming: bad and self-righteous.  Man-at-arms/Dr. Zarkov: men of science.
   Of course, the He-Man cartoon was a money making franchise created by Mattel.  When viewed as a 20 minute action figure commercial the episodes make a lot more sense.  The animated characters look very much like the toys, and I'm sure that is no accident.  So the story is of little importances when you are just trying to peddle plastic to children.  As long as watching leads to buying there isn't any reason for a good story.  Maybe I'm just bitter over the undeniable fact that I was just one of many children being exploited by corporations, but so far I think the He-Man cartoon sucked.  So far it has just a little more story then Beavis and Butt-Head, but about the same amount of intelligent thought required per episode.  The difference is that Beavis and Butt-Head never tried to pretend it was a wholesome, and conveyed positive message.
Sniffy the Squirrel

Sniffy the Squirrel

   I forgot my headphones in Wisconsin on my trip up this weekend, and only made it about half the day at work before I decided I absolutely could not get by without them.  Thus at lunch I went out in search of replacements.  In the past I have found the more money one invests in earbuds, the better the sound quality.  So I went and bought the most expensive pair I found to see what raising the bar all the way to the top would do.  I was surprised: the sound was exceptional.  They have a rubber padding around the outside that make the buds like earplugs blocking out surrounding noise.  And the sound they produced was quite rich and with a strong base end.  Most little speakers have difficulty producing base (try seeing how much base your cellphone can produce).  Music makes my day go by much more comfortably.  No stupid door alarms going off because people didn't scan their badge before exiting, no people on conference calls with their office doors open, and no people who laugh obnoxiously at everything.
   Pictured is Sniffy the Squirrel, a curious little critter who had no problem coming right up to us in order to examine our offering of bread.  Alas, he was a critic and the free bread didn't interest him—so he went off to frolic elsewhere.