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.


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

A New Start

31 08 2011

The only thing that is constant, is change.  After I had left Nokia last December I was going to use this blog to document the process of learning a new skill.  I chose to learn programming for Android OS because I was strongly expecting Nokia would start producing Android phones.  Little did I know what was going to happen soon after that: in February Nokia announced their contract with Microsoft about starting to produce phones with Windows Phone OS instead, and it was publicly communicated in crystal clear terms that Nokia will not join the Android camp.

Later on in May I was hired as a software architect by Tekla Corporation where my employment started in the beginning of August.  Tekla is a producer of computer software on Windows platform for Building Modeling & Construction, and for community infrastructure engineering.  It is truly a world class company having customers on all continents, and even its biggest rival is located abroad, in the USA.  When I was interviewing with the company I was surprised to learn that several incredibly famous buildings had been modelled using software provided by Tekla and I’ll mention Yas Marina Formula One Circuit in Abu Dhabi and the Beijing Olympic Games’ “Bird Nest” Stadium just to give an idea – please see Tekla web site for more examples.

Life has treated me very well indeed; having just a couple of weeks in Tekla under my belt I can already tell I love working for the company.  (N.B, this blog is completely my personal effort and not officially endorsed in any way by my employers, present or past.)

With the new interests in my mind, I will now dedicate this blog to the recreational size of software creation instead.  I plan to write about how to recognize things that make software architecture good, about how to break down complex algorithms into a succession of simpler tasks, and about how to model the world thru Object Oriented design principles.  There will also be an occasional article about the quirks, gray areas, and dark corners of C++, the programming language I know particularly well due to my past occupations.  I’ll also try to regularly come up with logic games and puzzles to humor the smart mind on idle moments.

If you like what you see here please do not hesitate to comment.  Even better, recommend this blog to a friend if you think they’ll enjoy reading it.  Active audience is the best way to motivate and reward any blogger.