Code Optimization

In this entry I will discuss ways for optimizing your coding combined with good practices when developing programs. In my first blog entry I discussed how I developed my algorithm for square root calculation but I didn't go through the how I converted the algorithm to code. Here are a few things that you should try to apply when coding:

1) Attempt to use a "top down" design
Top down design means to take high level concepts and break them down to simpler concepts. If we use the square root code as an example, here is how I would code the program top down (spelled out in plain English with defined variables)

Top level of program

1. Get the User input
2. Do Simulation

Second level of program

Get the User input

1. valueOfC = readDouble("Enter a value to calculate the square root: "); //Lowest level possible

Do Simulation

1. Check input versus assumptions
2. If the input does not cause error, go to calculation else display error message

Third level of program

Check input versus assumptions (Lowest Possible Level)

• If valueOfC < 0, set canSimulate to false
• If valueOfC = 0 set guessValueOfX = 0, numberOfIterations = 1, canSimulate to true
• If valueOfC = 1, set guessValueOfX = 1, numberOfIterations = 1, canSimulate to true
• If valueOfC between 0 and 1, set rangeMax = 1, rangeMin = valueOfC, guessValueOfX = (valueOfC + 1) / 2, numberOfIterations = 1, canSimulate to true
• If valueOfC greater than 1, set rangeMax = valueOfC, rangeMax = valueOfC, rangeMin = 1, guessValueOfX = (valueOfC + 1) / 2, numberOfIterations = 1, canSimulate to true

Java code for assumptions

If no error, do calculation else display error message

• If canSimulate is true go to midpoint algorithm to solve problem else go to error message output

Java code for checking simulation

At this point the 4th level would explain what is contained in doing the midpoint calculation and how to display the error message. If you look at the optimized code posted on my share location, you will see there are a few more levels before the code is complete. The point I am trying to drive home here is that outside of the strictly Java commands (Lowest level of coding), the commands that I am calling do not exist while I am building that level of the code but later created when I am programming at that lower level, thus Top down design.

2) Use comments to explain various parts of your code

Comments do not affect the execution of the code. This means if you want to put a paragraph giving a brief explanation of what is happening during a section of the code, is probably valuable for you or another programmer to troubleshoot later. Without putting comments in certain areas, if you run into simulation problems or unexpected behavior, you may not have a good clue what is causing the issue. My general rule of thumb is to comment on what you expect to happen within each function or method you create and the expected state or outcome of the method. Also it is a good idea to have an area for a variable definition/description section. This way you can help yourself and/or other coders understand what a variable or constant may be used for if they don't understand based off the name or usage of the variable.

3) Account for potential user error or program exceptions

In the square root code, there is not many places that you would want to account for error or exceptions but I did attempt to account for an exception in the check assumptions section of the code. If you look at the snapshot of the assumption code above, I coded for all other cases outside of the assumptions we listed to display the error message. Since all possible numbers were accounted for, that portion of the code should never be utilized, but error that is the example I attempted to display. In reality, you would do error checking on inputs (like the user input) and connections to external items like files, databases or something that is dynamic. Our code that reads the user input has built in error checking, so if you enter a letter, it will spit out a message letting you know that is an invalid input and take you back to the collect user input code. One suggestion I would make is that you could add a maximum iteration check. Let's say you lower the tolerance check to 10^-10 trying to get an exact value, you could end up with billions of iterations! For the most part, your computer could handle it but if you have a really high complex simulation you may want to stop at some max value and display some note letting the user know they hit the maximum of iterations.

4) Don't get frustrated when you are debugging

Complex coding can usually get you into many creation of many "bugs" and strange behavior that is not expected even with good coding style. Assuming that you utilize good "top down" coding design and utilize comments whenever possible, you should be able to narrow down what is causing the unintended behavior.

Hopefully this blog is helpful. In the future, I will have good examples of coding for exceptions and how to account for potential error. Also I will write a blog entry on debugging but at this time, I would like to get a few more coding examples out there before I do that.

If you want to find the optimized square root code you can find it at this link.

If you want more information on Java coding style and top down programming watch lectures 2 through 4 on Stanford's YouTube page.

Syd

Next entry - Fun with Graphics part 1 of 5

How to calculate the square root of a number using simple Java

Overview:

For a simple problem of calculating the square root of a number, I will lay out a simple algorithm that can be applied in any language without too much difficulty. Since I am focusing on Java, all code snippets will be coded with Java. The project will also be posted.

What you may need:

To create and compile your code, download a Java IDE (Integrated Development Environment) like NetBeans or Eclipse. If you would like an easy to follow self paced instruction, check out the Youtube playlist from Stanford University. I suggest lectures 4 through 8.

Problem statement:

Without getting into too much theoretical mathematics, the mathematical solution to the equation:

is

Where c is the number you want to calculate the square root of and x is the solution that you will seek. The equation does not intuitively give you a methodology but  we can use the first equation to see how close we are to finding the solution.

Assumptions:

The assumptions made here is based off advance algebra/pre-calculus concepts. For the purposes of this demonstration, the assumptions listed below will hold true in all cases.

• c can not be a negative number
• if the value of c is 0, the value of x is 0
• if the value of c is 1, then the value of x is 1
• if c is greater than 1, then the value of x will be less than c but greater than 1
• if c is between 0 and 1, then the value of x will be greater than c but less than 1

Equation for assumption in bullet #4

Equation for assumption in bullet #5

Proposed algorithm:

For any problem you want to resolve with code, you need to build an algorithm. What this means is you need a stepwise method to solve your problem.

My approach is first list your known constants and assumptions. This is something that can be coded in the early stages of the code. Next determine a logical process for the code to follow. The best way to look at this is building a flow chart as shown below.

Sample Flow of Program

Once you have determined your process flow, think about any sub-processes or contained algorithms that you will need. If you notice in my drawing, I have "Find x between c and 1" located in one of the process boxes. Once you figure out how you will do that, you will just build another logical flow for that process. Your process building will end once you are at a point where you can determine if you have found x or a very close solution to x.

I will utilize a take on a method I learned in my Numerical Methods class in college called midpoint finding. Since I know that x will have to exists between 1 and c for both assumptions #4 and #5, I can look at the midpoint value between 1 and c and set that equal to my guess for x. If I square the value of my guess and it is larger than c, I look at the midpoint between my guess and 1 and repeat until I get a guess that is within some defined tolerance that I will define. Similarly, if I square the value of my guess and it is smaller than c, I look at the midpoint between my guess and c and repeat until I reach a desired x. I will lay out the details of how this is done a little later because you may want to switch back and forth between smaller and larger depending on how small your tolerance is set to.

To solve the current problem at hand, I propose we use the following logic: (represent with graphics)

1) Gather user input and store to a variable I will call valueOfC which will be the value of c in the equation.

User Input

2) Compare valueOfC to each assumption

    a) If the valueOfC is less than 0 go to the output part of the program and tell the user "Can not calculate value"

    b) If the valueOfC is equal to 0, set a variable call numberOfIterations to 1 and guessValueOfX equal to 0 go to the output part of the program and tell the user "The Square Root of 0 is 0. It took 1 iteration to calculate".

   c) If the valueOfC is equal to 1, set a variable call numberOfIterations to 1 and guessValueOfX equal to 0 go to the output part of the program and tell the user "The Square Root of 1 is 1. It took 1 iteration to calculate".

   d) If the valueOfC is between 0 and 1, set a variable call rangeMax equal to 1, numberOfIterations to 1, rangeMin equal to valueOfC, and the guessValueOfX to the midpoint between rangeMax and rangeMin. I will send the variables valueOfC, guessValueOfX, rangeMax, and rangeMin to the goal seek algorithm.

   e) If the valueOfC is greater than 1, set a variable call rangeMax equal to valueOfC, numberOfIterations to 1, rangeMin equal to 1, and the guessValueOfX to the midpoint between rangeMax and rangeMin. I will send the variables valueOfC, guessValueOfX, rangeMax, and rangeMin to the goal seek algorithm.

3) Goal seek to find final answer

    a) Determine how close your guess is to the searched value for x. I will build the seek algorithm based on the following equations:



How to determine if you have solved the problem



We square the value of guessValueOfX and subtract valueOfC and set that equal to a variable called errorValue. I will then take the absolute value of errorValue (the number without the negative sign if the variable comes out less than 0) and set it equal to a variable called goalFind. goalFind can be compared to a tolerance constant (toleranceCheck), which I will set to 0.0001 (.01%). To refine our guess value, there is three possible outcomes for errorValue and goalFind

         i) If errorValue is less than 0 and goalFind is greater than toleranceCheck, then set rangeMax equal to guessValueOfX and add 1 to the numberOfIterations, set guessValueOfX equal to the midpoint between rangeMax and rangeMin. Go back to the start of goal seek algorithm.

         ii) If errorValue is greater than 0 and goalFind is greater than toleranceCheck, then set rangeMin equal to guessValueOfX and add 1 to the numberOfIterations, set guessValueOfX equal to the midpoint between rangeMax and rangeMin. Go back to the start of goal seek algorithm.

        iii) If goalFind is less than or equal to toleranceCheck go to program output telling the user the final value of guessValueOfX and the number of iterations it took to get there.

How to build this program:

For demonstration purposes I will utilize Eclipse IDE. You can download the program at the Stanford Eclipse link or a Google search for Eclipse. I will utilize the Console Java window so download the acm library file from the Java Task Force page or Google search acm.jar.

This blog will be the only time I will go step by step on project creation and code generation.

Once you have Eclipse open, you want to create a new Java project:

Create New Java Project

Name your project

I named the project SquareRootCalculator. Click Next to move on to the settings for your project. Click on the Libraries tab and click Add External JARs... 

Library tab

Add the acm.jar file

Once the acm library file is added, create a class file by right clicking the project name. This will be the file where your code will be created.

Create Class File

 I named the class file MySquareRootCalculator

Name your class file

You will now have a blank program with one line of code:

public class MySquareRootCalculator {

}

Initial code

Above the first line of code, we need to add an import statement which would bring up the console window:

import acm.program.*;

Import acm.program

After the import acm.program is added to your code, you have to add the text "extends ConsoleProgram" after MySquareRootCalculator

Extending to ConsoleProgram

Below the public class portion of the code, the following code needs to be added:

public void run() {

}

Establishing run method

Now you are ready to actually implement the program.

Between import acmprogram.*; and public class, you can make comments regarding the code using either "//" to make a line a comment line (portion of the code that is used for note taking only, "/* */" to make a comment block of code that will allow you to put comments for multiple lines between the * or "/** */" to make a special set of comments called Javadoc comments. I will add an error suppression piece of code because of serialization. You can read more at this Google link.

Between public class and the run method, I will define our variables and constants.

Variables and constants


In our run method is where I will put the guts of the code. All the algorithms will be built in between the run method's { }s.

Here is a quick snapshot of the code:

You can find the full project at this link.

Thank you for reading. The next blog will be about Code Optimization.

Syd

Intro to building specialized software

Hello World!

As some of the people who may have some experience to building or creating programs know, writing a sample program to display those words are suppose to give you the confidence that you can conquer the language at hand. The goal of my blog is to give you insight on how I am developing my software, what programming language(s) that I will use and how I develop my algorithms. If you are reading this, please feel free to use my ideas or provide suggestions if you have any.

Now on to business...

Since me and my business partners are looking to create a software package that will do massive amounts of calculations but be available on any environment, I will start doing development in Java. Without giving a Java history lesson, the language does not require a specific compiler for each and every operating system that exists. It only requires that a Java Virtual Machine exist on that particular device. This means you can pretty much put your code anywhere and have it do what you need it to do. The downside is that your coding style could greatly affect the performance of your program/application, so utilize good coding techniques. At some point in the future, other languages may be utilized for other various reasons, so be on the lookout if I switch gears.

Without jumping into what my business is about, I will set up small example problems and display my logic each blog. I will provide my source code if you would like to test or use it to help you build code of your own. My hope is that after you read my blog and start to create sample code of your own you will have the urge to create your own specialized software.

Next blog - Write a program to calculate the square root of a number doing simple math