How would you write factorial(n) in java?

Discussions

News: How would you write factorial(n) in java?

  1. How would you write factorial(n) in java? (32 messages)

    Evolution of the Python Programmer was pointed out on twitter this morning, which shows a lot of Python attempts at factorials. It's humor, but got me thinking. How would Java programmers really write a factorial method?

    Here's the thing: I wondered while reading it why each one of them didn't just look for the expert programmer's way, of importing an existing factorial function and just calling it. All the hacky ones just seemed like the programmers would have been trying to show off for all the female programmers out there.

    The enterprise one was disgusting. If code like that was in a review, whoever wrote it would be laughed out of the meeting. It's like using an EJB to call Formatter.format(). Sure, people did it or an equivalent, then they read Rod's book and decided to use Spring instead. But use the right amount of effort? no way. not enterprisish.

    What do you think of each of the suggestions? think they're appropriate for the sources?

    So while it's not hard to find java examples of factorials, why not also think of how people would write a factorial in java? What's the best way, and when? What do the options say about the programmers who use them?

    Threaded Messages (32)

  2. // and still run on the JVM, but take advantage of tailcall optimization and default parameters? this gets converted to a nice efficient loop under the hood, but has no mutable vars visible, so it's clean. users don't fill in the "acc" accumulator parameter.

    @tailrec def factorial(n:Int, acc:Int = 1):Int = {
       if (n>1) factorial(n-1, n*acc)
       else acc
    }

    // or you could probably use a fold too, tony morris has a good post about those http://blog.tmorris.net/scalalistfoldleft-for-java-programmers/

  3. public static int factorial(int f) {

        return ((f == 0) ? 1 : f * factorial(f - 1)); 


  4. To me, Python programmers of today look exactly the same as Java developers in the early days.

     

  5. Surely Scala syntax is more complicated than Java, no ?. Then again Java can be quite verbose. In any case, the more options we have for the JVM,  the merrier. I need to start learning Scala.

  6. Depends how you do it.[ Go to top ]

    If you write your Scala like you write you're Java, you'll end up with something that just looks like more concise Java, or Java with a lot of sweet syntactic sugar. This alone is a win.

    A non-idiomatic Scala implementation of the classic recursive factorial looks not much different than any other.

    def fac(n:Int):Int = if (n==1) 1 else n*fac(n-1)

    But as you get more into Scala you'll start using ideas which are generally foreign to most Java programmers (i.e. higher order functions, tailcall recursion, pattern matching, currying etc), you'll depart from the realm of the familiar. That's OK though, it's all good stuff, it's just a bunch of new patterns. It's the unfamiliarity with these that leads to the claims of Scala being complex, IMO. 

     

     

  7. Depends how you do it.[ Go to top ]

    If you write your Scala like you write you're Java, you'll end up with something that just looks like more concise Java, or Java with a lot of sweet syntactic sugar. This alone is a win.

    A non-idiomatic Scala implementation of the classic recursive factorial looks not much different than any other.

    def fac(n:Int):Int = if (n==1) 1 else n*fac(n-1)

    But as you get more into Scala you'll start using ideas which are generally foreign to most Java programmers (i.e. higher order functions, tailcall recursion, pattern matching, currying etc), you'll depart from the realm of the familiar. That's OK though, it's all good stuff, it's just a bunch of new patterns. It's the unfamiliarity with these that leads to the claims of Scala being complex, IMO. 

     

     

     

    Exciting !. I cant wait to get into Scala.

    Thanks a lot

  8. Depends how you do it.[ Go to top ]

    If you write your Scala like you write you're Java, you'll end up with something that just looks like more concise Java, or Java with a lot of sweet syntactic sugar. This alone is a win.

    A non-idiomatic Scala implementation of the classic recursive factorial looks not much different than any other.

    def fac(n:Int):Int = if (n==1) 1 else n*fac(n-1)

    But as you get more into Scala you'll start using ideas which are generally foreign to most Java programmers (i.e. higher order functions, tailcall recursion, pattern matching, currying etc), you'll depart from the realm of the familiar. That's OK though, it's all good stuff, it's just a bunch of new patterns. It's the unfamiliarity with these that leads to the claims of Scala being complex, IMO. 

     

     

  9. package com.example.math;

    import java.math.BigInteger;

    public class Functions {

        public static BigInteger factorial( int n ) {
            if ( n < 0 ) throw new IllegalArgumentException( "n mustn't be negative.") ;
            BigInteger result = BigInteger.ONE;
            for ( int i = 2 ; i <= n ; i++ ) {
                result = result.multiply(BigInteger.valueOf(i));
            }
            return result ;
        }
        
        public static void main(String[] args) {
            for ( int n = 0 ; n <= 10 ; n++ ) {
                System.out.println( n+"! = "+factorial(n) ) ;
            }
        }
    }

  10. Well, If we are sticking to int[ Go to top ]

    private static int[] f = {1,1,2,6,24,120,720,40320,5040,40320,362880,39916800,479001600};

    public static int fact(int n) { return f[n]; }

  11. The Scala Side?[ Go to top ]

    With the popularity of every Scala article that comes out, I'm wondering if we need to change the name of TSS to "The Scala Side."

  12. Well, If we are sticking to int[ Go to top ]

    private static int[] f = {1,1,2,6,24,120,720,40320,5040,40320,362880,39916800,479001600};

    public static int fact(int n) { return f[n]; }

     

    Cute. But ultimately wrong.

  13. Well, If we are sticking to int[ Go to top ]

    Brilliant!

  14. public class Factorial(){<br>&nbsp;&nbsp;<br>&nbsp;&nbsp;private int input;<br>&nbsp;&nbsp;<br>&nbsp;&nbsp;public Factorial(){<br>&nbsp;&nbsp;&nbsp;&nbsp;setInput(0);<br>&nbsp;&nbsp;}<br>&nbsp;&nbsp;<br>&nbsp;&nbsp;public Factorial(int input){<br>&nbsp;&nbsp;&nbsp;&nbsp;setInput(input);<br>&nbsp;&nbsp;}<br>&nbsp;&nbsp;<br>&nbsp;&nbsp;public Factorial(String input){<br>&nbsp;&nbsp;&nbsp;&nbsp;Integer integer = new Integer(input)<br>&nbsp;&nbsp;&nbsp;&nbsp;setInput(integer.intValue());<br>&nbsp;&nbsp;}<br>&nbsp;&nbsp;<br>&nbsp;&nbsp;public void setInput(int input){<br>&nbsp;&nbsp;&nbsp;&nbsp;this.input = input;<br>&nbsp;&nbsp;}<br>&nbsp;&nbsp;<br>&nbsp;&nbsp;public int getInput(){<br>&nbsp;&nbsp;&nbsp;&nbsp;return this.input;<br>&nbsp;&nbsp;}<br>&nbsp;&nbsp;<br>&nbsp;&nbsp;public BigInteger calculateFactorial(){<br>&nbsp;&nbsp;&nbsp;&nbsp;BigInteger factorial = new BigInteger("1");<br>&nbsp;&nbsp;&nbsp;&nbsp;int counter = input;<br>&nbsp;&nbsp;&nbsp;&nbsp;for(int i = input; i > 1; i--;){<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BigInteger mult = new BigInteger("" + i)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;factorial.multiply(mult);<br>&nbsp;&nbsp;&nbsp;&nbsp;}<br>&nbsp;&nbsp;&nbsp;&nbsp;return factorial;<br>&nbsp;&nbsp;}<br>&nbsp;&nbsp;<br>&nbsp;&nbsp;public String toString(){<br>&nbsp;&nbsp;&nbsp;&nbsp;StringBuffer sb = new StringBuffer();<br>&nbsp;&nbsp;&nbsp;&nbsp;sb.append("Factorial for: ");<br>&nbsp;&nbsp;&nbsp;&nbsp;sb.append(getInput());<br>&nbsp;&nbsp;&nbsp;&nbsp;return sb.toString();<br>&nbsp;&nbsp;}<br>&nbsp;&nbsp;<br>&nbsp;&nbsp;public static void main(String[] args){<br>&nbsp;&nbsp;&nbsp;&nbsp;int input = 7;<br>&nbsp;&nbsp;&nbsp;&nbsp;Factorial factorial = new Factorial(input);<br>&nbsp;&nbsp;&nbsp;&nbsp;BigInteger answer = factorial.calculateFactorial();<br>&nbsp;&nbsp;&nbsp;&nbsp;System.out.printf("The factorial of %d is %s.\n", input, answer.toString());<br>&nbsp;&nbsp;}<br>}

  15. That didn't edit the way i was quietly hoping it would. 

  16. public class Factorial(){
        
        private int input;
        
        public Factorial(){
            setInput(0);
        }
        
        public Factorial(int input){
            setInput(input);
        }
        
        public Factorial(String input){
            Integer integer = new Integer(input)
            setInput(integer.intValue());
        }
        
        public void setInput(int input){
            this.input = input;
        }
        
        public int getInput(){
            return this.input;
        }
        
        public BigInteger calculateFactorial(){
            BigInteger factorial = new BigInteger("1");
            int counter = input;
            for(int i = input; i > 1; i--;){
                BigInteger mult = new BigInteger("" + i)
                factorial.multiply(mult);
            }
            return factorial;
        }
        
        public String toString(){
            StringBuffer sb = new StringBuffer();
            sb.append("Factorial for: ");
            sb.append(getInput());
            return sb.toString();
        }
        
        public static void main(String[] args){
            int input = 7;
            Factorial factorial = new Factorial(input);
            BigInteger answer = factorial.calculateFactorial();
            System.out.printf("The factorial of %d is %s.\n", input, answer.toString());
        }
    }

  17. Is that a joke?

  18. This is incorrect code:

        public BigInteger calculateFactorial(){
            BigInteger factorial = new BigInteger("1");
            int counter = input;
            for(int i = input; i > 1; i--;){
                BigInteger mult = new BigInteger("" + i)
                factorial.multiply(mult);
            }
            return factorial;

    The correct code should be:

        public BigInteger calculateFactorial(){
            BigInteger factorial = new BigInteger("1");
            int counter = input;
            for(int i = input; i > 1; i--;){
                BigInteger mult = new BigInteger("" + i)
                factorial = factorial.multiply(mult);
            }

     

    Regards,

     

    Jacob Nikom

  19. Some points:

    1) use BigInteger

    2) avoid recursive (stack overflow)

    3) check input, must be zero or positive number

    4) avoid hold the whole result in the memory to prevent OutOfMemory exception

     

    anything else?

  20. Some points:

    1) use BigInteger

    2) avoid recursive (stack overflow)

    3) check input, must be zero or positive number

    4) avoid hold the whole result in the memory to prevent OutOfMemory exception

    anything else?

     

    2) Actually I'm using this question for interviews. People tend to solve it with recoursion. I would not categorise 'Using recoursion' a great problem. Apart from the fact, that it is not that efficient. I'm sure BigInteger will die before the stack will :-) But because 99% of the applicants were able to solve it and they all solved with recoursion, I excluded recoursion it in the question.

    1) Also in case somebody just use long, it could be a valid implementation. It depends what you need! Won't throw out somebody just because he did not use BigInteger.

    4) How do you avoid it? Where do you need that big numbers ;-)

    Another good interview question is to implement a singleton. Most of the 'J2EE architects' and 'senior developers' could not beat this!

    It seems, people tend to learn JPA or whatever cool technology before java itself.

     

  21. Another good interview question is to implement a singleton. Most of the 'J2EE architects' and 'senior developers' could not beat this!

     

     

    When you asked about how to create a singleton in an interview, did any interviewee tell you to grab the Effective Java 2nd edition and read it? I was asked that question in an interview before and my answer is: using enum and it was written in the Effective Java 2nd edition book but I didn't remember exactly. I don't know if the interviewer knew about that book or not, but it seemed to me that he thought I was kidding him. Actually I wasn't kidding and it's on page 18 of the book.

  22. Another good interview question is to implement a singleton. Most of the 'J2EE architects' and 'senior developers' could not beat this!

    Why would you implement a singleton in today's world of managed components? Using a singleton creates an undesirable dependency on a global variable.

    It is cleaner, more flexible, and more maintainable to address the concern of having exactly only one instance outside of the implementation. In practice, this would happen in the configuration of your dependency injection container or simply in an initialization method where you instantiate and connect your objects.

  23. Another good interview question is to implement a singleton. Most of the 'J2EE architects' and 'senior developers' could not beat this!

    Why would you implement a singleton in today's world of managed components? Using a singleton creates an undesirable dependency on a global variable.

    It is cleaner, more flexible, and more maintainable to address the concern of having exactly only one instance outside of the implementation. In practice, this would happen in the configuration of your dependency injection container or simply in an initialization method where you instantiate and connect your objects.

    Anyway, I was half kidding. There are cases where you do want this responsibility built into the class, such as GUI toolkits, certain classes representing immutable values, etc. But it does not hurt to question where a component really needs to be a singleton.

    I guess any undesirable global dependencies can be refactored away later...

  24. Thanks for the link - I was rolling on the floor laughing!

    A little depressing is that the because of the terminal obsoleteness of java I can't think of anything more interesting than the compressed versions

    long f(int i) { return i < 2 ? 1 : i * f(i - 1); }

    long f(int i) { int r = 1; while (i > 1) r *= i--; return r; }

    Modern languages like scala, ruby and maybe python are much better at this.

    Of course there is the enterprise version (loads of mandatory comments ommitted):

        public interface FactorialStrategy {
            /**
             * Calculates the factorial.
             * See specification Document foobar.doc page 17.
             * @author franz meier
             * @since Version 2.3.13.1.2.3
             * @param argument
             *            the argument to calculate the factorial with
             * @return the factorial of argument
             */
            long factorial(int i);
        }

        class FactorialRecursiveStrategy implements FactorialStrategy {
            @Override
            public long factorial(final int argument) {
                final long result;
                if (argument < 2) {
                    result = 1;
                } else {
                    final int nextargument = argument - 1;
                    result = argument * factorial(nextargument);
                }
                return result;
            }
        }

        public class FactorialStrategyFactory {
            private static final FactorialStrategy instance = new FactorialRecursiveStrategy();

            public FactorialStrategy getInstance() {
                return instance;
            }
        }

  25. EJB vs Spring again?[ Go to top ]

    It's like using an EJB to call Formatter.format(). Sure, people did it or an equivalent, then they read Rod's book and decided to use Spring instead

    True for EJB2 with its ridiculous overhead in artifacts that needed to be maintained, but what about the modern day EJB3?

    @Stateless

    public class SomeEJB {

       public String formatSomething() {

            // do stuff

           String someString = Formatter.format(someThing);

           // do stuff

           return someThing;

       }

    }

    What would make Spring perfectly suitable and EJB completely overkill (as your statement seems to suggest)?

     

  26. EJB vs Spring again?[ Go to top ]

    probably the whole J2EE Server you have to drag along to actually run it.

  27. EJB vs Spring again?[ Go to top ]

    probably the whole J2EE Server you have to drag along to actually run it.

    Is Spring included in the base JDK these days?

  28. EJB vs Spring again?[ Go to top ]

    just a couple jars to include.  Runs in a server, or in a standalone java application.  Just ad a single dependency to your Maven pom.  Done.  Frameworks like Spring, EJB, etc... should not bloat up the JDK...they are just higher level abstractions built on the base JDK.  You want to be able to rev and use them independently.

  29. EJB vs Spring again?[ Go to top ]

    just a couple jars to include.

    So you do have to drag the whole Spring container along, don't you?

  30. EJB vs Spring again?[ Go to top ]

    Are you really equating a couple of jars to an entire application server?  Really?  Wow.

  31. EJB vs Spring again?[ Go to top ]

    Heh, back in the day people used EJBs where they weren't necessary at all. They used a framework meant to provide transactional remoting capabilities to do things that a local class would have been fine for. I think that's what's being referred to here.

    Most people went down that particular rabbit hole, got burned ("How can it take so freaking long to just return a formatted date!?!?") and didn't put together that EJB wasn't meant for that sort of thing; the task is just too trivial.

    EJBs didn't need alternatives at the time; sure, they were a pain to work with, but that was fine, because what they were supposed to provide wasn't simple, either. People invested the work, when they shouldn't have... and blamed EJBs for it instead of recognizing that they were doing it wrong. And the results of that attitude are still around today.

    Developers can be incredibly stupid. :(

  32. Inspired by two of the earlier posts, I offer this implementation and unit test case. While testing if the BigInteger class could compute and represent a factorial where n=Integer.MAX_INT, I realize this method does not return large order factorial quickly. If the user of the method needed to know the values of several large order factorials, then a better implementation would use precomputed results for all values of n and probably require database.

    package com.example.math;

    import java.math.BigInteger;

    public class Functions {
            
            private static long[] smallFactorialResults =
            {      
                    1,                                            
                    1,
                    2,
                    6,
                    24,
                    120,
                    720,
                    5040,
                    40320,
                    362880,
                    3628800,
                    39916800,
                    479001600,
                    6227020800L,
                    87178291200L,
                    1307674368000L,
                    20922789888000L,
                    355687428096000L,
                    6402373705728000L,
                    121645100408832000L,
                    2432902008176640000L // n == 20
            };
            
            public static BigInteger factorial(int n)
            {
                    final BigInteger result;
                    // validate argument
                    if ( n < 0 )
                    {
                            throw new IllegalArgumentException("cannot compute a factorial less than zero. n = " + n +
                                    "not allowed");
                            
                    }
                    // avoid cost of BigInteger Math if the result can fit in a long
                    else if ( n < smallFactorialResults.length)
                    {
                            result = BigInteger.valueOf(smallFactorialResults[n]);
                    }
                    else
                    {
                            BigInteger product = BigInteger.valueOf(smallFactorialResults[smallFactorialResults.length-1]);
                            for (int i = smallFactorialResults.length; i <= n; i++)
                            {
                                    product = product.multiply(BigInteger.valueOf(i));
                            }
                            result = product;
                    }
                    
                    return result;
            }

    }

    package com.example.math;

    import java.math.BigInteger;

    import junit.framework.TestCase;

    public class FucntionsTest extends TestCase {

            public void testFactorial() {

                    BigInteger result = BigInteger.ONE;
                    try
                    {
                            result = Functions.factorial(-1);
                    }
                    catch (IllegalArgumentException ex)
                    {
                            assertTrue(true);
                    }
                    catch (Exception ex)
                    {
                            assertTrue(false);
                    }
                    
                    assertEquals(result,BigInteger.ONE);
                                    
                    // simple on array look ups
                    assertEquals(BigInteger.valueOf(1),Functions.factorial(0));
                    assertEquals(BigInteger.valueOf(1),Functions.factorial(1));
                    assertEquals(BigInteger.valueOf(120),Functions.factorial(5));
                    
                    // test boundary condition between lookups and big integer math
                    result = Functions.factorial(20);
                    assertEquals(BigInteger.valueOf(2432902008176640000L),result);
                    result = result.multiply(BigInteger.valueOf(21));
                    assertEquals(result,Functions.factorial(21));
                    
                    // test more than one iteration on the loop.
                    result = result.multiply(BigInteger.valueOf(22));
                    assertEquals(result,Functions.factorial(22));
                    
            }
            
            public void testForMaxFactorial() 
            {
                                         
                    // prove that argument n has no upper bound if typed as an integer
                    BigInteger result = BigInteger.ONE;
                    result = Functions.factorial(Integer.MAX_VALUE);
                    assertFalse(result.equals(BigInteger.ONE));
            
            }
            

    }

     

    I'll reply to this post with the result of the testForMaxFactorial method when it completes.

     

  33. Faster Factoiral Algorithms[ Go to top ]

    Realizing the above computing techinque was too slow, I searched the web and found a much better performing library from Luschny here http://www.luschny.de/math/factorial/FastFactorialFunctions.htm. It is available for use under the Creative Commons Library. Somewhere between 20,000,000 < n <= 90,000,000 the product becomes too large; hence, the computation fails. For values of n greater than 100,000 the Luschny PrimeSwing compuations are drasticaly faster than Python and the method listed above. Here are the results for 1,000,000!.

    Execution time for 1,000,000!

    • Luschny:                               5356ms
    • Python 2.7.x math.factorial(): 3293629ms
    • BigInteger Iteration:              4964233ms

     

    Python was faster than PrimeSwing when n <= 10,000 and always faster than BigInteger iteration.