Monday, August 31, 2009

code snippets

I think I have found a way to post java code snippets into blogger. Netbeans will export selected code into an html file and the code is formatted nicely. I had only to put a few lines of style (if I can't have class, at least I have style, right?) into my blogger layout. The result is a bit tidier than the screenshots and it can be copied as text, for those of you who like to do that sort of thing.

On the down side, I think that blogger decided to lose my fern picture in the title box during all of that. Conservation of formatting, no doubt.

Saturday, August 29, 2009

isPrime algorithm

This is something of a continuation of my previous post. I stalled out trying to post the code snippets, posted them as cropped screenshots, and finally discovered a mildly convenient way to export from netbeans to html and paste into blogger with the help of a few lines of css in my blog layout.

I find the Project Euler problems helpful because they challenge you to tidy up the algorithms. A question may be of a very approachable nature for small numbers, but the solution for large numbers relies on a solid understanding of what is necessary and sufficient to find the solution.

For example, if you want to create an algorithm that returns "true" if a number is prime and "false" if it is composite, then you might start with this:

public static boolean isPrime(int args){
int n = args;
for(int i=2; i<n; i++){
if(n%i==0){
return false;
}
}
return true;
}

...which works by checking every integer in the closed interval [2, n-1] as potential factors of n. The condition n%i==0 uses the modulus "%" operator and it is true when the remainder when n is divided by i is equal to zero. If there are any factors of n on that interval, then the code will return a value of "true".

With small numbers and simple tasks, the computer calculates quickly enough to make this seem like a good algorithm. For example, I can use this algorithm to learn in the blink of an eye that 370009919 (for example) is not a prime. However, it wastes a lot of energy and in some circumstances, a lot of time. It is wasteful because it checks 370009917 potential factors. If 370009919 is a composite number, then once we have learned that 2 is not a factor, we do not need to look at other even numbers. We could use:

public static boolean isPrime(int args){
int n = args;
if(n==2){
return true;
}
else if(n%2==0){
return false;
}
for(int i=3; i<n; i=i+2){
if(n%i==0){
return false;
}
}
return true;
}

...which still covers all of the possibilities, but after determining that 2 is not a factor, it will not look at any more even numbers because i goes up by 2's from 3. It is still quite wasteful, however.

If 370009919 is a composite number, then it must have a factor smaller than or equal to its square root, which is about 19236. If we pass the square root without finding a factor, we know the number is prime and we can stop. This effectively allows us to stop after 1/19236 of the work that the previous code ordered. We can take a square root of an int using Java, but the value will be a double. We can still compare our int i to the double sqrtN, but this time we want less-than-or-equal-to "<=" instead of less-than, since the maximum value of the minimum factor may be equal to the suare root, as would be the case for the square of any prime number.



public static boolean isPrime(int args){
int n = args;
double sqrtN = Math.sqrt(n);
if(n==2){
return true;
}
else if(n%2==0){
return false;
}
for(int i=3; i<=sqrtN; i=i+2){
if(n%i==0){
return false;
}
}
return true;
}

The code above is correct as long as Math.sqrt(n) is never less than the actual square root of n. If rounding errors and the hidden Java algorithm that computes "sqrt" might permit such a thing, then the code would possibly be incorrect. I could (A) look at the documentation to reassure myself, (B) conservatively make the second condition of the for-loop read: i<=(sqrtN+1), or (C), test the code for all squares of known primes in the range of int values to see if it correctly detects the factor every time. Also, this code will only return a true or a false. If I want to know the factor that was found, I can add a line of code to print out the factor as soon as it is found.

public static boolean isPrime(int args){
int n = args;
double sqrtN = Math.sqrt(n);
if(n==2){
return true;
}
else if(n%2==0){
return false;
}
for(int i = 3; i<=(sqrtN+1); i=i+2){
if(n%i==0){
System.out.println("found a factor: "+i);
return false;
}
}
return true;
}


The smallest factor is 1699.


I have not looked around to see how this algorithm could be further improved. It is a good idea to skip the evens after we determine that two is not a factor, but skipping the multiples of three (or five, and so on) would be, I suspect, too costly to provide an advantage. The BigInteger class has a method that determines if a number is prime, but I do not know if we are guaranteed more efficiency there, and I do not understand the cost should I need to convert to a BigInteger just to find out. I have seen references to the use of stored lists of primes, which would cut down execution time, but it does not address the programming question of primality. Also, if Java's square root algorithm is considered cheap, we could just replace "i<=sqrtN" with "i*i<=n". This would cost an extra multiplication for every value of i, but we could avoid finding the square root.

Many of the more sophisticated primality tests are designed to be quick and probabilistic, meaning there is a small chance that they will give an incorrect result. However, according to Wolfram Mathworld, the fastest general deterministic test, giving absolute certainty, is "Elliptic Curve Primality Proving", which recently took only six years of CPU time to verify the primality of a 20562-digit prime number.

Friday, August 28, 2009

to start programming

Luke commented on my last post:
I took Java as an undergrad but remember none of it. IF I want to start working on these problems as well as working on programing. What would you suggest... What Language? Helpful Sites? What programs I will need? Books to buy?

Disclaimer: what follows is all very basic but (I hope) at least moderately correct. I am really not a computer programmer and I only presume as far as to say that I am learning and I do enjoy it.

I recommend using Netbeans, which is an IDE (Integrated Development Environment) that can be downloaded from here. Netbeans is the first program of this type that I have used, so I know there are people out there that would argue for other IDE's. Netbeans and the Java Development Kit (JDK) are both free, sponsored by Sun Microsystems. Netbeans is very helpful because it will alert you (without being very distracting) when you have made a syntax error, or when you have created a variable that is not used for anything. Netbeans suggests methods while you are typing, but not in a way that I feel interferes in case you do know what you want to type. It also dims out the code that is 'commented out'.

I work on a need-to-know basis. I try to challenge myself just enough to make use of what I know while learning a little bit at a time. It is a fairly experimental process, so as you try new things you need to be writing programs in which you understand all of the code except maybe one or two lines. As a task becomes more interesting and more necessary, you will find the curiosity to look up how it might be done.

For example, I am getting pretty comfortable with int's, long's, double's and BigInteger's, but there are a few problems that will require me to learn some things about dealing with text, and I have simply not gotten around to it yet. As I try to gain some new skill, I move in little steps. A programmer is supposed to begin with a "Hello, World!" program and go from there. I recommend constructing a few simple programs using the tutorials. After you have something that at least returns a result without errors, you can begin to define variables and construct algorithms.

Sun has some Java tutorials (here is an example) as well as full documentation for the Java language (here is an example). The tutorials include code and some explanations, while the documentation is very technical but it explains the properties of each instance of a given class.

When using Java, you will need to learn the differences of data types. For example, a variable which has been defined as an int cannot exceed a certain value, 231-1 = 2147483647. Its minimum value is -231 = -2147483648. This is because the variable is given 32 bits of disk space, one of which is a sign bit to signify (+) or (-). If your application will encounter bigger numbers than what is expressible as an int, you will need to prepare for that by initiating the variable as a long (64 bits) or a BigInteger, which has arbitrary precision. Sometimes you will need to convert between data types, and sometimes that will involve the risk of a loss of information.

Netbeans supports a trial and error learning technique. You can make small changes in your code and execute the program with a right-click of the mouse. You can track the value of a variable (to see if it is undergoing the changes you are trying to inspire) by putting this line in your code:

System.out.println("a label in quotation marks: "+variableName);

You can use this line to keep track of the progress while the program is running, to see if an anticipated condition is ever met, or to observe where the program stopped doing what you wanted it to do.

There are various tutorials and message boards around the internet, and even reading information about a different language may be helpful. Netbeans has been invaluable as I have been learning the Java language and syntax.

Wednesday, August 26, 2009

the prairie

A few days ago I finished reading The Prairie by James Fenimore Cooper. Grandpa gave me that book a few years ago after he and Grandma took a meandering trip westward along Lewis and Clark's route through the American West. He picked it up along the way. I didn't read it until now.

The main character is in this book quite an old man, but Cooper alludes to different parts of his life as told in the previous books, of which I have read only The Last of the Mohicans. The character is one Natty Bumppo, a man of the frontier, a warrior, woodsman, and wanderer. In this book he is referred to only as "the trapper", with but a single mention of the initials of his proper name. He is above all honorable and unassuming. The bit about his identity though... In each of the books, he is something else to the people around him and he is called by their perceptions. Near the end of his life, this man of few possessions, having lived such an unfettered existence as God gives the grass of the field, asks for a stone on his grave, bearing his name. His name, used so seldom in his life--it does not appear in this book--is treasured and protected as the very center of his identity.

Tuesday, August 18, 2009

new hobby

I have stumbled across this website off and on through my education and the forces which inspire participation have finally converged in time and space to affect my joining up.

Project Euler is a website which simply poses questions of mathematical (primarily number theory) interest which generally require a clever algorithm and expression in some computer language. The questions are well stated and challenging.

You can register and let the site keep track of which problems you have solved. When you solve a problem, you can look at a message board with comments and code snippets from people who have also already arrived at the solution. This has been a good challenge for me as I try to learn and relearn how to program.

The last problem I solved (don't worry, I won't give away the answer) asked for the sum of the prime factors of 20,000,000C15,000,000, which is a rather large number that can be found about a quarter of the way through the twenty-million and first row of Pascal's triangle, but I rarely write that many rows.

Leonhard Euler was a Swiss mathematician who would have enjoyed these problems. Blind and hundreds of years before Java, he still would have knocked the socks off the likes of me.

Sunday, August 16, 2009

between the clouds

Rows and floes of angel hair
And ice cream castles in the air
And feather canyons evrywhere
I've looked at clouds that way
-Joni Mitchell

I took this picture from our neighbors' front terrace. We sipped tea with Dot and watched the drama of the firmament against the rare clarity of this particular monsoon afternoon. It was very clear when we arrived, and I took this picture just after the last fir-covered hilltop was smothered by the clouds. I have always been perplexed to find myself between two ranges of clouds which each seem to know their place. The tops of the bottom clouds and the bottoms of the top clouds seem so content with their boundaries that I stare puzzled, stuck in the middle of it all. Another fifteen minutes and our own hill was in a dense fog.

Wednesday, August 12, 2009

to burn or not to burn

This one is for my sister Sarah. I guess I have been mulling over her blog post from May about "hyperbaking" and a more recent post of hers about finding the proportion of the benefits gleaned from biking and running. At the very heart of it she is talking about fastidiously saving calories while cooking and ravenously consuming them while exercising. Something about the juxtaposition of these ideas struck the ironical chords that reside deep within me. Cooking like Bob Cratchit thaws his fingers by a candle and exercising like Nebuchadnezzar's slave stoking the furnace.

Essentially, hyperbaking or hypercooking is a neat way of not wasting as much heat. You cook noodles, for example, by bringing water to a boil and turning off the flame, letting the heat of the water do the cooking. You throw out less-than-boiling water instead of boiling water and you have used that heat in a more productive way than usual. It is a good idea, but of course it would be a bit of work to get the timing correct for a given project. I suppose there are recipes around to help with that. On the downside, it seems counter-productive if you are just making some sort of yummy dessert to power your not-so-pragmatic running habits.

Sarah's recent post about running a mile being equivalent to biking four miles made me think of this post by Steven Levitt on the Freakonomics blog. He suggested that recreational exercise should be taxed for its consumption of fuel and ultimate acceleration of global warming. In my own twisted fashion, I could not help but wonder if running a mile is somehow equivalent to burning a styrofoam cup. Or three.

Ah, global warming... Unless of course it turns out to be global cooling, in which case we will need to be less efficient in all that we do, right? We would probably have a "cash for hybrids" program and redistribute all of those globe-warming machines that are so uselessly sitting around now. We could then feel free to start a nuclear war, and environmentally-conscious people would probably popularize hypobaking, in which one does not shut the oven door. And recreational exercise would naturally be encouraged.