/*

Умножение Карацубы

*/

​

using System;

using System.Text;

​

public class Program

{

    public static void Main(string[] args)

    {

        Console.WriteLine(karatsuba("545645476547643", "32413356578708785653541254786"));

    }

​

    private static string karatsuba(string num1, string num2)

    {

        bool firstNeg = num1[0] == '-';

        bool secNeg = num2[0] == '-';

​

        if (firstNeg)

            num1 = negate(num1);

        if (secNeg)

            num2 = negate(num2);

        normalizeStrings(ref num1, ref num2);

​

        var result = karatsubaRecursive(num1, num2);

​

        if (firstNeg ^ secNeg)

            result = "-" + result;

​

        return result;

    }

​

    private static string karatsubaRecursive(string num1, string num2)

    {

        normalizeStrings(ref num1, ref num2);

​

        if (num1.Length == 1)

        {

            return (byte.Parse(num1.Substring(0, 1)) * byte.Parse(num2.Substring(0, 1))).ToString();

        }

​

        var n = (int)Math.Ceiling(num1.Length*0.5f);

​

        var x1 = num1.Substring(0, num1.Length - n);

        var x2 = num1.Substring(num1.Length - n);

​

        var y1 = num2.Substring(0, num2.Length - n);

        var y2 = num2.Substring(num2.Length - n);

​

        var x1y1 = karatsubaRecursive(x1, y1);

        var x2y2 = karatsubaRecursive(x2, y2);

​

        var x1px2 = additionPositive(x1, x2);

        var y1py2 = additionPositive(y1, y2);

​

        var x1x2y1y2 = karatsubaRecursive(x1px2, y1py2);

        var t1 = subtractionPositive(x1x2y1y2, x1y1);

        var t2 = subtractionPositive(t1, x2y2);

​

        var part1 = addZeroes(x1y1, 2 * n);

        var part2 = addZeroes(t2, n);

​

        var part12 = additionPositive(part1, part2);

        var result = additionPositive(part12, x2y2);

​

        return result;

    }

​

    private static string additionPositive(string num1, string num2)

    {

        normalizeStrings(ref num1, ref num2);

​

        string result = string.Empty;

        byte left = 0;

        for (int i = num1.Length-1; i >=0; i--)

        {

            var a = byte.Parse(num1.Substring(i, 1)) + left;

            var b = byte.Parse(num2.Substring(i, 1));

​

            result = ((a + b) % 10) + result;

            left = (byte)((a + b) / 10);

        }

​

        if (left > 0)

        {

            result = left + result;

        }

​

        trimZeroes(ref result);

​

        return result;

    }

​

    private static string subtractionPositive(string num1, string num2)

    {

        normalizeStrings(ref num1, ref num2);

​

        string result = string.Empty;

        byte took = 0;

        for (int i = num1.Length-1; i >= 0; i--)

        {

            var a = byte.Parse(num1.Substring(i, 1)) - took;

            var b = byte.Parse(num2.Substring(i, 1));

​

            if (a < b)

            {

                took = 1;

                a += 10;

            }

            else

            {

                took = 0;

            }

​

            result = ((a - b) % 10) + result;

        }

​

        trimZeroes(ref result);

​

        return result;

    }

​

    private static void normalizeStrings(ref string num1, ref string num2)

    {

        if (num1.Length > num2.Length)

        {

            var sb = new StringBuilder();

            for (int i = 0; i < num1.Length-num2.Length; i++)

            {

                sb.Append("0");

            }

            sb.Append(num2);

            num2 = sb.ToString();

        }

        else if (num2.Length > num1.Length)

        {

            var sb = new StringBuilder();

            for (int i = 0; i < num2.Length-num1.Length; i++)

            {

                sb.Append("0");

            }

            sb.Append(num1);

            num1 = sb.ToString();

        }

    }

​

    private static string negate(string num)

    {

        if (num[0] == '-')

            return num.Substring(1);

        else

            return "-" + num;

    }

​

    public static string addZeroes(string num, int zeroes)

    {

        var sb = new StringBuilder(num);

        for (int i = 0; i < zeroes; i++)

        {

            sb.Append("0");

        }

​

​

        var result = sb.ToString();

        trimZeroes(ref result);

        return result;

    }

​

    private static void trimZeroes(ref string num)

    {

        int i;

        for (i = 0; i < num.Length-1; i++)

        {

            if (num[i] != '0')

                break;

        }

​

        num = num.Substring(i);

    }

​

}