How do I find the factorial of a positive number?

18

1

The challenge:

Write a program or a function that inputs a positive number and returns its factorial.

Note: This is a question. Please do not take the question and/or answers seriously. More information here. Every question is also a question, so the highest voted answer wins.

alephalpha

Posted 2013-12-29T06:07:58.287

Reputation: 23 988

6

See also The Evolution of Haskell programmer.

– Petr Pudlák – 2013-12-29T07:46:51.020

4-1, sorry, because we're getting a huge flood of these code trolling questions and this does not really add anything new to them – Doorknob – 2013-12-29T11:25:59.563

Related: http://codegolf.stackexchange.com/questions/1635/forking-factorials

– Paul – 2013-12-30T10:08:13.953

Code-trolling is in the process of being removed, as per the official stance. This question has a fair amount of votes with many answers, many of which are extremely highly voted. It recieved just over 50% "delete" votes on the poll, but it is unique in that it recieved so many answers and votes, so I am locking it for historical significance.

– Doorknob – 2014-05-12T00:13:49.350

Answers

46

This is a very simple numerical computing problem that we can solve with Stirling's approximation:

Stirling's approximation formula

As you can see, that formula features a square root, which we will also need a way to approximate. We will choose the so-called "Babylonian method" for that because it is arguably the simplest one:

Babylonian method

Note that computing the square root this way is a good example of recursion.

Putting it all together in a Python program gives us the following solution to your problem:

def sqrt(x, n): # not the same n as below
    return .5 * (sqrt(x, n - 1) + x / sqrt(x, n - 1)) if n > 0 else x

n = float(raw_input())
print (n / 2.718) ** n * sqrt(2 * 3.141 * n, 10)

With a simple modification the above program can output a neat table of factorials:

1! =    0.92215
2! =    1.91922
3! =    5.83747
4! =   23.51371
5! =  118.06923
6! =  710.45304
7! = 4983.54173
8! = 39931.74015
9! = 359838.58817

This method should be sufficiently accurate for most applications.

nwk

Posted 2013-12-29T06:07:58.287

Reputation: 621

16+1 The simplicity and accuracy of this method makes it a clear winner – Joe the Person – 2013-12-31T12:09:27.030

44

C#

Sorry, but I hate recursive function.

public string Factorial(uint n) {
    return n + "!";
}

tia

Posted 2013-12-29T06:07:58.287

Reputation: 745

1Technically, you've satisfied the brief! ;) +1 for brief abuse – WallyWest – 2014-01-06T05:30:54.850

36

Java

public int factorial ( int n ) {
switch(n){
case 0: return 1;
case 1: return 1;
case 2: return 2;
case 3: return 6;
case 4: return 24;
case 5: return 120;
case 6: return 720;
case 7: return 5040;
case 8: return 40320;
case 9: return 362880;
case 10: return 3628800;
case 11: return 39916800;
case 12: return 479001600;
default : throw new IllegalArgumentException();
}
}

emory

Posted 2013-12-29T06:07:58.287

Reputation: 989

16I tried it - very efficient. Will ship with next release. :) – Johannes – 2013-12-29T22:33:41.107

Beside the "magical numbers syndrom", this could actually be a good implementation as long as n<13, much less stacks. Write it "case 4: return 432;" and you'd have a decent class, much faster than the old recursive one. – Fabinout – 2014-01-30T17:16:04.813

6@Fabinout, the implementation is correct even for n>=13. 13!>Integer.MAX_VALUE. – emory – 2014-01-30T21:11:19.203

21

Python

Of course the best way how to solve any problem is to use regular expressions:

import re

# adapted from http://stackoverflow.com/q/15175142/1333025
def multiple_replace(dict, text):
  # Create a regular expression  from the dictionary keys
  regex = re.compile("(%s)" % "|".join(map(re.escape, dict.keys())))
  # Repeat while any replacements are made.
  count = -1
  while count != 0:
    # For each match, look-up corresponding value in dictionary.
    (text, count) = regex.subn(lambda mo: dict[mo.string[mo.start():mo.end()]], text)
  return text

fdict = {
    'A': '@',
    'B': 'AA',
    'C': 'BBB',
    'D': 'CCCC',
    'E': 'DDDDD',
    'F': 'EEEEEE',
    'G': 'FFFFFFF',
    'H': 'GGGGGGGG',
    'I': 'HHHHHHHHH',
    'J': 'IIIIIIIIII',
    'K': 'JJJJJJJJJJJ',
    'L': 'KKKKKKKKKKKK',
    'M': 'LLLLLLLLLLLLL',
    'N': 'MMMMMMMMMMMMMM',
    'O': 'NNNNNNNNNNNNNNN',
    'P': 'OOOOOOOOOOOOOOOO',
    'Q': 'PPPPPPPPPPPPPPPPP',
    'R': 'QQQQQQQQQQQQQQQQQQ',
    'S': 'RRRRRRRRRRRRRRRRRRR',
    'T': 'SSSSSSSSSSSSSSSSSSSS',
    'U': 'TTTTTTTTTTTTTTTTTTTTT',
    'V': 'UUUUUUUUUUUUUUUUUUUUUU',
    'W': 'VVVVVVVVVVVVVVVVVVVVVVV',
    'X': 'WWWWWWWWWWWWWWWWWWWWWWWW',
    'Y': 'XXXXXXXXXXXXXXXXXXXXXXXXX',
    'Z': 'YYYYYYYYYYYYYYYYYYYYYYYYYY'}

def fact(n):
    return len(multiple_replace(fdict, chr(64 + n)))

if __name__ == "__main__":
    print fact(7)

Petr Pudlák

Posted 2013-12-29T06:07:58.287

Reputation: 4 272

1Of course indeed :) – Pierre Arlaud – 2014-01-03T21:27:07.880

15

Haskell

Short code is efficient code, so try this.

fac = length . permutations . flip take [1..]

Why it's trolling:

I'd laugh at any coder who wrote this... The inefficiency is beautiful. Also probably incomprehensible to any Haskell programmer who actually can't write a factorial function.

Edit: I posted this a while ago now, but I thought I'd clarify for future people and people who can't read Haskell.

The code here takes the list of the numbers 1 to n, creates the list of all permutations of that list, and returns the length of that list. On my machine it takes about 20 minutes for 13!. And then it ought to take four hours for 14! and then two and a half days for 15!. Except that at some point in there you run out of memory.

Edit 2: Actually you probably won't run out of memory due to this being Haskell (see the comment below). You might be able to force it to evaluate the list and hold it in memory somehow, but I don't know enough about optimizing (and unoptimizing) Haskell to know exactly how to do that.

jgon

Posted 2013-12-29T06:07:58.287

Reputation: 271

Hideous and yet so elegant, all at the same time. – PLL – 2014-01-10T11:21:01.627

1Are you sure about the memory issue? At any one point, you need to hold in memory: - the list [1..n]. - One particular permutation of [1..n], consed to a thunk for the rest of the permutations (polynomial in n). - An accumulator for the length function. – John Dvorak – 2014-03-11T06:47:21.953

Fair point, probably not actually. Didn't really think about it too much. I'll add a comment at the bottom. – jgon – 2014-03-17T18:23:22.633

10

C#

Since this is a math problem, it makes sense to use an application specifically designed to solve math problems to do this calculation...

Step 1:

Install MATLAB. A trial will work, I think, but this super-complicated problem is likely important enough to merit purchasing the full version of the application.

Step 2:

Include the MATLAB COM component in your application.

Step 3:

public string Factorial(uint n) {
    MLApp.MLApp matlab = new MLApp.MLApp();
    return matlab.Execute(String.Format("factorial({0})", n);
}

Moshe Katz

Posted 2013-12-29T06:07:58.287

Reputation: 211

Matlab for students starts at $100. Professional versions or site licenses can go way into the thousands. – Moshe Katz – 2013-12-30T05:43:09.860

4Moshe Katz - justified because factorials. – Mike H. – 2014-01-22T21:57:35.170

9

C#

Factorials are a higher level math operation that can be difficult to digest all in one go. The best solution in programming problems like this, is to break down one large task into smaller tasks.

Now, n! is defined as 1*2*...*n, so, in essence repeated multiplication, and multiplication is nothing but repeated addition. So, with that in mind, the following solves this problem:

long Factorial(int n)
{
    if(n==0)
    {
        return 1;
    }

    Stack<long> s = new Stack<long>();
    for(var i=1;i<=n;i++)
    {
        s.Push(i);
    }
    var items = new List<long>();
    var n2 = s.Pop();
    while(s.Count >0)
    {
        var n3 = s.Pop();
        items.AddRange(FactorialPart(n2,n3));
        n2 = items.Sum();
    }
    return items.Sum()/(n-1);
}

IEnumerable<long> FactorialPart(long n1, long n2)
{
    for(var i=0;i<n2;i++){
        yield return n1;
    }
}

Matt Sieker

Posted 2013-12-29T06:07:58.287

Reputation: 401

You have a bottleneck sending all this through one CPU or core, which I think I may have solved in my answer :-) – Paul – 2013-12-30T10:19:37.040

9

#include <math.h>

int factorial(int n)
{
    const double g = 7;
    static const double p[] = { 0.99999999999980993, 676.5203681218851,
                                -1259.1392167224028, 771.32342877765313,
                                -176.61502916214059, 12.507343278686905,
                                -0.13857109526572012, 9.9843695780195716e-6,
                                1.5056327351493116e-7 };
    double z = n - 1 + 1;
    double x = p[0];
    int i;
    for ( i = 1; i < sizeof(p)/sizeof(p[0]); ++i )
        x += p[i] / (z + i);
    return sqrt(2 * M_PI) * pow(z + g + 0.5, z + 0.5)  * exp(-z -g -0.5) * x + 0.5;
}

Trolls:

  • A 100% correct way of computing factorial that completely misses the point of either doing it iteratively or recursively.
  • You have no idea why it works and could not generalize it to do anything else.
  • More costly than just computing it with integer math.
  • The most obvious "suboptimal" code (z = n - 1 + 1) is actually self-documenting if you know what's going on.
  • For extra trolling I should compute p[] using a recursive calculation of the series coefficients!

(It's the Lanczos approximation of the gamma function)

Ben Jackson

Posted 2013-12-29T06:07:58.287

Reputation: 332

Is there any point in - 1 + 1 here? My compiler optimizes it (it's not floating point number where optimizing code like this could be dangerous), so it appears to be unneeded. – Konrad Borowski – 2014-01-14T14:36:26.147

4@xfix: double z = n - 1 is part of the approximation of the gamma function. The + 1 is from the relationship that gamma(n + 1) = n! for integer n. – Ben Jackson – 2014-01-14T14:39:20.400

9

We all know from college that the most efficient way to calculate a multiplication is through the use of logarithms. After all, why else would people use logarithm tables for hundreds of years?

So from the identity a*b=e^(log(a)+log(b)) we form the following Python code:

from math import log,exp

def fac_you(x):
    return round(exp(sum(map(log,range(1,x+1)))))

for i in range(1,99):
    print i,":",fac_you(i)

It creates a list of numbers from 1 to x, (the +1 is needed because Python sucks) calculates the logarithm of each, sums the numbers, raises the e to the power of the sum and finally rounds the value to the nearest integer (because Python sucks). Python has a built-in function for calculating factorials, but it only works for integers, so it can't produce big numbers (because Python sucks). This is why the function above is needed.

Btw, a general tip for students is that if something doesn't work as expected, it's probably because the language sucks.

nitro2k01

Posted 2013-12-29T06:07:58.287

Reputation: 1 283

Wish I could give some extra votes there for the description, but Python sucks – Mark K Cowan – 2014-01-24T14:45:32.903

1I laughed at "fac you" – Number9 – 2014-03-17T19:56:32.033

8

Unfortunately, Javascript lacks a built-in way to compute the factorial. But, you can use its meaning in combinatorics to determine the value nevertheless:

The factorial of a number n is the number of permutations of an list of that size.

So, we can generate every list of n-digit number, check if it is a permutation, and if so, increment a counter:

window.factorial = function($nb_number) {
  $nb_trials = 1
  for($i = 0; $i < $nb_number; $i++) $nb_trials *= $nb_number
  $nb_successes = 0
  __trying__:
  for($nb_trial = 0; $nb_trial < $nb_trials; $nb_trial++){
    $a_trial_split = new Array
    $nb_tmp = $nb_trial
    for ($nb_digit = 0; $nb_digit < $nb_number; $nb_digit++){
      $a_trial_split[$nb_digit] = $nb_tmp - $nb_number * Math.floor($nb_tmp / $nb_number)
      $nb_tmp = Math.floor($nb_tmp / $nb_number)
    }
    for($i = 0; $i < $nb_number; $i++)
      for($j = 0; $j < $nb_number; $j++)
        if($i != $j)
          if($a_trial_split[$i] == $a_trial_split[$j])
            continue __trying__
    $nb_successes += 1
  }
  return $nb_successes
}

alert("input a number")
document.open()
document.write("<input type = text onblur = alert(factorial(parseInt(this.value))))>")
document.close()


Trolls:

  • Types hungarian notation, snake_case and unneccessary sigils. How evil is that?
  • Invented my own convention for jump labels, incompatible with the current use of this convention.
  • Every possible variable is accidentally global.
  • The solution is not O(n), not O(n!), but O(n^n). This alone would have sufficed to qualify here.
  • Incrementing a number and then converting as base-n is a bad way to generate a list of sequences. Even if we did want duplicates. Mysteriously breaking for n > 13 is not the only reason.
  • Of course we could have used number.toString(base), but that doesn't work for bases above 36. Yes, I know 36! is a lot, but still...
  • Did I mention Javascript had the modulus operator? Or Math.pow? No? Oh well.
  • Refusing to use ++ outside of for-loops makes it even more mysterious. Also, == is bad.
  • Deeply nested braceless looping constructs. Also, nested conditionals instead of AND. Also, the outer condition could have been avoided by ending the inner loop at $i.
  • The functions new Array, document.write (with friends) and alert (instead of a prompt or an input label) form a complete trifecta of function choice sins. Why is the input added dynamically after all?
  • Inline event handlers. Oh, and deep piping is hell to debug.
  • Unquoted attributes are fun, and the spaces around = make them even harder to read.
  • Did I already mention I hate semicolons?

John Dvorak

Posted 2013-12-29T06:07:58.287

Reputation: 9 048

8

Ruby and WolframAlpha

This solution uses the WolframAlpha REST API to calculate the factorial, with RestClient to fetch the solution and Nokogiri to parse it. It doesn't reinvent any wheels and uses well tested and popular technologies to get the result in the most modern way possible.

require 'rest-client'
require 'nokogiri'

n = gets.chomp.to_i
response = Nokogiri::XML(RestClient.get("http://api.wolframalpha.com/v2/query?input=#{n}!&format=moutput&appid=YOUR_APP_KEY"))
puts response.xpath("//*/moutput/text()").text

migimunz

Posted 2013-12-29T06:07:58.287

Reputation: 181

7

Javascript

Javascript is a functional programming language, this means you have to use functions for everything because its faster.

function fac(n){
    var r = 1,
        a = Array.apply(null, Array(n)).map(Number.call, Number).map(function(n){r = r * (n + 1);});
    return r;
}

Luka

Posted 2013-12-29T06:07:58.287

Reputation: 171

1Can you explain? – Mhmd – 2013-12-31T15:55:29.210

71 is not a function. Your code is thus slow. – Pierre Arlaud – 2014-01-02T13:59:02.183

4@ArlaudPierre r = -~(function(){}) will surely solve that. – nitro2k01 – 2014-01-05T11:49:04.050

4I am on a work machine so I don't really want to install this language. Where can I find a version that will run in my browser? – joeytwiddle – 2014-01-13T20:43:27.473

@joeytwiddle Do you have google chrome? If so, just run it on the console (I get there by: F12 (key for "inspect element")->Console). Other browsers probably have this too. http://ideone.com/ has Javascript. http://jsfiddle.net/ runs Javascript too.

– Justin – 2014-01-13T21:33:09.317

3I'm a bit scared of using Google because my boss has an account with them, and I don't want him to know I'm playing golf at work. I was looking for an extension for Firefox that could run Javascript, but I can't seem to find one. Some of my friends run Javascript on jsfiddle.net but that's using somebody else's electricity which is a bit like stealing. My mum said I shouldn't hang around with people like that, but they are my friends so what can I do? Anyway she sometimes takes more creamer than she needs. Thanks for the tips, I use Ctrl-Shift-J or K in Firefox. Disclaimer: #comment-trolling – joeytwiddle – 2014-01-13T21:54:40.783

@Luka "Javascript is a functional programming language, this means you have to use functions for everything because its faster." made me laugh so hard. Best answer so far. – Mike H. – 2014-01-22T21:56:13.727

5

Using Bogo-Sort in Java

public class Factorial {
    public static void main(String[] args) {
        //take the factorial of the integers from 0 to 7:
        for(int i = 0; i < 8; i++) {
            System.out.println(i + ": " + accurate_factorial(i));
        }
    }

    //takes the average over many tries
    public static long accurate_factorial(int n) {
        double sum = 0;
        for(int i = 0; i < 10000; i++) {
            sum += factorial(n);
        }
        return Math.round(sum / 10000);
    }

    public static long factorial(int n) {
        //n! = number of ways to sort n
        //bogo-sort has O(n!) time, a good approximation for n!
        //for best results, average over several passes

        //create the list {1, 2, ..., n}
        int[] list = new int[n];
        for(int i = 0; i < n; i++)
            list[i] = i;

        //mess up list once before we begin
        randomize(list);

        long guesses = 1;

        while(!isSorted(list)) {
            randomize(list);
            guesses++;
        }

        return guesses;
    }

    public static void randomize(int[] list) {
        for(int i = 0; i < list.length; i++) {
            int j = (int) (Math.random() * list.length);

            //super-efficient way of swapping 2 elements without temp variables
            if(i != j) {
                list[i] ^= list[j];
                list[j] ^= list[i];
                list[i] ^= list[j];
            }
        }
    }

    public static boolean isSorted(int[] list) {
        for(int i = 1; i < list.length; i++) {
            if(list[i - 1] > list[i])
                return false;
        }
        return true;
    }
}

This actually works, just very slowly, and it isn't accurate for higher numbers.

James Hagborg

Posted 2013-12-29T06:07:58.287

Reputation: 61

4

PERL

Factorial can be a hard problem. A map/reduce like technique -- just like Google uses -- can split up the math by forking off a bunch of processes and collecting the results. This will make good use of all those cores or cpus in your system on a cold winter's night.

Save as f.perl and chmod 755 to make sure you can run it. You do have the Pathologically Eclectic Rubbish Lister installed, don't you?

#!/usr/bin/perl -w                                                              
use strict;
use bigint;
die "usage: f.perl N (outputs N!)" unless ($ARGV[0] > 1);
print STDOUT &main::rangeProduct(1,$ARGV[0])."\n";
sub main::rangeProduct {
    my($l, $h) = @_;
    return $l    if ($l==$h);
    return $l*$h if ($l==($h-1));
    # arghhh - multiplying more than 2 numbers at a time is too much work       
    # find the midpoint and split the work up :-)                               
    my $m = int(($h+$l)/2);
    my $pid = open(my $KID, "-|");
      if ($pid){ # parent                                                       
        my $X = &main::rangeProduct($l,$m);
        my $Y = <$KID>;
        chomp($Y);
        close($KID);
        die "kid failed" unless defined $Y;
        return $X*$Y;
      } else {
        # kid                                                                   
        print STDOUT &main::rangeProduct($m+1,$h)."\n";
        exit(0);
    }
}

Trolls:

  • forks O(log2(N)) processes
  • doesn't check how many CPUs or cores you have
  • Hides lots of bigint/text conversions that occur in every process
  • A for loop is often faster than this code

Paul

Posted 2013-12-29T06:07:58.287

Reputation: 357

TIL that in perl ARGV[0] is actually the first argument and not the script! – ThinkChaos – 2014-01-05T11:17:56.630

@plg I believe $0 might contain the script filename, but that is not the same as $ARGV[0] – Paul – 2014-01-05T11:30:37.053

Yep, that's what I read. I just found it surprising that in perl it's not $ARGV[0] because most languages I know a bit have it there – ThinkChaos – 2014-01-05T11:35:47.063

4

Python

Just an O(n!*n^2) algorithm to find the factorial. Base case handled. No overflows.

def divide(n,i):
    res=0
    while n>=i:
         res+=1
         n=n-i
    return res

def isdivisible(n,numbers):
    for i in numbers:
         if n%i!=0:
             return 0
         n=divide(n,i)
    return 1

def factorial(n):
    res = 1
    if n==0: return 1 #Handling the base case
    while not isdivisible(res,range(1,n+1)):
         res+=1
    return res

Sudharsan Mohan

Posted 2013-12-29T06:07:58.287

Reputation: 851

3

Well, there is an easy solution in Golfscript. You could use a Golfscript interpreter and run this code:

.!+,1\{)}%{*}/

Easy huh :) Good luck!

Martijn Courteaux

Posted 2013-12-29T06:07:58.287

Reputation: 759

2I don't know GolfScript, but this one disappoints me... Based on the other GolfScript examples on this site, I would have expected the answer to be ! – Mr Lister – 2014-01-11T07:19:43.803

1That is the negation operator. 0 becomes 1 and everything else becomes 0. – Martijn Courteaux – 2014-01-11T12:20:42.003

3

Mathematica

factorial[n_] := Length[Permutations[Table[k, {k, 1, n}]]]

It doesn't seem work for numbers larger than 11, and factorial[11] froze up my computer.

Stephen Montgomery-Smith

Posted 2013-12-29T06:07:58.287

Reputation: 231

3

Ruby

f=->(n) { return 1 if n.zero?; t=0; t+=1 until t/n == f[n-1]; t }

The slowest one-liner I can imagine. It takes 2 minutes on an i7 processor to calculate 6!.

rewritten

Posted 2013-12-29T06:07:58.287

Reputation: 309

2

Python

Below is a Python version of the solution, which is not limited to the 32 bit (or 64 bit on a very recent system) limit for integer numbers in Python. To get around this limitation, we shall use a string as input and output for the factorial routine and internally split the string in it's digits to be able to perform the multiplication.

So here is the code: the getDigits function splits a string representing a number in to its digits, so "1234" becomes [ 4, 3, 2, 1 ] (the reverse order just makes the increase and multiply functions simpler). The increase function takes such a list and increases it by one. As the name suggests, the multiply function multiplies, e.g. multiply([2, 1], [3]) returns [ 6, 3 ] because 12 times 3 is 36. This works in the same way as you would multiply something with pen and paper.

Then finally, the factorial function uses these helper functions to calculate the actual factorial, for example factorial("9") gives "362880" as its output.

import copy

def getDigits(n):
    digits = []
    for c in n:
        digits.append(ord(c) - ord('0'))

    digits.reverse()
    return digits

def increase(d):
    d[0] += 1
    i = 0
    while d[i] >= 10:
        if i == len(d)-1:
            d.append(0)

        d[i] -= 10
        d[i+1] += 1
        i += 1

def multiply(a, b):
    subs = [ ]
    s0 = [ ]
    for bi in b:

        s = copy.copy(s0)
        carry = 0
        for ai in a:
            m = ai * bi + carry
            s.append(m%10)
            carry = m//10

        if carry != 0:
            s.append(carry)

        subs.append(s)
        s0.append(0)

    done = False
    res = [ ]
    termsum = 0
    pos = 0
    while not done:
        found = False
        for s in subs:
            if pos < len(s):
                found = True
                termsum += s[pos]

        if not found:
            if termsum != 0:
                res.append(termsum%10)
                termsum = termsum//10
            done = True
        else:
            res.append(termsum%10)
            termsum = termsum//10
            pos += 1

    while termsum != 0:
        res.append(termsum%10)
        termsum = termsum//10

    return res

def factorial(x):
    if x.strip() == "0" or x.strip() == "1":
        return "1"

    factorial = [ 1 ]
    done = False
    number = [ 1 ]
    stopNumber = getDigits(x)
    while not done:
        if number == stopNumber:
            done = True

        factorial = multiply(factorial, number)
        increase(number)

    factorial.reverse()

    result = ""
    for c in factorial:
        result += chr(c + ord('0'))

    return result

print factorial("9")

Notes

In python an integer doesn't have a limit, so if you'd like to do this manually you can just do

fac = 1
for i in range(2,n+1): 
    fac *= i

There's also the very convenient math.factorial(n) function.

This solution is obviously far more complex than it needs to be, but it does work and in fact it illustrates how you can calculate the factorial in case you are limited by 32 or 64 bits. So while nobody will believe this is the solution you've come up with for this simple (at least in Python) problem, you can actually learn something.

brm

Posted 2013-12-29T06:07:58.287

Reputation: 131

There is no limit on integer numbers in Python... right? You might need to explain this better. – Riking – 2013-12-30T08:49:49.577

@Riking Yes, in python there's no limit for integers. I've added a few notes to make it more clear. – brm – 2013-12-30T09:25:44.973

2

The correct approach for these difficult math problems is a DSL. So I'll model this in terms of a simple language

data DSL b a = Var x (b -> a)
             | Mult DSL DSL (b -> a)
             | Plus DSL DSL (b -> a)
             | Const Integer (b -> a) 

To write our DSL nicely, it's helpful to view it as a free monad generated by the algebraic functor

F X = X + F (DSL b (F X)) -- Informally define + to be the disjoint sum of two sets

We could write this in Haskell as

Free b a = Pure a
         | Free (DSL b (Free b a))

I will leave it to the reader to derive the trivial implementation of

join   :: Free b (Free b a) -> Free b a
return :: a -> Free b a
liftF  :: DSL b a -> Free b a

Now we can descibe an operation to model a factorial in this DSL

factorial :: Integer -> Free Integer Integer
factorial 0 = liftF $ Const 1 id
factorial n = do
  fact' <- factorial (n - 1)
  liftF $ Mult fact' n id

Now that we've modeled this, we just need to provide an actual interpretation function for our free monad.

denote :: Free Integer Integer -> Integer
denote (Pure a) = a
denote (Free (Const 0 rest)) = denote $ rest 0
...

And I'll leave the rest of the denotation to the reader.

To improve readability, it's sometimes helpful to present a concrete AST of the form

data AST = ConstE Integer
         | PlusE AST AST
         | MultE AST AST

and then right a trivial reflection

reify :: Free b Integer -> AST

and then it's straightforward to recursively evaluate the AST.

Daniel Gratzer

Posted 2013-12-29T06:07:58.287

Reputation: 953

2

Python

The most reasonable solution is clearly to check through all numbers until you find the one which is the factorial of the given number.

print('Enter the number')
n=int(input())
x=1
while True:
    x+=1
    tempx=int(str(x))
    d=True
    for i in range(1, n+1):
        if tempx/i!=round(tempx/i):
            d=False
        else:
            tempx/=i
    if d:
        print(x)
        break

PygameNerd

Posted 2013-12-29T06:07:58.287

Reputation: 121

2

Just go to Google and type in your factorial:

5!

http://lmgtfy.com/?q=5!

Mike H.

Posted 2013-12-29T06:07:58.287

Reputation: 121

2

A most elegant recursive solution in C

Every one knows the most elegant solutions to factorials are recursive.

Factorial:

0! = 1
1! = 1
n! = n * (n - 1)!

But multiplication can also be defined recursively as successive additions.

Multiplication:

n * 0 = 0
n * 1 = n
n * m = n + n * (m - 1)

And so can addition as successive incrementations.

Addition:

n + 0 = n
n + 1 = (n + 1)
n + m = (n + 1) + (m - 1)

In C, we can use ++x and --x to handle the primitives (x + 1) and (x - 1) respectively, so we have everything defined.

#include <stdlib.h>
#include <stdio.h>

// For more elegance, use T for the type
typedef unsigned long T;

// For even more elegance, functions are small enough to fit on one line

// Addition
T A(T n, T m) { return (m > 0)? A(++n, --m) : n; }

// Multiplication
T M(T n, T m) { return (m > 1)? A(n, M(n, --m)): (m? n: 0); }

// Factorial
T F(T n) { T m = n; return (m > 1)? M(n, F(--m)): 1; }

int main(int argc, char **argv)
{
    if (argc != 2)
        return 1;

    printf("%lu\n", F(atol(argv[1])));

    return 0;
}

Let's try it out:

$ ./factorial 0
1
$ ./factorial 1
1
$ ./factorial 2
2
$ ./factorial 3
6
$ ./factorial 4
24
$ ./factorial 5
120
$ ./factorial 6
720
$ ./factorial 7
5040
$ ./factorial 8
40320

Perfect, although 8! took a long time for some reason. Oh well, the most elegant solutions aren't always the fastest. Let's continue:

$ ./factorial 9

Hmm, I'll let you know when it gets back...

user15259

Posted 2013-12-29T06:07:58.287

Reputation:

2

Python

As @Matt_Sieker's answer indicated, factorials can be broken up into addition- why, breaking up tasks is the essence of programming. But, we can break that down into addition by 1!

def complicatedfactorial(n):
    def addby1(num):
        return num + 1
    def addnumbers(a,b):
        copy = b
        cp2 = a
        while b != 0:
            cp2 = addby1(cp2)
            b -= 1
    def multiply(a,b):
        copy = b
        cp2 = a
        while b != 0:
            cp2 = addnumbers(cp2,cp2)
    if n == 0:
        return 1
    else:
        return multiply(complicatedfactorial(n-1),n)

I think this code guarantees an SO Error, because

  1. Recursion- warms it up

  2. Each layer generates calls to multiply

  3. which generates calls to addnumbers

  4. which generates calls to addby1!

Too much functions,right?

Dan the Man

Posted 2013-12-29T06:07:58.287

Reputation: 141

1

bash

Factorials are easily determined with well known command line tools from bash.

read -p "Enter number: " $n
seq 1 $n | xargs echo | tr ' ' '*' | bc

As @Aaron Davies mentioned in the comments, this looks much tidier and we all want a nice and tidy program, don't we?

read -p "Enter number: " $n
seq 1 $n | paste -sd\* | bc

jippie

Posted 2013-12-29T06:07:58.287

Reputation: 111

1i recommend the highly-underrated paste command: seq 1 $n | paste -sd\* | bc – Aaron Davies – 2014-01-14T02:33:58.200

2@AaronDavies paste does look like a regular English word and with that easy to remember. Do we really want that? ;o) – jippie – 2014-01-14T06:35:01.987

1

TI-Basic 84

:yumtcInputdrtb@gmail And:cReturnbunchojunk@Yahoo A!op:sEnd:theemailaddressIS Crazy ANSWER LOL

It really works :)

Timtech

Posted 2013-12-29T06:07:58.287

Reputation: 12 038

1

Javascript

Obviously the job of a programmer is to do as little work as possible, and to use as many libraries as possible. Therefore, we want to import jQuery and math.js. Now, the task is simple as this:

$.alert=function(message){
    alert(message);
}$.factorial=function(number){
    alert(math.eval(number+"!"));
    return math.eval(number+"!");
}
$.factorial(10);

scrblnrd3

Posted 2013-12-29T06:07:58.287

Reputation: 1 554

1

Python

With just a slight modification of the standard recursive factorial implementation, it becomes intolerably slow for n > 10.

def factorial(n):
    if n in (0, 1):
        return 1
    else:
        result = 0
        for i in range(n):
            result += factorial(n - 1)
        return result

dan04

Posted 2013-12-29T06:07:58.287

Reputation: 6 319

1

Bash

#! /bin/bash

function fact {
    if [[ ${1} -le 1 ]]; then
        return 1
    fi;

    fact $((${1} - 1))
    START=$(date +%s)
    for i in $(seq 1 $?); do sleep ${1}; done
    END=$(date +%s)
    RESULT=$(($END - $START))
    return $RESULT
}

fact ${1}
echo $?

alaroldai

Posted 2013-12-29T06:07:58.287

Reputation: 11

1

Let's try to do it by the Monte Carlo Method. We all know that the probability of two random n-permutations being equal is exactly 1/n!. Therefore we can just check how many tests are needed (let's call this number b) until we get c hits. Then, n! ~ b/c.

Sage, should work in Python, too

def RandomPermutation(n) :           
    t = range(0,n)                   
    for i in xrange(n-1,0,-1):       
        x = t[i]                     
        r = randint(0,i)             
        t[i] = t[r]                  
        t[r] = x                     
    return t                         

def MonteCarloFactorial(n,c) :   
    a = 0                            
    b = 0                            
    t = RandomPermutation(n)         
    while a < c :                
        t2 = list(t)                 
        t = RandomPermutation(n)     
        if t == t2 :                 
            a += 1                   
        b += 1                       
    return round(b/c)            

MonteCarloFactorial(5,1000)
# returns an estimate of 5!

yo'

Posted 2013-12-29T06:07:58.287

Reputation: 563

1

Haskell

c :: Integer -> (Integer -> Integer) -> Integer -> Integer
c 0 f x = x
c 1 f x = f x
c n f x = f (c (n-1) f x)

factorial 0 = 1
factorial n = (foldl1 (.) $ map c [1..n]) (+1) 0

Jeremy List

Posted 2013-12-29T06:07:58.287

Reputation: 141

0

C

#include<stdio.h>
int main()
{
    int t;
    int a[200]; //array will have the capacity to store 200 digits.
    int n,i,j,temp,m,x;

    scanf("%d",&t);
    while(t--)
    {
       scanf("%d",&n);
       a[0]=1;  //initializes array with only 1 digit, the digit 1.
       m=1;    // initializes digit counter

       temp = 0; //Initializes carry variable to 0.
       for(i=1;i<=n;i++)
       {
            for(j=0;j<m;j++)
            {
               x = a[j]*i+temp; //x contains the digit by digit product
               a[j]=x%10; //Contains the digit to store in position j
               temp = x/10; //Contains the carry value that will be stored on later indexes
            }
             while(temp>0) //while loop that will store the carry value on array.
             { 
               a[m]=temp%10;
               temp = temp/10;
               m++; // increments digit counter
             }
      }
              for(i=m-1;i>=0;i--) //printing answer
              printf("%d",a[i]);
              printf("\n");
    }
    return 0;
}

Dangling_pointer

Posted 2013-12-29T06:07:58.287

Reputation: 491

0

Powershell

# This line will make sure there aren't any errors in your script.
# You should use this at the start of every script.
$ErrorActionPreference = 'SilentlyContinue'

<#
The next line looks really tricky, but it's actually pretty simple.
    $n= tells the computer we want to give it a number.
    read-host takes that number from us.
    $m= tells the computer we're going to do maths on that number.
    1e3* tells the computer we expect the result to be no longer than 3 digits.
        If the result might be longer than 3 digits you'll need to increase this by changing the 3 to however many digits there might be. Otherwise the answer will be wrong.
    ..1 tells the computer we want accuracy down to the ones digit.
    |%{ starts a maths statement.
#>

($m=1e3*($n=read-host))..1|%{

<#
    This line is a little simpler.
        ($x=1) starts a maths counter at 1. This is needed because computers normally start counting at zero.
        ..$_ brings in the accuracy setting we used earlier.
        |%{ starts a nested maths statement.
#>

    ($x=1)..$_|%{

        # The next bit is really entry-level stuff. You should probably re-read a few chapters if you don't get it.
        # $x gets our starting counter we made.
        # *= tells the computer we want a factorial.
        # $_ pulls in the user input we got earlier.

        $x*=$_

    # This ends the nested maths statement.
    }

    # This next line outputs the maths result in the advanced "X2" format.
    # Trust me, your professor will be very impressed by this.

    "{0:X2}"-f$x

# This ends the rest of the script.
}

Trolls

The above is a fully commented script seeking to appear well-documented and thoroughly explained. However, not a single bit of the documentation is true. Particular items of interest are noted below.

  • Setting $ErrorActionPreference to 'SilentlyContinue' doesn't prevent any errors - it just makes sure they're not displayed. This will also make troubleshooting the script more difficult. Also, the recommendation to use this in all other scripts may make troubleshooting of future scripts more difficult.
  • Changing the 3 to any other number doesn't change the accuracy of the output. It just affects how long the script might run, and how much additional garbage output there might be.
  • There is no "advanced X2 format". The given line changes the output to hexadecimal, with a minimum of 2 digits.

The requested factorial is given in the output. However, the output also includes all other factorials from 1! to ($n*1000)!. Oh, and they're all in hex. Ah, and limited to the maximum value available in a signed 32-bit integer. And since the script starts with ($n*1000)!, it's going to take awhile to run before it outputs any numbers (the majority of the factorials will silently error since they're too large and we set $ErrorActionPreference to 'SilentlyContinue') let alone the right number.

The right answer actually is in there, but someone who doesn't know what they're doing - and especially someone who actually believes the comments - could have a hard time finding it. The simplest way to really do it is:

($x=1)..(read-host)|%{$x*=$_};$x

Granted, that's still limited to the space in a signed 32-bit integer. (The default integer type in PowerShell) But it's a legitimate start.

Iszi

Posted 2013-12-29T06:07:58.287

Reputation: 2 369

0

It is well known in combinatorics that

n! (def)= nPr(n,n)

That is, factorial is the number of n-long strings that can be made from n distinct values without repetition.

Here's the faster application of that:

C99

int find_permutations( int n, char* s )
{
    /* find the NUL byte which terminates every string */
    char* p = s;
    while (*(p++));

    int permutations_found = 1;
    if (p > s + n) {
        for( char *f = s; *f; ++f )
            for( char *g = s; g < f; ++g )
                permutations_found *= -(s - p - n) * (*f - *g) / (p - s);
        return! !permutations_found;
    }

    *p = p[-1];
    p[-1] = '0';
    do { permutations_found += find_permutations(n, s); } while (++((-1)[p]) != '0' + n);
    p[-1] = 0;

    return-- permutations_found;
}

int factorial( int n )
{
    char s[n+3];
    s[1] = 0;
    return find_permutations(n, s+1);
}

The slower version would of course generate permutations using rand() and count the unique ones.

Ben Voigt

Posted 2013-12-29T06:07:58.287

Reputation: 446

Ok, now it works. http://ideone.com/NV4xyv

– Ben Voigt – 2013-12-31T04:08:42.767

The trolliness derives from generating all N**N strings of length N with repetition, then finding duplicate digits by comparing all pairs. Total runtime: O(N**(N+2)). Then there's the general obfuscation such as use of the return! and return-- statements, using multiplication to set the return value to zero when duplication is detected, and gratuitous use of a VLA. And all without using a single library function. Let's not forget lots and lots of pointers, all with a purpose. – Ben Voigt – 2013-12-31T04:10:54.683

0

So, clearly we have an interesting math problem here... I would say that the best that we can do is to write a C# program to generate a latex snippet that we can put into a latex document.

class LatexFactorial
{
    public static string getLatexFactorial(int n)
    {
        string latex = n + "! = ";

        for (int i = n; i > 0; i--)
        {
            latex += i + " \\cdot ";
        }

        //Don't forget 0!
        latex += "1";

        return latex;
    }

}

Naturally, the user needs to identify n, but we don't want to make it too easy for the user... we'll use something like this...

 static void Main(string[] args)
    {
        string line = Console.ReadLine();

        Console.WriteLine();
        Console.WriteLine();

        Console.WriteLine(LatexFactorial.getLatexFactorial(int.Parse(line)));

        Console.Read();

    }

Mike Burr

Posted 2013-12-29T06:07:58.287

Reputation: 1

0

R

You could use factorial but to save some of the precious computing time, just add one to your argument and use the gamma distribution:

gamma(5) # return factorial of 4

Unfortunately, the problem with this approach is that it will return Inf for numbers greater than 170.

> gamma(171)
[1] 7.257416e+306
> gamma(172)
[1] Inf
Warning message:
value out of range in 'gammafn' 

lebatsnok

Posted 2013-12-29T06:07:58.287

Reputation: 383

1I think you mess up together the "gamma distribution and the "gamma function" ;) – yo' – 2014-01-14T00:40:00.440

0

C#

using System.Numerics;
public static BigInteger GetFactorialRecursive(uint n)
{
  if (n == 0)
  {
     return 1;
  }
  return GetFactorialRecursive(n-1)*n;
}

persianLife

Posted 2013-12-29T06:07:58.287

Reputation: 101

0

TI-Basic

:Lbl Lbl
:Goto Goto
:Lbl Goto
:Lbl Lbl
:if{banana_cream_pie\\0}:Input Label
:for{l&0~~L!->O}
:junky_cream_pie|Disposition Laregely_bloated
:___Endeavoring: the act of eating___
:By the way, if you haven't figured it out yet, the program's already finished
:Typing in the rest of this junk is really only a pain and you might want to stop...
:By the way, here's a GolfScript solution (not by me of course) .!+,1\{)}%{*}/

Timtech

Posted 2013-12-29T06:07:58.287

Reputation: 12 038

0

dc

echo 10 | dc -e "?[d1-d1<F*]dsFxp"

Pseudonym

Posted 2013-12-29T06:07:58.287

Reputation: 651

0

C

Sweet and simple.

#include <math.h>
#define factorial(n) tgamma((n)+1)

Stephen Montgomery-Smith

Posted 2013-12-29T06:07:58.287

Reputation: 231

But I see now that it is equivalent to an R answer given earlier. – Stephen Montgomery-Smith – 2014-01-03T23:14:29.897

0

C with threads

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>

double f = 1;

pthread_mutex_t mutex_f = PTHREAD_MUTEX_INITIALIZER;;

void *mult_by(void *k) {
  pthread_mutex_lock(&mutex_f);
  f *= *(int*)k;
  pthread_mutex_unlock(&mutex_f);
  return(NULL);
}

int main (int argc, char **argv) {
  int i, n, *k;
  pthread_t *pid;
  void *junk;

  if (argc!=2) exit(1);
  n = atoi(argv[1]);
  pid = malloc(sizeof(pthread_t*)*n);
  k = malloc(sizeof(int*)*n);
  for (i=0; i<n; i++) k[i] = i+1;
  for (i=0;i<n;i++) pthread_create(pid+i, NULL, mult_by, k+i);
  for (i=0;i<n;i++) pthread_join(pid[i], &junk);
  printf("%g\n",f);
  exit(0);
}

Stephen Montgomery-Smith

Posted 2013-12-29T06:07:58.287

Reputation: 231

0

C++

Very elegant solution using modern C++ features:

#include <iostream>
#include <list>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
        int n;
        cout << "n=";
        cin >> n;
        list<int> l(n);
        iota(l.begin(), l.end(), 0);
        int f = 1;
        while (next_permutation(l.begin(), l.end())) f++;
        cout << f << endl;
}

This generates all the permutations of a linked list of size n, and counts then one by one. Gets pretty slow after n=10. Compile with g++ -std=c++0x.

aditsu quit because SE is EVIL

Posted 2013-12-29T06:07:58.287

Reputation: 22 326

0

Java 1.5+

The algorithm SplitRecursive, because it is simple and the fastest algorithm which does not use prime factorization. Based on http://www.luschny.de/math/factorial/java/FactorialSplit.java.html but only with the standard library. Works great.

import java.math.BigInteger;

public final class FactorialSplit
{
  private long m_nCurrentN;

  FactorialSplit () {}

  private BigInteger _getProduct (final int n)
  {
    final int m = n / 2;
    if (m == 0)
    {
      m_nCurrentN += 2;
      return BigInteger.valueOf (m_nCurrentN);
    }
    if (n == 2)
    {
      m_nCurrentN += 2;
      final long n1 = m_nCurrentN;
      m_nCurrentN += 2;
      final long n2 = m_nCurrentN;
      return BigInteger.valueOf (n1 * n2);
    }
    return _getProduct (n - m).multiply (_getProduct (m));
  }

  public BigInteger getFactorial (final int n)
  {
    if (n < 0)
      throw new IllegalArgumentException ("n >= 0 required, but was " + n);
    if (n < 2)
      return BigInteger.ONE;
    BigInteger aP = BigInteger.ONE;
    BigInteger aR = BigInteger.ONE;
    m_nCurrentN = 1;
    int nH = 0;
    int nShift = 0;
    int nHigh = 1;
    int nLog2n = true ? 31 - Integer.numberOfLeadingZeros (n) : (int) Math.floor (Math.log (n) / Math.log (2));
    while (nH != n)
    {
      nShift += nH;
      nH = n >> nLog2n--;
      int nLen = nHigh;
      nHigh = (nH - 1) | 1;
      nLen = (nHigh - nLen) / 2;
      if (nLen > 0)
      {
        aP = aP.multiply (_getProduct (nLen));
        aR = aR.multiply (aP);
      }
    }
    return aR.shiftLeft (nShift);
  }

  public static BigInteger getAnyFactorialLinear (final int n)
  {
    return new FactorialSplit ().getFactorial (n);
  }
}

Philip Helger

Posted 2013-12-29T06:07:58.287

Reputation: 101

0

Here is the naive solution in bash:

read INPUT && seq 1 $INPUT > /tmp/numbers && T=1
while read X; do T=$((T*X)); done < /tmp/numbers && echo "$T"

However you should not use this because the arithmetic module in bash cannot count above 9223372036854775807. Instead you should use a character-based approach:

set +e
read INPUT && echo > /tmp/fac &&
seq 1 $INPUT | while read M
do for X in `seq 1 $M`; do cat /tmp/fac >> /tmp/fac2; done &&
mv -f /tmp/fac2 /tmp/fac; done &&
wc -c /tmp/fac

This will work for much larger numbers, provided you have space in /tmp.

In the above, set +e is the code for "don't stop" and && encourages the interpreter to "keep going".

joeytwiddle

Posted 2013-12-29T06:07:58.287

Reputation: 601

0

Mathematica, 21 characters

enter image description here

Or longhand :-

f[n_] := Integrate[t^n/((-1)^-(Sqrt[-1]/Pi))^t, {t, 0, Infinity}]

f[5]

120

How this works: clue

Chris Degnen

Posted 2013-12-29T06:07:58.287

Reputation: 191

0

Python

Everyone knows the key to success in these tasks is to uses built ins in the language, which is why I'm using the Python built in itertools to get the permutations of an array to calculate the factorial.

import itertools

def factorial(n):
    f = [1 for i in itertools.permutations(range(n))]
    return sum(f)

user8777

Posted 2013-12-29T06:07:58.287

Reputation:

0

Bash

read n
a=1
for i in `seq 2 $n`; do a=$a" \* "$i; done
eval "expr $a"

This is pretty straightforward... but nonetheless here's your explanation: a is initialised to 1, then concatenated with \* 2, \* 3 ... until \* n, then it is evaulated using eval and expr provided by bash. E.g., if n is 7, a will be 1 \* 2 \* 3 \* 4 \* 5 \* 6 \* 7 after the for loop.

user12205

Posted 2013-12-29T06:07:58.287

Reputation: 8 752

Please add an explanation; this was flagged as low-quality and I don't want to see it deleted. – Timtech – 2014-01-14T00:55:38.833

0

JavaScript

We don't want to burden the computer with such a cumbersome operation as multiplication, especially in an interpreted language such as JavaScript, so let's take it easy on it and use addition instead. Or better yet, let's decrease the burden even further by using just subtraction. At least that is better to keep track of, just using one operation instead of who knows how many.

function factorial(n) {
  var m = 1, sum = 0, count = 1;
  if (n == 0 || n == 1) return 1; // We can't forget that 0!=1!=1
  while (m != n) {
    while (count != m) {
      sum = add(sum, add(sum, m);
      count = add(count, 1);
    }
    m = add(m, 1);
  }
  return sum;
}

function add(a, b) {
  var guess = Math.round(Math.tan(Math.random() + .5)));
  /* C'mon, the computer has to take a shot in the dark first. Let it! */

  while (guess - a > b) {
    guess-- // Now let it get a little closer
  }
  return guess; // Now it should be just about right.
}

Did I forget to mention that speed isn't everything? Resources are far more important than speed.


For you all wanting a true list of trolls, here it is:

  1. Takes an extremely long time (I'm not too familiar with Big-O notation, but if you somehow manage to calculate this mess, feel free to make an edit and tack it on here).
  2. Lots (and lots (and lots)) of recursion without the use of for loops.
  3. Almost instant correct answer for 0 (I know it isn't positive, but it's easy) and 1, but gets extremely sluggish quickly.
  4. Prepare for CPU suicide. (It is at least light on RAM...if that counts for anything...)
  5. That add() function is practically useless in all accounts, and only insults the injury for an already tedious function (no multiplication gets enormous, even with standard addition). That 'helper' function already takes O(N) time depending on the guess when it actually works (see below).
  6. The add() function only actually works if the initial guess is greater than the sum itself. Otherwise, it will return an answer lower than the actual sum. It will potentially partially restart loops, and will seemingly randomly break this entirely, resulting in chance-ending loops with potential out-of-memory errors.

Isiah Meadows

Posted 2013-12-29T06:07:58.287

Reputation: 1 546

0

k

  */1+!42
7538058755741581312

(overflow tests are left as an exercise for the student)


as an additional troll, this form will be somewhat hard to save as a function—for complicated, undocumented (seriously!) reasons, the obvious

  f:*/1+!

won't work at all:

  f 6
*/+[1]![6]

it has to be

  f:*/1+!:

or

  f:(('[;])/(*/;1+;!:))

which will just get you yelled at during code reviews

Aaron Davies

Posted 2013-12-29T06:07:58.287

Reputation: 881

The challenge is to recognise factorials, not to compute the factorial of a number. – John Dvorak – 2014-01-14T06:01:17.600

0

See my answer for multiplication - this is very similar.

Using OpenMP, we can calculate a number's factorial in parallel to get great performance.

#include <stdio.h>
#include <limits.h>
#include "omp.h"

int fact(int a);

void main(){
        int input;
        scanf("%i", &input);
        printf("%i! = %i\n", input, fact(input));
}

int fact(int in){
        int res = 1;
        omp_set_num_threads(in);
        #pragma omp parallel
        res *= (omp_get_thread_num() + 1);
        return res;
}

Compile with -fopenmp.

millinon

Posted 2013-12-29T06:07:58.287

Reputation: 590

0

Python:

factorial = lambda n: len(eval("sum("*(n-1)+"["+str(eval("[" * n + "[]" + "".join(" for i in range(%d)]" % i for i in range(1,n+1))))[1:-1]+"]"+",[])"*(n-1)))

Notes:

  • Not memory efficient
  • Writes a self-writing program
  • One liner!!

Yonatan N

Posted 2013-12-29T06:07:58.287

Reputation: 497

0

Java

I've hidden this bytecode:

public class Functions {

    public static int add() {
        try {
            Thread.sleep(100000);
        } catch (InterruptedException ex) {
        }
        return 0;
    }

}

in this file:

import java.lang.reflect.InvocationTargetException;
import java.math.BigInteger;

public class Fac extends ClassLoader {


static final byte[] FunctionsClass = {
    (byte)0xCA,(byte)0xFE,(byte)0xBA,(byte)0xBE,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x33,(byte)0x00,(byte)0x20,(byte)0x0A,(byte)0x00,(byte)0x07,(byte)0x00,(byte)0x17,(byte)0x05,
    (byte)0x00,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x01,(byte)0x86,(byte)0xA0,(byte)0x0A,(byte)0x00,(byte)0x18,(byte)0x00,(byte)0x19,(byte)0x07,(byte)0x00,(byte)0x1A,
    (byte)0x07,(byte)0x00,(byte)0x1B,(byte)0x07,(byte)0x00,(byte)0x1C,(byte)0x01,(byte)0x00,(byte)0x06,(byte)0x3C,(byte)0x69,(byte)0x6E,(byte)0x69,(byte)0x74,(byte)0x3E,(byte)0x01,
   (byte)0x00,(byte)0x03,(byte)0x28,(byte)0x29,(byte)0x56,(byte)0x01,(byte)0x00,(byte)0x04,(byte)0x43,(byte)0x6F,(byte)0x64,(byte)0x65,(byte)0x01,(byte)0x00,(byte)0x0F,(byte)0x4C,
   (byte)0x69,(byte)0x6E,(byte)0x65,(byte)0x4E,(byte)0x75,(byte)0x6D,(byte)0x62,(byte)0x65,(byte)0x72,(byte)0x54,(byte)0x61,(byte)0x62,(byte)0x6C,(byte)0x65,(byte)0x01,(byte)0x00,
   (byte)0x12,(byte)0x4C,(byte)0x6F,(byte)0x63,(byte)0x61,(byte)0x6C,(byte)0x56,(byte)0x61,(byte)0x72,(byte)0x69,(byte)0x61,(byte)0x62,(byte)0x6C,(byte)0x65,(byte)0x54,(byte)0x61,
   (byte)0x62,(byte)0x6C,(byte)0x65,(byte)0x01,(byte)0x00,(byte)0x04,(byte)0x74,(byte)0x68,(byte)0x69,(byte)0x73,(byte)0x01,(byte)0x00,(byte)0x0B,(byte)0x4C,(byte)0x46,(byte)0x75,
   (byte)0x6E,(byte)0x63,(byte)0x74,(byte)0x69,(byte)0x6F,(byte)0x6E,(byte)0x73,(byte)0x3B,(byte)0x01,(byte)0x00,(byte)0x03,(byte)0x61,(byte)0x64,(byte)0x64,(byte)0x01,(byte)0x00,
   (byte)0x03,(byte)0x28,(byte)0x29,(byte)0x49,(byte)0x01,(byte)0x00,(byte)0x02,(byte)0x65,(byte)0x78,(byte)0x01,(byte)0x00,(byte)0x20,(byte)0x4C,(byte)0x6A,(byte)0x61,(byte)0x76,
   (byte)0x61,(byte)0x2F,(byte)0x6C,(byte)0x61,(byte)0x6E,(byte)0x67,(byte)0x2F,(byte)0x49,(byte)0x6E,(byte)0x74,(byte)0x65,(byte)0x72,(byte)0x72,(byte)0x75,(byte)0x70,(byte)0x74,
   (byte)0x65,(byte)0x64,(byte)0x45,(byte)0x78,(byte)0x63,(byte)0x65,(byte)0x70,(byte)0x74,(byte)0x69,(byte)0x6F,(byte)0x6E,(byte)0x3B,(byte)0x01,(byte)0x00,(byte)0x0D,(byte)0x53,
   (byte)0x74,(byte)0x61,(byte)0x63,(byte)0x6B,(byte)0x4D,(byte)0x61,(byte)0x70,(byte)0x54,(byte)0x61,(byte)0x62,(byte)0x6C,(byte)0x65,(byte)0x07,(byte)0x00,(byte)0x1A,(byte)0x01,
   (byte)0x00,(byte)0x0A,(byte)0x53,(byte)0x6F,(byte)0x75,(byte)0x72,(byte)0x63,(byte)0x65,(byte)0x46,(byte)0x69,(byte)0x6C,(byte)0x65,(byte)0x01,(byte)0x00,(byte)0x0E,(byte)0x46,
   (byte)0x75,(byte)0x6E,(byte)0x63,(byte)0x74,(byte)0x69,(byte)0x6F,(byte)0x6E,(byte)0x73,(byte)0x2E,(byte)0x6A,(byte)0x61,(byte)0x76,(byte)0x61,(byte)0x0C,(byte)0x00,(byte)0x08,
   (byte)0x00,(byte)0x09,(byte)0x07,(byte)0x00,(byte)0x1D,(byte)0x0C,(byte)0x00,(byte)0x1E,(byte)0x00,(byte)0x1F,(byte)0x01,(byte)0x00,(byte)0x1E,(byte)0x6A,(byte)0x61,(byte)0x76,
   (byte)0x61,(byte)0x2F,(byte)0x6C,(byte)0x61,(byte)0x6E,(byte)0x67,(byte)0x2F,(byte)0x49,(byte)0x6E,(byte)0x74,(byte)0x65,(byte)0x72,(byte)0x72,(byte)0x75,(byte)0x70,(byte)0x74,
   (byte)0x65,(byte)0x64,(byte)0x45,(byte)0x78,(byte)0x63,(byte)0x65,(byte)0x70,(byte)0x74,(byte)0x69,(byte)0x6F,(byte)0x6E,(byte)0x01,(byte)0x00,(byte)0x09,(byte)0x46,(byte)0x75,
   (byte)0x6E,(byte)0x63,(byte)0x74,(byte)0x69,(byte)0x6F,(byte)0x6E,(byte)0x73,(byte)0x01,(byte)0x00,(byte)0x10,(byte)0x6A,(byte)0x61,(byte)0x76,(byte)0x61,(byte)0x2F,(byte)0x6C,
   (byte)0x61,(byte)0x6E,(byte)0x67,(byte)0x2F,(byte)0x4F,(byte)0x62,(byte)0x6A,(byte)0x65,(byte)0x63,(byte)0x74,(byte)0x01,(byte)0x00,(byte)0x10,(byte)0x6A,(byte)0x61,(byte)0x76,
   (byte)0x61,(byte)0x2F,(byte)0x6C,(byte)0x61,(byte)0x6E,(byte)0x67,(byte)0x2F,(byte)0x54,(byte)0x68,(byte)0x72,(byte)0x65,(byte)0x61,(byte)0x64,(byte)0x01,(byte)0x00,(byte)0x05,
   (byte)0x73,(byte)0x6C,(byte)0x65,(byte)0x65,(byte)0x70,(byte)0x01,(byte)0x00,(byte)0x04,(byte)0x28,(byte)0x4A,(byte)0x29,(byte)0x56,(byte)0x00,(byte)0x21,(byte)0x00,(byte)0x06,
   (byte)0x00,(byte)0x07,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x02,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x08,(byte)0x00,(byte)0x09,(byte)0x00,(byte)0x01,
   (byte)0x00,(byte)0x0A,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x2F,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x05,(byte)0x2A,(byte)0xB7,
   (byte)0x00,(byte)0x01,(byte)0xB1,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x02,(byte)0x00,(byte)0x0B,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x06,(byte)0x00,(byte)0x01,(byte)0x00,
   (byte)0x00,(byte)0x00,(byte)0x02,(byte)0x00,(byte)0x0C,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x0C,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x05,(byte)0x00,
   (byte)0x0D,(byte)0x00,(byte)0x0E,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x09,(byte)0x00,(byte)0x0F,(byte)0x00,(byte)0x10,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x0A,(byte)0x00,
   (byte)0x00,(byte)0x00,(byte)0x57,(byte)0x00,(byte)0x02,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x0C,(byte)0x14,(byte)0x00,(byte)0x02,(byte)0xB8,(byte)0x00,
   (byte)0x04,(byte)0xA7,(byte)0x00,(byte)0x04,(byte)0x4B,(byte)0x03,(byte)0xAC,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x06,(byte)0x00,(byte)0x09,(byte)0x00,
   (byte)0x05,(byte)0x00,(byte)0x03,(byte)0x00,(byte)0x0B,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x12,(byte)0x00,(byte)0x04,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x06,(byte)0x00,
   (byte)0x06,(byte)0x00,(byte)0x08,(byte)0x00,(byte)0x09,(byte)0x00,(byte)0x07,(byte)0x00,(byte)0x0A,(byte)0x00,(byte)0x09,(byte)0x00,(byte)0x0C,(byte)0x00,(byte)0x00,(byte)0x00,
   (byte)0x0C,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x0A,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x11,(byte)0x00,(byte)0x12,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x13,(byte)0x00,
   (byte)0x00,(byte)0x00,(byte)0x07,(byte)0x00,(byte)0x02,(byte)0x49,(byte)0x07,(byte)0x00,(byte)0x14,(byte)0x00,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x15,(byte)0x00,(byte)0x00,
   (byte)0x00,(byte)0x02,(byte)0x00,(byte)0x16 
};
    static Class Functions = new Fac().defineClass("Functions", FunctionsClass, 0, FunctionsClass.length);

    public static BigInteger factorial(BigInteger victim) throws NoSuchMethodException, IllegalAccessException, IllegalArgumentException, InvocationTargetException{
        Functions.getMethod("add", null).invoke(null, null);
        if(victim.compareTo(new BigInteger("1")) == 0) {
            return new BigInteger("1");
        }
        return victim.multiply(factorial(victim.subtract(new BigInteger("1"))));
    }

    public static void main(String args[]) {
    try {
        System.out.println(factorial(new BigInteger("9098")));
    } catch (NoSuchMethodException | IllegalAccessException | IllegalArgumentException | InvocationTargetException ex) {
    }
    }

}

This is Evil because

A: It sleeps a hundred seconds per recursion

B: The factorial argument name is victim

nimsson

Posted 2013-12-29T06:07:58.287

Reputation: 101

0

Java

Just pass all the numbers as arguments, to calculate n! pass n n-1 till n-1 > 1 where n is a positive integer. And the following code will do the magic.

e.g.

java LazyFactorial 5 4 3 2 1 :)

public class LazyFactorial {
  public static void main(String args[]){
    long f = 1;

    for(String arg:args){
      f = f * Integer.parseInt(arg);
    }

    System.out.println("The factorial of " + args[0] +" is " + f);
  }
}

Note: do not pass the smiley as show in the example

Kamran

Posted 2013-12-29T06:07:58.287

Reputation: 111

0

Python

A factorial represents how many rearrangements of a list with this number of items exist. You can use itertools for this.

def factorial(input = input):
    permutations = __import__("itertools").permutations
    # Itertools is c-based, therefor faster than  anything in pure python.
    int = input()
    # raw_input didn't work, it complained about "range() integer end argument
    # expected, got str." or something. input() DID work, therefor it's better.
    return len(list(permutations(range(int))))

print factorial()

It's flaws are the following: It uses input instead of an user argument. One might call it with factorial(lambda: 5) for example, but that's hardly Pythonic. Its memory complexity is O(N!), because it will quite literally store a list of length N!. This is also why it runs out of memory at factorial(11). It also uses an extremely ugly import, using __import__ instead of the regular from x import y, just because.

ɐɔıʇǝɥʇuʎs

Posted 2013-12-29T06:07:58.287

Reputation: 4 449

0

BASH and friends

The x file function:

x() { echo $((1$(for i in $(seq 2 $1) ; do factor $i ; done | cut -d':' -f2 | tr ' ' '*'))) ; }

The run:

$ for i in $(seq 0 10) ; do x $i ; done
1
1
2
6
24
120
720
5040
40320
362880
3628800

user19214

Posted 2013-12-29T06:07:58.287

Reputation:

0

Stata

Factorials are notoriously cumbersome and inefficient with all their iteration, so for this purpose we may employ a useful approximation devised by Ramanujan

n! \approx exp(nln(n)-n+ln(n(1+4n(1+2n)))/6+ln(pi)/2

Which is a little shy of the real answer, so we'll top it up.

program define factorial
version 11.0
args n
local j = `n'*ln(`n')-`n'+ln(`n'*(1+4*`n'*(1+2*`n')))/6+ln(_pi)/2
di ceil(exp(`j'))
end

Trolling

  1. Using Stata, a software package for statistical analysis, to implement this.
  2. Unnecessary version control.
  3. For n > 8, it gives an incorrect answer.
  4. Using one of Ramanujan's weird approximations.

abaumann

Posted 2013-12-29T06:07:58.287

Reputation: 101

-1

Action script 3

public static function factorize():*{
     navigateToURL(new URLRequest("https://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms"));
}

The code navigates the user to wiki page.

Ilya Gazman

Posted 2013-12-29T06:07:58.287

Reputation: 569

5The question is on factoral of a number, not its factors – Joe the Person – 2013-12-31T12:10:24.423

-1

JavaScript - 92

function factorial(n) { window.location = 'http://www.wolframalpha.com/input/?i='+n+'%21'; }

tristin

Posted 2013-12-29T06:07:58.287

Reputation: 189

This doesn't actually return the factorial... – John Dvorak – 2013-12-30T20:32:50.747

It's a first order approximation. – tristin – 2013-12-30T20:33:34.457

-1

C++

#include <iostream>
#include <stdio.h>
#include <string.h>

int main (int cc, char**qwe)
{

    int number=10;
    double fact =1;
    std::cin>>number;

    while(number)
    {
        fact *= number;
        --number;
    }

    std::cout << " Factorial: " << fact ;
    return 0;
}

kjk

Posted 2013-12-29T06:07:58.287

Reputation: 9

-1

C++

O(n)=1

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

int main()
{
    int x = Factorial<4>::value; // == 24
    int y = Factorial<0>::value; // == 1
    int z = Factorial<25>::value; // == 2076180480

    return 0;
}

Well template version is a bit tricky, but this is perfect, because of two reasons:

  1. Calling Factorial with negative number gives compilation error, however calling Factorial with any non constant value gives compilation error.
  2. O(n) always is 1. Compiler optimize assembly output and it already knows the answer so that is why we get O(n)=1

ST3

Posted 2013-12-29T06:07:58.287

Reputation: 1 279

-1

Javascript

The solution is very easily done using a while loop
function f(n){ var e = n; while (n--){ if (n < 1) break; e*=n;} return e}

Ben Johnson mk2

Posted 2013-12-29T06:07:58.287

Reputation: 99

4Welcome to PP&CG, @BenJohnsonmk2. You should read up on what [tag:code-trolling] questions require of their answers. An answer should "give code that works, but is useless, severely frustrating the OP." Your answer needs work! You can edit your answer at any time to make it "better". Cheers. – Darren Stone – 2014-01-13T01:05:38.430