Over the past week we’ve moved all of our hosting to the bigger, better, faster servers at **DreamHost**. So far so good!

### Australian telephone tones

I made this set of telephone tones for an IP-PBX running asterisk. A lot of telephone-related audio files on the Internet seem to be recordings of actual beeps, so the quality is not great. Given that they are trivial to synthesise with Audacity, I made these:

- Dial tone
- Busy tone (or single tone to loop)
- Call waiting tone (or single tone to loop)
- Ringing tone (or single tone to loop)

To convert them to `.ulaw` format for asterisk (click here to download archive), I saved them as a `.wav` file and ran this bash script over the directory:

```
#!/bin/bash
for a in *.wav; do
sox $a -r 8000 -t ul $a.ulaw
done
```

### Making tones for other countries

Get a copy of the document "Various tones used in national networks (According to ITU-T Recommendation E.180) (03/1998)". It describes the tones used in most of the world. There is also a Cisco tones database, which has slightly different numbers.

Open up Audacity and use the **Generate → Tones** feature to make the first beep. Where there are multiple frequencies, make each frequency in different tracks, then merge them into a single track.

Use **Generate → Silence** to add the delay on the end, then continue from there

Afterward, you need to normalise the volume. Read the number from the volume Cisco tones database, then use **Effect → Amplify**, and set the new peak volume to the value shown — for the above tones this is -10 or -13dB.

### HP Mini 210 review

I used a HP Mini 210 netbook for around 18 months. It costed just $329 AUD when I bought it, and had Windows XP and a 160GB hard drive.

I was originally interested in dual-booting Windows alongside Linux, but HP support proved to be very stubborn and would not provide recovery disks or the Windows licence key, so I ran it with only Linux instead.

Here are some features to note:

- An SD card can be placed in the slot and stays out of the way.
- The VGA port makes it suitable for doing presentations.
- The battery life is not fantastic. Around 3 hours when new, and reduced to just 20 minutes or so by the first year.
- Not particularly durable. The right-click stopped working on the mousepad after a while. I enabled mac-style gestures in Ubuntu to overcome this.
- The ventilation is poor. It has no vents on the bottom at all, which is great for keeping the inside dry, but it has a very weak fan and does not handle heavy loads gracefully.

Some things you can do to improve it.

- As soon as I found out how to open the case (video), I got an Intel SSD, which was quite expensive, but can be used in whatever netbook you have. It makes it quieter, faster, more power efficient, and removes the shock-sensitivity that plagues notebook hard-drives.
- Consider getting a high-capacity battery. I replaced the dead standard size one with a cheap 3rd-party battery (link), but it could still do with more power.
- The default install is filled with crapware. Either reinstall windows or run something else. GNU/Linux compatibility is great, and it also runs Windows 7 with no worries. It turns out your Windows XP key is inside the case, so open it up and use it.

It was a good laptop for the price, but not exceptionally fast, durable, or long in its battery life. This netbook should be purchased with the understanding that it will have a short life.

### Alphanumeric phone numbers

Some popular phone numbers (eg. `1300-FOOBAR`) are not numbers at all. If you are running a VOIP server then you may be interested in this snippet of PHP code to convert them into actual numbers, allowing users to dial by typing the more familiar form.

```
function normaliseTelephoneNumber($start) {
/* Return an extension with numbers substituted in place of letters for dialling */
$map = array( "A" => "2", "B" => "2", "C" => "2",
"D" => "3", "E" => "3", "F" => "3",
"G" => "4", "H" => "4", "I" => "4",
"J" => "5", "J" => "5", "L" => "5",
"M" => "6", "N" => "6", "O" => "6",
"P" => "7", "Q" => "7", "R" => "7", "S" => "7",
"T" => "8", "U" => "8", "V" => "8",
"W" => "9", "X" => "9", "Y" => "9", "Z" => "9",
"+" => "+", "*" => "*", "#" => "#");
$new = "";
$hasnumber = false;
$ext = strtoupper($start);
for($i = 0; $i < strlen($ext); $i++) {
$c = substr($ext, $i, 1);
if(isset($map[$c])) {
$new .= $map[$c];
if($hasnumber == false) {
/* No numbers before letters */
return $start;
}
} else if(is_numeric($c)) {
$new .= $c;
$hasnumber = true;
}
}
if($hasnumber == true) {
return $new; /* Return numeric version as appropriate */
} else {
return $start; /* Leaves full words like "joe" or "bazza" unchanged */
}
return $new;
}
```

Note that this will only alter the number if it begins with numbers. This is to make sure that (at least in my case) the local network extensions don't get messed with:

```
echo normaliseTelephoneNumber("1300-FOOBAR")."n"; /* 1300366227 */
echo normaliseTelephoneNumber("mike")."n"; /* mike */
```

### Introducing BigInteger

Most ordinary-scale programs don’t use very large numbers, but today I’ll show you how to use Java to do some more serious calculating, with the Fibonacci numbers as an example:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …

The numbers in this sequence always get larger, so you don’t need to be a software engineer to see that `int` and `long` wont be big enough. Just to highlight the problem, here is a naive approach to listing the Fibonacci numbers:

```
class FibonacciLong {
static long solutions = 0;
public static void main(String[] args) {
long num1 = 0;
long num2 = 1;
long tmp;
solution(num1);
solution(num2);
while(true) {
tmp = num1 + num2;
solution(tmp);
num1 = num2;
num2 = tmp;
}
}
static void solution(long number) {
solutions++;
System.out.println(solutions + "t" + number);
}
}
```

The output of this program overflows after the 93^{rd} term. Java only uses signed integer types, so we end up with a negative number:

```
1 0
2 1
3 1
4 2
5 3
6 5
....
92 4660046610375530309
93 7540113804746346429
94 -6246583658587674878
```

To find larger values, we can use the `BigInteger` class, under `java.math`. They are constructed like this:

`BigInteger num1 = new BigInteger("0");`

They don’t really work like the primitive types. They are manipulated with methods like `.add()` and `.subtract()`, rather than the operators that we are accustomed to: `+ - * / %`.

The below code has been written with BigInteger instead of long. It will return the n^{th} term of the Fibonacci sequence, or enumerate solutions until the cows come home.

```
import java.math.BigInteger;
class FibonacciBigInteger {
static long solutions = 0;
static long find = 0;
public static void main(String[] args) {
if(args.length >= 1) {
find = Long.parseLong(args[0]);
}
BigInteger num1 = new BigInteger("0");
BigInteger num2 = new BigInteger("1");
BigInteger tmp;
solution(num1);
solution(num2);
while(true) {
tmp = num1.add(num2);
solution(tmp);
num1 = num2;
num2 = tmp;
}
}
static void solution(BigInteger number) {
solutions++;
if(find == 0 || solutions == find) {
System.out.println(number.toString());
if(find != 0) { System.exit(0); }
}
}
}
```

The good news is that this program is now capable of working with numbers too large to say aloud. So today is a good day to start using Unix’s `wc` program to appreciate how big these numbers actually are:

```
mike~$ java FibonacciBigInteger 420000 | wc -m
87776
```

Subtract one character because there is an end-of-line in the output— and this means that the 420,000^{th} Fibonacci number is 8775 digits long. We have discovered a new fact!

**Note:** There is still one variable in the program above that will overflow eventually, so you should also convert that to a BigInteger if you are hoping to calculate past about the nine quintillionth Fibonacci number (which you would be crazy to do with this method).

### Version 0.5 of raycaster released

I have finished porting my raycaster project to java, fixing it up a bit in the process

Based on this screenshot, I kicked up the brightness a bit much (feel free to download the source code and fix that!)

### Palindromes

This is a highly miscellaneous Java snippet to find palindromes.

It will read `stdin` line-by-line and spit back the palindromes it finds.

```
import java.io.*;
class Palindrome {
/* Return palindromes from a given list of words read from stdin */
public static void main(String[] args) {
boolean okay;
String line;
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
do {
try {
/* Read a line, and spit it back again it if is a palindrome */
line = input.readLine();
if(isPalindrome(line)) {
System.out.println(line);
}
okay = true;
} catch (Exception e) {
/* Exception will be raised after end-of-file */
okay = false;
}
} while(okay);
}
static boolean isPalindrome(String test) {
/* Return true if a string is palindromic, false otherwise */
int len = test.length();
if(len <= 1) {
/* Disallow null / single-char palindromes */
return false;
}
for(int i = 0; i < len; i++) {
/* Compare first and last, second and second-last, etc) */
if(test.charAt(i) != test.charAt(len - 1 - i)) {
/* Found different letters, stopping. */
return false;
}
}
return true;
}
}
```

On UNIX, you could feed it a dictionary to list all of the palindromes:

`java Palindrome < /etc/dictionaries-common/words`

On my computer that returns 57 palindromes made from ordinary words:

aha bib bob boob civic dad deed deified did dud eke ere eve ewe eye gag gig hah huh kayak kook level ma'am madam MGM minim mom mum non noon nun oho pap peep pep pip poop pop pup radar redder refer rotor sagas sees seres sexes shahs sis solos stats tat tenet tit toot tot wow

There are certainly more if we allow 1-letter words or case-insensitive matching (allowing all sorts of proper nouns), but I really don't think they count.

### Finding prime numbers

It’s not so hard to calculate small-ish primes. The below method is called a prime sieve, and can be done manually:

Take two, the smallest prime number.

We know that no multiples of two are prime (4, 6, 8, 10, 12 etc), so we can cross them off our list and just print two.

Then we go to 3. 3 is prime. But 6, 9, 12 and 15 can’t be, so we print 3 and cross those multiples off.

4 has been marked as not prime, so we skip it.

5 is prime, so we cross off 10, 15, 20.

so on and so forth

Computers are much better at this than humans though, so I wrote this algorithm up in java. You can find all primes up to *n* fairly quickly (for small values of *n*).

```
class Primes {
public static void main(String[] args) {
int searchMax = 16777216;
if(args.length == 1) {
/* Allow over-riding the maximum */
searchMax = Integer.parseInt(args[0]);
}
boolean[] isprime = new boolean[searchMax];
int i, tmp, count = 0;
/* Initialise */
isprime[0] = isprime[1] = false;
for(i = 2; i < searchMax; i++) {
isprime[i] = true;
}
/* Main loop */
for(i = 2; i < searchMax; i++) {
if(isprime[i]) {
System.out.println(i);
count++;
tmp = i * 2;
while(tmp < searchMax) {
isprime[tmp] = false;
tmp += i;
}
}
}
System.err.println("Found " + count + " primes between 1 and " + searchMax + " non-inclusive");
}
}
```

Of course, the limitation of this is that java isn’t terribly good at handling larger arrays, so I wouldn’t expect more than a few million primes from this code.

**Update:** The above code was tested for finding the first 7 million prime numbers.

### Gettting lost with depth-first search

I was thinking about how to make mazes, and ended up making a maze generator.

It’s based on ‘depth-first search’, a recursive algorithm to make a spanning tree. Example output below:

Unfortunately for us, java doesn’t particularly like deep recursion, so this generator will fizzle out with an error on really big mazes. On the other hand, it can produce output as HTML:

You can download the maze generator here:

- MazeGenerator.jar
- MazeGenerator-src.tar.gz (source code)

It’s a command line program. From the terminal, the usage is like this:

`java -jar MazeGenerator.jar [width] [height] [formatting]`

Width/height will change the size of your maze. You can set the format to ‘html’, or type in a character for the filled-in blocks to be. (The default is u2588 ‘Solid block’).

### Solving the eight queens puzzle

In the eight queens puzzle, you need to place eight queens on a chessboard so that they aren’t attacking eachother. It has 92 solutions.

I implemented one method for solving the problem. It works for any *n*x*n* chessboard, but it’s not so fast with large boards.

- Compiled: Queens.jar
- Source: Queens.java

You can invoke this with `java -jar Queens.jar` for an 8×8 board, or `java -jar Queens.jar n` for an

*n*x

*n*board with

*n*queens.

It works by processing the board in vertical strips, first placing a queen in the top-right, and then attempting to place a queen in the second column at the first available space. Once it crosses the board like this, it has found a solution, but it goes through plenty of bad combinations first.

**Update:** online solution-viewer is now running to make that command-line output more useful.