Arithmetic with Large Numbers in JavaScript

Most programming languages store very large numerical values using a maximum of 64 bits, which is enough to represent 18 quintillion unique values, which in turn uses about 20 decimal digits of precision. This is obviously plenty for most applications. However, for truly gigantic numbers, or for numbers with very many digits of precision, even 18 quintillion isn’t enough.

As an example, consider the value of 1234 raised to the 56th power. The result is a 174-digit number. Since, again, most programming languages only have 64 bits to store that value in, and since they therefore can only store about 20 digits in that amount of space, they might simply round the value off, representing it as, perhaps, 1.299119026 x 10^173.

Again, this is good enough for most applications. But some applications require absolute precision. Not even a single digit is insignificant, so rounding is out of the question. One such application is found in encryption algorithms, in which large integers are commonly raised to the power of other large integers, resulting in truly gigantic integers whose every digit must be accurately recorded.

The code shown below implements a library of objects that will allow large numbers to be added, subtracted, multiplied, divided, and exponentiated without any loss of precision. To see it in action, copy it into an .html file and open that file in a web browser that runs JavaScript.

<html>
<body>
<script type='text/javascript'>

function LargeIntegerTest()
{
	this.main = function()
	{
		var operationsToTestAsStrings =
		[
			"1234 + 56",
			"1234 - 56",
			"1234 * 56",
			"1234 / 56",
			"1234 % 56",
			"1234 ^ 56",
		];

		var textToShow = "";

		var operationLookup = new Array();
		operationLookup["+"] = "add";
		operationLookup["-"] = "subtract";
		operationLookup["*"] = "multiply";
		operationLookup["/"] = "divide";
		operationLookup["%"] = "modulo";
		operationLookup["^"] = "raiseToPower";

		for (var i = 0; i < operationsToTestAsStrings.length; i++)
		{
			var operationToTestAsString = operationsToTestAsStrings[i];

			var operatorAndOperands = operationToTestAsString.split(" ");

			var operator = operatorAndOperands[1];
			var operand0AsInt = parseInt(operatorAndOperands[0]);
			var operand1AsInt = parseInt(operatorAndOperands[2]);
			var operand0 = new LargeInteger(10).setFromInt(operand0AsInt);
			var operand1 = new LargeInteger(10).setFromInt(operand1AsInt);

			var result;

			result = operand0.clone()[operationLookup[operator]](operand1);

			textToShow += operationToTestAsString + " = " + result.toString() + "<br />";
		}

		var htmlElementToShow = document.createElement("p");
		htmlElementToShow.innerHTML = textToShow;
		document.body.appendChild(htmlElementToShow);
	}
}

// classes

function LargeInteger(base)
{
	this.base = base;
	this.digits = new Array();
}
{
	// instance methods

	LargeInteger.prototype.add = function(other)
	{
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		var numberOfDigitsGreater;

		if (numberOfDigitsInThis >= numberOfDigitsInOther)
		{
			numberOfDigitsGreater = numberOfDigitsInThis;
		}
		else
		{
			numberOfDigitsGreater = numberOfDigitsInOther;
		}

		var numberOfDigitsInSum = numberOfDigitsGreater + 1;

		this.expandNumberOfDigitsTo(numberOfDigitsInSum);
		other.expandNumberOfDigitsTo(numberOfDigitsInSum);

		var carryDigit = 0;

		for (var i = 0; i < numberOfDigitsInSum; i++)
		{
			var sumAtDigit = this.digits[i] + other.digits[i] + carryDigit;

			var digitValue = sumAtDigit % this.base;
			carryDigit = (sumAtDigit - digitValue) / this.base;

			this.digits[i] = digitValue;
		}

		this.removeLeadingZeroes();
		other.removeLeadingZeroes();

		return this;
	}

	LargeInteger.prototype.clone = function()
	{
		var returnValue = new LargeInteger(this.base);

		returnValue.overwriteWith(this);

		return returnValue;
	}

	LargeInteger.prototype.decrement = function()
	{
		return this.subtract(new LargeInteger(this.base).setFromInt(1));
	}

	LargeInteger.prototype.divide = function(other)
	{
		var dividend = this.clone();
		var divisor = other.clone();
		var base = dividend.base;

		var one = new LargeInteger(base).setFromInt(1);

		var lengthOfDivisorInDigits = divisor.digits.length;
		var differenceInLengths = dividend.digits.length - lengthOfDivisorInDigits;

		dividend.multiplyByBaseRaisedTo(lengthOfDivisorInDigits);
		divisor.multiplyByBaseRaisedTo(differenceInLengths + lengthOfDivisorInDigits);

		var result = new LargeInteger(base).setFromInt(0);

		while (divisor.digits.length > 0)
		{
			if (divisor.isLessThanOrEqualTo(dividend))
			{
				dividend.subtract(divisor);
				result.add(one);
			}
			else
			{
				divisor.divideByBaseRaisedTo(1);
				result.multiplyByBaseRaisedTo(1);
			}	
		}

		result.divideByBaseRaisedTo(2 * lengthOfDivisorInDigits);

		this.overwriteWith(result);

		return this;
	}

	LargeInteger.prototype.divideByBaseRaisedTo = function(exponent)
	{
		this.digits.splice(0, exponent);

		return this;
	}

	LargeInteger.prototype.expandNumberOfDigitsTo = function(numberOfDigitsTotal)
	{
		var numberOfDigitsToAdd = numberOfDigitsTotal - this.digits.length;
		for (var i = 0; i < numberOfDigitsToAdd; i++)
		{
			this.digits.push(0);	
		}

		return this;
	}

	LargeInteger.prototype.increment = function()
	{
		return this.add(new LargeInteger(this.base).setFromInt(1));
	}

	LargeInteger.prototype.isLessThanOrEqualTo = function(other)
	{
		var returnValue;
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		if (numberOfDigitsInThis < numberOfDigitsInOther)
		{
			returnValue = true;
		}
		else if (numberOfDigitsInThis == numberOfDigitsInOther)
		{
			returnValue = true;

			for (var i = numberOfDigitsInThis - 1; i >= 0; i--)
			{
				var digitThis = this.digits[i];
				var digitOther = other.digits[i];

				if (digitThis > digitOther)
				{
					returnValue = false;
					break;
				}
				else if (digitThis < digitOther)
				{
					break;
				}			
			}
		}
		else
		{
			returnValue = false;
		}

		return returnValue;
	}

	LargeInteger.prototype.modulo = function(other)
	{
		var dividend = this.clone();
		var divisor = other.clone();

		var lengthOfDivisorInDigits = divisor.digits.length;
		var differenceInLengths = dividend.digits.length - lengthOfDivisorInDigits;

		var divisorOriginal = divisor.clone();
		divisor.multiplyByBaseRaisedTo(differenceInLengths);

		while (divisor.digits.length >= lengthOfDivisorInDigits)
		{
			if (divisor.isLessThanOrEqualTo(dividend))
			{
				dividend.subtract(divisor);
			}
			else
			{
				divisor.divideByBaseRaisedTo(1);
			}	
		}

		this.overwriteWith(dividend);

		return this;
	}

	LargeInteger.prototype.multiply = function(other)
	{
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;		

		var numberOfDigitsInProduct = numberOfDigitsInThis + numberOfDigitsInOther; 
		var product = new LargeInteger(this.base).expandNumberOfDigitsTo(numberOfDigitsInProduct);

		for (var i = 0; i < numberOfDigitsInThis; i++)
		{
			var digitFromThis = this.digits[i];

			for (var j = 0; j < numberOfDigitsInOther; j++)
			{
				var digitFromOther = other.digits[j];

				var productOfDigits = 
					digitFromThis 
					* digitFromOther;

				var productDigitIndex = i + j;

				var carryDigit = productOfDigits; 

				while (carryDigit > 0)
				{
					var sumAtDigit = product.digits[productDigitIndex] + carryDigit;

					var digitValue = sumAtDigit % this.base;
					carryDigit = (sumAtDigit - digitValue) / this.base;

					product.digits[productDigitIndex] = digitValue;

					productDigitIndex++;
				}
			}
		}

		product.removeLeadingZeroes();
		this.overwriteWith(product);

		return this;
	}

	LargeInteger.prototype.multiplyByBaseRaisedTo = function(exponent)
	{
		for (var i = 0; i < exponent; i++)
		{
			this.digits.splice(0, 0, 0);
		}

		return this;
	}

	LargeInteger.prototype.overwriteWith = function(other)
	{
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		for (var i = 0; i < numberOfDigitsInOther; i++)
		{
			this.digits[i] = other.digits[i];
		}

		if (numberOfDigitsInThis > numberOfDigitsInOther)
		{
			this.digits.splice
			(
				numberOfDigitsInOther, 
				numberOfDigitsInThis - numberOfDigitsInOther
			);
		}		

		return this;
	}

	LargeInteger.prototype.raiseToPower = function(exponent)
	{
		var result = this.raiseToPowerBySquaring(exponent);

		this.overwriteWith(result);

		return this;
	}

	LargeInteger.prototype.raiseToPowerBySquaring = function(exponent)
	{
		var returnValue = LargeInteger.raiseValueToPowerBySquaring
		(
			this.clone(), 
			exponent.clone(), 
			new LargeInteger(this.base).setFromInt(1),
			new LargeInteger(this.base).setFromInt(2)
		);

		return returnValue;
	}

	LargeInteger.raiseValueToPowerBySquaring = function
	(
		valueToRaise, exponent, constantOne, constantTwo
	)
	{
		var returnValue;

		if (exponent.digits.length == 1 && exponent.digits[0] == 1)
		{
			returnValue = valueToRaise;
		}
		else if (exponent.digits[0] % 2 == 0)
		{
			returnValue = LargeInteger.raiseValueToPowerBySquaring
			(
				valueToRaise.clone().multiply(valueToRaise), 
				exponent.clone().divide(constantTwo),
				constantOne,
				constantTwo
			);
		}
		else
		{
			returnValue = LargeInteger.raiseValueToPowerBySquaring
			(
				valueToRaise.clone().multiply(valueToRaise), 
				exponent.clone().subtract(constantOne).divide(constantTwo),
				constantOne,
				constantTwo
			).multiply
			(
				valueToRaise
			);
		}

		return returnValue;
	}

	LargeInteger.prototype.removeLeadingZeroes = function()
	{
		return this.removeLeadingZeroesDownTo(0);
	}

	LargeInteger.prototype.removeLeadingZeroesDownTo = function(numberOfDigitsTotal)
	{
		var i = this.digits.length - 1;

		while (i >= numberOfDigitsTotal && this.digits[i] == 0)
		{
			this.digits.splice(i, 1);	
			i--;
		}

		return this;
	}

	LargeInteger.prototype.setFromInt = function(valueToSet)
	{
		var d = 0;

		while (valueToSet > 0)
		{
			var digitValue = valueToSet % this.base;
			valueToSet = (valueToSet - digitValue) / this.base;
			this.digits[d] = digitValue;

			d++;
		}

		this.removeLeadingZeroes();

		return this;
	}

	LargeInteger.prototype.subtract = function(other)
	{
		var base = this.base;

		var numberOfDigitsInOther = other.digits.length;

		var numberOfDigitsInThis = this.digits.length;
		other.expandNumberOfDigitsTo(numberOfDigitsInThis);

		for (var i = 0; i < numberOfDigitsInOther; i++)
		{
			var digitFromThis = this.digits[i];
			var digitFromOther = other.digits[i];

			if (digitFromThis < digitFromOther)
			{
				var valueBorrowed = 0;
				var j = i;

				while (valueBorrowed == 0)
				{
					j++;

					var digitToBorrowFrom = this.digits[j];
					if (digitToBorrowFrom > 0)
					{
						valueBorrowed = base;
						this.digits[j]--;

						j--;
						while (j > i)
						{
							this.digits[j] = base - 1;
							j--;
						}
					}
				}

				digitFromThis += valueBorrowed;				
			}

			this.digits[i] = digitFromThis - digitFromOther;
		}

		this.removeLeadingZeroes();
		other.removeLeadingZeroes();

		return this;
	}

	LargeInteger.prototype.toInt = function()
	{
		var returnValue = 0;

		var placeMultiplierCurrent = 1;

		var numberOfDigits = this.digits.length;

		for (var i = 0; i < numberOfDigits; i++)
		{
			returnValue += this.digits[i] * placeMultiplierCurrent;

			placeMultiplierCurrent *= this.base;
		}

		return returnValue;
	}

	LargeInteger.prototype.toString = function()
	{
		var returnValue = "";

		var numberOfDigits = this.digits.length;

		for (var i = numberOfDigits - 1; i >= 0; i--)
		{
			returnValue += "" + this.digits[i];
		}

		return returnValue;
	}

}

new LargeIntegerTest().main();

</script>

</body>
</html>
Advertisements
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s