Factoring Integers In O(1) Time

27 09 2011

They say that factoring integers is hard. Well, what do they know – this article presents a program which takes an integer (at compile time) and prints its factors in O(1) time. If the number has multiple factors then just one pair will be printed. If the number is prime, then the number itself, times one, will be printed.

Naturally it is impossible to compute factors of an integer in constant time. The trick used here is called Template Metaprogramming. Template metaprogramming is essentially creating a set of C++ templates which encode a program. Algorithms can be represented by a handful of template metaprogramming idioms – there are idioms for conditionals, recursion, expression evaluation, data passing, and more – and if the template is instantiated anywhere in the code, the metaprogram is executed by the compiler at compile time. At this point it is worth noting that template metaprograms cannot contain mutable values; therefore it is impossible to metaprogram regular index-based loops, but recursion must be used instead. This means that trees can be more economical data structures than linear arrays or lists, because the latter needs much more “stack space” (=simultaneously instantiated template objects) than e.g. tree. Anyway, in order to create a program which apparently factors integers in constant time, a vastly greater compilation time must have passed to compute the actual result, but the result is eventually stored into the program code as a plain old constant value.

The most canonical factoring algorithm is trial division. However, in this article I’ve decided to use the Unusual Recursive Factoring Algorithm instead because it uses more economical tree traversal, as opposed to indexed loop needed in trial division. Alas, my fear was unfounded: it seems that the modern compilers (I used MS Visual C++ Express 2010) no longer have limitations to the number and/or depth of template instantiations which they had when I first tried this code for real.

Anyway, here’s the code.

Advertisements




Swapping Without Temporary Storage

21 09 2011

Swapping two variables typically uses a temporary variable. But how do you swap if you are short of storage space? For instance, suppose you have your home keys in your left hand, and a grocery bag in your right hand. If you’re right-handed you’ll need to swap the keys to the other hand in order to open the door, but how do you do that with no temporary storage around?

The following algorithm is perhaps not the most efficient one but it fits the bill perfectly!

template <typename Thing> void Swap( Thing &oneHand,Thing &otherHand )
{
try
{
throw oneHand;
}
catch( Thing falling )
{
oneHand = otherHand;
otherHand = falling;
}
}

Again, the complete code can be found here.

N.B. This article was written tongue firmly in cheek. If you read the code like a story it should appear humorous, but in real world I do not advocate using exceptions as a mechamism for program flow control.





Comma Operator BASICs

15 09 2011

For some of us BASIC was the first programming language we learned. Not because it was pedagogically great, but because it was pretty much the only programming language that was easily available. It came preinstalled on the earliest PC’s as well as the other home computers of the 80’s: Commodores, Sinclairs, Ataris, and many others.

Here is an example of BASIC program:

10 PRINT “What is your name? “;
20 INPUT name$;
30 PRINT “How old are you? “;
40 INPUT age;
50 PRINT “Hello, “,name$,”! Next year you will be “,age+1,” years old.”;
60 END

But hey! This blog was supposed to be about C++, so let’s make that program compileable with a C++ compiler. To do that, we need to do a few things.

Overload comma operator

Original creators of C++ deliberately misused the >> and << operators to read data from an input stream, and to write data to an output stream. I will emulate both functionalities using , (comma) operator instead. It is possible to use a single comma operator to emulate both >> and << operators, because the type of the first argument will determine whether input or output is intended:

template <typename T>

inline istream &operator,( istream &s,T &data ) { return s >> data; }

template <typename T>

inline ostream &operator,( ostream &s,const T &data ) { return s << data; }

Define required BASIC keywords

The BASIC keywords END, INPUT and PRINT are not a part of C++ language, but they can be defined using the C++ preprocessor:

#define END exit(0);

#define INPUT cin,

#define PRINT cout,

Forget about line numbering

Modern BASIC language doesn’t need line numbers anyway.

Once again, here is the complete code for this article.





Fun With Virtual Assignment

7 09 2011

All C++ classes have an assignment operator. If a class definition does not explicitly declare assignment operator, it will be automatically generated by the compiler. Its presence cannot be avoided, but it can be disabled either by declaring it private (compilation fails if other classes try to access it) or declaring it without giving a definition (link will fail if any piece of code tries to access it). The automatically generated assignment operator takes a const reference to the class type itself as its argument.

Many C++ textbooks claim that assignment operator cannot be inherited, but that is simply not true. While it is true that an inherited operator cannot be easily accessed, it still exists: A phenomenon called name hiding will make the base class version difficult to access because the automatically generated derived class version provides a match in a narrower scope. (I’ll write a separate article about the mechanics of name hiding some time in the future.)

The obvious way for a derived class to allow access to its base class assignment operator is by adding a “using Base::operator=” declaration in its definition. Alas, now the derived class technically has an assignment operator so its normal assignment operator will not be automatically generated. As a result, an object of the derived type can still be assigned to another object of the derived type, but only the base part will ever be actually assigned. A way around this is to manually define the assignment operator which would have been generated, but this can be tedious and error prone, and generally not recommended.

But instead of just allowing access to the base class assignment operator, what if the derived class overrides it instead? As surprising as it sounds, this is possible: an assignment operator can be declared virtual and later be overridden by the derived class. This means that the derived class will start getting “notifications” when new values are assigned to it thru its base class interface. If the assignment operator is non-virtual, then something called object slicing will happen when a derived object is assigned a value thru its base class interface – in other words, the derived class would have no idea that the base class data have changed.

Here is some code for experimenting.





Friday Puzzle #1

1 09 2011

Here’s a programming challenge for the weekend.

The Easy Part

Write a function in C++ that reverses a regular zero-terminated string without using extra array. For example, …

char *pString = “Hello”;

ReverseString( pString );

After executing ReverseString, the contents of pString should be “olleH”.

The Hard Part:

Write a function in C++ that takes a regular zero-terminated string and an integer, and rotates the string as much to left as the integer specifies.  To rotate a string means to move the given number of characters from front to back, and shifting all other characters to the left accordingly.  Again, no extra array must be used.  For example, after executing …

char *pString = “Hello”;

RotateString( pString,2 );

… the pBuffer should contain “lloHe”.  In other words, the first two characters “He” have been moved to the end while the remaining characters “llo” have been shifted towards the front.

The hard part is indeed quite hard but there is actually an extremely elegant solution which may arise to you if you warm up with the easy part.  If you wish to participate, post your solution as a comment to this article.  I will edit the body of this article closer to the end of the weekend (perhaps some time Sunday evening Finnish time) to give my solution, or as soon as I see someone post an even more elegant solution.