Calculating an exponent in O(log n)

In my algorithms class the teacher challenged us to come up with an algorithm that calculates the value of a base raised to an exponent recursively. Obviously this is quite easy to do in O(n) but he pushed us to figure out a way to do it in O(log n). After playing around a bit I think that I have come up with a good algorithm.


unsigned __int64 exponent(unsigned int base, unsigned int exp)
{
    if (exp < 1)
        return 1;
    else if (exp == 1)
        return base;
    else if (exp % 2 == 0)
    {
        unsigned __int64 retval = exponent(base, exp / 2);
        return retval * retval;
    }
    else
    {
        unsigned __int64 retval = exponent(base, (exp - 1) / 2);
        return base * retval * retval;
    }
}

The algorithm takes advantage of the fact that an x^y = x^(y/2) * x^(y/2). Thus for each cycle it only needs to compute half of the remaining exponent and just multiply it by itself (Since there's only one recursive call for each half we get O(log n) as opposed to O(2^n) if we had done the calls separately). For odd exponents it multiplies the base by the same values computed by the even case. Originally I had it just multiply once like in a linear solution, but this introduced a greater run time for certain exponents. Using a modified version of the even case greatly reduced the number of cycles.

One big caveat is that the data type is limiting. While the algorithm can get the correct result for large exponents, a frequent problem is integer overflow as the algorithm can result in some very large numbers.

Jesse Conner - May 15, 2014 - C++, Code
A Program For Taking a Set Amount of RAM

Yeah, so I got bored one day and decided what better to do than to make a program that asks how much RAM it should take and then takes that much.


#include <iostream>

using namespace std;

int main(void)
{
	int count = 0;
	int bytes = 0;
	char* mem;
	cout << "How much RAM (MB)? " << endl;
	cin >> count;
	bytes = 1024 * 1024 * count;
	mem = new char[bytes];
	cout << bytes << " bytes allocated" << endl;
	cout << "Free?";
	cin >> mem;
	delete [] mem;
}

The character pointer mem is what is used to take up all of the space. The program prompts for count, and then converts that number from megabytes to the number of bytes that need to be allocated. The program then attempts to allocate the required number of bytes. If the program hasn’t yet crashed it will ask the user if they want to free the memory, and once the user responds the memory is freed.

Jesse Conner - January 24, 2014 - C++, Code
My Pretty Little Liars Theory

At first I dismissed the show as “girly” but as I gave the series a try as per some coworkers’ recommendations I quickly found myself wrapped up in the mysteries of Rosewood. Like many other fans I have been patiently waiting since the summer finale back in August for tonight’s Halloween special. Over the last month and a half or so I have been trying to wrap my brain around the mystery surrounding Allie’s disappearance, and the identity of A. I am thrilled to share my theory.

Spoiler Alert!

One thing that has become clear is that someone who looked enough like Allie to avoid any sort of identification died and was buried under the gazebo behind the Dilaurentis house. We know from the autopsy that that individual suffered blunt force head trauma but ultimately died from suffocation, a result of being buried alive. Ms. Grunwald claims to have found Allie the night she went missing and that she took her to the hospital badly beaten. Allie then went missing from Ms. Grunwald’s car and her whereabouts from then on are unknown. This leaves us with two options, either Allie was rescued by some party that we are not yet aware of or possibly ran away by herself, or A captured her and returned her to the gazebo where she was buried for a second time and consequently died. According to Ms. Grunwald, Allie is still alive. I think that it is reasonable to assume that she went looking for Allie after she disappeared. A reasonable place to look would be the site of Allie’s attempted murder. This causes some serious doubts in the theory that she was recaptured and murdered that night.
Additional clues have surfaced over the seasons that Alison is not actually dead. If I recall correctly the person hiding in the Dilaurentis house has still not been explained, and someone obviously saved the liars from the fire at the lodge. Baring any supernatural activity (Which would be a first for the series) I believe that it is a reasonable conclusion that Allie is still alive.
So then who died? I hate to use this, as the show runners have claimed that they’re not doing it, but honestly at this point only the twin theory makes sense. Why kill the twin? Either a case of mistaken identity or Allie had it out for the twin herself. If it was a case of mistaken identity then A obviously clued in shortly afterward as they are still searching for Allie, seeing as Allie seems to be pretty good at staying hidden and how else would A realize that there is a twin, I think we can rule out the mistaken identity theory.
I think that I am going to leave it there. Hopefully some answers will be provided when the episode airs in half an hour.
One side note, Allie was scared of a male when she was in contact with Ms. Grunwald prior to her disappearance. Yet we are told that Mona had been A all along. Mona is accounted for when the Liars find A’s lab. When Ezra shows up at the end he is clearly surprised, yet someone was watching the Liars while they were in the lab (behind the picture). CeCe was at least somewhat incapacitated from her fall, and if Ezra was the one that saved her then how did he get her back to the lab to spy on the Liars without realizing the Liars were there? Ezra is not A, although he may be involved.

Jesse Conner - October 22, 2013 - TV
Simple HTML Countdown Page

Today I set out to make a simple HTML countdown. I was pleased with the results, so I have decided to share my source.

The HTML


<!DOCTYPE html>

<html lang="en" xmlns="http://www.w3.org/1999/xhtml">
<head>
   <meta charset="utf-8" />
   <title>Countdown</title>
   <link href="style.css" rel="stylesheet" />
   <script src="countdown.js"></script>
</head>
<body onload="setTime()">
   <div id="console"></div>
</body>
</html>

This is all pretty straight forward, it is really just a blank page with references to the stylesheet to make it look pretty and javascript to make it work. The only thing really note worthy here is a div (console) to hold the calculated time and a call to setTime() when the body loads. (Doing it prior will cause an undefined element error.

The CSS


body
{
    background-color:black;
    margin: 0px; 
    padding: 0px;
    font:Andale Mono, monospace;
}

#console {
    background-color: black;
    color:white;
    height:120px; 
    position:absolute; 
    top:0px; 
    left:0px; 
    right:0px; 
    bottom:0px; 
    margin: auto; 
    text-align:center; 
    font-size:128px;
}

Once again this is pretty straight forward. By positioning it absolute at 0,0,0,0 and then assigning a margin #console stays nicely in the centre of the page. In retrospect I don’t think that the height is necessary for the element to remain centred.

The Javascript


function setTime() {
    var c = document.getElementById("console");

    var source = new Date();
    var target = new Date(2013, 9, 22, 20, 0, 0, 0);
    c.innerHTML = (target - source);
    setTimeout(setTime, 1);
}

source gets the current time from the default constructor of Date, and then target is the date that you are counting down to. Something worth mentioning is that the month field starts at 0, so to get October for example, you would use 9 (instead of the 10 that you might be used to)

Demo

Feel free to try out the HTML Countdown Sample for yourself and please let me know of any potential improvements (ex. pulling the time with php to avoid client time setting issues) in the comment section below.

Jesse Conner - October 21, 2013 - Code, Web
Reversing a stack in C++

I think that the simplest way to reverse a stack in C++ is to use some basic recursion to assign each element the address of its predecessor. The code goes as follows (building on this sample code)


	void Stack::reassign(Node* lastAddr, Node* target)
	{
		if(target)
		{
			reassign(target, target->_next);
			if(!target->_next)
				_top=target;
			target->_next=lastAddr;
		}

		
	}

	void Stack::reverse()
	{
		reassign((Node*)0, _top);
	}

It’s very short, but the inner working can be confusing. reverse() is publicly accessible and kicks the chain into motion. When reassign() is called it first checks to see if the node that you are trying to reassign exists, if not it breaks the recursion chain (otherwise it would run forever or crash). Next it calls itself with the next node in the list with a copy of it’s address so it can be linked back. When it gets to the end of the chain it assigns that node to the _top of the list. (I got stuck on this at first, without this the stack is simply the last node). As it works its way back to the surface it assigns the address of the node that originally called it to the _next property thus the list gets reversed. (Hopefully that makes sense, It’s kind of hard to explain)

Jesse Conner - October 8, 2013 - C++, Code
New New Go Buses

As a daily rider of public transit I know that the little things matter, and that every design tweak is important to the user experience. I was thrilled to learn that GO was continuing their legacy by bringing a new style of buses into service. Even though the variant of GO buses commonly known as the “New GO Buses” do not seem to be far spread through the system yet, GO has continued innovating with their “New New GO Buses”

At first I was very excited when I saw the distinctive shiny new yellow handle bars upon boarding the bus, but my reaction turned sour shortly after. The new design definitely takes a page from the previous generation. With nice curved seat backs that allow even the tallest passengers to ride comfortably. The air conditioning system seems to be even more effective than that of its predecessor, which is critical during this sweltering time of year in Southern Ontario. As previously mentioned the hand-holds are a nice bright shade of yellow that allow for quick location during the dark of night. They also retain their position on the top of the seats that was previously introduced in the “New GO Buses. Many of the features remain largely unchanged. The stop request is only a thin strip at the top of the window to prevent accidental requests, and the seats adjust using a square slider as opposed to the full length grip that controlled them in the first generation buses.

Despite these nice changes overall the new design feels like a step backwards. Instead of fixing the flimsy plastic t-ship foot rests found on the “New GO Buses” or simply reverting to the metal u-shaped foot rests from the first generation buses Metrolinx disappointingly decided to just remove the rests altogether. Another element of the design that has changed for the worse is the armrests. The new armrests are much wider, which can be seen as a plus, however, because of their shape they no longer push back all the way between the seats. On the plus side this serves as a small barrier between riders on a crowded bus, but on more sparsely populated buses it serves as a painful reminder of its presence when first taking a seat, and continues to remind you of its awkward placement whenever the rider tries to sit in any manner aside from facing straight forward.

While the “New New GO Buses” offer some welcomed improvements over its predecessors, certain elements of the design demonstrate that Metrolinx failed to pay attention to the fine details that can make or break a trip that the average rider takes ten times a week, often for more than an hour at a time. When such repetition is involved it’s the little things that matter, and it is clear that those elements were not taken into consideration.

 

6.1/10

Jesse Conner - September 10, 2013 - Review