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
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