Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.79
G@leON
6 / 6 / 1
Регистрация: 02.06.2009
Сообщений: 99
#1

Длинная арифметика - C++

13.05.2012, 13:32. Просмотров 1785. Ответов 14
Метки нет (Все метки)

Здраствуйте, пишу модуль длинной математики. В принципе, работоспособность у него положительная. Но в силу моей неопытности меня мучают вопросы оптимизации. М.б. кто то сможет (или уже смог) реализовать более красивый код, чем мой.Собственно сначала ввод/вывод.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*  Функция long_input не возвращает значения, а работает с сылочными параметрами.
    Эти параметры: ссылка на строку ввода и на vector<int>,
    в который и будет записано число любой размерности.
    В каждый элемент вектора записывается 4-значная цифра из строки.
    Предположим, в строку вы записали 103487365824375284.
    Тогда в векторе у вас будет следующее представление: 5284 | 2437 | 3658 | 3487 | 10
*/
 
void long_input(vector<int> &l_number, string &l_str){
    int len = 4;
        // len - скольки значное число хранится в каждом elem (4 - оптимально)
    for (int index = l_str.size() - 1; index >= 0; index -= len)
    {
        int start = index - len + 1;
        if (start < 0)
            start = 0;
        string elem = l_str.substr(start, index - start + 1);
            // Ф-ция substr извлекает подстроку длинной (index - start + 1)
            // из строки l_str начиная с позиции start
        l_number.push_back(atoi(elem.c_str()));
    }
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*  Функция long_output_s не возвращает значения, а работает с сылочными параметрами.
    Эти параметры: ссылка на vector<int>, в котором записано число и строку вывода.
    Здесь преобразование обратное тому, что происходит при вводе.
*/
 
void long_output_s(string &l_str, vector<int> &l_number) {
    l_str = "";
    bool l_p = true;
    char buffer[4];
    vector<int>::iterator iter = l_number.end() - 1;
    sprintf(buffer, "%d", *iter);
    l_str += buffer;
    if (iter == l_number.begin())
        l_p = false;
    while (l_p){
        --iter;
        if (iter == l_number.begin())
            l_p = false;
        sprintf(buffer, "%.4d", *iter);
        l_str += buffer;
    }
 
}
Как допишу модуль, и вытащу (с вашей помошью, если можно) из него все костыли, обязательно поделюсь))
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2012, 13:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Длинная арифметика (C++):

Длинная арифметика - C++
Ребята,объясните как решить задачу , напишите хоть часть кода. Пусть даны числа a , b . Найти a+b, если a и b не больше чем 10 в...

Длинная арифметика - C++
Вот условие задачи: Во время исследований, посвященных появлению жизни на планете Олимпия, учеными было сделано несколько сенсационных...

Длинная арифметика - C++
Здравствуйте помогите пожалуйста с задачкой на с++ борландс :wall: 1. &quot;Вычислить точное значение (n!)! &quot; 2. &quot;Для заданной...

Длинная арифметика - C++
Всем доброго вечера. Нужна помощь в решении задачи. Составить программу для вычисления числа: 2^64-1. В результате сохранить все...

Длинная арифметика N+1 - C++
Помогите плиз. Вводится n. Вывести N+1. Ограничений нет. Я понимаю что надо ввести массив и читать каждый символ. Оставшиеся елементы...

Длинная арифметика. - C++
Даны два длинных числа a и b. Найти частное и остаток при делении числа a на b. Не могу реализовать деление отрицательных чисел. Помогите...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.05.2012, 13:35 #2
Цитата Сообщение от G@leON Посмотреть сообщение
// len - скольки значное число хранится в каждом elem (4 - оптимально)
Оптимально - 9.
По идее, можно и больше...
1
G@leON
6 / 6 / 1
Регистрация: 02.06.2009
Сообщений: 99
13.05.2012, 13:41  [ТС] #3
Цитата Сообщение от diagon Посмотреть сообщение
Оптимально - 9.
По идее, можно и больше...
Ага, читал, но везде писали по разному, кто 9, кто 4. В книжке Окулова "Программирование в алгоритмах" говорится, что оптимально 4. ))
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
13.05.2012, 13:42 #4
Цитата Сообщение от G@leON Посмотреть сообщение
Ага, читал, но везде писали по разному, кто 9, кто 4. В книжке Акулова "Программирование в алгоритмах" говорится, что оптимально 4.
Окулова
1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.05.2012, 13:45 #5
Цитата Сообщение от G@leON Посмотреть сообщение
Ага, читал, но везде писали по разному, кто 9, кто 4. В книжке Акулова "Программирование в алгоритмах" говорится, что оптимально 4.
Оптимально 9, ибо чем больше цифр хранится в одном элементе. тем меньше этих самых элементов в векторе, и, соответственно, быстрее производятся операции и требуется меньше памяти.
0
G@leON
6 / 6 / 1
Регистрация: 02.06.2009
Сообщений: 99
13.05.2012, 13:59  [ТС] #6
Так, такой вопрос, смотрел насколько ресурсов, 1 из них мне очень даже понравился.
C++
1
2
Для глубокого понимания всего, что тут происходит, предлагаю вам ознакомиться с ресурсом:
    [url]http://cppalgo.blogspot.com/2010/05/blog-post.html[/url]
У меня возник вопрос, что лучше, сделать свою структуру, или м.б. даже класс. Или же решать функциональным подходом. Ответ, вроде может показаться очевидным - делай класс. Но конкретная реализация на ресурсе использовала массивы, что мне кажется несколько менее красивым, чем использование вектора. Я же заменил всю структуру вектором. То м.б. удобно будет сделать класс (структуру), который будет состоять из вектора.
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.05.2012, 14:04 #7
Реализаций много, одна из лучших для с++ - библиотека gmp, в которой можно использовать код на чистом C, либо обертку вокруг него в виде класса.
А в класс стоит оборачивать, чтобы можно было писать подобные конструкции.
C++
1
2
BigInteger a = 3;
std::cout << a * 2; //выведет 6
Это намного удобнее для пользователя, чем функции.
Вот еще один неплохой ресурс с длинной арифметикой на с++ - http://e-maxx.ru/algo/big_integer
2
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
13.05.2012, 14:19 #8
Цитата Сообщение от diagon Посмотреть сообщение
Реализаций много, одна из лучших для с++ - библиотека gmp, в которой можно использовать код на чистом C, либо обертку вокруг него в виде класса.
А в класс стоит оборачивать, чтобы можно было писать подобные конструкции.
C++
1
2
BigInteger a = 3;
std::cout << a * 2; //выведет 6
Это намного удобнее для пользователя, чем функции.
Вот еще один неплохой ресурс с длинной арифметикой на с++ - http://e-maxx.ru/algo/big_integer
Не всегда внешние ресурсы спасают, например, мне разрешено использовать на тестирующей машине только стандартные либы, и не более. Приходится всё самому писать
0
G@leON
6 / 6 / 1
Регистрация: 02.06.2009
Сообщений: 99
13.05.2012, 14:34  [ТС] #9
Может оно тогда к лучшему и не заморачиваться по поводу написания модуля арифметики, если уж gmp есть? Очень удобная библиотека для пользования. В info все от и до описано.

Как же я так пропустил ее мимо

Добавлено через 1 минуту
Цитата Сообщение от Ternsip Посмотреть сообщение
Не всегда внешние ресурсы спасают, например, мне разрешено использовать на тестирующей машине только стандартные либы, и не более. Приходится всё самому писать
Ну это смотря для каких целей.

Я тогда на время от этой темы уйду, вернусь недельки через 2-3 к ней. Все таки самому изобрести велосипед по новой тоже бывает полезно. А там и собственно класс выложу, для работы с длинными, что бы пользователя порадовать, особенно тех, кому использовать сторонние либы нельзя.
Всем спасибо...
1
G@leON
6 / 6 / 1
Регистрация: 02.06.2009
Сообщений: 99
12.06.2012, 16:23  [ТС] #10
И так, возвращаясь к теме длинной арифметики, коей я интересовался некоторое время назад.
GMP - библиотека действительно очень удобная, хотя и много было вопросов по поводу того как ее подключить, все ответы уже есть, тем более они на русском...
Что касаемо сообщений на тему, мне нельзя использовать сторонние либы или нужно свой класс реализовать или я не силен, а сторонние либы какие то громоздкие больно (именно с такой проблемой я по началу сам столкнулся): вот здесь http://cppalgo.blogspot.com/2010/05/blog-post.html все по полочкам разложено о написании собственного класса с пояснениями, как и что. Автор использует struct, но кто вам мешает использовать class и вынести это в заголовочный файл. Там даже код есть, немного переделываем, если есть желание, и все готово.
Свою реализацию класса выложу после экзамена 18 июня с пояснениями. Еще раз спасибо тем, кто помог мне, и показал полезные ссылки...
1
G@leON
6 / 6 / 1
Регистрация: 02.06.2009
Сообщений: 99
16.06.2012, 21:49  [ТС] #11
Класс длинно-численной арифметики выставляю чуть раньше обещанного. Прошу сильно не ругать, если где то увидели корявую реализацию. Советы по оптимизации принимаются (как в части математической, так и в части реализации самого кода) - буду очень признателен. Все советы по исправлению и доработке буду обязательно использовать, что однозначно улучшит данный вариант.
Я описал только названия - что для чего. В принципе, очень похожий код вы найдете по ссылке из предыдущего сообщения + полное описание математики произходящего.
0
Вложения
Тип файла: rar big_int.rar (3.6 Кб, 35 просмотров)
Jupiter
Каратель
Эксперт С++
6554 / 3975 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
16.06.2012, 21:56 #12
C++
1
2
3
4
5
6
7
8
using std::istream;
using std::ostream;
using std::string;
using std::cin;
using std::cout;
using std::endl;
using std::max;
using namespace std;
смысл?

C++
1
#define MAX_LEN 500 // в зависимости от задачи
лучше сделать как параметр шаблона

класс, функции друзья лучше завернуть в пространство, и заоодно все служебные константы
0
Avazart
Эксперт С++
7188 / 5362 / 280
Регистрация: 10.12.2010
Сообщений: 23,663
Записей в блоге: 17
17.06.2012, 00:10 #13
А почему собственно вектор? Разве дек не оптимальнее?

Насчет gmp - там нет логарифмов,экспонент итп поэтому придется реализовывать самому через ряды (с использованием gmp конечно) - думаю это можно было бы написать + обвертку класса по то му как при работе через ф-ции код получается не такой читаемый
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.06.2012, 09:01 #14
Цитата Сообщение от Avazart Посмотреть сообщение
Разве дек не оптимальнее?
Мне кажется, что вектор будет получше.
С одной стороны, будут переезды из одного куска памяти в другой, с другой стороны - во всем остальном вектор быстрее, так как удалять элементы нужно только с конца.

В коде мне не нравится ограничение на максимальную длину чисел. Если использовать вектор, то таких ограничений не будет, можно и без вектора неограниченную длину сделать.
И еще нужно обернуть класс в отдельное пространство имен, и уже в этом пространстве написать все необходимые using'и. А то сейчас получается такая ситуация, что при включении вашего хедера автоматически раскрывается пространство имен std, а это не есть гуд.
0
Avazart
Эксперт С++
7188 / 5362 / 280
Регистрация: 10.12.2010
Сообщений: 23,663
Записей в блоге: 17
17.06.2012, 16:09 #15
Мне кажется, что вектор будет получше.
так как удалять элементы нужно только с конца.
Ну да, но это если расматривать только большие целые, а если большие с плавующей точкой?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.06.2012, 16:09
Привет! Вот еще темы с ответами:

Длинная арифметика - C++
Поодскажите какую-нибудь библиотеку, где реализована работа со знаковыми целыми числами произвольной длины.

Длинная арифметика - C++
Помогите реализовать длинную арифметику #include &lt;iostream&gt; #include &lt;string&gt; using namespace std; int main(){ int a; string...

Длинная арифметика - C++
Срочно нужны исходники (функции): 1. Перевод обычного числа в длинное (массив, строка , вектор кто с чем работает) 2. Нахождение суммы...

Длинная арифметика С++ - C++
требуется написать задачу для подсчета суммы s=1^2+2^2+3^2+...+n^2 n&gt;=20000


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
17.06.2012, 16:09
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru