Skip to content

Instantly share code, notes, and snippets.

@Felix-Kyun
Created January 14, 2025 17:58
Show Gist options
  • Save Felix-Kyun/e201ef580a17dd1c27fb7e4441b5ba8f to your computer and use it in GitHub Desktop.
Save Felix-Kyun/e201ef580a17dd1c27fb7e4441b5ba8f to your computer and use it in GitHub Desktop.
js program to find factorials of larger numbers
const toInt = (str) => str - "0";
function factorial(num) {
num = trimLeadingZero(num);
if (num === "0" || num === "1") return "1";
return stringMultiply(num, factorial(stringSubtract(num, 1)));
}
function trimLeadingZero(num) {
let numArray = Array.from(num);
if (num.length === 1) return num;
for (let i = 0; i < num.length; i++) {
if (num[i] === "0") numArray.shift();
else return numArray.join("");
}
return numArray.join("");
}
function stringSubtract(minuend, subtrahend) {
let carry = subtrahend;
let numArray = Array.from(minuend);
for (let i = numArray.length - 1; i >= 0; --i) {
if (toInt(numArray[i]) < carry) {
// we need to carry over 1
numArray[i] = toInt(numArray[i]) + 10 - carry + "";
carry = 1;
} else {
numArray[i] = toInt(numArray[i]) - carry + "";
carry = 0;
}
}
return numArray.join("");
}
// only to be used when multiplier is single digit
function stringSingleMultiply(multiplicand, multiplier) {
if (multiplier == 0) return "0";
let carry = 0;
let numArray = Array.from(multiplicand);
for (let i = numArray.length - 1; i >= 0; --i) {
let num = toInt(numArray[i]) * multiplier;
carry += num;
numArray[i] = (carry % 10) + "";
carry = carry != 0 ? Math.floor(carry / 10) : 0;
}
if (carry != 0) numArray.unshift(carry + "");
return numArray.join("");
}
function stringMultiply(multiplicand, multiplier) {
let result = "0";
for (let i = multiplier.length - 1, power = 0; i >= 0; --i, ++power) {
result = stringAddition(
result,
stringSingleMultiply(
multiplyBase10Expo(multiplicand, power),
multiplier[i]
)
);
}
return result;
}
function stringAddition(num, addend) {
if (addend === "0") return num;
let finalLength = num.length > addend.length ? num.length : addend.length;
let finalString = [];
let carry = 0;
for (i = 0; i < finalLength; i++) {
if (i < num.length) {
carry += toInt(num[num.length - i - 1]);
}
if (i < addend.length) {
carry += toInt(addend[addend.length - i - 1]);
}
finalString.unshift((carry % 10) + "");
carry = Math.floor(carry / 10);
}
if (carry != 0) finalString.unshift(carry + "");
return finalString.join("");
}
// basically does (num * 10 ^ power)
function multiplyBase10Expo(num, power) {
for (let i = 0; i < power; i++) {
num += "0";
}
return num;
}
console.log(factorial("1000"));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment