Feedback

C# - Multiplikation ganzer (großer) Zahlen wie in der Schule

Veröffentlicht von am 27.03.2020
(0 Bewertungen)
Was ist eigentlich die Fakultät von 1050?

In .NET gibt es (meines Wissens nach) keinen Datentype, der mit so großen Zahlen operieren kann (bei 28! fällt Decimal auseinander).

Aber wenn man es auf dem Papier macht, wie man es in der Schule gelernt hat, gibt es kein Limit, außer der Geduld.
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("");
    //}
}
Abgelegt unter multiplikation, großezahlen.

1 Kommentare zum Snippet

Nuffin schrieb am 02.07.2020:
include System.Numeric;
...
BigInteger a = BigInteger.Parse(...);
BigInteger b = BigInteger.Parse(...);
Console.WriteLine(a * b);
 

Logge dich ein, um hier zu kommentieren!