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

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

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

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

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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#
1
2
3
4
5
6
7
8
9
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#
1
2
3
4
5
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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, можно попробовать использовать структуру на число, например

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

и перед сложением/вычитанием выравнивать место запятых в числах, а в умножении
$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 минуты
Сложение - и так все ясно.
Вычитание - есть некоторые сложности, но так же все ясно.
Умножение - сложнее сложения, но проще вычитания.
Деление - Это комбинация сравнения чисел и вычитания, т.е., по-моему, самое сложное, но состоит из простого

Новые блоги и статьи Все статьи Все блоги /
Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	Контроль уникальности заводского номера - вариант №2 Maks 24.03.2026 В отличие от предыдущего варианта добавлено прерывание циклов, также добавлены новые переменные для сохранения контекста ошибки перед прерыванием цикла: Процедура ПередЗаписью(Отказ, РежимЗаписи,. . .	SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .
Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера - вариант №1 Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .

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

@somethingrotten 67 / 67 / 9 Регистрация: 18.04.2011 Сообщений: 124
	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 Пример: 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
	Попробуйте реализовать через китайскую теорему об остатках. Дает хороший выигрыш в скорости на * и / Размер чисел ограничен только разумными пределами 1

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

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

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

Решение