How not to write factorial in Java

The translation of this article has already been published once on Habré , but for some reason the most important part remained behind the scenes. Below is a complete translation.

I was inspired to write this article by the note “ How would you write factorial in Java? ”. So excuse me, I’m going to talk a little bit in the code: I have a main thought that I’ll express at the end.

If you need to write factorial in Java, then most of you will probably start with something such:

public static int factorial(int n) { if (n == 0) return 1; return n * factorial(n-1); } 

')
Wrap it up in a class (we are still talking about Java), it will probably be some kind of auxiliary (* Util) class, for example:

 public class FactorialUtil { public static int factorial(int n) { if (n == 0) return 1; return n * factorial(n-1); } } 

Just, isn't it?

There is also a non-recursive solution:

 public class FactorialUtil { public static int factorial(int n) { int ret = 1; for (int i = 1; i <= n; ++i) ret *= i; return ret; } } 

The attentive reader will notice that the result may be greater than the maximum allowed integer (integer type), and will certainly want to rewrite the function so that it uses BigInteger or at least long, depending on the requirements of the program. So,

 public class FactorialUtil { public static BigInteger factorial(int n) { BigInteger ret = BigInteger.ONE; for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i)); return ret; } } 

Please note that so far I have not used the fact that I constantly calculate the same intermediate values ​​from 1 to n. If I cached these values, of course, the calculations could be much faster. If we have already calculated a value once, then save it for future use, for example, in the HashMap:

 public class FactorialUtil { static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>(); public static BigInteger factorial(int n) { BigInteger ret; if (n == 0) return BigInteger.ONE; if (null != (ret = cache.get(n))) return ret; ret = BigInteger.valueOf(n).multiply(factorial(n-1)); cache.put(n, ret); return ret; } } 

Simple enough, right?
Each of these methods has its advantages and disadvantages, therefore, given that this library will probably come in handy more than once in the future, we should use the standard mechanism popular in Java libraries. I'm talking about the pluggable system of modules, which allows at runtime to decide which algorithm to use: slow, but consuming less memory, or fast, but consuming more memory. First we need to remake our class in Singleton, because any plug-in gizmos require initialized classes and a siglton that returns the default implementation.

So, we create a class whose job is to support a singleton for our factory (Factory class), and links to an algorithm that implements the method. This class provides the old interface that was shown above, and also allows you to use a new, improved algorithm:

 public class FactorialUtil { private static FactorialUtil singleton; private FactorialAlgorithm algorithm; /** * Default (internal) constructor constructs our default algorithm. */ private FactorialUtil() { algorithm = new CachedFactorialImplementation(); } /** * New initializer which allows selection of the algorithm mechanism * @param algorithm */ public FactorialUtil(FactorialAlgorithm a) { algorithm = a; } /** * Default public interface for handling our factorial algorithm. Uses * the old standard established earlier for calling into our utility class. * @param n * @return */ public static BigInteger factorial(int n) { if (singleton == null) { // Use default constructor which uses default algorithm singleton = new FactorialUtil(); } return singleton.doFactorial(n); } /** * New mechanism which allows us to instantiate individual factorial * utilitiy classes and invoke customized factorial algorithms directory. * @param n * @return */ private BigInteger doFactorial(int n) { // Defer to our algorithm return algorithm.factorial(n); } } 

Note that the above class is responsible for creating the singleton and passing control to the class of the algorithm. It even has a private constructor that initializes the class of the algorithm, as well as the ability to create and use another algorithm.

It depends on the interface of the algorithm:

 public interface FactorialAlgorithm { BigInteger factorial(int n); } 

And here is an implementation that uses intermediate results caching, which we mentioned earlier:

 public class CachedFactorialImplementation implements FactorialAlgorithm { static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>(); @Override public BigInteger factorial(int n) { BigInteger ret; if (n == 0) return BigInteger.ONE; if (null != (ret = cache.get(n))) return ret; ret = BigInteger.valueOf(n).multiply(factorial(n-1)); cache.put(n, ret); return ret; } } 

See how beautiful this structure is! I mean that we can easily add a non-caching non-recursive implementation:

 public class LoopedFactorialImplementation implements FactorialAlgorithm { @Override public BigInteger factorial(int n) { BigInteger ret = BigInteger.ONE; for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i)); return ret; } } 

The disadvantage of this design, from the point of view of Java, should be obvious: it does not allow us to choose an algorithm at runtime (and this was originally our main idea). That is, obviously, we need to load the configuration and select the algorithm according to it. For example, we can read some system property (System property), which contains the name of the class that implements the algorithm. Ideally, our main method should look something like this:

  public static void main(String[] args) { System.getProperties().setProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm"); System.out.println("5! = " + FactorialUtil.factorial(5)); } 

Which means that we need to have an associative array containing all existing implementations. From it we could take the necessary algorithm before creating our singleton inside the factory method.

So, we need a factory that can generate algorithms. We store both an array of created singleton factories, and an array of class names and implementations in classMapping. Thus, we do not create an object of the class-algorithm until we really need it (there is nothing to call extra constructors and waste resources uselessly).

 /** * Factory class manages the factorial algorithms in our system. * @author wwoody * */ public class FactorialAlgorithmFactory { private static HashMap<String,FactorialAlgorithm> mapping = new HashMap<String,FactorialAlgorithm>(); private static HashMap<String,Class<? extends FactorialAlgorithm>> classMapping = new HashMap<String,Class<? extends FactorialAlgorithm>>(); private static FactorialAlgorithm defaultAlgorithm = new CachedFactorialImplementation(); /** Static initializer registers some of my known classes */ static { try { Class.forName("com.chaosinmotion.factorial.LoopedFactorialImplementation"); Class.forName("com.chaosinmotion.factorial.CachedFactorialImplementation"); } catch (ClassNotFoundException e) { // Should never happen. } } /** Get the default algorithm for computing factorials */ public static FactorialAlgorithm getDefaultAlgorithm() { if (defaultAlgorithm == null) { // Warning: this will fail if for whatever reason CachedFactorialImplementation // is not in the class path. defaultAlgorithm = getAlgorithm("cachedAlgorithm"); } return defaultAlgorithm; } /** Get the factorial algorithm specified by name */ public static FactorialAlgorithm getAlgorithm(String name) { FactorialAlgorithm f = mapping.get(name); if (f == null) { // We haven't created an instance yet. Get it from the class mapping. Class<? extends FactorialAlgorithm> c = classMapping.get(name); if (c != null) { // Create a new instance of the factorial algorithm specified try { f = c.newInstance(); mapping.put(name, f); return f; } catch (Exception e) { // Log the error Logger.getLogger("com.chaosinmotion.factorial"). warning("Unable to instantiate algorithm " + c.getCanonicalName() + ", named " + name); } } return getDefaultAlgorithm(); // return something. } else return f; } /** Register the class so we can construct a new instance if not already initialized */ public static void registerAlgorithm(String name, Class<? extends FactorialAlgorithm> f) { classMapping.put(name, f); } } 

Rewrite the class FactorialUtil so that it uses our named algorithms:

 public class FactorialUtil { private static FactorialUtil singleton; private FactorialAlgorithm algorithm; /** * Default (internal) constructor constructs our default algorithm. */ private FactorialUtil() { String name = System.getProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm"); if (name == null) { algorithm = FactorialAlgorithmFactory.getDefaultAlgorithm(); } else { algorithm = FactorialAlgorithmFactory.getAlgorithm(name); } } /** * New initializer which allows selection of the algorithm mechanism * @param algorithm */ public FactorialUtil(FactorialAlgorithm a) { algorithm = a; } /** * Utility to create by name. Calls into FactorialAlgorithmFactory to * actually get the algorithm. * @param name */ public FactorialUtil(String name) { algorithm = FactorialAlgorithmFactory.getAlgorithm(name); } /** * Default public interface for handling our factorial algorithm. Uses * the old standard established earlier for calling into our utility class. * @param n * @return */ public static BigInteger factorial(int n) { if (singleton == null) { // Use default constructor which uses default algorithm singleton = new FactorialUtil(); } return singleton.doFactorial(n); } /** * New mechanism which allows us to instantiate individual factorial * utilitiy classes and invoke customized factorial algorithms directory. * @param n * @return */ private BigInteger doFactorial(int n) { // Defer to our algorithm return algorithm.factorial(n); } } 

And also we will need to add to the CachedFactorialImplementation and LoopedFactorialImplementation classes static initialization blocks, which will register them in the factory:

 public class CachedFactorialImplementation implements FactorialAlgorithm { static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>(); static { FactorialAlgorithmFactory.registerAlgorithm("cachedAlgorithm", CachedFactorialImplementation.class); } @Override public BigInteger factorial(int n) { BigInteger ret; if (null != (ret = cache.get(n))) return ret; ret = BigInteger.valueOf(n).multiply(factorial(n-1)); cache.put(n, ret); return ret; } } 

and

 public class LoopedFactorialImplementation implements FactorialAlgorithm { static { FactorialAlgorithmFactory.registerAlgorithm("loopedAlgorithm", LoopedFactorialImplementation.class); } @Override public BigInteger factorial(int n) { BigInteger ret = BigInteger.ONE; for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i)); return ret; } } 

The highest beauty of this architecture is that we can connect our own implementation of factorial on the fly in FactorialUtil. To do this, you just need to create your own class that implements the FactorialAlgorithm interface and register it through the FactorialAlgorithmFactory in the static initialization block:

 public class RecursiveFactorialImplementation implements FactorialAlgorithm { static { FactorialAlgorithmFactory.registerAlgorithm("recursiveAlgorithm", RecursiveFactorialImplementation.class); } @Override public BigInteger factorial(int n) { if (n == 0) return BigInteger.ONE; return BigInteger.valueOf(n).multiply(factorial(n-1)); } } 

Finally, in the main method, we make sure that our class is loaded, and set the system property.

  public static void main(String[] args) { try { Class.forName("com.chaosinmotion.factorial.RecursiveFactorialImplementation"); } catch (ClassNotFoundException e) { // if this fails, no matter; we'll still use the default implementation. } System.getProperties().setProperty("com.chaosinmotion.factorialalgorithm", "recursiveAlgorithm"); System.out.println("5! = " + FactorialUtil.factorial(5)); } 

No problems! Moreover, this architecture allows you to connect and more sophisticated solutions such as these .



I am sure that many Java programmers, having reached this place, nod their heads and admire the elegance of this architecture. There will be those who are already pressing the button “Leave a comment” and writes: “Damn it, it would be better for you to set the system properties so-and-so”. For example, I could place an initializer for different classes in a file with properties (* .properties) or in an XML file. Or maybe it would be better if the value of the system property was the full name of the class.

And, of course, there will be those who have made entries in their notebook all the way and are already copying pieces of code from this blog (yes, all this code is working, I tested it on my car).

But wait, finally my main thought.

All this crap.

Each is a string.

Undoubtedly, in some circumstances, the connected architecture is useful and even necessary. But this is quite rare - so rare that it is even unfunny. In 99% of cases, when I saw such a code, it was completely and completely useless. It hides the true purpose of the code, replacing the two-three-lined auxiliary method with dozens and even hundreds of lines of the smug, bombastic pompous Java. It may help you to feel good, but it creates an ugly mess that future developers will have to clean up, or most likely avoid, like the plague.

And the most interesting, did you notice something? During all this discussion, you did not notice anything?

We have never taken care of negative numbers.



A smart Java developer knows when to stop. Life is too short to build castles in the clouds. He knows that a simple solution with a cycle is more than enough, and of course he will take care of negative numbers. (Well, you know, yes? Our recursive solution will fall into an infinite loop if you give a negative number as an input.)

A truly smart Java developer can get a little deeper into the problem and find out that factorial is a special case of the Gamma function . Perhaps the correct solution is none of the above pieces of code, but in general Stirling approximation for the gamma function:

 static double Gamma(double z) { double tmp1 = Math.sqrt(2*Math.PI/z); double tmp2 = z + 1.0/(12 * z - 1.0/(10*z)); tmp2 = Math.pow(z/Math.E, z); // ooops; thanks hj tmp2 = Math.pow(tmp2/Math.E, z); return tmp1 * tmp2; } 

But it already depends on the problem area - which we actually didn’t even think about, creating all these factories of ours.



My biggest complaint about Java developers is that they develop a whole bunch of really bad habits. Specifications are unclear. They think that someday the code may need to be extended in a different direction. Therefore, they write a whole bunch of bloated architectural nonsense, believing that one day all this extra garbage will suddenly help them and make their lives easier. And Java as a language allows you to do this quickly and conveniently, so it’s easy for us to build an architecture that will make our lives easier in the future.

But the future never gets any easier, right?

Because a year later they were going through all this excess baggage written at the time when they thought they understood the problem area (although it is now clear that they did not understand), instead of having a few lines of simple code (like our very first an example of factorial), which they could reconsider if necessary, is forced to deal with a heap of nonsense that no one can understand.

And instead of sneaking through this heap to untie a knot or at least understand how this mechanism works, they simply slap the patch over the architecture, as in the classic example of a lava flow . For example, they do not understand how to create a plug-in algorithm, and therefore they override the FactoryUtil class or simply write the FactoryUtil class again and add another hundred or two (ill-conceived) code there, just to quickly patch up the misunderstanding of the previous hundred lines (ill-conceived ) code.



Therefore, please do us all a favor: if you feel like adding complexity simply because “sometime it will be useful to us” or “the system is not flexible enough yet” or “there must be reusability in our code” or (don’t let God!) because “it's cool” - just go home early. See cartoons. Or hire the " Start ".

Stop creating additional work for us without a good reason.