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!

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 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!

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.