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.




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: