AVR Butterfly: Part 1

10 07 2009

After thinking about doing something interesting like making a robot for some time, I always end up getting bogged down in details and never get around to it. Instead of such a big project, I decided to just pick up an AVR Butterfly demonstration board to play with and learn more about programming micro-controllers. It’s got an d ATmega169PV with 512KB of memory; as well a handful of input/output pins with a built in clock, LCD, temperature sensor, buzzer, voltage sensor and analog to digital converter. It can also (in theory, see below) can be programmed with an RS232 port and no special hardware, and using all free software to compile C code or just program straight Assembly. And all this for only $20, hard to beat. I ordered it from Mouser and got it in the mail yesterday.

For assembly I found that I had a ton of male header connectors, but no females. A trip to radio shack came up with nothing, so I stripped apart an old computer and found what I needed. The cables that go to the serial and parallel port are 10 pin female and work well. Only downside is that they are stranded wire and will be a pain to push into a bread board.

DSCN0794

The connectors are too wide for all 3 of the 10 pin headers, but the middle one I think is just JTAG stuff for the most part and won’t be used for now at least.

DSCN0795

For the RS232 I used the female connector on the end of the power button,  along with a spare pin off a front LED connector.

DSCN0796

The other end just goes to a DB9 I had laying around. Only downside to all this is that it’s quite easy to plug things in the wrong direction.

DSCN0799I hook it up to the RS232 and manage to make it say, “Hello”. After that when I try to actually program a simple C program into it though, I find that I happen to have one of the misprogrammed/recalled AVR butterflies which do not have the boot loader bit set correctly on them. Instead of starting instructions at the beginning of memory, it skips the bootloader and isn’t programmable through the RS232 until I toggle a bit using either JTAG or SPI.  The way to diagnose the problem is to note that when you apply power, instead of sleeping until you press up on the joystick, it will just start tickering AVR Butterfly across the screen right away. It also won’t send the series of question marks to the serial port on boot that are expected. The details on how to change the bit with SPI are elusive, since it’s something most people trying to program chips via JTAG or SPI should already know apparently, and the schematic link I found for using a parallel port to program the SPI was dead, so I’m currently waiting on some forum replies plus an email to Mouser to see if they will do anything about sending me a recalled product. They’ll probably tell me I can send it back and get a new one, but it’s really not worth the trouble, especially if they charge for shipping; and I also soldered on my header connectors already… Worse case I’ll make friends with some people at the lab at work and see if I can get ahold of a JTAG programmer during my lunch break.

Advertisements




Project Euler – Problem 28

24 04 2009

I don’t have much to rant about, Linux has been behaving itself, and with finals coming most of my free time is spent on homework and studying. However, I did get around to solving a couple Euler Problems, so I thought I’d fill the awkward silence of my blog with one of them (although it’s so easy, I don’t expect anyone to be Googling for it).

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7 8  9 10
19  6  1 2 11
18  5 4  3 12
17 16 15 14 13

It can be verified that the sum of both diagonals is 101.

What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?

At first glance I thought about how to generate the spiral inside an array, but after a second more of observation I decided there was no reason to. It’s fairly clear that each loop of the spiral increases the dimensions of the square by 2, meaning the corners are differing from each other by 2 more each time around the spiral. The corners then, can be found by just starting with the sum equal to 1, incrementing the current number by 2 and adding it to the sum (repeating four times), then by 4 four times, then by 6 four times.. you get the picture. Here it is thrown together in C, short and to the point.

#include 
#define SPIRAL_SIZE 1000

int main() {
	int incr, i;
	unsigned int sum = 1;
	unsigned int current_num = 1;

	for (incr = 2; incr <= SPIRAL_SIZE; incr+=2) {
		for (i = 1; i <= 4; i++) {
			current_num = current_num + incr;
			sum = sum + current_num;
		}
	}
	printf("Result: %d\n", sum);
}




A Programmer’s Quest for Primes: Part 1 – Brute Force

4 03 2009

While trying to come up with something to program, I looked to prime numbers in my discrete math class and decided to make a simpler prime number calculator. The deeper I delve into the world of prime numbers the more interested I become. The building blocks of all numbers with plentiful applications in cryptography have captured my spare time recently. This is part 1 of my quest for calculating prime numbers. I have no real goal in this quest, other than to expand my knowledge of mathematics and sharpen my skills of programming; it’s the journey that matters, not the destination.

First off some math. What is a prime number?

Prime Number: A positive integer p greater than 1 is called prime if the only positive factors of p are 1 and p. A positive integer that is not prime is called composite.

For example, 42 is not prime, it can be written as the product of the factors 2 and 28. 28 isn’t prime either, it can be written as 2*14. 14 can be written as 2*7. What can 7 be written as? or 2? Nothing, these are primes. Now a useful theorem.

Fundamental Theorem of Arithmetic: every positive integer greater than 1 can be written uniquely as a prime or as a product of two or more primes.

That means 42 can be written as 2*2*2*7, all of which are prime numbers. 105 can be written as 3*5*7, all prime.

Now, how can you tell of a number is prime? Well, if the number is composite, that means it can be divided by some prime number. You can keep a list of prime numbers and then try and divide that number by them all. If it doesn’t divide by any prime numbers, it’s prime itself. For example, we find a list of prime numbers: 2, 3, 5, 7, 11. Now suppose we want to see if the number 13 is prime. We’d do the following,

13 % 2 == 0? If so prime.

13 % 3 == 0? If so prime.

13 % 5 == 0? If so prime.

13 % 7 == 0? If so prime.

13 % 11 == 0? If so prime.

None of these numbers can divide 13, so 13 is prime. When we get into prime numbers like 576,194,557 though, this process will be doing millions of checks on the prime numbers found before, which will be horribly slow.

A quick way to make a huge speed difference is use another handy theorem.

Theorem: If n is a positive composite integer, then n has a prime divisor less than or equal to sqrt(n).

So rather than checking if 576,194,557 is divisible by each prime found before it, we can just check if it’s divisible by any of the primes less than or equal to 24,004.

Before getting down to the programming, one more quick way to make it more efficient is to count by 2’s, since we know all prime numbers are odd. In fact, prime numbers always end in either 1, 3, 7, or 9. Increasing the number you’re checking for primeness by 2 every time can eliminate checking anything that ends with 0, 2, 4, 6, or 8.

Therefore,  a simple brute force method for finding primes: create an array (in the heap, because the stack will overflow), and store all the primes you find in it. Increase your candidate number by 2, try to divide it by all the primes in the list, and break out of the loop if you find a number that divides it or if you reach a prime larger than sqrt(candidate). The latter means it’s composite and the former means it’s prime. Keep doing this until you find as many primes as you like. My source code for such a program written in ANSI C can be found here, http://pherricoxide.jumbofx.com/code/simpleprimecalc.c. It’s well commented and should compile with any ANSI C compiler. This is the first of hopefully several prime calculators I’m going to write.

Using this program on a 1.4ghz Intel Core 2 Duo with 2GB RAM, the first 100 million primes are found in about 137 minutes.

The problem is, as the numbers get bigger, this program runs slower and slower. The graph below shows time plotted on the horizontal axis and number of primes found plotted on the vertical. You rapidly find primes in the beginning, but after a while it will inevitably take you long minutes just to find a few primes. Using this method, we hardly have to worry about running out of RAM, because by the time we get 2GB of data (around 200 million primes), the process will be going so slowly it will hardly be worth continuing the search, at least using this brute force method.

primes

Stay tuned for faster prime calculations with better code, better algorithms, and someday perhaps even some cluster computing, as I continue my quest for primes. Until then, here are some prime numbers to spot check your own prime calculating programs with.

1 millionth prime: 15,485,863 (found in 7 seconds)

5 millionth prime: 86,028,121 (found in 112 seconds)

10 millionth prime: 179424673 (found in 5 minutes)

20 millionth prime: 373,587,883 (found in 12 minutes)

30 millionth prime: 573,259,391

40 millionth prime: 776,531,401

50 millionth prime: 982,451,653 (found in 50 minutes)

60 millionth prime: 1,190,494,759

70 millionth prime: 1,400,305,337

80 millionth prime: 1,611,623,773

90 millionth prime: 1,824,261,409

100 millionth prime: 2,038,074,743 (found in 137 minutes)