Friday 16 September 2016

QA Consulting - Personal Blog #1



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