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