King Gorira

No, that’s not misspelled (at least not by me).  In looking for subjects for my next homework project, I opened our shed and found something I thought would be interesting: ImageThis is an old style pachinko (パチンコ) machine.  In fact, this is the infamous “King Gorira” machine, with a King Kong type theme for the centerpiece:

Image

The user flips a lever and a little steel ball is shot to the top of the play area. The ball bounces around the pins and a prize is awarded based on where the ball lands.  The prize is, of course, more little steel balls. Since these machines were (and are) used for gambling similar to the way slot machines work in U.S casinos, I guess you could say that a gambling addiction with this machine would be like having a monkey on your back.  You could say that; I wouldn’t because it’s insensitive.  What struck me as interesting about it is that it is a physical machine. There are no electronics used in getting it to work, but work it does. Well, my model doesn’t work (that’s why it’s in the shed), but this type of machine can and does work well.  This class is still about computational thinking and seeing computer concepts in everyday life.  So what does this machine compute?

The machine is like a black box function.  Well, specifically it IS a box, and it ACTS LIKE a function.  One little steel ball goes in, and zero or more little steel balls come out.  But what function is being represented?  It is a gambling machine, so it is a safe bet (har, har) that it is a random function (a function that returns a random result).  Common sense tells us that the random function is probably biased towards no little steel balls coming out (loss) rather than many little steel balls coming out (win).  The following questions are now posed:

  1. Where is the mechanical source of randomness?
  2. Is the bias an adjustable property?
  3. How can this functionality be modeled and/or manufactured?
  4. How can the randomness be interpreted?

Common sense tells us that if you do the same action twice, you get the same result twice.  This is true on a large scale.  If you let go of a glass tumbler over a cement floor, the glass will drop and break.  Every time.  Action: drop, Result: break.  Take my word for it.  If on the other hand we look at the details, things change.  The glass does not always break into the same number of pieces, nor are the pieces always the same shape.  A coin is another example.  In the big picture, I can spin a coin on a table, and every time it will spin for a while and then come to a stop flat on the table.[1] In detail, each time it will either land on heads or tails:

coin

The truth is this: you can’t really do it the same way every time!  Every time you spin a coin (or drop a glass, or whatever) you do it a little bit differently.  The torque applied to the coin, the starting position of the glass, the air density under the wings of a butterfly.  There are all sorts of little variations that add up. This is called chaos, which is a Greek word meaning “I don’t know what comes next”.  In the case of the pachinko machine, the little steel ball changes direction every time it hits a pin.  The direction it travels (other than a simple “down”) is dependent on the angle of impact as well as the speed, direction, and rotation of the ball.  Even minute changes in any of these things could effect the change of direction.  Also every time a pin is hit, the velocity and rotation of the little steel ball changes as well.  So by hitting a series of pins, the machine is not creating randomness, as much as it is making use of the chaos that is inherent in nature.

Since the bias of the result is built into the positioning of the pins and the placement of the “reward” centers, I believe that the bias could be changed (or eliminated) by changing the position of the pins.  To eliminate the bias, the little steel ball would have to start with (approximately) the same position and velocity every time and the pattern of pins would have to be regular.  Specifically, if the little steel ball hits a pin from the top, it has two options: bounce right, or bounce left.  Putting a pin under each of these options, would cause an additional choice of the same type.  Putting a pin under each of these options and continuing the pattern would yield a “more random” answer in the same sense that flipping a coin multiple times would provide a larger set of potential random results (one flip: {heads, tails}, two flips: {heads/heads, heads/tails, tails/heads, tails/tails}).

This gives us options as to implementation of the best pin pattern. To achieve unbiased random results, I would think a fixed pattern of pins with offset alternating rows would work:

pins1

However, if we are dropping the little steel ball from the same spot every time, only the pins inside the green triangle are needed:

pins2

Given a single start point and two possible options each time a ball hits a pin, we get a finite state machine that looks something like this:

fsm1 In the diagram, each state is labeled with the paths a little steel ball could take to get to that state.  The output of our mechanical function is the position of the little steel ball as it leaves the grid of pins, represented by the end states in the graph.  Since, for our purposes, the output of a random function (mechanical or otherwise) needs to be a random number, the output could be interpreted in a number of ways.  The most straight forward is that there are six different ways that the little steel ball can leave the pins, so the output of our randomness “function” is a random number between 0 and 5, inclusive.  Things to note at this point:

  1. We are assuming (and reasonably so) that the chance of a little steel ball bouncing left/right is 50%/50%.
  2. We are are then assuming (based on assumption 1) that all paths through the pins are equally likely.
  3. If the output positions are numbered 0 through 5, a little steel ball is more likely to end up as a 2 or a 3 than as a 0 or a 5.

This means that our random numbers would not be unbiased. To get unbiased random numbers (or more accurately to control the bias of the numbers) I believe the best method would be to find the probability of each output position occurring and then map the output positions to either 0 or 1 based on this data.  This would allow the bias of a 0 or 1 (win/loss) to be shifted accordingly.  To arrange for no bias, using an odd number of rows of pins (which means an even number of output states) and alternating the output stats mapping between 0 and 1 would work, because each result (0,1) in aggregate would have the same number of paths leading to it.  Thus, the result of dropping multiple little steel balls would be to generate a random string of 0’s and 1’s which would allow for random numbers of any size or range.

[1] Actually, there was one time it didn’t, but that time there was a Ouija board, a dyslexic chinchilla, and a jar of mayonnaise substitute involved, so I don’t give it much credit.

Dung Beetles…

It is not my intent to provide an animal theme to all of my posts, it’s just worked out that way so far. However, when my friend Johnny asked “What animal are you teaching math with today?”, my immediate response was “Dung Beetles and double integration”. I was joking, of course, but when he seemed skeptical I felt a overwhelming urge to validate my answer. So here it is:

Using standard units, distance is measured in meters (m). Area is measured in square meters (m2). Mathematically, the integral (result of integration) of x is x2. By the same token, distance (m) integrated becomes area (m2). Volume is measured in cubic meters (m3). The integral of x2 is x3, and continuing the pattern, area (m2) integrated is volume (m3).

Now, at this point I know Johnny is asking himself, “Fascinating as all this math crap is, what does it have to do with my favorite members of family Scarabaeidae?” The answer is related to what the little buggers do for a living. Imagine a beetle walking along. As it walks it picks up pieces of it’s favorite food (you can guess what THAT is), and rolls it into a ball. It pushes this ball forward, continuing to pick up pieces of euphemistically named material and adding them to the ball. The ball can get up to 50 times the weight of the beetle itself (that’s a lot of… well, anyway). The point here is that as the beetle traverses the distance, the ball gets larger. The ball, being a solid object, has volume and that volume is related to the distance traveled. Thus, the dung beetle is actually performing double integration converting distance into volume.

Three notes:

  1. For you math pedants out there, yes I am aware that the integral of x is actually 1/2 of x2, and that integrating again gives us 1/6 of x3, but trying to draw fractions is hard, and the explanation above is sufficient within a constant of proportionality.
  2. For you Entomology pedants out there, yes I’m aware that most dung beetles will build a ball in one place then push it some distance.  Again, the description above fits our integration example better.  And if you know enough about the feeding and mating habits of insects to correct me on this, you shouldn’t be getting your bug information from this blog anyway.
  3. Why does a dung beetle roll it’s food into a sphere?  Because, it’s really hard to push a tetrahedron.

Being a little dense…

Tags

, , , , ,

This being the first post not directly for a homework, you might expect me to say something profound.  Probably not gonna happen.  Rambling is a much more likely outcome.  Continue at your own risk.

The previous homework problems did get me thinking about number bases and how much information can be stored in a given amount of space.  From this post it was obvious that what took four digits to represent in decimal (base 10) took five digits in heximal (base 6) and this one shows representing a four digit number in decimal requiring twelve digits in binary (base 2).  So it seems obvious that increasing the base increases what I would call the “density” of the representation (more possible values in a smaller area). Upon realizing this, my first question was “By how much?”.

If we look at single digit representations, the answer is “very little.”  A single binary digit (a “bit”) can represent two possible values (0 or 1).  A single heximal digit (would that be a “hit”?) can represent six possible values (0 through 5).  This means that a heximal digit can represent four more values than a bit can. Also, notice the difference between a digit and a value. A digit represents a value, but they are not the same thing.

A difference of four values per digit doesn’t seem like much.  So, let’s look at what happens when we use more than one digit.  With two bits(*), we can represent four values (00, 01, 10, 11).  With two heximal digits we can represent 36 values (00 through 55).  This is a difference of 32 values, much more than four values per digit. Let’s keep going!  With three digits, you can represent eight values in binary, or 216 values in heximal.  A difference of 208 possible values.  With eight bits (AKA a “byte”) we can represent one of 256 possible values, but with eight heximal digits that number becomes more than 1.6 million.

When I saw this, I thought “Wow! That’s a lot!”. Then I realized that eight decimal digits represent 100 million possible values, which makes the heximal digits look like chump change.  So what does all this mean?

  1. Increasing the base increases the range of possible values for a given number of digits exponentially.  I graphed this out and it looks like the “hockey stick” graph used in global warming papers. Coincidence? Hmmmmm…..
  2. Increasing the number of digits for a given base increases the the range of possible values exponentially, as well.  I didn’t graph this one, but that’s how positional number systems work.
  3. Information is a funny thing.  If we want to represent a million possible values it would take 20 binary digits, 8 heximal digits, 6 decimal digits, or  3 base 100 digits.  However, no matter which representation we use, we can still only represent one value at a time. It would take a minimum of 6 bits to represent a single character in this sentence. So 504 bits could represent a single value between 0 and 5 x 10151 (that’s a really big number) or it could represent the previous sentence.  Unless we know the mapping used or have some kind of context for it, the information contained in those 504 bits is useless.

*With two bits, you can also get a shave and a haircut.

Bear-inary Numbers

Tags

, ,

At my office (yes, I am working full-time and getting a Ph.D.… feel sorry for me), there is a nice lady who makes things out of polymer clay.  Her name is Sherri, and she particularly likes to make teddy bears out of the stuff.  Here is a photo of a sloth of bears (yes, the collective noun for bears is “sloth”) disembarking from a plastic foam aircraft:

Image

Presumably, that’s a “bear”-plane they are getting out of.  Anyway, it occurred to me that because the bears are not rotationally symmetric (as was the previous example of tables and chairs) that they could be used to represent numbers without having to resort to things such as flower pots.  Given two unambiguous positions that the bears can rest in (sitting face-up towards you, or face down with head pointed toward you), we can use the bears to represent binary (base 2) numbers.

Image

For example, if the face-up bears represent a one and the face-down bears represent a zero, then the picture above would represent “11101101” or “237” in decimal (base 10).  So, given the homework’s second target number of “3914”, what would the representation be?

Image

The sketch above not only showcases my mad artistic skillz, but shows the final result of an un-bear-able number of calculations.  “111101001010” in binary (base 2) is “3914” in decimal (base 10), so having 12 bears face-up, face-up, face-up, face-up, face-down, face-up, face-down, face-down, face-up, face-down, face-up, and face-down respectively is a valid representation.

Future things to think about:

  1. Bears in 3-D:  This method of representation seems to hold from any direction, even if the bears were free-floating in space.  Its orientation is unambiguous, since if the side or bottom of a bear is visible, you are looking at it from the wrong angle.  However, left-to-right reading order is still assumed.
  2. Bears in Color:  Color could also be used in representation.  If you had an unlimited number of bears in each color combination and/or style, the color could also be used to represent numbers.  Either to expand the base (from magenta + face-down = 0 to chartreuse + face-up = 132, or some such) or to represent multiple numbers (position gives a binary number and color gives another different number).
  3. Dancing Bears:  Just as with the table and chairs example previously, the spacial arrangement of the bears could also be used for representation.  However, as with the previous example, finding the proper orientation becomes an issue.  Maybe the color of the bears could be used for orientating (the indigo bear is always above the aquamarine one).

Note: My wife wanted me to include more bear puns in this post.  However, I paws-ed and thought about how bear-y important this grade is, and told her “I have sufficient claws not to, honey.”

Heximal Turtles

Tags

, , , ,

Our first homework in Professor Fishwick’s class revolves around a seemingly simple task:

Find a pattern in an object that is either artificial (made by humans) or natural, and observe that the pattern could be used to represent numbers (integers).

After the class in which this homework was assigned, I was walking back to my car (having parked in a different place that day) and passed an alcove with tables and chairs, presumably for student use:

Image

The first thing I noticed was that each table had a different number of chairs. It then occurred to me that this difference could be used to represent information. If, on the other hand, each table had the same number of chairs, we would know two things:

  1. That information could not be stored by using the relative number of chairs, and
  2. Someone is OCD regarding this alcove.

The question (relevant to my homework and not a human behavioral post-doc’s) is how do we represent a number using such a set of tables and chairs.

My first thought was that the number of chairs around each table could represent a number in a positional decimal system. In this instance the target number from the homework “2014” would be represented by four tables surrounded with two, zero, one, and four chairs respectively. However, there are a couple of problems with this scenario:

Problem #1:  It would be very difficult to put nine chairs around one of those tables. It works okay for our target number of “2014”, but if our number was “199” the last two tables would need to have chairs stacked on top to accommodate them all.

Problem #2:  I want to use a base number system other than decimal. The homework specifically says that “you will need to map elements from your photograph to a number system in a base”. Decimal (base 10) is a valid base, but since it is what we use all the time in day-to-day life, it doesn’t really feel like I’m mapping anything.

Fortunately, we can use problem #2 to solve problem #1.  By using a different base, we can control the maximum number of chairs around each table.  My thought (stop me if you see the flaw) was to use the maximum number of chairs that can fit around a table as the base.  With these tables and chairs, we can squeeze six chairs around a single table, so I decided to use heximal (base 6).  Conversion: “2014” decimal is “13154” in heximal.  Here is the sketched result in a top-down view:

Image

Yes, those are supposed to be chairs positioned around tables not, as my wife put it, “sadly deformed sea-turtles trying to follow each other”.  Damn it Jim, I’m a computer scientist, not an artist! Anyway, you may notice that when taken from left to right the number of chairs around each table are one, three, one, five, and four. “13154” in heximal is our target number of “2014” in decimal. Yea!

Future things to think about:

  1. The flaw in my logic from before: If we decide to use base six, the number of chairs needed per table will range from zero to five. We will never need six chairs (the maximum that will fit) around a table. This is fine, but for maximum density I probably should have used base seven (septimal, if you are wondering).
  2. Position of the chairs can mean as much as the number: The position of the chairs around the table could be used instead of just the number of chairs. However, if position and not number is used, orientation of the chairs around the table becomes a factor.
  3. Downfall of a positional number system: If a person knew of our chair encoding, but approached the tables from the other side, the number would be “45131” or “6319” in decimal.  Thus, order is important.  Maybe putting a flower pot on the first “digit” (table) and always reading left to right would help.

The next post will be the second half of our first homework: encoding “3914” in a completely different way…