Tag Archives: math

Blog, Examples

Gaussian Elimination

Leave a comment

I have just written a script which executes the Gaussian Elimination Algorithm.

When we have a collection of lines we wish to know if they all intersect at some point. Many times we are interested in determining what that point is. In order to calculate this information, we first need an understanding of the lines themselves. The way the Gaussian Elimination Algorithm works is that the collection of lines are input using a notation of Ax = b, where the matrix A is called the coefficient matrix, as the nth row of it corresponds to the coefficients for the nth line being considered. The vector b represents the right hand side vector (in two dimensions, we would call these constants the y-intercepts of the lines. In higher dimensions they hold a similar property). The vector x represents the point where the lines intersect. It is this quantity which Gaussian Elimination seeks to determine.

The basic procedure of Gaussian Elimination is to use \”elementary row operations\” on the matrix (A|b), which is called the augmented matrix, to transform A into upper triangular form. Once this is done, a procedure called back-substitution can find the solution (x) to this problem.

The elementary row operations that we are allowed to perform are:

  • Interchange two rows.
  • Multiply a row by a nonzero number.
  • Add a row to another one multiplied by a number.

    • For the last property listed above, we will determine this number by dividing the coefficient of the term we which to eliminate by the negative of the coefficient of the element on the main diagonal of the same column of the matrix. This will have the property of cancelling out, or producing a desired zero in the resulting row.

    If this algorithm produces an upper triangular matrix from which we can solve for x using back-substitution. This procedure of back-substitution is simply solving for the vector x from the bottom of the matrix to the top. If the algorithm does not produce an upper triangular matrix (because somewhere along the line, we are unable to obtain a ratio because we have zero’s on the diagonal and all zeros below the diagonal), then we say the matrix is singular. This means that there is no unique point where the lines all intersect.

    To learn more and see more examples, check out My Script on Gaussian Elimination.

    Blog, Examples

    The Euclidean Algorithm

    4 Comments

    I remember being in school and learning about fractions. In particular, I remember the problems we had when trying to add and subtract fractions. This problem also presented itself when we tried to multiply fractions, although we still received partial credit if we couldn’t reduce fractions to their lowest terms.

    What I’m referring to is the problem of finding the Greatest Common Divisor (GCD) of two numbers. The GCD of two numbers is the largest number that divides into both numbers with a remainder of zero each time. This problem has many applications, but for most of us we can relate to it because of our frustrations with fractions.

    The algorithm that I’m writing about and have written a script for is called the Euclidean Algorithm, which solves precisely this problem. To be more precise, the Euclidean Algorithm finds the greatest common divisor between two integer numbers.

    There are different versions of the algorithm, but the one I have implemented finds the GCD by subtracting the smaller number from the larger number, and if the result is greater than 0, the procedure repeats itself with the two lower numbers. Otherwise, the result (the GCD) is the final number that was greater than 0.

    Lets see an example:
    Consider the number 9 and 21.
    21 – 9 = 12. 12 is greater than 0, so we repeat the procedure with 9 and 12.
    12 – 9 = 3. 3 is greater than 0, so we repeat the procedure with 3 and 9.
    9 – 3 = 6. 6 is greater than 0, so we repeat the procedure with 3 and 6.
    6 – 3 = 3. 3 is greater than 0, so we repeat the procedure with 3 and 3.
    3 – 3 = 0. 0 is not greater than 0, so can exit the loop portion of the algorithm.
    Since 3 was the last positive number that we arrived at in this procedure, we see that the GCD of 9 and 12 is 3.

    To learn more and see more examples, check out My Script on The Euclidean Algorithm.

    Examples

    Sieve of Eratosthenes

    Leave a comment

    Prime numbers are an important concept in Number Theory and Cryptography which often uses the difficulty of finding prime numbers as a basis for building encryption systems that are difficult to break without going through all (or a very large number of) possible choices.

    Remember that a prime number is a number greater than 1 whose only divisors are 1 and that number itself. One of the most famous algorithms for searching for prime numbers is the Sieve of Eratosthenes. I added a script which implements the Sieve of Eratosthenes to my Examples page.

    This algorithm prints out all prime numbers less than a given number by first canceling out all multiples of 2 (the smallest prime), then all multiples of 3 (the second smallest prime), then all multiples of 5 (the third smallest prime – multiples of 4 do not need to be considered because they are also multiples of 2), etc until we have reached a number which cannot be a divisor of this maximum number.

    So if we are given a number, n, the first step of the algorithm is write out a table that lists all the numbers that are less than n. For example lets run this Sieve on 50. So all numbers less than 50 are

    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.

    So since 1 is not a prime number (by the definition of prime numbers), we cancel that number out.

    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.

    Next, we look at the list and the first number that is not crossed out is a prime. That number is 2. We will put a mark by 2 and cancel out all of 2’s multiples.

    1, 2*, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.

    Again, we look at the list and the first number that is not marked or crossed out is 3, so that number is prime. We will put a mark by 3 and cancel out all of 3’s multiples.

    1, 2*, 3*, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.

    Once again, we look at the list and the first number that is not marked or crossed out is 5, so that number is prime. We will put a mark by 5 and cancel out all of 5’s multiples.

    1, 2*, 3*, 4, 5*, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.

    We look at the list and the first number that is not marked or crossed out is 7, so that number is prime. We will put a mark by 7 and cancel out all of 7’s multiples.

    1, 2*, 3*, 4, 5*, 6, 7*, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.

    Now, we look and the first number that is not crossed out is 11. However, since 11 is greater than sqrt(50) we know that each of 11’s multiples that are less than 50 will have been cancelled out by a previous prime number. So we have finished the algorithm.

    Check out my script which implements the Sieve of Eratosthenes for more examples.

    Blog, Examples

    Examples Page

    1 Comment

    Sometimes, the most effective way to understand a new concept is to actually see it in action. On My Examples Page, I have implemented a variety of scripts to help teach many different concepts.This is the page that is the easiest for me to update, so you will regularly see changes to this page along with an accompanying blog entry at My Blog Page.

    This page is focused on teaching individual concepts and/or algorithms. In particular, with the HTML5 Canvas element, I’ve been able to visualize many of these concepts. Generally I try to provide a script that executes the given algorithm (or concept) and allows for users to view these concepts on random instances. When possible, I provide a button labeled “New Problem” (or something similar) which will allow the user to view a different instance of the algorithm.