"Учу" длинную арифметику

@majesty1992 · Регистрация: 15.12.2009

Author24 — интернет-сервис помощи студентам

Доброго времени суток. Начал пробывать реализовывать длинную арифметику на шарпе, но вышло очень криво, соответственно очень долго(это слабо сказанно). Подскажите как можно оптимизировать. Прошу не писать что-то вроде "Пиши на плюсах" и др. Интересует только шарп.
Сумма

C#

 private static string Sum(string F, string S)
        {
            string result="";
            if ((F[0] == '-') && (S[0] != '-')) return Minus(S, F.Remove(0,1));
            if ((F[0] != '-') && (S[0] == '-')) return Minus(F, S.Remove(0,1));
            bool minus = false;
            if ((F[0] == '-') && (S[0] == '-'))
            {
                S = S.Remove(0, 1);
                F = F.Remove(0, 1);
                minus = true;
            }
            int NullsCount=Math.Abs(F.Length-S.Length);
            if (NullsCount != 0)
            {
                if (F.Length<S.Length) F = string.Concat(new string('0', NullsCount), F);
                else S = string.Concat(new string('0', NullsCount), S);
            }
            F = string.Concat("0", F);
            S = string.Concat("0", S);
            string value;
            string ost="0";
            for (int i = F.Length - 1; i >= 0; i--)
            {
                value = (Convert.ToInt32(F[i].ToString()) + Convert.ToInt32(S[i].ToString())+Convert.ToInt32(ost)).ToString();
                if (value.Length == 2)
                {
                    ost = value[0].ToString();
                    result = string.Concat(value[1].ToString(), result);
                }
                else
                {
                    ost = "0";
                    result = string.Concat(value[0].ToString(), result);
                }
            }
            if (result[0] == '0')
            {
                result = result.Remove(0, 1);
            }
            if (minus) result=string.Concat('-', result);
            return result;
        }

Вычитание

C#

 private static string Minus(string F, string S)
        {
            string result = "";
            if ((F[0]!='-')&&(S[0]=='-')) return Sum(F,S.Remove(0,1));
            else if ((F[0]=='-')&&(S[0]!='-')) return Sum(F,string.Concat("-",S));
            if (S[0] == '-') S = S.Remove(0, 1);
            bool minus=false;
            if (LongEq(F, S) == 0) return "0";
            else if (LongEq(F, S) == 2)
                minus = true;
            else minus = false;
            if (F[0] == '-') F = F.Remove(0, 1);
            int NullsCount = Math.Abs(F.Length - S.Length);
            if (NullsCount != 0)
            {
                if (F.Length < S.Length) F = string.Concat(new string('0', NullsCount), F);
                else S = string.Concat(new string('0', NullsCount), S);
            }
            char ost = '0';
            if (minus)
            for (int i = F.Length-1; i >= 0; i--)
            {
                int a = Convert.ToInt16(F[i].ToString());
                int b = Convert.ToInt16(S[i].ToString());
                if (a > b) b += 10;
                result = string.Concat((b-a- System.Convert.ToInt16(ost.ToString())).ToString(),result);
                if (b > 9) ost = '1';
                else ost = '0';
            }
            else
                for (int i = F.Length - 1; i >= 0; i--)
                {
                    int a = Convert.ToInt16(F[i].ToString());
                    int b = Convert.ToInt16(S[i].ToString());
                    if (a < b) a += 10;
                    result = string.Concat((a - b - System.Convert.ToInt16(ost.ToString())).ToString(), result);
                    if (a > 9) ost = '1';
                    else ost = '0';
                }
            if (minus) return string.Concat("-", result);
            else
            return result;
        }

Умножение

C#

private static string TotalUmnoj(string F,string S)
        {
            if ((F == "0") || (S == "0")) return ("0");
            int number = 0;
            if (F.Length < S.Length)
            {
                number = F.Length;
                string buff = F;
                F = S;
                S = buff;
            }
            else number = S.Length;
            string ost="0";
            for (int i = 0; i < number; i++)
            {
                string buff = Umnoj1(F, S[number - i - 1]);
                buff = string.Concat(buff, new string('0', i));
                ost = Sum(ost, buff);
            }
            return ost;
        }

Умножение одного символа на число

C#

private static string Umnoj1(string F, char C)
        {
            string result = "";
            char ch = '0';
            for (int i = F.Length - 1; i >= 0; i--)
            {
                string buff = (Convert.ToInt16(F[i].ToString()) * Convert.ToInt16(C.ToString())+Convert.ToInt16(ch.ToString())).ToString();
                if (buff.Length == 1)
                {
                    result = string.Concat(buff[0], result);
                    ch = '0';
                }
                else
                {
                    result = string.Concat(buff[1], result);
                    ch = buff[0];
                }
            }
            if (ch == '0') return result;
            else
            return string.Concat(ch,result);
        }

Заранее благодарю.

@somethingrotten · 14.07.2011, 21:19

Предложу вариант попроще, если требуется не именно разработка метода своими руками.

C#

BigInteger a=BigInteger.Parse("3423564687135871657687135432403210340354035403540");
BigInteger b=BigInteger.Parse("68716871358703587054038709708570123123078078601312301307890756");
BigInteger c;
//умножение
c=a*b;
//сложение
c=a+b;
//вычитание
c=a-b;

Размер числа ограничен оперативной памятью. Нужен .NET Framework 4.

@majesty1992 · 14.07.2011, 21:22 **[ТС]**

Спасибо конечно большое, однако хочется самому поучится делать такие вещи.

@somethingrotten · 14.07.2011, 21:48

А, окей)

Тогда, во-первых, лучше выкинуть все операции со строками - все эти Convert.ToInt16 и ToString очень тормозные. Оставьте их только при вводе чисел, а в самом начале метода, например, разбейте их на байтовые массивы - по разрядам.
Потом - при сложении, по-моему, нет никакой необходимости дополнять числа нулями до одинаковых длин. Во-первых, это просто не нужно - определите сначала длину меньшего числа, и ограничьте цикл ей +1 (на случай, если будет остаток в старший разряд). Когда цикл кончается, оставшиеся цифры большего числа просто приписываются к результату слева. Во-вторых, представьте, сколько вы сэкономите времени, когда в примере типа

598374508923540872648572689475623865283+1

избавитесь от
1 -> 000000000000000000000000000000000000001
3+1=4;
8+0=8;
2+0=2;
5+0=5...

И при этом каждая цифра парсится в int, а потом обратно. Конечно, оно тормозит.

Вычитание: а зачем писать отдельный метод, когда оно ничем не отличается от сложения? Просто опять же, когда будете переводить в массив - умножьте каждое число на -1, и метод сложения будет так же работать. При этом остаток, который переносится в старший разряд, будет получаться отрицательным - когда "занимаем" единицу.

Умножение: вы используете "столбиком", умножая число на все цифры по очереди. Есть довольно неплохой выбор алгоритмов быстрого умножения - самый быстрый, емнип, все еще алгоритм Карацубы. Один из самых простых алгоритмов переделан из быстрого возведения в степень:

0. Есть числа a и b
1. Переводим a в двоичную систему
2. Считываем подряд символы (единицы и нули) из a, отбросив первый символ
3. Сохраним изначальное число b как b0
4. На каждом шаге, если полученный символ=0, то b=2b. Если символ=1, то b=2b+b0

Пример: 2*5.
5 в двоичной системе = 101. Отбрасываем первую единицу, остается 01.
Первый символ равен 0: умножаем 2 на 2, получаем 4.
Второй символ равен 1: умножаем 4 на 2 и прибавляем 2 - получаем искомые 10.

Алгоритм не очень выгоден для маленьких чисел (2*5 мы бы получили одной операцией, а тут две), но для больших быстрее, чем столбиком.

@chessman1 · 14.07.2011, 21:50

Попробуйте реализовать через китайскую теорему об остатках.
Дает хороший выигрыш в скорости на * и /
Размер чисел ограничен только разумными пределами

@Xero201 · 14.07.2011, 22:21

Сообщение от majesty1992

Подскажите как можно оптимизировать

можно, например, брать не по одному символу а по 18, если использовать long int, в котором до 19 символов может быть

Добавлено через 7 минут

Сообщение от somethingrotten

Вычитание: а зачем писать отдельный метод, когда оно ничем не отличается от сложения?

эм... 7+4 вроде бы отличается от 7-4 или я неправильно понял?

@majesty1992 · 14.07.2011, 22:50 **[ТС]**

TO:somethingrotten
Очень много дельный советов - особенно с нулями - спасибо.
А вот с вычитанием я тоже не понял... я ведь их взаимозаменяю когда необходимо

C#

1 2	if ((F[0] == '-') && (S[0] != '-')) return Minus(S, F.Remove(0,1)); if ((F[0] != '-') && (S[0] == '-')) return Minus(F, S.Remove(0,1));

C#

1 2	if ((F[0]!='-')&&(S[0]=='-')) return Sum(F,S.Remove(0,1)); else if ((F[0]=='-')&&(S[0]!='-')) return Sum(F,string.Concat("-",S));

Тут ещё такой факт - я писал все эти ф-ции на скорую руку, т.е. пытался реализовать то, как мы делаем на бумаге, отсюда и забиваение нулями, но действительно ОЧЕНЬ много лишних операций...
Просто когда делаешь что-то на подобии суммы всех чисел от одного до 1000 в степени этого же числа используя вышеупомянутый код, может уйти больше часа...
Всё-таки без определённых алгоритмов никуда=)
Насчёт long... не знаю склоняюсь всё таки к разбитию числа на байтовый массив... думаю так быстрее будет

@somethingrotten · 14.07.2011, 23:31

majesty1992, про вычитание я имел в виду, что у вас для него есть отдельный метод:

C#

1	private static string Minus(string F, string S)

Это необязательно - ну, и вообще слегка загромождает код. Вычитания как самостоятельного действия вообще не существует - это просто сложение со знаком) Допустим, вы переводите число в массив.

C#

1 2	int[] first=new int[F.Length]; for (int i=0; i<F.Length; i++) fist[i]=Convert.ToInt32(F[i]);

Теперь как получить отрицательное число? Умножаем каждый разряд на (-1) и поразрядное сложение превратится в поразрядное вычитание. То есть можно сделать как-то так:

C#

int sign;
if (F[0]=='-') sign=-1;
else sign=1;
int[] first=new int[F.Length];
for (int i=0; i<F.Length; i++) fist[i]=sign*Convert.ToInt32(F[i]);

Это не влияет на скорость, просто позволяет упростить код. Правда, есть одна проблемка - с байтовым массивом так не выйдет, потому что byte - тип неотрицательный. Можно, конечно, как при дополнительном коде, сделать -1=255 и распознавать это в теле цикла, но как-то это некрасиво. При прочих равных можно попробовать совет насчет long)

Насчет возведения в степень - просто обязательно юзать алгоритм, типа вышеприведенного, в оригинальной форме (формулы соответственно заменяются на b=b^2, если 0 и b=b0*b^2 если 1). Вдвойне обязательно - если это степень по модулю)

Up. Кстати, чтобы сделать код проще и красивей, вместо String.Concat можно писать +=.

Xero201, я не про результат операции, а про принцип работы сложения) Формула (а значит, метод) не изменится, если в нее подавать отрицательные числа - следовательно, нам нужен всего лишь один метод)

@Xero201 · 14.07.2011, 23:34

Сообщение от majesty1992

склоняюсь всё таки к разбитию числа на байтовый массив... думаю так быстрее будет

зацени (тоже на скорую руку)

C#

Dictionary<char, int> dic;
 
        private void Form1_Load(object sender, EventArgs e)
        {
            dic = new Dictionary<char, int>();
            for (int i = 0; i < 10; i++)
            {
                dic.Add(i.ToString()[0], i);                
            }
 
            tfA.Text = "1110921901290129480975051327507321065704706264321";
            tfB.Text = "92007850498104593475690347573";
 
            tfResult.Text = sum(tfA.Text, tfB.Text);
            
        }
 
        private string sum(String a, String b)
        {
            String result = "";
            int ost = 0;
            
            if (b.Length > a.Length)
            {
                string c = b;
                b = a;
                a = c;
            }
 
            int i;
 
            int lenA = a.Length-1;
            int lenB = b.Length-1;
 
 
            for (i = 0; i < b.Length; i++) {
                int go = dic[a[lenA-i]] + dic[b[lenB-i]]+ost;
                if (go > 9)
                {
                    ost = 1;
                    go %= 10;
                }
                else
                {
                    ost = 0;
                }
                result += dic[go.ToString()[0]];          
            }
            while (ost == 1)
            {
                if (a.Length == i)
                {
                    ost = 0;
                    result += "1";
                }
                else
                {
                    int go = dic[a[lenA-i++]] + ost;
                    if (go > 9)
                    {
                        ost = 1;
                        go %= 10;
                    }
                    else
                    {
                        ost = 0;
                    }
                    result += dic[go.ToString()[0]];
                }
            }
 
            result = Reverse(result);
           
            if (i < a.Length) { result = a.Substring(0, a.Length - i)+result; }
 
            return result;
        }
 
        public string Reverse(string s)
        {
            char[] charArray = s.ToCharArray();
            Array.Reverse(charArray);
            return new string(charArray);
        }

@majesty1992 · 15.07.2011, 00:02 **[ТС]**

Dictionary<char, int> dic;
не знаком с этой конструкцией
Короче начну писать с нуля с байтовыми масивами. Я думаю, что если от строк избавлюсь эфективность увеличиться.
Умножение - буду пробывать Карацубу.

@Jesterru · 06.05.2018, 18:56

somethingrotten, как и автор, пытаюсь написать класс для длинной арифметики чисел с плавающей запятой.

Сообщение от somethingrotten

Потом - при сложении, по-моему, нет никакой необходимости дополнять числа нулями до одинаковых длин

Если есть два числа дробных ("_" - пустота) :

1234567,8901
____432,1___

То, если я не ошибаюсь, придется привести эти числа к виду :

1234567,8901
0000432,1000

Иначе как тогда складывать их?

@Антон1985 · 06.05.2018, 20:12

Jesterru, можно попробовать использовать структуру на число, например

Код

НАЧСТРУКТ
  ПОЛЕ мантисса  // массив байтов
  ПОЛЕ порядок  // целое число
КОНСТРУКТ

и перед сложением/вычитанием выравнивать место запятых в числах, а в умножении
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{m}_{1}*{10}^{{p}_{1}} * {m}_{2}*{10}^{{p}_{2}} = {m}_{1}*{m}_{2}*{10}^{{p}_{1}+{p}_{2}}$
и делении
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{{m}_{1}*{10}^{{p}_{1}}}{{m}_{2}*{10}^{{p}_{2}}} = \frac{{m}_{1}}{{m}_{2}}*{10}^{{p}_{1}-{p}_{2}}$
ещё проще.

@Jesterru · 07.05.2018, 15:47

Антон1985, Я все таки решил, что лучше использовать 1 массив, содержащий и целую, и дробную части, а так же переменную, обозначающую позицию запятой. Для всех операций потребуется только 1 - правильно расположить массивы друг относительно друга, что делается достаточно просто при создании матрицы, даже Array.Resize делать не надо

Добавлено через 2 минуты
Сложение - и так все ясно.
Вычитание - есть некоторые сложности, но так же все ясно.
Умножение - сложнее сложения, но проще вычитания.
Деление - Это комбинация сравнения чисел и вычитания, т.е., по-моему, самое сложное, но состоит из простого

@majesty1992 40 / 13 / 8 Регистрация: 15.12.2009 Сообщений: 70
	14.07.2011, 21:22 [ТС]	3
	Спасибо конечно большое, однако хочется самому поучится делать такие вещи. 0

@somethingrotten 67 / 67 / 9 Регистрация: 18.04.2011 Сообщений: 124
	14.07.2011, 21:48	4
	А, окей) Тогда, во-первых, лучше выкинуть все операции со строками - все эти Convert.ToInt16 и ToString очень тормозные. Оставьте их только при вводе чисел, а в самом начале метода, например, разбейте их на байтовые массивы - по разрядам. Потом - при сложении, по-моему, нет никакой необходимости дополнять числа нулями до одинаковых длин. Во-первых, это просто не нужно - определите сначала длину меньшего числа, и ограничьте цикл ей +1 (на случай, если будет остаток в старший разряд). Когда цикл кончается, оставшиеся цифры большего числа просто приписываются к результату слева. Во-вторых, представьте, сколько вы сэкономите времени, когда в примере типа 598374508923540872648572689475623865283+1 избавитесь от 1 -> 000000000000000000000000000000000000001 3+1=4; 8+0=8; 2+0=2; 5+0=5... И при этом каждая цифра парсится в int, а потом обратно. Конечно, оно тормозит. Вычитание: а зачем писать отдельный метод, когда оно ничем не отличается от сложения? Просто опять же, когда будете переводить в массив - умножьте каждое число на -1, и метод сложения будет так же работать. При этом остаток, который переносится в старший разряд, будет получаться отрицательным - когда "занимаем" единицу. Умножение: вы используете "столбиком", умножая число на все цифры по очереди. Есть довольно неплохой выбор алгоритмов быстрого умножения - самый быстрый, емнип, все еще алгоритм Карацубы. Один из самых простых алгоритмов переделан из быстрого возведения в степень: 0. Есть числа a и b 1. Переводим a в двоичную систему 2. Считываем подряд символы (единицы и нули) из a, отбросив первый символ 3. Сохраним изначальное число b как b0 4. На каждом шаге, если полученный символ=0, то b=2b. Если символ=1, то b=2b+b0 Пример: 25. 5 в двоичной системе = 101. Отбрасываем первую единицу, остается 01. Первый символ равен 0: умножаем 2 на 2, получаем 4. Второй символ равен 1: умножаем 4 на 2 и прибавляем 2 - получаем искомые 10. Алгоритм не очень выгоден для маленьких чисел (25 мы бы получили одной операцией, а тут две), но для больших быстрее, чем столбиком. 2

@chessman1 167 / 96 / 23 Регистрация: 13.03.2011 Сообщений: 402
	14.07.2011, 21:50	5
	Попробуйте реализовать через китайскую теорему об остатках. Дает хороший выигрыш в скорости на * и / Размер чисел ограничен только разумными пределами 1

@Xero201 68 / 66 / 19 Регистрация: 27.12.2008 Сообщений: 212
	14.07.2011, 22:21	6
	Сообщение от majesty1992 Подскажите как можно оптимизировать можно, например, брать не по одному символу а по 18, если использовать long int, в котором до 19 символов может быть Добавлено через 7 минут Сообщение от somethingrotten Вычитание: а зачем писать отдельный метод, когда оно ничем не отличается от сложения? эм... 7+4 вроде бы отличается от 7-4 или я неправильно понял? 1

@majesty1992 40 / 13 / 8 Регистрация: 15.12.2009 Сообщений: 70
	15.07.2011, 00:02 [ТС]	10
	Dictionary<char, int> dic; не знаком с этой конструкцией Короче начну писать с нуля с байтовыми масивами. Я думаю, что если от строк избавлюсь эфективность увеличиться. Умножение - буду пробывать Карацубу. 0

@Jesterru 3 / 2 / 2 Регистрация: 19.06.2016 Сообщений: 299
	06.05.2018, 18:56	11
	somethingrotten, как и автор, пытаюсь написать класс для длинной арифметики чисел с плавающей запятой. Сообщение от somethingrotten Потом - при сложении, по-моему, нет никакой необходимости дополнять числа нулями до одинаковых длин Если есть два числа дробных ("_" - пустота) : 1234567,8901 ____432,1___ То, если я не ошибаюсь, придется привести эти числа к виду : 1234567,8901 0000432,1000 Иначе как тогда складывать их? 0

@Антон1985 138 / 101 / 102 Регистрация: 03.02.2014 Сообщений: 427
	06.05.2018, 20:12	12
	Jesterru, можно попробовать использовать структуру на число, например Код НАЧСТРУКТ ПОЛЕ мантисса // массив байтов ПОЛЕ порядок // целое число КОНСТРУКТ и перед сложением/вычитанием выравнивать место запятых в числах, а в умножении $https://www.cyberforum.ru/cgi-bin/latex.cgi?{m}_{1}{10}^{{p}_{1}} {m}_{2}{10}^{{p}_{2}} = {m}_{1}{m}_{2}{10}^{{p}_{1}+{p}_{2}}$ и делении $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{{m}_{1}{10}^{{p}_{1}}}{{m}_{2}{10}^{{p}_{2}}} = \frac{{m}_{1}}{{m}_{2}}{10}^{{p}_{1}-{p}_{2}}$ ещё проще. 1

@Jesterru 3 / 2 / 2 Регистрация: 19.06.2016 Сообщений: 299
	07.05.2018, 15:47	13
	Антон1985, Я все таки решил, что лучше использовать 1 массив, содержащий и целую, и дробную части, а так же переменную, обозначающую позицию запятой. Для всех операций потребуется только 1 - правильно расположить массивы друг относительно друга, что делается достаточно просто при создании матрицы, даже Array.Resize делать не надо Добавлено через 2 минуты Сложение - и так все ясно. Вычитание - есть некоторые сложности, но так же все ясно. Умножение - сложнее сложения, но проще вычитания. Деление - Это комбинация сравнения чисел и вычитания, т.е., по-моему, самое сложное, но состоит из простого 0

"Учу" длинную арифметику

Решение