Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.64/50: Рейтинг темы: голосов - 50, средняя оценка - 4.64
28 / 28 / 10
Регистрация: 10.03.2012
Сообщений: 249
1

Реализовать класс длинной арифметики

13.07.2012, 15:49. Показов 9147. Ответов 24
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Начал писать класс длинной арифметики. Пока готов только метод для умножения больших чисел:

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
сlass Mathematic
    {
        int[] divisor;  // второй элемент
        int[] divided;  // первый элемент
        int[] result; // понятно результат    
        int max = 0;
 
        public void Product(string a, string b)
        {
            ////////--- Інициализация елементов умножения ---
           
            divisor = new int[b.Length];
            divided = new int[a.Length];
            
            if (a.Length > b.Length)                        // количество ячеек в результате должна быть в 2 раза больше 
            {                                               // чем больший элемент умножений
                result = new int[2 * a.Length];             // на всякий случай
                max = 2*a.Length ;
                for (int i = 0; i < 2*a.Length; i++)
                { result[i] = 0; }
            }
            else
            {
                result = new int[2 * b.Length];
                max = 2*b.Length ;
                for (int i = 0; i < 2*b.Length; i++)
                { result[i] = 0; }
            }
 
            for (int i = 0; i < a.Length; i++)
                divided[i] = 0;
            for (int i = 0; i < b.Length; i++)
                divisor[i] = 0;
            ////////--- Заполнение елементов умножения ---
            int k = a.Length-1;
            foreach (char ch in a)                                 //номер ячейки будет равен номеру разряда -1 тоесть первый пазряд в 0-й ячейке.
            {
                divided[k] = Convert.ToInt32(ch.ToString());
                k--;
            }
 
            k = b.Length - 1;
            foreach (char ch in b)
            {
                divisor[k] = Convert.ToInt32(ch.ToString());
                k--;
            }
            ////////--- Алгоритм умножения ---
            for (int i = 0; i < a.Length; i++)
            {
                for (int j = 0; j < b.Length; j++)                    //как-то так умножаю. разряды в этом цыкле не учитываются. если 3 на 4 множим
                {                                                     // записывав ячейку 12 вместо 2.  
                    if (divided[i] * divisor[j] < 10)
                    {
                        result[i + j] += divided[i] * divisor[j];
                    }
                    else
                    {
                        result[i + j] += (divided[i] * divisor[j]) % 10;
                        result[i + j + 1] += (int)Math.Truncate((decimal)(divided[i] * divisor[j]) / 10);
                    }
                }
            }
 
            for(int i=0; i<max-1;i++)
            { 
                if (result[i] >= 10)
                {
                    result[i + 1] += (int)Math.Truncate((decimal)result[i] / 10);       //прохожусь по резалту и навожу порядок с разрядами.
                    result[i] = result[i] % 10;
                }
            }
 
            for (int i = max-1; i>=0; i--)
            {
                Console.Write(result[i]);
            }
            Console.ReadLine();
        }
    }
Но беда в том что оооочень большие числа калькулятор винды не хочет умножать(возвращает отрицательные значения).

1. Прокоментируйте мой код. Может что-то можно сделать "умнее". А такое полюбому есть)

2. Подскажите где можно проверить уменожив числа типа "47835634765783465783465783647665464"

Сейчас займусь делением.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.07.2012, 15:49
Ответы с готовыми решениями:

Вычисление факториала с помощью длинной арифметики
Я понимаю что эта тема поднималась уже не раз, но всё же помогите найти 100!. Я вообщем...

Реализация длинной арифметики: исправить код
разработать класс или библиотеку функций для работы с m-битными целыми числами. Библиотека должна...

Оптимизация класса для длинной арифметики
Решил написать класс для работы с ОООЧЕНЬ длинными числами Какая была концепция : 1 - Числа...

Класс длинной арифметики
Дайте класс длинной арифметики - хотелось бы разобраться в этой штуке, а то какие исходники не...

24
Неадекват
1492 / 1230 / 246
Регистрация: 02.04.2010
Сообщений: 2,789
13.07.2012, 16:08 2
Цитата Сообщение от van Persie Посмотреть сообщение
Подскажите где можно проверить уменожив числа типа "47835634765783465783465783647665464"
BigInteger в помощь. В рефлекторе же можешь посмотреть как он устроен
1
28 / 28 / 10
Регистрация: 10.03.2012
Сообщений: 249
13.07.2012, 16:18  [ТС] 3
Цитата Сообщение от freeba Посмотреть сообщение
BigInteger в помощь. В рефлекторе же можешь посмотреть как он устроен
C#
1
BigInteger a = 170792292598674535657433489573489578934;
Ошибка 1 Значение целочисленной константы слишком велико C:\Users\Home\Desktop\Арифметика\Mathematic\Mathematic\Program.cs 18
0
9 / 9 / 1
Регистрация: 09.05.2012
Сообщений: 36
13.07.2012, 17:07 4
Вообще я считаю калькулятор с большими числами надо херачить в строках.

ну типа
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
strin slog1="222222222211113123123123123123123123" 
string slog2="123123124124890098091407128904701827414 "
string sum ="";
int leng1 = slog1.length();
int leng2 = slog2.length();
int max, num;
if (leng1 <= leng2)
{
     max = leng2;
     num = 2;
}
else
{
     max = leng1;
     num = 1;
}
bool newDec=false;
for(int i = max - 1; i>=0; i--)
{
     //запилить еще проверочку на то, что одно из слагаемых уже кончилось
     int res = int.parse(slog1[i])+int.parse(slog1[i]);
     if (newDec) res++;
     if (res >= 10)
    {
            newDec = true;
            res -= 10;
     }
     else
            newDec = false;
     sum += res.toString();
}
//в итоге получишь результат, но записанный с право-на лево
На счет правильности хз - но идея, я думаю понятна
1
28 / 28 / 10
Регистрация: 10.03.2012
Сообщений: 249
13.07.2012, 18:34  [ТС] 5
Цитата Сообщение от Niksan_la2 Посмотреть сообщение
Вообще я считаю калькулятор с большими числами надо херачить в строках.

При каждом изменении строки создается новые объект string, а старый продолжает висеть в памяти(если я правильно понимаю). И со временем память будет забиваться мусором.
0
Неадекват
1492 / 1230 / 246
Регистрация: 02.04.2010
Сообщений: 2,789
13.07.2012, 19:53 6
Цитата Сообщение от Niksan_la2 Посмотреть сообщение
Вообще я считаю калькулятор с большими числами надо херачить в строках.
Ни в коем случае!!! За такую ересь на костре жечь!

Пример BigInteger:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using System;
 
using System.Numerics;
 
namespace tmp1
{
    class Program
    {
        static void Main(string[] args)
        {
            BigInteger num1 = BigInteger.Parse("23794697328459783597834697563408975679346975436534875963846593840563945");
            BigInteger num2 = BigInteger.Parse("6375242695764325043753294875021857432657934265972637456792345943");
 
            Console.WriteLine("Сумма: {0}\nПроизведение: {1}\nРазность: {2}\nЧастное: {3}", 
                num1 + num2, num1 * num2, num1 - num2, num1 / num2);
 
            Console.ReadKey(true);
        }
    }
}
Добавлено через 1 минуту
Цитата Сообщение от van Persie Посмотреть сообщение
При каждом изменении строки создается новые объект string, а старый продолжает висеть в памяти(если я правильно понимаю). И со временем память будет забиваться мусором.
Сборщик рано или позно все подчистит, но затраты на преобразование и постоянное выделение памяти в куче будут велики.
1
63 / 63 / 14
Регистрация: 05.08.2011
Сообщений: 323
Записей в блоге: 5
13.07.2012, 21:56 7
Цитата Сообщение от freeba Посмотреть сообщение
Сборщик рано или позно все подчистит, но затраты на преобразование и постоянное выделение памяти в куче будут велики.
Поэтому используем using
0
Эксперт Java
4091 / 3825 / 745
Регистрация: 18.05.2010
Сообщений: 9,331
Записей в блоге: 11
13.07.2012, 22:21 8
Цитата Сообщение от Mans7 Посмотреть сообщение
Поэтому используем using
причем здесь using?
using(интерфейс IDisposable) используется для освобождения неуправляемых ресурсов, коими строки не являются.
0
63 / 63 / 14
Регистрация: 05.08.2011
Сообщений: 323
Записей в блоге: 5
13.07.2012, 23:13 9
Вы меня не поняли... и, судя по всему, это и не нужно.
0
28 / 28 / 10
Регистрация: 10.03.2012
Сообщений: 249
14.07.2012, 01:23  [ТС] 10
Цитата Сообщение от Mans7 Посмотреть сообщение
Вы меня не поняли... и, судя по всему, это и не нужно.

Так объясни что ты имел ввиду
0
9 / 9 / 1
Регистрация: 09.05.2012
Сообщений: 36
14.07.2012, 09:42 11
Цитата Сообщение от freeba Посмотреть сообщение
Ни в коем случае!!! За такую ересь на костре жечь!
бигинтеджер это не по хардкору. Да и не развивает мышление ни разу.
0
Неадекват
1492 / 1230 / 246
Регистрация: 02.04.2010
Сообщений: 2,789
14.07.2012, 10:26 12
Работу со строками как с числами тоже сложно к хардкору отнести. Вполне допустимое решение для студентов троечников, но не более.

Настоящий маньяк может пойти несколькими путями:
- Преобразовать число к 255-ричной системе счисления, запихать его в массив байт и работать как в алгоритме со строками. Есть существенная разница в скорости и потреблении памяти между (byte, byte) => byte и (byte.Parse(string), byte.Parse(string)) => byte.ToString()

- Получить просветление посмотря на реализацию BigInteger. Преобразовать число в двоичную форму и запихнуть полученное число в uint[] не забыв положить первые четыре байта в int, ибо знаковое. Получим выйгрыш в скорости простых операций по сравнении с первым вариантом.

- Перейти с шарпа на питон.

- Придумать что-нибудь не менее изощренное.

А строки это так. Детишкам забавляться
2
9 / 9 / 1
Регистрация: 09.05.2012
Сообщений: 36
14.07.2012, 14:08 13
Цитата Сообщение от freeba Посмотреть сообщение
А строки это так. Детишкам забавляться
Я не думаю, что автор данного топика является гуру-программистом. И ему не помешало бы придумывать что то свое, а не пользоваться готовыми библиотеками.
1
28 / 28 / 10
Регистрация: 10.03.2012
Сообщений: 249
14.07.2012, 14:24  [ТС] 14
Цитата Сообщение от Niksan_la2 Посмотреть сообщение
Я не думаю, что автор данного топика является гуру-программистом. И ему не помешало бы придумывать что то свое, а не пользоваться готовыми библиотеками.

Ну так я и придумываю что-то своё

С байтовым массивом никогда не встречался ещё
0
Jupiter
14.07.2012, 14:27
  #15

Не по теме:

Цитата Сообщение от freeba Посмотреть сообщение
- Перейти с шарпа на питон.
ну или на лисп:D

0
Неадекват
1492 / 1230 / 246
Регистрация: 02.04.2010
Сообщений: 2,789
14.07.2012, 15:11 16

Не по теме:

Цитата Сообщение от Jupiter Посмотреть сообщение
ну или на лисп
Ну да, там побыстрее длинноарифметика работает. Хотя обратная польская запись выражений отпугнет любого неофита. Скобочки опять же, сотни, сотни и сотни сотен скобочек - это намного хуже чем сотни подчеркивайний и тысячи отступов в питоне, наверное...:D



Цитата Сообщение от Niksan_la2 Посмотреть сообщение
не помешало бы придумывать что то свое, а не пользоваться готовыми библиотеками.
Спорный вопрос. Извечное противостояние прикладного и фундаментального. ИМХО лучше научиться работать с тремя готовыми библиотеками, чем потратить время на написание заведомо худшего аналога одной из них.
1
9 / 9 / 1
Регистрация: 09.05.2012
Сообщений: 36
16.07.2012, 08:59 17
Цитата Сообщение от freeba Посмотреть сообщение
Спорный вопрос. Извечное противостояние прикладного и фундаментального. ИМХО лучше научиться работать с тремя готовыми библиотеками, чем потратить время на написание заведомо худшего аналога одной из них.
ИМХО, лучший вариант написать самому что-то, хотя и не лучший аналог - зато сам. Потом посмотреть как это реализовано в оптимизированных библиотек. И уже использовать ее (ну, в смысле эту самую библиотеку)
0
28 / 28 / 10
Регистрация: 10.03.2012
Сообщений: 249
16.07.2012, 16:32  [ТС] 18
Было бы неплохо если бы хоть кто-то прокоментировал мой код
0
65 / 50 / 7
Регистрация: 09.11.2012
Сообщений: 219
27.11.2012, 19:17 19
Цитата Сообщение от van Persie Посмотреть сообщение
Подскажите где можно проверить уменожив числа типа "47835634765783465783465783647665464"
В Python. Там можно вычислять как минимум до 100000! (факториал, кто не понял). Больше просто не пробовал.
0
28 / 28 / 10
Регистрация: 10.03.2012
Сообщений: 249
28.11.2012, 00:09  [ТС] 20
Цитата Сообщение от Necronomicron Посмотреть сообщение
В Python. Там можно вычислять как минимум до 100000! (факториал, кто не понял). Больше просто не пробовал.
Не знаком с Python. Меня интересует C#.
0
28.11.2012, 00:09
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.11.2012, 00:09
Помогаю со студенческими работами здесь

Реализация длинной арифметики
Здравствуйте, форумчане. Готовлюсь к предстоящим олимпиадам решая задачи. Возникла проблема: решая...

Объясните код длинной арифметики
Не могу понять синтаксиса этого кода void add(vlong *op1, vlong *op2, vlong *res) { vlong *mxop,...

Бенчмарк для длинной арифметики
Долгими зимними вечерами я люблю страдать ерундой и писать свои велосипеды. Таким образом, я...

Ошибка в реализации длинной арифметики
Здравствуйте. Я скопировал с e-maxx'а и объединил всё в одну программу: #include &lt;stdio.h&gt;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru