Monday, June 29, 2009

How Many Prime Numbers are There?

Prime numbers, most of us have heard of them. Primes are those special numbers which are only divisible by its self and 1 (i.e. 2 is only divisible by 2, 7 is only divisible by 7, 179424673 is only divisible by 179424673, and so on). It is believed that the Ancient Greeks were the first to study them and we today continue to use them for encryption and other important things to modern day life.

The Egyptians maybe able to lay claim to have discover prime numbers, but it is with the ancient Greeks that we get a lot of what we are thought in school about primes. Pythagoras' school study primes for their beauty and mystical and numerological properties. Euclid showed in his 9 book of Elements that there are infinitely many primes.

Simple proof of the infinite number of primes:

Assume there are only a finite number of primes, such that p1, p2, p3, ..., pn are all the prime numbers that exist. Given p1 * p2 * p3 * ... * pn + 1 = P, we know that P must be larger than any of the finite number of primes, therefore P must be divisible by one of our finite number of primes. Here lays the problem, if P is divide by any of the finite number of primes then there must be a remainder of 1 (i.e. 2 * 3 * 5 * 7 + 1 divided by either 2, 3, 5, or 7 would have to leave a remainder of 1 (go head try it on a calculator), the plus 1 is the issue). This is a contradiction, therefore there must not be a finite number of primes and thus we have an infinite number of primes.

This simple proof is similar to what Euclid gave in his 9th book of Elements. It is based on the fact that numbers keep on going and that giving a list of numbers we can create new numbers that are not on that list. So the argument is that given a list of prime numbers we can find a prime number that is not on the list by simply taking the prime numbers on the list multiplying them and adding 1 to the total (note, this does not mean that the multiple of a number of different prime numbers plus 1 is prime, just that is a good way of finding another prime number).

For example take 2, 3, and 5. (2 * 3) + 1 = 7, which is prime. (2 * 3 * 5) + 1 = 31, which is also prime. (3 * 5) + 1 = 16, which is not prime. (If you think that all you need is 2 and another prime, then try (2 * 7) + 1 = 15, which is not prime.)

I hope I have shown you that there are an infinite number of prime numbers. Now go out there and find them you could win money if you find a really large one!

Sunday, June 28, 2009

0^0 = 1, 0, undefined?

We all have been told that x^0 (x to the 0th power) equals 1, but few have looked at why this is true. What does it really mean when we say, take 5 to the 0th power? What does 0 to a power mean--or more to the point, what does 0^0 mean?

If I type x^0 in Wolfram|Alpha, the simple output is 1 (there are some series and integral representations of the answer too, but I have never really cared for that kind of thing (too messy)). But what are we really doing? A power function is short hand for saying take this number and multiply it by itself this many times (i.e. 3^3 = 3 * 3 * 3 = 27). So, when we say 3 to the 1st power, we are simply saying 3 in an abstract way. If you think about multiplication as a series of steps to get to an amount, this makes sense (i.e. 3 * 4 * 5 = 12 * 5 = 60). The easy way to think about powers is as a function. The first input to the function is the number you want to multiply by itself and the second input is the number of times you want to multiply the number by itself: hence 2^4 could be thought of as power(2, 4) = 2 * 2 * 2 * 2 = 16. Therefore, 3^1 is power(3, 1) = 3 not multiplied by anything else, so the value is simply the same as the first input into the function. This is easy enough (I know this is not true for negative powers).

So what does it mean to take something to the 0th power? The simple power function given above breaks down at this point (i.e. power(3, 0) = 3 * ? or something like that). So what does 3^0 equal? We have been told in school that x^0 equals 1, so 3^0 = 1. But why? One way to think about it is that 3^3 = 3 * 3 * 3 = 27, 3^2 = 3 * 3 = 9, and 3^1 = 3. Do you notice a pattern? When we are moving down the power chain, we are simply taking the previous answer and dividing it by the number, hence 3^2 = (3^3)/3. Therefore, we can say:

x^b = (x^a)/x, when a = b + 1 and where x is any number (Real or Complex).

This looks really complex, but it is not. What we are saying is that x to any power is equal to the value of x to a power one above the current one divided by x (i.e. 2^4 = (2^5)/2 or 2 * 2 * 2 * 2 = (2 * 2 * 2 * 2 * 2)/2 (cross off one of the 2s on the right side and you get 2 * 2 * 2 * 2 = 2 * 2 * 2 * 2, which we know is true)). Using this form, 3^0 = (3^1)/3, which is the same as saying 3^0 = 3/3 = 1. Thus, we state in general that:

x^0 = x/x = 1, where x is any number (Real or Complex) other than 0.

Why can we not say that 0^0 = 1? It would make our lives a lot easier. Well, we have also been told that 0 times any number is 0. As such, we can say 0^3 = 0 * 0 * 0 = 0, 0^2 = 0 * 0 = 0, and 0^1 = 0. Following this pattern, we get 0^0 = 0.

So does 0^0 = 0 or 1? Well we have another problem (D'oh). You cannot divide by 0 (I was told in my Number Theory class (MATH 480) that St. Peter keeps track off the number of times you divide by 0. If the number is too high you cannot get into heaven). Why can you not divide by o? We do not know what it means to take a number of things and place them in equal amount of sets that contain 0 of the thing (i.e. if Pirates are splitting up gold, and there is no gold to be split, how much gold does each Pirate get (I assume the answer is that the captain will get split in two)). Since we cannot split a number of things into equal sets containing 0 of the things, then 0^0 = 0/0, which I guess is undefined?!?

The problem is that 0^0 is an Indeterminate, which in the world of Mathematics is marked on the map with the words, "Here be dragons". You can argue that 0^0 = 1, since x/x = 1. You could also argue that 0^0 = 0, since x * 0 = 0. Or you can play it safe and say 0^0 = undefined. I like the third definition because I work in IT and it is safer to catch an error than to just assume an answer. At any rate, I hope you have a better understanding on how the power function works and on what x^0 means.

Saturday, June 27, 2009

How URLs Work

Uniform Resource Locators (URL), you know: www.google.com, www.amazon.com, etc. Believe it or not these strings of text hold a lot of information about the structure and design of the site you are connection to. URL are really paths which go down the file structure (like /home/mike/
or c:\windows\, more on this latter) to the resource (file in most cases) that you are remotely accessing. When you type www.twitter.com in your browser you are tell the site, the path of the resource you want to access.

The format of URLs are a bit odd (according to Wikipedia the creator of URLs, Tim Berners-Lee, regrets the format) . You see, it follows a reverse order before the first /. Lets break down an URL to illustrate how an URL works. Take this URL for an example:

http://comp-phil.blogspot.com/2009/06/using-just-addition-and-negation-to.html

The first part http:// says which Internet protocol you are using to access the site (other popular examples are ftp:// and https://). Every browser I have ever used assumes if you just type www.vanguard.com that want to use HTTP so it will prefix http:// to your URL.

The next part, comp-phil.blogspot.com, is a bit odd. You see it is backwards, the way it is parsed is from the last . (dot) to first . (dot)., comp-phil.blogspot.com, looks like this /com/blogspot/comp-phil to the web server you are connecting to.



The image above shows how (on a very small scale) the Internet is organized. The com tells the DNS server which branch of the Internet the site is on (org, gov, net, uk, etc.). The next part, blogspot, tells you which domain branch the site is on. In this example the comp-phil says which sub-domain the site is on. Last, the www says (basicly) that the sub-domain is www (World Wide Web). So, the example can be thought of as /com/blogspot/comp-phil/www/. There is an implied .:80 at the end of this section, so this section of the URL really looks like www.comp-phil.blogspot.com.:80, if you do not believe me try www.google.com.:80 in your browser, I'll wait. Welcome back, the . (dot) after the com, says that it is the root directory (think UNIX directory structure), the :80 at the end says that the server is listening to port 80. Port 80 is the IANA assigned port number for the World Wide Web HTTP (web sites).

The last section of the example, /2009/06/using-just-addition-and-negation-to.html, is just the directory structure from the server's sub-domain to the resource you are requesting. If you look on the server you would see that in the /2009/06/ directory of the sub-domain a HTML file called using-just-addition-and-negation-to.html.

That's it, not very comlicated at all (well the www.comp-phil.blogspot.com part is complex, but understandable). Next time you type in www.twitter.com/MikeMKH in your browser you will understand what you really doing (and while you are there follow me and say hi).

Wednesday, June 24, 2009

UDP is Important

UDP (User Datagram Protocol) is a protocol which allows systems to send information. UDP is the quick and dirty way to transfer information, it does not use hand shakes (like TCP), it simply fires-and-forgets. Messages send by UDP are said to be transaction oriented, meaning that delivery and duplication protection are not guaranteed. This means that by using UDP to send a message anywhere from 0 to infinite amount of the same message maybe received by the receiver.

Often it is taught in school to think of UDP as junk mail, a junk mailer normally does not care if a piece of junk mail arrives at a home, instead the junk mailer cares about getting out a lot of mail at low costs. I prefer to think of UDP as an elderly man that does not have a good memory, often times this man will tell stories not knowing that they he has already told this story to the listener. The old man wants to convey some type of message (we hope), and to do this he tells a story. A young man listens to the story and normally will be polite (we hope) and allow the old man to tell the story even if he has already heard it. The old man could be thought of as UDP and the story as the packet being delivered. In this example the stories can be told to the young man 0 to infinite amount of times (we hope not infinite).

So, what good is UDP and why is it important? Well sometimes in order to save bandwidth and time a system will opt to use UDP over other protocols (like TCP) in order to transfer information. This is often used in application where a lot of data is being sent but if packets are lost or duplicated it is no big deal. Streaming media is an example of an application that would use UDP, most user are willing to accept a few blups in their Dramatic Chipmunk streaming video or their streaming "Beat It" by Michael Jackson on Grooveshark.

So why is UDP important? Well UDP is the protocol used by DNS (Domain Name System). So why is DNS important, well DNS is what allows you to use the internet. DNS translate the URL http://comp-phil.blogspot.com/ into 74.125.95.191 which is the IP address of comp-phil.blogspot.com. If it wasn't for DNS you would have to type in 72.21.210.250 every time you wanted to buy a book from Amazon. So you can say that UDP is important because DNS is import and DNS uses UDP.

Tuesday, June 23, 2009

Separation Of Concerns Can Have an Effect on Your Company

In software engineering separation of concerns is a design principle which breaks down the characteristic of different elements in a design in such-a-way as to hide the design decision from other elements. Through the use of separation of concerns, a system can be broken down and layered into different spheres of concerns. This break down allows for more maintainable, flexible and, modifiable systems. In general it is a best practice to follow the separation of concerns design principle.

The separation of concerns also has another effect, but this effect goes beyond the system. The separation of concerns effects the way a system is built. The way that most systems are built, teams of people are broken down along the lines of which different elements in the system they are building. These elements are created when the separation of concerns design principle is followed and different spheres of concerns are created.

Like-wise, on a larger scale, whole companies can be broken down using the separation of concerns design principle. Think about it, most companies have different departments doing their accounting, legal issues, IT, etc. This brake down of a company along different departments follows the separation of concerns design principle.

As you can see the separation of concerns design principle effects more than just the design of a system. Separation of concerns, can, does, and will effect the organization of your team, area, department, and even the company as a whole.

Thursday, June 18, 2009

How (Most) Computer Security Really Works

Prime numbers, you know those number the Greeks called πρώτοι αριθμοί. Well they are important, in fact very important to the modern world. In fact the protection of all of the world's important data rest on their backs.

First lets review what a prime number is, simply put a prime number is any number which cannot be divided by any number evenly except for its self and 1. Stated more formally, x is prime if and only if its x/y is not integer except for when y = 1 or y = x. This means that 2, 3, 5, 7, 11, 13, 17, 23, ... are prime number while 4, 6, 8, 10, 12, 14, 16, ... are not (4/2 = 2, 6/2 = 3, ...).

So what does this really mean. Well there is a theory, a theory which states that any positive integer greater than 1 can be represented by the product of at least one prime number. This means that every integer greater than 1 is made up of prime numbers.

Examples:
2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3
...
195 = 3 * 5 * 13
...
8961 = 3 * 29 * 103
...
121980 = 2 * 2 * 5 * 7 * 11 * 787
...

This theory is called the Fundamental Theorem of Arithmetic. This theorem is more than just fundamental to arithmetic, this theorem is fundamental to computer security.

You see computer security is based on encryption. Encryption is used to transform information into an unreadable form. Encryption is undone by decryption, which is used to transform the unreadable encrypted information back into the original form of the information.

Now is when prime numbers and the fundamental theory of arithmetic come into play, you see most encryption methods use the product of two prime numbers. As the fundamental theory of arithmetic shows us, the product of two prime numbers can only be dividable by those two prime numbers and 1. This product of two prime numbers is used in different algorithms in order to generate encrypted text.

Now you know the world of computer security's deep dark secret, most of computer security is based on the fact that it is hard to do prime factorization on very large numbers.

Wednesday, June 17, 2009

Using Just Addition and Negation to Create All Mathematical Operations

Addition, Subtraction, Division, Multiplication, and Negation (Negative numbers); these are the basic operations we all learned in grade school. Truth be told you do not really need them. No, your grade school teacher did not lie to you or teach you something pointless (at least in this case). These operations make great short hand, but are not really needed.

You can create all of the operations you know from grade school to college level (including PhD level) with just simply using Addition and Negation. Given a set of numbers (Real or Complex), you can create out of the simple operation of Addition (+) and Negation (-x, where x is a number) any other operation you can thing of. For example, say you have set of 5 things and lose 2 of them, to find out how many of the set you still have you take 5 and Subtract 2 of them to get 3; but you could have taken 5 and Added the Negative value of 2 to them to get 3. You can think of Subtraction as simply the Addition of a Negative amount of something.

In more symbolic form:
x - y = x + -y
where x and y are members of a set of numbers

The same is true for Multiplication. Given 5 sets of 3 things, you have a total of 15 things (5 * 3 = 15). You could also say that given 5 sets of 3 things, you Add 5 to 5, 3 Times giving you 15 (5 + 5 + 5 = 15).

Again in more symbolic form:
x * y = x + ... + x
where ... represent y number of + x (I know the symbolic x + ... + x does not really look good for 0 or 1, but I do not want to introduce a function)

You may be thinking what about Negative numbers in Multiplication, well Negative numbers are not really any thing special. Say you owe 5 people 3 bucks and have no money, you have Negative 15 dollars (5 * -3 = -5 + -5 + -5 = -15). In the symbolic above either x or y can be Negative numbers.

Likewise, Division can be thought of as Multiple Subtraction, which is really just Multiple Addition of Negative numbers (as shown above). An example maybe needed, say you have 15 of something and need to give an equal number of the thing to 3 people (think of Pirates splitting up gold). Well, you need to give 1 of the thing to each person a number of times until you run out of them, meaning at the end you have give 5 of the thing to each of the 3 people (15 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 3 + 3 + 3 + 3 + 3). In another way, you have 15 of something and Subtract 3 from the 15 until you have 0 left (15 - 3 - 3 - 3 - 3 - 3 = 0, or 3 + 3 + 3 + 3 + 3 = 15). Or you have 15 of something and Add Negative 3 to the 15 until you have 0 left (15 + -3 + -3 + -3 + -3 + -3 = 0). All of these ways of thinking give the same result, 5 sets of 3. That is what Division really is, finding how many equal sets (if you are working with whole numbers) can be made out of a number.

In more symbolic form:
x / y = z + ... + z
where z is a number from the same set as x and y and ... represent y number of + z (again I know the symbolic z + ... + z does not really look good for 0 or 1, but I am trying to not introduce any new functions)

So what about Dividing by 0? Well as we know Dividing by 0 is undefined and here is why. Say you have 15 of something and need to split it equal among 0 groups what are you really doing? You are saying that you can take 0 groups of something and Add them up to be 15 of something. This is impossible since 0 + 0 = 0 and likewise 0 + ... + 0 = 0, where ... can be any number of + 0. Also, we all know that x * 0 = 0, since 0 Added to 0 an x number of times would still be 0 (as shown above).

What does any of this have to do with Programming? Well there are CPUs called RISC CPUs, RISC stands for Reduced Instruction Set Computer. The goal of RISC to have as few instruction as possible. On the computation side I would argue that all you need is Addition and Negation. My argument would be based on this post, as I have shown all of the mathematical operations we know can be express with just Addition and Negation operations. Thus, for computations RISC would only need the ability to Add and Negate.