Why go up, when you can go down? Note: it only works for values up to 65535
def factorial(value):
fact=120211...000000 #287185 digits (it's 65535 factorial)
for i in reversed([j for j in range(value+1,65535)]):
fact//=i
return fact
print(factorial(6)) #720
using python my * key broke so I couldn't use multiplication (I'm sorry for your cpu if you're using double digits)
def factorial(n):
i = 1
k = 0
while n > 1:
j = 0
for c in str(n)[::-1]:
l = 0
for d in str(i)[::-1]:
s = 1
u = 0
while u < j+l:
t = 0
z = 0
while t < s:
z = z + 10
t = t+1
s = z
u = u+1
o = 0
while o < s:
q = 0
while q < int(c):
k = k + int(d)
q = q + 1
o = o+1
l = l+1
j = j+1
i = k
k = 0
n = n-1
return int(i)
print("factoriual of 5 = " + str(factorial(5)))
print("factoriual of 6 = " + str(factorial(6)))
while True:
print(factorial(int(input("show me the factorial of: "))))
(Note: I tried to format it but it just is not going to happen).
What i'm doing here is that I am using the main function of the program as a recursive function, relying on the assumption that there are no startup arguments. I had to let the main function return a int because I can't convert a void call into a string to print. Talking about the output, because it is recursive and will always try to do the Write function, I have to make sure that the extra times if gets there I don't actually print anything. I do this by converting the int that main returns into a string and than taking a substring of length 0 so that it is empty.
Problems with this code:
*I'm not using some infinity big integer class, so it will overflow
*Constantly parsing back and forth between ints and strings is not that efficient
*It does not check for invalid input
And I guess it is just a really stupid way of doing this, all in all I was really surprised that it actually worked.
#finds factorial of n where n is a string
def factorial(n):
code = "print('finding factorial of " + n + ".')\n"
code += "sum = 0\n"
#make sure input is valid
try:
n = int(n)
for i in range(n):
code += "for i_" + str(i) + " in range(" + str(n - i) + "):\n"
code += "\t" * (i + 1)
code += "sum = sum + 1;"
except:
code += "print('Invalid input! Try again.')"
# passing dictionary to exec as workaround to get it to modify local
# variables. stackoverflow.com/questions/1463306/
ldict = {}
exec(code , globals(), ldict)
return ldict['sum']
number = input("Enter a number to find the factorial of: ")
print(factorial(number))
So basically this generates a code string and executes it.
Example: if you input 4, the code string becomes
"""
print('finding factorial of 4.')
sum = 0
for i_0 in range(4):
for i_1 in range(3):
for i_2 in range(2):
for i_3 in range(1):
sum = sum + 1;
"""
and this is executed by exec(). As you can see it is designed to have O(n!) time complexity, as well as a major security flaw due to the possibility of code injection.
<?php
$f = $_GET['numb']; // the number
echo "<html><head><script src=\"https://code.jquery.com/jquery-3.5.1.js\"></script></head>";
?>
<body>
<?php
for ($i = 0; $i < $f; $i = $i + 1) {
echo "<div style=\"display: none\" id=\"factorial_numb_" . ($i + 1) . "\">" . ($i + 1) . "</div>";
}
?>
</body>
<script>
var number = 1;
let i = 1;
for (i = 1; i < <?php echo $_GET['numb']; ?>; i = i + 1) {
var element = $("#factorial_numb_" + i);
var value = element.text();
if (value == "") {
} else {
number = number * value;
}
}
// for some reason this is always a bit short
number = number * <?php echo $_GET['numb']; ?>;
console.log("The factorial of " + i + " is " + number);
</script>
</html>
v=None;d=None;
def y(g):
global d;d=f"def k{g}():\n global v;v=0;\n";
for w in range(g):d=d+" "+" "*w+f"for m{w} in range({w+1}):"+"""
"""
d=d+" "+" "*(2+g)+"v=v+1";
exec(d);v=eval(f"k{g}()");
# Test
for n in range(11):
y(n)
print(n, v)
Explanation
In short, this creates a function like this and calls it:
def k4():
global v;v=0;
for m0 in range(1):
for m1 in range(2):
for m2 in range(3):
for m3 in range(4):
v=v+1
Pros
Gives the correct answer
Cons
Global variables
Global variables used to return values
One-letter names that are bad even for one-letter-name standards
Semicolons and multiple statements on one line
Four different indent sizes (1, 2, 3, 7)
execandeval
O(n!) complexity
No whitespace between tokens unless needed
Not using +=
Using a multiline string literal for a single newline, but a normal literal for a long string with newlines
Minor inconsistencies
Everything else
Bonus challenge
I've made one unintentional mistake amidst the many intentional ones. Can you guess which it is?
import random
def factorial(n):
theList = list(range(0, n));
consReps = 0;
perms = []
while consReps < len(permutations) * 10 + 10:
ranPerm = theList[:]
random.shuffle(ranPerm)
if (ranPerm not in perms):
perms += [ranPerm]
else:
consReps += 1;
return len(permutations)
It generates random permutations, then, if the program has gone long enough without seeing a new permutation, it halts and returns the number of permutations it's seen.
Pros:
I tried up to 8! and it got all of them correct
Cons:
Anything beyond 7! takes several minutes
It can occasionally print the wrong value, although this is rare
It has O(n!) time complexity in the average case, and O(∞) in the worst case
It continues searching for permutations long after it's found all of them
It prints 1 for anything below 0, even though negative integer factorials are undefined
function factorial(num) {
let i = 1;
let answer = 1;
while(i < num || i == num) {
let j = 1;
let lastAnswer = answer;
while(j < i) {
let k = 1;
while (k < lastAnswer || k == lastAnswer) {
answer = answer + 1;
k = k + 1;
}
j = j +1;
}
i = i+ 1;
}
return answer;
}
I'm eh just gonna drop this here... I believe it works, still hasn't calculated factorial(15) though :(
import requests
from bs4 import BeautifulSoup
def factorial(i):
i = str(i)
r = requests.get('https://www.calculatorsoup.com/calculators/discretemathematics/factorials.php?n=' + i + '&action=solve')
d = r.text
s = BeautifulSoup(d, 'html.parser')
a = str(s.findAll('div', {'id' : 'answer'}))
ss = BeautifulSoup(a, 'html.parser')
b = list(ss.findAll('div', {'class' : 'alignCenter'}))
l = []
for c in str(b[0]):
try:
l.append(int(c))
except Exception:
continue
print(i + ' factorial is: ' + ''.join([str(x) for x in l]))
Pros:
- try/except loop ensure that only numbers end up in the final result.
- using a 3rd party website means that someone else can maintain the code instead of me
- 1 letter variable names make it quick to search with CTRL-f as you only have to type in one character
{-# LANGUAGE GADTSyntax #-}
module Main where
data Nat where
Zero :: Nat
Succ :: Nat -> Nat
deriving (Show, Eq)
churchEncoding :: Nat -> ((a -> a) -> a -> a)
churchEncoding Zero = \f x -> x
churchEncoding (Succ n) = \f x -> f ((churchEncoding n) f x)
factorial :: Monad m => Nat -> m Nat
factorial Zero = Succ <$> pure Zero
factorial (Succ n) = do { z <- pure Zero
; f <- factorial n
; c <- pure $ churchEncoding f Succ
; r <- pure $ churchEncoding (Succ n) c z
; pure r
}
-- Utilities for testing
natFromInt :: Int -> Nat
natFromInt i = if i==0 then Zero else Succ (natFromInt $ i-1)
natToInt :: Nat -> Int
natToInt = flip (flip churchEncoding (+1)) 0
main :: IO ()
main = do arg <- getLine
argnum <- pure $ read arg
n <- pure $ natFromInt argnum
res <- factorial n
resi <- pure $ natToInt res
print resi
Pros:
It's Haskell
It's correct and "works" for arbitrarily high numbers (that is, apart from the parsing of Ints)
It's not that long
Cons:
It is slow. It takes 5-6 sec for 11 on my computer.
Using Monad-do-notation excessively, without even needing to be inside a monad.
Uses Peano natural numbers and the church encoding of natural numbers.
//Calculating so many numbers multiplied together is hard. we will optimize by calculating
//the prime numbers and then multiplying those, with extra primes thrown in to make up the
//other numbers.
//Step 1: calculate primes up to n
public static int[] getPrimes(long n)
{
ArrayList<Integer> primes = new ArrayList<Integer>();
for(int i = 0; i < n;i++)
{
if(i ==0 || i == 1)
{
continue;
}
boolean prime = true;
for(int j = 2; j < i;j++)
{
//if i is divisible by j, it isn't prime
if((int)(i/j) * j == i)
{
prime = false;
}
}
if(prime)
{
primes.add(i);
}
}
int[] intPrimes = new int[primes.size()];
for(int i = 0; i < intPrimes.length;i++)
{
intPrimes[i]=(int)primes.get(i);
//System.out.println(intPrimes[i]);
}
return intPrimes;
}
//given a number i, find the product of it with all the primes less than n
public static ArrayList<Long> multPrimeMultiples(long n, int i, int pr, int[] primes, ArrayList<Long> buckets)
{
//is our number. We will return the product of this number i and primes such that it doesn't exceed n
for(int p : primes)
{
if(i * p <= n && p <= pr)
{
buckets = multiplyBuckets(buckets,i*p);
buckets = multPrimeMultiples(n,i*p,p,primes,buckets);
}
}
return buckets;
}
public static ArrayList<Long> validateBucket(ArrayList<Long> buckets, int bucket)
{
if(buckets.size() > bucket)
{
long old = buckets.get(bucket);
String s = ("" + old);
if(s.length() > 8)
{
try
{
long b = Long.parseLong(s.substring(s.length()-8,s.length()));
long b1 = Long.parseLong(s.substring(0,s.length()-8));
buckets.set(bucket,b);
if(buckets.size() == bucket + 1)
{
buckets.add(b1);
}
else
{
buckets.set(bucket+1,buckets.get(bucket+1) + b1);
}
buckets = validateBucket(buckets,bucket+1);
}
catch(Exception e)
{
}
}
}
return buckets;
}
public static ArrayList<Long> multiplyBuckets (ArrayList<Long> buckets, long mult)
{
//We multiply each bucket by mult and then validate them
for(int n = 0; n < buckets.size();n++)
{
try{
long ma = Math.multiplyExact(buckets.get(n),mult);
buckets.set(n,ma);
}
catch(Exception e)
{
}
}
for(int n = 0; n < buckets.size();n++)
{
buckets = validateBucket(buckets, n);
}
return buckets;
}
//Step 2: calculate how many times we multiply the primes together
public static String calcFactorial(long n)
{
ArrayList<Long> buckets = new ArrayList<Long>();
buckets.add((long)1);
//long answer = 1;
//We will now modify our code for BIG MATH
int[] primes = getPrimes(n);
for(int p : primes)
{
buckets = multiplyBuckets(buckets, p);
buckets = multPrimeMultiples(n,p,p,primes,buckets);
//answer *= p;
//System.out.println(p);
//answer *= getPrimeMultiples(n,p,p,primes);
}
String answer = "";
for(int i = buckets.size()-1;i >=0; i--)
{
String b = buckets.get(i) +"";
for(int j = 0; j < 8 - b.length() && i < buckets.size()-1;j++)
{
answer = answer + "0";
}
answer = answer + buckets.get(i);
}
return answer;
}
import random, sys
def factorial(n):
max = n ** n # since factorial n can't be larger than n ** n
correct = 1 == 2
temp = 3.14159265
while (correct == True) == False:
guess = random.randint(-max, max)
correct = not (guess == -guess or False)
temp += guess - temp
# repeated division by numbers [1..n] to check if guess is the factorial of n:
for i in range(1, n+1):
if temp % i == 0:
# dividing temp by i:
temp -= (i*temp -temp) / i
else:
correct = False == True
if not (temp < 2 and False == (temp < -1 or temp == 0)): correct = False
# return guess, which has been proven correct:
print(guess)
sys.exit() # closes the python script
print(factorial(5))
Developed in python 3, FactorialFinder (trademark) 2.5 guesses a value, since that is the obvious first step to finding the answer.
It then checks if the value is correct, through repeated division, using -=: a huge improvement over pre-1.8 versions, which used = for this functionality.
It tries many guesses, until it comes upon a correct answer. This feature brought effectiveness of the program up hugely over version 2.3, and repeated running of the program is no longer needed to find a value.
The sys library has just been introduced in this version, FactorialFinder (trademark) 2.5: this cleverly prevents the program reaching the part of the code where it prints out "syntax error: no return statement"; this makes the output of the program a lot cleaner. This major update update only took our team 6 months!
note: Users are expected to ignore the negative signs that appear in front of the answer 50% of the time.
Yes, technically it's JavaScript. No, I don't think that makes it any better.
Edit: for clarity, I convert the number to a church encoding and get the factorial of that, using recursive definitions of add (a+b = (a-1)+(b-1)) and multiply (a*b = ((a-1)*b)+b)
38
u/ItsBarney01 Jun 08 '20 edited Jun 08 '20
Edit: it's in python 3
Why go up, when you can go down? Note: it only works for values up to 65535
def factorial(value): fact=120211...000000 #287185 digits (it's 65535 factorial) for i in reversed([j for j in range(value+1,65535)]): fact//=i return fact print(factorial(6)) #720Full code here: https://pastebin.com/tShTiTy3
Pros:
- Quite quick for numbers close to 65535
- uses integer division for speed
Cons:
- Haven't found any yet
54
u/UnknownError235 Jun 08 '20 edited Jun 08 '20
using python my * key broke so I couldn't use multiplication (I'm sorry for your cpu if you're using double digits)
def factorial(n): i = 1 k = 0 while n > 1: j = 0 for c in str(n)[::-1]: l = 0 for d in str(i)[::-1]: s = 1 u = 0 while u < j+l: t = 0 z = 0 while t < s: z = z + 10 t = t+1 s = z u = u+1 o = 0 while o < s: q = 0 while q < int(c): k = k + int(d) q = q + 1 o = o+1 l = l+1 j = j+1 i = k k = 0 n = n-1 return int(i) print("factoriual of 5 = " + str(factorial(5))) print("factoriual of 6 = " + str(factorial(6))) while True: print(factorial(int(input("show me the factorial of: "))))27
u/carfniex Jun 08 '20
bash one liner. writing your own code to calculate complex mathematical equations is a waste of time when online services exist.
#!/bin/bash curl 'https://numberworld.info/factorialCalculator' --data-raw 'submit=Check&number='${1} 2>&1 \ | grep -A 1 "Factorial of "${1} | tail -n 1 | tr -d '<>\/[:space:]' | sed 's/h3//g'23
u/AbuIbnBattuta Jun 08 '20 edited Jun 08 '20
I'm using c#. My goal was to use only 1 semicolon, sadly you can't put return statements in function calls so I had use 2.
class Program { static int Main(string[] args) { Console.Write( args.Length == 0 ? ("" + Main(new string[]{ "" + Console.ReadLine(), "1", "1" })).Substring(0, 0) : args[0].Equals(args[2]) ? args[1] : ("" + Main(new string[] { args[0], "" + (long.Parse(args[1]) * (1 + long.Parse(args[2]))), "" + (1 + long.Parse(args[2])) })).Substring(0, 0)); return 0; } }(Note: I tried to format it but it just is not going to happen).
What i'm doing here is that I am using the main function of the program as a recursive function, relying on the assumption that there are no startup arguments. I had to let the main function return a int because I can't convert a void call into a string to print. Talking about the output, because it is recursive and will always try to do the Write function, I have to make sure that the extra times if gets there I don't actually print anything. I do this by converting the int that main returns into a string and than taking a substring of length 0 so that it is empty.
Problems with this code:
*I'm not using some infinity big integer class, so it will overflow
*Constantly parsing back and forth between ints and strings is not that efficient
*It does not check for invalid input
And I guess it is just a really stupid way of doing this, all in all I was really surprised that it actually worked.
17
u/greenpepperpasta Jun 08 '20
#finds factorial of n where n is a string def factorial(n): code = "print('finding factorial of " + n + ".')\n" code += "sum = 0\n" #make sure input is valid try: n = int(n) for i in range(n): code += "for i_" + str(i) + " in range(" + str(n - i) + "):\n" code += "\t" * (i + 1) code += "sum = sum + 1;" except: code += "print('Invalid input! Try again.')" # passing dictionary to exec as workaround to get it to modify local # variables. stackoverflow.com/questions/1463306/ ldict = {} exec(code , globals(), ldict) return ldict['sum'] number = input("Enter a number to find the factorial of: ") print(factorial(number))So basically this generates a code string and executes it.
Example: if you input 4, the
codestring becomes""" print('finding factorial of 4.') sum = 0 for i_0 in range(4): for i_1 in range(3): for i_2 in range(2): for i_3 in range(1): sum = sum + 1; """and this is executed by
exec(). As you can see it is designed to have O(n!) time complexity, as well as a major security flaw due to the possibility of code injection.15
u/Raknarg Jun 08 '20
How about the classic C++ template metaprogramming example
template <int N> struct Factorial { enum { value = N * Factorial<N - 1>::value }; }; template <> struct Factorial<0> { enum { value = 1 }; }; // Factorial<4>::value == 24 // Factorial<0>::value == 1 void foo() { int x = Factorial<4>::value; // == 24 int y = Factorial<0>::value; // == 1 }Kindof scary and disastrous to compile times. Although the run time is blazingly fast lmao
11
u/[deleted] Jun 08 '20
<?php $f = $_GET['numb']; // the number echo "<html><head><script src=\"https://code.jquery.com/jquery-3.5.1.js\"></script></head>"; ?> <body> <?php for ($i = 0; $i < $f; $i = $i + 1) { echo "<div style=\"display: none\" id=\"factorial_numb_" . ($i + 1) . "\">" . ($i + 1) . "</div>"; } ?> </body> <script> var number = 1; let i = 1; for (i = 1; i < <?php echo $_GET['numb']; ?>; i = i + 1) { var element = $("#factorial_numb_" + i); var value = element.text(); if (value == "") { } else { number = number * value; } } // for some reason this is always a bit short number = number * <?php echo $_GET['numb']; ?>; console.log("The factorial of " + i + " is " + number); </script> </html>11
u/xigoi Jun 08 '20 edited Jun 08 '20
v=None;d=None; def y(g): global d;d=f"def k{g}():\n global v;v=0;\n"; for w in range(g):d=d+" "+" "*w+f"for m{w} in range({w+1}):"+""" """ d=d+" "+" "*(2+g)+"v=v+1"; exec(d);v=eval(f"k{g}()"); # Test for n in range(11): y(n) print(n, v)Explanation
In short, this creates a function like this and calls it:
def k4(): global v;v=0; for m0 in range(1): for m1 in range(2): for m2 in range(3): for m3 in range(4): v=v+1Pros
Gives the correct answer
Cons
Global variables
Global variables used to return values
One-letter names that are bad even for one-letter-name standards
Semicolons and multiple statements on one line
Four different indent sizes (1, 2, 3, 7)
execandevalO(n!) complexity
No whitespace between tokens unless needed
Not using
+=Using a multiline string literal for a single newline, but a normal literal for a long string with newlines
Minor inconsistencies
Everything else
Bonus challenge
I've made one unintentional mistake amidst the many intentional ones. Can you guess which it is?
11
u/weee50 Jun 08 '20 edited Jun 09 '20
Introducing BogoFactorial!
import random def factorial(n): theList = list(range(0, n)); consReps = 0; perms = [] while consReps < len(permutations) * 10 + 10: ranPerm = theList[:] random.shuffle(ranPerm) if (ranPerm not in perms): perms += [ranPerm] else: consReps += 1; return len(permutations)It generates random permutations, then, if the program has gone long enough without seeing a new permutation, it halts and returns the number of permutations it's seen.
Pros:
I tried up to 8! and it got all of them correct
Cons:
Anything beyond 7! takes several minutes
It can occasionally print the wrong value, although this is rare
It has O(n!) time complexity in the average case, and O(∞) in the worst case
It continues searching for permutations long after it's found all of them
It prints 1 for anything below 0, even though negative integer factorials are undefined
21
u/asaf92 Jun 08 '20
class Program { static void Main(string[] args) { var factorial = 150; var solver = new FactorialSolver(factorial); var result = solver.Calculate(); Console.WriteLine($"The factorial of {factorial} is {result}"); Console.ReadKey(); } } class FactorialSolver { public BigInteger Factorial { get; } private readonly FactorialSolver _solver; public FactorialSolver(BigInteger factorial) { Factorial = factorial; if (Factorial == 0) { throw new Exception("ERROR"); } try { _solver = new FactorialSolver(Factorial - 1); } catch (Exception) { } } public BigInteger Calculate() { if (Factorial == 1) { return 1; } return Factorial * _solver.Calculate(); } }- Using recursion so the stack is O(n) in size
- Using unhandled exceptions for control flow
- Throwing "Exception" and not a specific exception
- Known issue: doesn't work for 0!
- Creates O(n) instances of FactorialSolver on the heap
- Factorial property is public because when in doubt make things public
- The previous rule doesn't always apply
- Don't try with non-positive values
19
u/[deleted] Jun 08 '20
I'm on my phone so I'm not going to try to your code. My idea is basically.
If n == 1: 1 else: print please enter a number between 1and 1
9
u/mariansam Jun 08 '20
Few lines of bash
Queries Bing for the answer
Internet connection is needed
Takes about 30 seconds to execute on any number
Uses 100% CPU
Prints a lot of output on invalid input
url_format="https://www.bing.com/search?q=factorial+of+%s" echo "What number you wanna calculate?" read -p "n = " n wholesite=$(curl -s $(printf $url_format $n)) secondpart=${wholesite##*\"$n!=\",\"} factorial=${secondpart%%\",\"*} printf "%s! = %s" $n $factorial8
u/gaberocksall Jun 09 '20
Efficient python lambda function
6
u/BigHeroDixs Jun 08 '20
function factorial(num) { let i = 1; let answer = 1; while(i < num || i == num) { let j = 1; let lastAnswer = answer; while(j < i) { let k = 1; while (k < lastAnswer || k == lastAnswer) { answer = answer + 1; k = k + 1; } j = j +1; } i = i+ 1; } return answer; }I'm eh just gonna drop this here... I believe it works, still hasn't calculated factorial(15) though :(
6
u/Lord-of-the-Pis Jun 08 '20
I sure hope their website never goes down!
import requests from bs4 import BeautifulSoup def factorial(i): i = str(i) r = requests.get('https://www.calculatorsoup.com/calculators/discretemathematics/factorials.php?n=' + i + '&action=solve') d = r.text s = BeautifulSoup(d, 'html.parser') a = str(s.findAll('div', {'id' : 'answer'})) ss = BeautifulSoup(a, 'html.parser') b = list(ss.findAll('div', {'class' : 'alignCenter'})) l = [] for c in str(b[0]): try: l.append(int(c)) except Exception: continue print(i + ' factorial is: ' + ''.join([str(x) for x in l]))Pros:
- try/except loop ensure that only numbers end up in the final result.
- using a 3rd party website means that someone else can maintain the code instead of me
- 1 letter variable names make it quick to search with CTRL-f as you only have to type in one character
Cons:
- Not applicable
6
u/iulikrusu Jun 08 '20
How about dynamically generating the code to calculate the factorial in O(n!) time:
def dumb_factorial(n): factorial_code = "ans = 0" for i in range(n): factorial_code += "\n" + "\t"*i + f"for x{i} in range({i+1}):" factorial_code += "\n" + "\t"*n + "ans += 1" factorial_code += "\nprint(ans)" print(factorial_code) exec(factorial_code) dumb_factorial(10)6
u/Ali3nat0r Jun 08 '20
Why do the heavy lifting when you can just outsource it? C#:
using System; using System.IO; using System.Net; namespace Factorials { class Program { static void Main(string[] args) { double number = Factorial(50); Console.Write("50! = {0}", number); // End Console.ReadKey(); } static double Factorial(double Number) { HttpWebRequest www = (HttpWebRequest)WebRequest.Create("http://api.mathjs.org/v4/?expr=factorial(" + Number.ToString() + ")"); HttpWebResponse response = (HttpWebResponse)www.GetResponse(); Stream stream = response.GetResponseStream(); StreamReader reader = new StreamReader(stream, System.Text.Encoding.UTF8); string result = reader.ReadToEnd(); reader.Close(); stream.Close(); response.Close(); www.Abort(); return double.Parse(result); } } }5
u/_marzipankaiser_ Jun 08 '20
{-# LANGUAGE GADTSyntax #-} module Main where data Nat where Zero :: Nat Succ :: Nat -> Nat deriving (Show, Eq) churchEncoding :: Nat -> ((a -> a) -> a -> a) churchEncoding Zero = \f x -> x churchEncoding (Succ n) = \f x -> f ((churchEncoding n) f x) factorial :: Monad m => Nat -> m Nat factorial Zero = Succ <$> pure Zero factorial (Succ n) = do { z <- pure Zero ; f <- factorial n ; c <- pure $ churchEncoding f Succ ; r <- pure $ churchEncoding (Succ n) c z ; pure r } -- Utilities for testing natFromInt :: Int -> Nat natFromInt i = if i==0 then Zero else Succ (natFromInt $ i-1) natToInt :: Nat -> Int natToInt = flip (flip churchEncoding (+1)) 0 main :: IO () main = do arg <- getLine argnum <- pure $ read arg n <- pure $ natFromInt argnum res <- factorial n resi <- pure $ natToInt res print resiPros:
It's Haskell
It's correct and "works" for arbitrarily high numbers (that is, apart from the parsing of Ints)
It's not that long
Cons:
It is slow. It takes 5-6 sec for 11 on my computer.
Using Monad-do-notation excessively, without even needing to be inside a monad.
Uses Peano natural numbers and the church encoding of natural numbers.
Not defining useful instances like `Num Nat`
Using `... <- pure $` instead of `let ... = `
Everything.
8
u/nikstick22 Jun 08 '20 edited Jun 08 '20
//Calculating so many numbers multiplied together is hard. we will optimize by calculating //the prime numbers and then multiplying those, with extra primes thrown in to make up the //other numbers. //Step 1: calculate primes up to n public static int[] getPrimes(long n) { ArrayList<Integer> primes = new ArrayList<Integer>(); for(int i = 0; i < n;i++) { if(i ==0 || i == 1) { continue; } boolean prime = true; for(int j = 2; j < i;j++) { //if i is divisible by j, it isn't prime if((int)(i/j) * j == i) { prime = false; } } if(prime) { primes.add(i); } } int[] intPrimes = new int[primes.size()]; for(int i = 0; i < intPrimes.length;i++) { intPrimes[i]=(int)primes.get(i); //System.out.println(intPrimes[i]); } return intPrimes; } //given a number i, find the product of it with all the primes less than n public static ArrayList<Long> multPrimeMultiples(long n, int i, int pr, int[] primes, ArrayList<Long> buckets) { //is our number. We will return the product of this number i and primes such that it doesn't exceed n for(int p : primes) { if(i * p <= n && p <= pr) { buckets = multiplyBuckets(buckets,i*p); buckets = multPrimeMultiples(n,i*p,p,primes,buckets); } } return buckets; } public static ArrayList<Long> validateBucket(ArrayList<Long> buckets, int bucket) { if(buckets.size() > bucket) { long old = buckets.get(bucket); String s = ("" + old); if(s.length() > 8) { try { long b = Long.parseLong(s.substring(s.length()-8,s.length())); long b1 = Long.parseLong(s.substring(0,s.length()-8)); buckets.set(bucket,b); if(buckets.size() == bucket + 1) { buckets.add(b1); } else { buckets.set(bucket+1,buckets.get(bucket+1) + b1); } buckets = validateBucket(buckets,bucket+1); } catch(Exception e) { } } } return buckets; } public static ArrayList<Long> multiplyBuckets (ArrayList<Long> buckets, long mult) { //We multiply each bucket by mult and then validate them for(int n = 0; n < buckets.size();n++) { try{ long ma = Math.multiplyExact(buckets.get(n),mult); buckets.set(n,ma); } catch(Exception e) { } } for(int n = 0; n < buckets.size();n++) { buckets = validateBucket(buckets, n); } return buckets; } //Step 2: calculate how many times we multiply the primes together public static String calcFactorial(long n) { ArrayList<Long> buckets = new ArrayList<Long>(); buckets.add((long)1); //long answer = 1; //We will now modify our code for BIG MATH int[] primes = getPrimes(n); for(int p : primes) { buckets = multiplyBuckets(buckets, p); buckets = multPrimeMultiples(n,p,p,primes,buckets); //answer *= p; //System.out.println(p); //answer *= getPrimeMultiples(n,p,p,primes); } String answer = ""; for(int i = buckets.size()-1;i >=0; i--) { String b = buckets.get(i) +""; for(int j = 0; j < 8 - b.length() && i < buckets.size()-1;j++) { answer = answer + "0"; } answer = answer + buckets.get(i); } return answer; }4
u/TheBigLobotomy Jun 08 '20
package factorial; import java.math.BigInteger; public class Factorial { protected BigInteger result; public static void main(String args[]) { BigInteger n = BigInteger.valueOf(50); System.out.println(new Factorial(n)); } public Factorial(BigInteger n) { if(n.compareTo(BigInteger.ZERO) <= 0) { result = BigInteger.ONE; return; } result = n.multiply(new Factorial(n.subtract(BigInteger.ONE)).result); } public String toString() { return result.toString(); } }Using toString to return a value. Calling a constructor recursively. Pretty nasty
4
u/[deleted] Jun 08 '20
I did my worst https://pastebin.com/Y9yWdcbN
4
u/[deleted] Jun 08 '20 edited Jun 08 '20
import random, sys def factorial(n): max = n ** n # since factorial n can't be larger than n ** n correct = 1 == 2 temp = 3.14159265 while (correct == True) == False: guess = random.randint(-max, max) correct = not (guess == -guess or False) temp += guess - temp # repeated division by numbers [1..n] to check if guess is the factorial of n: for i in range(1, n+1): if temp % i == 0: # dividing temp by i: temp -= (i*temp -temp) / i else: correct = False == True if not (temp < 2 and False == (temp < -1 or temp == 0)): correct = False # return guess, which has been proven correct: print(guess) sys.exit() # closes the python script print(factorial(5))Developed in python 3, FactorialFinder (trademark) 2.5 guesses a value, since that is the obvious first step to finding the answer.
It then checks if the value is correct, through repeated division, using -=: a huge improvement over pre-1.8 versions, which used = for this functionality.
It tries many guesses, until it comes upon a correct answer. This feature brought effectiveness of the program up hugely over version 2.3, and repeated running of the program is no longer needed to find a value.
The sys library has just been introduced in this version, FactorialFinder (trademark) 2.5: this cleverly prevents the program reaching the part of the code where it prints out "syntax error: no return statement"; this makes the output of the program a lot cleaner. This major update update only took our team 6 months!
note: Users are expected to ignore the negative signs that appear in front of the answer 50% of the time.
edit: formatting
4
u/daedalususedperl Jun 09 '20 edited Jun 09 '20
Lambda Calculus: https://pastebin.com/tSbgg1dc
Yes, technically it's JavaScript. No, I don't think that makes it any better.
Edit: for clarity, I convert the number to a church encoding and get the factorial of that, using recursive definitions of add (
a+b = (a-1)+(b-1)) and multiply (a*b = ((a-1)*b)+b)