On the 5th of September I began as a trainee
consultant for QA Consulting located up in Salford Quays in Manchester. I had
real difficulty finding a place to stay with my friend who also began with QA
on the same day. Eventually after hundreds of enquiries for housing, a single
positive response came back and we were able to move in into a small flat only
eight minutes’ walk away.
The Salford Quays area looks great and must be one of the
best looking areas of Manchester (in my opinion) and it’s also just a bridge
away from Media City, where the BBC has decentralised from London up to Greater
Manchester.
We started going through Java at breakneck pace. Since I’ve
studied computer science for years I could easily understand and complete the
content required for each deliverable numbering twelve in total. It did contain
some interesting and thought provoking topics, which could be expanded over the
week. We started with the typical ‘Hello World’ applications expanding to
simple string manipulations, then onto a basic object oriented designs of
software and small calculator based tools such as a room painting calculator
that worked out the best paint to buy.
We then moved onto algorithms for prime numbers, tasked with
calculating numbers up to 3,000,000 and 3,000,000,000. My initial design
handled the 3 million with relative ease solving it in 2959 milliseconds a
reasonable result however ground to a halt when dealing with 3 billion, due to
the combinatorial explosion nature of the search space.
private static Boolean isPrimeNumber(long n)
{
if (n < 2) return false;
for (long i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
I then looked for faster and more efficient algorithms for
calculating primes and discovered the Sieve of Atkin a modern algorithm created
in 2003 by Atkin and Bernstein. One limitation of this is that it can only be
used for a maximum number of the integer limit (2147483647) and java does not
provide uint types or cannot initialise arrays of size long, fair enough since
a Boolean array of 3 billion would be roughly ~30GB. It does however do 2.14
billion numbers in 2248 milliseconds, and 3 million in an incredible 24
milliseconds.
//Sieve of Atkin
Arrays.fill(sieve, false);
long startTime, endTime;
startTime = System.nanoTime();
sieve[0] = false;
sieve[1] = false;
sieve[2] = true;
sieve[3] = true;
for (int x = 1; x < limitSqrt; x++)
{
for (int y = 1; y < limitSqrt; y++)
{
int n = (4 * x * x) + (y * y);
if (n <= limit && (n % 12 == 1 || n % 12 == 5))
{
sieve[n] = !sieve[n];
}
n = (3 * x * x) + (y * y);
if (n <= limit && (n % 12 == 7))
{
sieve[n] = !sieve[n];
}
n = (3 * x * x) - (y * y);
if (x > y && n <= limit && (n % 12 == 11))
{
sieve[n] = !sieve[n];
}
}
}
for (int n = 5; n <= limitSqrt; n++)
{
if (sieve[n])
{
int x = n * n;
for (int i = x; i <= limit; i += x)
{
sieve[i] = false;
}
}
}
We then covered a couple comparison algorithms before moving
onto a remake of the classic Battleships board game. A turn based game that
requires placing ships onto two grid based boards; ships come in varying length
and can be rotated for different orientations. The players then take turn
firing blind into the opponent’s water, if they hit a ship a confirmation will
be returned to the user. Once all ships are destroyed by one side the game is
won.
For this project I used java’s swing, my first time using
the technology, to create two grid shaped boards comprised of JLabels that
could be hovered over and clicked to place a ship in each location, a simple UI
had also been created to allow users to see the numbers of each type of ship
placed and eventually would contain other information useful to the player.
While I did create a working application it did not contain the second phase
where users fired missiles at each other, users could paint their ships on the
board, akin to the application paint.
Overall a successful first week QA Consulting and looking
forward to more.
No comments:
Post a Comment