Always Bet on Math

"If we offend it is with our good will.
That you should think we come not to offend
But with good will. To show our simple skill,
That is the true beginning of our end."
-- Shakespeare, A Midsummer Night's Dream
Act V, Scene I, Lines 108-111

Last week at work we did Pascal's Triangle as part of our weekly Code Dojo.  We followed the animated image on the Wikipedia entry as our guide to the algorithm.



This worked OK and we were able to solve it fairly quickly with something similar to the C# entry on Rosetta Code.  Something like this:

        public static void CreateTriangle(int n) {
            if (n > 0) {
                for (int i = 0; i < n; i++) {
                    int c = 1;
                    Console.Write(" ".PadLeft(2 * (n - 1 - i)));
                    for (int k = 0; k <= i; k++) {
                        Console.Write("{0}", c.ToString().PadLeft(3));
                        c = c * (i - k) / (k + 1);
                    }
                    Console.WriteLine();
                }
            }
        }

This code works but it does not really give the reader of it any idea as to what the code is for.  In order for someone to be able to follow this code they would have to run the algorithm a few times (in their heads, on paper, ...) to prove to themselves that it actually works.

In Rich Hickey's talk, "Hammock Driven Development", he talks about taking time to think.  Which reminds me of a quote often misattributed to Einstein:

Some years ago the head of the Industrial Engineering Department of Yale University said, "If I had only one hour to solve a problem, I would spend up to two-thirds of that hour in attempting to define what the problem is."
-- Robert E. Finley and Henry R. Ziobro, The Manufacturing Man and His Job
as quoted by Garson O’Toole at http://quoteinvestigator.com/2014/05/22/solve/

Let us spend a few minutes looking into what the problem actually is.

If look further down in the Wikipedia entry we see the following.


taken from https://commons.wikimedia.org/wiki/File:PascalsTriangleCoefficient.svg

Awesome, Pascal's Triangle can be reduced to binomial coefficients!  Since it has been about 13 years since I got my degree in mathematics I'll need to look up how to use and solve a binomial coefficient.  Luckily MathWorld give use the following:

Great, now all we need to do is have a way to solve for factorials, which we can also find on MathWorld!

We are now all set to solve the problem.

Here is my solution in Clojure:


(I did this as part of my daily kata)

We see in the Clojure code that I TDDed my way into: first a function which will find factorials, then a function to solve for binomial coefficients, and finally I a function which will give Pascal's Triangle.  Solving the problem in this way gives us not only a readable solution which allows someone reading the code to follow the solution but now we have a function for factorials and one for binomial coefficients!

Do not misread this blog post I am not saying that the solution given in C# above is wrong or bad, but only that by spending time to research a problem can often given a much more rich solution to the problem.

As IBM would say, "Think".

taken from http://www-03.ibm.com/ibm/history/ibm100/images/icp/P496146V03975A59/us__en_us__ibm100__cult_think__think_sign__620x350.jpg

Primality by Trial Division OR TDD Example in F# using FsUnit

"Youth, beauty, wisdom, courage – all
That happiness and prime can happy call."

-- Shakespeare All's Well That Ends Well
Act II, Scene I, Lines 182-183

I find RosettaCode to be a valuable resource of ideas for my daily Code Kata.  Recently I came across an entry in RosettaCode that did not have a F# example.  Once I finished my kata I mended that issue.

Problem statement (from RosettaCode):

Write a boolean function that tells whether a given integer is prime. Remember that 1 and all non-positive numbers are not prime.  Use trial division. Even numbers over two may be eliminated right away. A loop from 3 to √n will suffice, but other loops are allowed.

Step 1 (2 isPrime = true):

First step in solving the prime, if 2 is given in the input isPrime should return true.

Test Case:

[<Test>]

let ``Validate that 2 is prime`` () =

  isPrime 2 |> should equal true

Code (to pass):

let isPrime x = true

It may look dumb, but this is all that is needed to pass the test.

Step 2 (4 isPrime = false):

Test Case:

[<Test>]

let ``Validate that 4 is not prime`` () =

  isPrime 4 |> should equal false

Code (to pass):

let isPrime x =

  match x with

  | 2 -> true

  | x when x % 2 = 0 -> false

The mod 2, might be jumping the gun a little bit, but it follows the rules is just enough code to pass the tests.

Note that the match in this state will give a warning (warning FS0025: Incomplete pattern matches on this expression. For example, the value '0' may indicate a case not covered by the pattern(s). However, a pattern rule with a 'when' clause might successfully match this value.), we'll address that later.

Step 3 (3 isPrime = true):

Test Case:

[<Test>]

let ``Validate that 3 is prime`` () =

  isPrime 3 |> should equal true

Code (to pass):

let isPrime x =

  match x with

  | 2 -> true

  | x when x % 2 = 0 -> false

  | _ -> true

Again, this might seem dumb, but it is all we need to pass the test and we've fixed the warning from before.

Step 4 (9 isPrime = false):

Test Case:

[<Test>]

let ``Validate that 9 is not prime`` () =

  isPrime 9 |> should equal false

Code (to pass):

let isPrime x =

  match x with

  | 2 | 3 -> true

  | x when x % 2 = 0 -> false

  | _ -> false

Again, a bit dumb, but this was all that is needed to pass the tests.

Step 5 (5 isPrime = true):

Test Case:

[<Test>]

let ``Validate that 5 is prime`` () =

  isPrime 5 |> should equal true

Code:

let isPrime x =

  match x with

  | 2 | 3 -> true

  | x when x % 2 = 0 -> false

  | _ ->

     let rec aux i =

        match i with

        | i when x % i = 0 -> false

        | i when x < i*i -> true

        | _ -> aux (i+2)

     aux 3

This does not follow TPP, but RosettaCode gave us the algorithm they wanted us to use.  Since we followed TDD, we know that we did not break anything by putting a larger block of code in this iteration.

Last Step (277 isPrime = true):

Test Case:

[<Test>]

let ``Validate that 277 is prime`` () =

  isPrime 277 |> should equal true

Code:

The code is exactly the same as above, this test case was just a double check to make sure the solution scaled well.

Full Example:

Entry in RosettaCode (as of 28 April 2013):

http://rosettacode.org/wiki/Primality_by_trial_division#F.23

Code on TryFSharp.org:

http://www.tryfsharp.org/create/mikemkh/Primality_by_Trial_Division.fsx

Code:

open NUnit.Framework

open FsUnit

let isPrime x =

  match x with

  | 2 | 3 -> true

  | x when x % 2 = 0 -> false

  | _ ->

     let rec aux i =

        match i with

        | i when x % i = 0 -> false

        | i when x < i*i -> true

        | _ -> aux (i+2)

     aux 3

[<Test>]

let ``Validate that 2 is prime`` () =

  isPrime 2 |> should equal true

[<Test>]

let ``Validate that 4 is not prime`` () =

  isPrime 4 |> should equal false

[<Test>]

let ``Validate that 3 is prime`` () =

  isPrime 3 |> should equal true

[<Test>]

let ``Validate that 9 is not prime`` () =

  isPrime 9 |> should equal false

[<Test>]

let ``Validate that 5 is prime`` () =

  isPrime 5 |> should equal true

[<Test>]

let ``Validate that 277 is prime`` () =

  isPrime 277 |> should equal true

Thank you, F# Weekly for all the links to this blog!

Finding Perfect Numbers

"Behoves me keep at utterance. I am perfect"
-- Shakespeare Cymbeline
Act III, Scene I, Line 73

Perfection is rare, one can even say perfection is anti-science.  For with perfection there is nothing more to investigate, nothing to ponder, nothing to study.

Perfect Numbers

In mathematics we have a class of numbers which are called perfect.  These numbers have the property that the some of their proper divisors is equal to them.

We can break this algorithm down into three steps.

Step 1: Find divisors

Given the example of n = 6

In Haskell

filter (\x -> mod 6 x == 0) [1..5]

In F#

[1..5] |> List.filter (fun x -> 6 % x = 0)

Step 2: Sum divisors

Still working with n = 6, we have [1, 2, 3] to sum.

In Haskell

sum [1, 2, 3]

In F#

[1; 2; 3] |> List.sum

Step 3: Compare

In Haskell

6 == 6

In F#

6 = 6

Putting it together

In Haskell (on codepad)

isPerfect :: Int -> Bool
isPerfect n =
  sum (
    filter (\x -> mod n x == 0) [1..(n-1)]) == n

main = print $ isPerfect 496

> true

In F# (on tryfsharp)

let isPerfect n =
  let d = [1..(n-1)] 
            |> List.filter (fun x -> n % x = 0)
            |> List.sum
  d = n
;;

isPerfect 496;;

> true

On Mapping

"You must be the change you wish to see in the world."
-- Mahatma Gandhi

Working in an industry with large amounts of data and having a need to apply changes to this data, I often find myself needing to apply functions against members of a data set.  In the world of functional programming this applying functions against a data set takes place on the island of higher order function on the beach known as mapping.

A mapping does exactly what we need to do when we want to apply a function against a data set, it takes each member of the data set and applies the function against it giving a resulting data set which has the results applied against it.

Here are a few simple examples:

Case 0: Identity function

The identity function does nothing, it literally takes the input and passes it as the output, applying nothing against the input.

Both Haskell and F# have a built in function called id which is the identity function.

In Haskell (on codepad):

map id [1 .. 4]

=> [1,2,3,4]

In F# (on tryfsharp):

List.map id [1 .. 4];;

val it : int list = [1; 2; 3; 4]

Case 1: Increment by 1

The "Hello World" for mapping (that actually does something) would be the increment by 1.  The function would add 1 to each input yielding an output with values that are one greater than the input.

Both Haskell and F# allow for the applying of the addition operator (+) in a mapping,

In Haskell (on codepad):

map (+1) [1 .. 4]

=> [2,3,4,5]

In F# (on tryfsharp):

List.map ((+) 1) [1 .. 4];;

val it : int list = [2; 3; 4; 5]

Case 2: Obtain first element of a tuple (or any complex data type)

One use that might not be obvious at first but is really useful is to map a certain part of a data set.  Mapping a certain value of a data set can allow for other higher order functions to apply to element later on in a chain.  Lets say you have a list of tuples and would like to get the first value of each one.

Both Haskell and F# have a first function which returns the first value in a tuple.

In Haskell (on codepad):

map fst [(1,2), (2,3), (3,5), (4,2)]

=> [1,2,3,4]

In F# (on tryfsharp):

List.map fst [(1,2); (2,3); (3,5); (4,2)];;

val it : int list = [1; 2; 3; 4]

There you have it a few simple examples of mapping in Haskell and F#.

Higher Order Functions

"Do not confine your children to your own learning for they were born in another time."
--Hebrew Proverb

A higher order function is a function which does at least one of the following two things:

1. it takes a function as an input
2. it returns a function as an output

A normal working programmer more likely than not will use a higher order function in his normal day to day work.

Case 1: Mapping

Simple case in point, if you have use simple SELECT statement in SQL, you have used a higher order function.  A SELECT applies a function you give it against the input it is given from the FROM clause.  Let's use the following statement to illustration this point:


SELECT
    x AS 'value'
   ,(x + x) AS 'add to self'
   ,(x + 1) AS 'increment by 1'
   ,(x * 5) AS 'multiply by 5'
  FROM (
    VALUES (1),(2),(3),(4),(5)
  ) AS value(x)
;

The input given to the SELECT is 1, 2, 3, 4, and 5 from the FROM statement (using the VALUES statement and the AS to create a "table" with the values and a column called x, this will only work in SQL Server, because of the VALUES if you want to use it on a different platform use the UNION ALL for the different values).  We have 4 functions being applied by SELECT to the input given to it.

1. identity function (do nothing)
2. add the value to it self
3. add 1 to the value
4. multiply the value by 5

As one would expect the output is the following (from SQL fiddle):

VALUE	ADD TO SELF	INCREMENT BY 1	MULTIPLY BY 5
1	2	2	5
2	4	3	10
3	6	4	15
4	8	5	20
5	10	6	25

This is type of higher order function is called a mapping.

We can do the same thing in F# using the following code:

let values = [1; 2; 3; 4; 5];;

values |> List.map id;;
values |> List.map (fun x -> x + x);;
values |> List.map (fun x -> x + 1);;
values |> List.map (fun x -> x * 5);;


Using List.map we are able to apply a function against each member of the list, this is exactly what we did in the SQL above!  This F# code gives use the exact same output:


>val values : int list = [1; 2; 3; 4; 5]

> val it : int list = [1; 2; 3; 4; 5]
> val it : int list = [2; 4; 6; 8; 10]
> val it : int list = [2; 3; 4; 5; 6]
> val it : int list = [5; 10; 15; 20; 25]

Case 2: Filtering

Another simple case of everyday use of higher order functions would be the simple WHERE clause again from SQL.  The WHERE clause applies Boolean functions you give it against the input it gets from the FROM clause.  If the output of the Boolean function with the given input is true then the value is passed on, if it is false then it is filtered out.  Let's use the following statement to show this:


SELECT
    x AS 'is even'
  FROM (
    VALUES (1),(2),(3),(4),(5)
  ) AS value(x)
  WHERE (x % 2) = 0
;

This statement filters out the odd numbers using the modulo operation and compares the result against the value 0, thus if the number is divisible by 2 (and hence even) then it is include in the output given to the SELECT statement (which is doing a simple mapping using the identity function).  The output is again as one would expect (from SQL fiddle):

IS EVEN
2
4

This is called filtering in higher order functional terms.

We can do the same thing in F# using the following code:


let values = [1; 2; 3; 4; 5];
 
values |> List.filter (fun x -> x % 2 = 0);;

Again we are simply taking a list of values and by using List.filter we are filtering out the output using a function which compares the input against the modulo operation with 2 to see if the number is even.  This would give the following output:


>val values : int list = [1; 2; 3; 4; 5]

>val it : int list = [2; 4]

Case 3: Folding

Last simple case for today, when you need to apply an operation against a set of values and this operation should give you a single result say a SUM or AVG windowing function.  This is folding in higher order functional land.

Let's use the following SQL to explore this:


SELECT DISTINCT
    SUM(x) OVER () AS 'sum'
   ,AVG(x) OVER () AS 'average'
  FROM (
    VALUES (1),(2),(3),(4),(5)
  ) AS value(x)
;


We are folding the sum of 1, 2, 3, 4, and 5 into one value, 15, and the average value is 3.

As we can see in the following output  (from SQL fiddle):

SUM	AVERAGE
15	3

We can do the same thing in F# using the following code:


let values = [1; 2; 3; 4; 5];

values |> List.sum;;
(values |> List.fold (fun acc x -> acc + x) 0) / values.Length;;


For the sum we use the built in function List.sum to obtain the value.  For the average we sum using List.fold just to show how List.sum might be implemented.  Then we take the sum and divide it by the number of values we summed giving use the average.  This gives use the following output:


>val values : int list = [1; 2; 3; 4; 5]

> val it : int = 15
> val it : int = 3


There you have it higher order functions with examples in F# and SQL!

Sample code is on SQL Fiddle here and Try F# here.  Enjoy.

Sieve of Eratosthenes in F#

"God may have not play dice with the universe, but something strange is going on with the prime numbers."
Paul Erdős

"Mathematicians  have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate."
Leonhard Euler

Before Caesar, before one anno domini, before the internet, there was the library of Alexander and  Eratosthenes.  Eratosthenes of Cyrene was the third librarian of the library of Alexander.  Among other things, he was the first person to calculate the circumference and tilt of the Earth!

If that was not enough, Eratosthenes summoned a simple prime sieve to find prime numbers.  The Sieve of Eratosthenes works in the following way:

1. list integers from 2 to N
2. initially mark 2 as prime (it is prime)
3. cross off all of the integers which are increments of the marked number apart
4. take the next non-crossed off number and mark it as prime
5. repeat step 3 until all numbers are either crossed off or marked as prime

Visually here is what the sieve looks like:

skip to the end

We mark the prime numbers with green and those that have been crossed off with red.

What would the Sieve of Eratosthenes look like in F#?  Well we would want to have a list created from 2 to N, then a function which would take the head of the list and filter out the numbers from the list that are divisible by the head (I know this is not exactly the same as what is above) and loop back around to the top of the function with the new filtered list.


> let sieve n =
-   let rec aux list =      
-     match list with
-     | [] -> []
-     | hd :: tl -> hd :: aux (list |> List.filter (fun x -> x % hd <> 0) )
-   aux [2 .. n]
- ;;

val sieve : int -> int list

Let's test it (I'll blog about using FsUnit at a latter date, so we'll just use poking around testing for now).


> sieve 3;;
val it : int list = [2; 3]
> sieve 11;;
val it : int list = [2; 3; 5; 7; 11]
> sieve 100;;
val it : int list =
  [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
   73; 79; 83; 89; 97]

> sieve 2;;  

val it : int list = [2]

> sieve 1;;

val it : int list = []

Looks like it works.

How to Find Perfect Numbers with F#

"But no perfection is so absolute, That some impurity doth not pollute."
-- The Rape of Lucrece Ver. 124 by William Shakespeare

"It is reasonable to have perfection in our eye ; that we may always advance towards it"
-- Samuel Johnson in letters to The Adventurer

Few things in life can be said to be perfect, but in mathematics there do exist numbers which are said to be perfect.  A perfect number is a number who's sum of its divisors (other than its self) is equal to its self.  

For exemplification, the number 6 is a perfect number.  Why is 6 perfect?

• 6 is divisible by 1
• 6 is divisible by 2
• 6 is divisible by 3

The sum of 1, 2, and 3 is 6 (e.g. 1 + 2 + 3 = 6).  Thus by the definition of a perfect number given above, 6 is a perfect number.  In fact 6 is the first perfect number (1 is never include in the realm of special numbers).

In order to say that a number is perfect we would need to do the following.

1. Find all of the divisors of the given number
2. Sum up the divisors found in step 1
3. Compare the sum found in step 2 to the input

Above is an example of what the flow would look like with the number 6.  We would take the numbers 1 - 5 as a list of possible divisors.  Filter down to 1, 2, and 3.  Sum 1, 2, and 3 giving us 6.  Last comparing the sum we got from the summing step to the input.  Since 6 equals 6, we would return true.

Hmmm, step 1 sounds a lot like a filter and step 2 sounds like folding.  I bet we can write a simple F# function that can find perfect numbers using a filter and a fold (using fsi.exe and Mono).

> let isPerfect x =

-   match x with

-   | x when x <= 1 -> false

-   | _ -> [1 .. x-1] |> List.filter (fun n -> x % n = 0) |> List.sum = x

- ;;

val isPerfect : int -> bool

In the function above we pattern match anything less than and including 1 as false, since by definition those numbers are not perfect numbers (if we wanted we could go up to and including 5 since 6 is the first perfect number).  Succeeding we just need to create a list of numbers up to the number x that we are checking for perfection.  We take this list and filter out the numbers that are not divisors leaving just the divisors.  Then we use the built in folding of summing with the List.sum function.  Finally we compare the sum of the divisors against the input number x.

Now lets test out the function with the perfect numbers 6, 28, and 496.  We'll also test with the less than perfect numbers of 5 and 99.

> isPerfect 6;;

val it : bool = true

> isPerfect 28;;

val it : bool = true

> isPerfect 496;;

val it : bool = true

> isPerfect 5;;  

val it : bool = false

> isPerfect 99;;

val it : bool = false

In fact if we wanted to we could use this function with List.filter against all of the numbers from 1 to 9999!

> [1 .. 9999] |> List.filter isPerfect

- ;;

val it : int list = [6; 28; 496; 8128]

That is in fact the first 4 perfect numbers which were known to the Greeks.

Note, this code is made to be readable not to be fast a few changes should be made to make it fast.

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!

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.

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.

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.