samples/2022/03/algorithms/factorial.js

"use strict";

function mul2(v) {
	let res = [];
	let shift = 0;
	let t;
	for (let i = v.length - 1; i >= 0; i--) {
		t = v[i]*2 + shift;
		shift = t >= 10 ? 1 : 0;
		res.unshift(t % 10);
	}

	if (shift > 0) {
		res.unshift(1);
	}

	return res;
}

function div2(v) {
	let res = [];
	let s = 0, div;
	let leading = false;
	for (let i = 0; i < v.length; i++) {
		s = s*10 + v[i];
		div = s >> 1;
		s = s - 2*div;
		if (!leading && div > 0) {
			leading = true;
		}
		if (leading || Math.abs(div) > 1e-6) {
			res.push(div);
		} 
	}

	if (!res.length) {
		res.push(0);
	}

	return res;
}

function odd(a) {
	return a.length > 0 ? a[a.length-1] % 2 === 1: false;
}

function zero(a) {
	return !a.length || (a.length == 1 && a[0] === 0);
}

function sum(a, b) {
	let x = [...a];
	let y = [...b];
	let shift = 0;
	let res   = []
	let e1, e2, e3;
	while (x.length || y.length) {
		e1 = x.length ? x.pop() : 0;
		e2 = y.length ? y.pop() : 0;
		e3 = e1+e2+shift;
		res.unshift(e3 % 10);
		shift = e3 >= 10 ? 1 : 0;
	}

	if (shift) {
		res.unshift(1);
	}

	return res;
}

function mul(a, b) {
	let x = [...a];
	let y = [...b];
	let x2;
	let y2;

	let s = [0];

	while (!zero(x)) {
		x2 = div2(x);
		y2 = mul2(y);
		if (odd(x)) {
			s = sum(s, y);
		}
		x = x2;
		y = y2;
	}

	return s;
}

function factorial(x) {
	let c = [ 0 ];
	let m =  [1];
	let mp = [1];
	for (let i = 0; i < x; i++) {
		c = sum(c, [1]);
		m = mul(mp, c);
		mp = m;
	}

	return m;
}

console.log(factorial(7).map((el) => '' + el).join(''));