public static class Program
{
public static void Main()
{
System.Console.WriteLine(MultiplyByHand("-5", "3")); //-15
System.Console.WriteLine(MultiplyByHand("-5", "-3")); //15
System.Console.WriteLine(MultiplyByHand("5", "-3")); //-15
System.Console.WriteLine(MultiplyByHand("5", "3")); //15
System.Console.WriteLine(MultiplyByHand("0", "-0")); //0
System.Console.WriteLine(MultiplyByHand("0", "-7")); //0
System.Console.WriteLine(MultiplyByHand("-0", "7")); //0
System.Console.WriteLine(MultiplyByHand("6", "7")); //42
System.Console.WriteLine(MultiplyByHand("10", "10")); //100
System.Console.WriteLine(MultiplyByHand("9", "999")); //8991
System.Console.WriteLine(MultiplyByHand("99", "999")); //98901
System.Console.WriteLine(MultiplyByHand("999", "99")); //98901
System.Console.WriteLine(MultiplyByHand("98901", "999")); //98802099
System.Console.WriteLine(MultiplyByHand("9999999999999", "9999999999999")); //99999999999980000000000001
string factorial5 = Factorial(5);
System.Console.WriteLine(factorial5);
string factorial500 = Factorial(500);
System.Console.WriteLine(factorial500);
string factorial1050 = Factorial(1050);
System.Console.WriteLine(factorial1050);
System.Console.ReadLine();
}
private static string Factorial(uint number)
{
string factorial = "1";
if (number < 2)
{
return factorial;
}
bool overflown = false;
for (uint currentNumber = 2; currentNumber <= number; currentNumber++)
{
if (!overflown)
{
try
{
decimal lastFactorial = decimal.Parse(factorial);
decimal currentFactorial = checked(currentNumber * lastFactorial);
factorial = currentFactorial.ToString();
}
catch (System.OverflowException)
{
overflown = true;
}
}
if (overflown)
{
factorial = MultiplyByHand(currentNumber.ToString(), factorial);
}
}
return factorial;
}
private static string MultiplyByHand(string a, string b)
{
if (NotANumber(a))
{
throw new System.ArgumentException("a is not a number", nameof(a));
}
else if (NotANumber(b))
{
throw new System.ArgumentException("b is not a number", nameof(a));
}
bool aNegative = false;
bool bNegative = false;
if (a[0] == '-')
{
aNegative = true;
a = a.Substring(1);
}
if (b[0] == '-')
{
bNegative = true;
b = b.Substring(1);
}
if (b.Length > a.Length)
{
string temp = a;
a = b;
b = temp;
}
int maxResultLength = a.Length + b.Length; //max is (number of places of a) + (number of places of b + 1), e.g. 9 x 9 = 81, 99 x 999 = 98901, 10 x 10 = 100
byte[,] grid = MultiplyDigits(a, b, maxResultLength);
byte[] resultDigits = SumColumns(grid, b.Length, maxResultLength);
string result = BuildResult(resultDigits, aNegative, bNegative);
return result;
}
private static bool NotANumber(string text)
{
if (string.IsNullOrWhiteSpace(text))
{
return true;
}
if (text[0] == '-')
{
if (text.Length == 1)
{
return true;
}
text = text.Substring(1);
}
for (int position = 0; position < text.Length; position++)
{
if (text[position] < '0' || text[position] > '9')
{
return true;
}
}
return false;
}
private static byte[,] MultiplyDigits(string a, string b, int maxResultLength)
{
byte[,] grid = new byte[b.Length, maxResultLength];
char[] aDigits = a.ToCharArray();
char[] bDigits = b.ToCharArray();
for (int bPosition = bDigits.Length - 1; bPosition >= 0; bPosition--)
{
int[] remainder = new int[maxResultLength];
int verticalPosition = bDigits.Length - 1 - bPosition;
for (int aPosition = aDigits.Length - 1; aPosition >= 0; aPosition--)
{
int horizontalPosition = aPosition + bPosition + 1;
char aDigit = aDigits[aPosition];
char bDigit = bDigits[bPosition];
byte aFactor = byte.Parse(aDigit.ToString());
byte bFactor = byte.Parse(bDigit.ToString());
int product = aFactor * bFactor;
SetRowDigit(grid, remainder, verticalPosition, horizontalPosition, product);
}
for (int remainderPosition = remainder.Length - 1; remainderPosition >= 0; remainderPosition--)
{
if (remainder[remainderPosition] > 0)
{
SetRowDigit(grid, remainder, verticalPosition, remainderPosition, 0);
}
}
}
//LogMultiplication(grid, b.Length, maxResultLength);
return grid;
}
private static void SetRowDigit(byte[,] grid, int[] remainder, int verticalPosition, int horizontalPosition, int product)
{
int value = product + grid[verticalPosition, horizontalPosition] + remainder[horizontalPosition];
remainder[horizontalPosition] = 0;
if (value >= 10)
{
string columnText = value.ToString();
char digit = columnText[columnText.Length - 1];
grid[verticalPosition, horizontalPosition] = byte.Parse(digit.ToString());
remainder[horizontalPosition - 1] = value / 10;
}
else
{
grid[verticalPosition, horizontalPosition] = (byte)value;
}
}
private static byte[] SumColumns(byte[,] grid, int rowCount, int maxResultLength)
{
byte[] resultDigits = new byte[maxResultLength];
int[] remainder = new int[maxResultLength];
for (int horizontalPosition = maxResultLength - 1; horizontalPosition >= 0; horizontalPosition--)
{
int sum = 0;
for (int verticalPosition = rowCount - 1; verticalPosition >= 0; verticalPosition--)
{
sum += grid[verticalPosition, horizontalPosition];
}
SetResultDigit(resultDigits, remainder, horizontalPosition, sum);
//LogAddition(resultDigits, remainder, horizontalPosition, maxResultLength);
}
for (int remainderPosition = remainder.Length - 1; remainderPosition >= 0; remainderPosition--)
{
if (remainder[remainderPosition] > 0)
{
SetResultDigit(resultDigits, remainder, remainderPosition, 0);
}
}
//System.Diagnostics.Debug.WriteLine("");
return resultDigits;
}
private static void SetResultDigit(byte[] resultDigits, int[] remainder, int horizontalPosition, int sum)
{
int value = sum + resultDigits[horizontalPosition] + remainder[horizontalPosition];
remainder[horizontalPosition] = 0;
if (value >= 10)
{
string columnText = value.ToString();
char digit = columnText[columnText.Length - 1];
resultDigits[horizontalPosition] = byte.Parse(digit.ToString());
remainder[horizontalPosition - 1] = value / 10;
}
else
{
resultDigits[horizontalPosition] = (byte)value;
}
}
private static string BuildResult(byte[] resultDigits, bool aNegative, bool bNegative)
{
var result = new System.Text.StringBuilder();
bool leadingZero = true;
for (int position = 0; position < resultDigits.Length; position++)
{
if (!leadingZero || resultDigits[position] > 0)
{
result.Append(resultDigits[position]);
leadingZero = false;
}
}
if (result.Length == 0)
{
return "0";
}
if ((aNegative && !bNegative) || (!aNegative && bNegative))
{
result.Insert(0, '-');
}
return result.ToString();
}
//private static void LogMultiplication(byte[,] sumParts, int rowCount, int maxResultLength)
//{
// for (int row = 0; row < rowCount; row++)
// {
// bool leadingZero = true;
// for (int column = 0; column < maxResultLength; column++)
// {
// var value = sumParts[row, column];
// if (!leadingZero || value > 0)
// {
// System.Diagnostics.Debug.Write(value);
// leadingZero = false;
// }
// else
// {
// System.Diagnostics.Debug.Write(" ");
// }
// }
// System.Diagnostics.Debug.WriteLine("");
// }
// System.Diagnostics.Debug.WriteLine("");
//}
//private static void LogAddition(byte[] resultDigits, int[] remainder, int horizontalPosition, int maxResultLength)
//{
// bool leadingZero = true;
// for (int column = 0; column < maxResultLength; column++)
// {
// var value = resultDigits[column];
// if (!leadingZero || value > 0 || column >= horizontalPosition)
// {
// System.Diagnostics.Debug.Write(value);
// leadingZero = false;
// }
// else
// {
// System.Diagnostics.Debug.Write(" ");
// }
// }
// if (horizontalPosition > 0 && remainder[horizontalPosition - 1] > 0)
// {
// System.Diagnostics.Debug.Write(" (remainder " + remainder[horizontalPosition - 1] + ")");
// }
// System.Diagnostics.Debug.WriteLine("");
//}
}