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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.79
G@leON
 Аватар для G@leON
6 / 6 / 1
Регистрация: 02.06.2009
Сообщений: 95
13.05.2012, 13:32     Длинная арифметика #1
Здраствуйте, пишу модуль длинной математики. В принципе, работоспособность у него положительная. Но в силу моей неопытности меня мучают вопросы оптимизации. М.б. кто то сможет (или уже смог) реализовать более красивый код, чем мой.Собственно сначала ввод/вывод.

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;
    }
 
}
Как допишу модуль, и вытащу (с вашей помошью, если можно) из него все костыли, обязательно поделюсь))
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2012, 13:32     Длинная арифметика
Посмотрите здесь:

Длинная арифметика C++
C++ Длинная арифметика
C++ Длинная арифметика
C++ Длинная арифметика
C++ Длинная арифметика
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.05.2012, 13:35     Длинная арифметика #2
Цитата Сообщение от G@leON Посмотреть сообщение
// len - скольки значное число хранится в каждом elem (4 - оптимально)
Оптимально - 9.
По идее, можно и больше...
G@leON
 Аватар для G@leON
6 / 6 / 1
Регистрация: 02.06.2009
Сообщений: 95
13.05.2012, 13:41  [ТС]     Длинная арифметика #3
Цитата Сообщение от diagon Посмотреть сообщение
Оптимально - 9.
По идее, можно и больше...
Ага, читал, но везде писали по разному, кто 9, кто 4. В книжке Окулова "Программирование в алгоритмах" говорится, что оптимально 4. ))
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
13.05.2012, 13:42     Длинная арифметика #4
Цитата Сообщение от G@leON Посмотреть сообщение
Ага, читал, но везде писали по разному, кто 9, кто 4. В книжке Акулова "Программирование в алгоритмах" говорится, что оптимально 4.
Окулова
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.05.2012, 13:45     Длинная арифметика #5
Цитата Сообщение от G@leON Посмотреть сообщение
Ага, читал, но везде писали по разному, кто 9, кто 4. В книжке Акулова "Программирование в алгоритмах" говорится, что оптимально 4.
Оптимально 9, ибо чем больше цифр хранится в одном элементе. тем меньше этих самых элементов в векторе, и, соответственно, быстрее производятся операции и требуется меньше памяти.
G@leON
 Аватар для G@leON
6 / 6 / 1
Регистрация: 02.06.2009
Сообщений: 95
13.05.2012, 13:59  [ТС]     Длинная арифметика #6
Так, такой вопрос, смотрел насколько ресурсов, 1 из них мне очень даже понравился.
C++
1
2
Для глубокого понимания всего, что тут происходит, предлагаю вам ознакомиться с ресурсом:
    [url]http://cppalgo.blogspot.com/2010/05/blog-post.html[/url]
У меня возник вопрос, что лучше, сделать свою структуру, или м.б. даже класс. Или же решать функциональным подходом. Ответ, вроде может показаться очевидным - делай класс. Но конкретная реализация на ресурсе использовала массивы, что мне кажется несколько менее красивым, чем использование вектора. Я же заменил всю структуру вектором. То м.б. удобно будет сделать класс (структуру), который будет состоять из вектора.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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
Ternsip
 Аватар для 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
Не всегда внешние ресурсы спасают, например, мне разрешено использовать на тестирующей машине только стандартные либы, и не более. Приходится всё самому писать
G@leON
 Аватар для G@leON
6 / 6 / 1
Регистрация: 02.06.2009
Сообщений: 95
13.05.2012, 14:34  [ТС]     Длинная арифметика #9
Может оно тогда к лучшему и не заморачиваться по поводу написания модуля арифметики, если уж gmp есть? Очень удобная библиотека для пользования. В info все от и до описано.

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

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

Я тогда на время от этой темы уйду, вернусь недельки через 2-3 к ней. Все таки самому изобрести велосипед по новой тоже бывает полезно. А там и собственно класс выложу, для работы с длинными, что бы пользователя порадовать, особенно тех, кому использовать сторонние либы нельзя.
Всем спасибо...
G@leON
 Аватар для G@leON
6 / 6 / 1
Регистрация: 02.06.2009
Сообщений: 95
12.06.2012, 16:23  [ТС]     Длинная арифметика #10
И так, возвращаясь к теме длинной арифметики, коей я интересовался некоторое время назад.
GMP - библиотека действительно очень удобная, хотя и много было вопросов по поводу того как ее подключить, все ответы уже есть, тем более они на русском...
Что касаемо сообщений на тему, мне нельзя использовать сторонние либы или нужно свой класс реализовать или я не силен, а сторонние либы какие то громоздкие больно (именно с такой проблемой я по началу сам столкнулся): вот здесь http://cppalgo.blogspot.com/2010/05/blog-post.html все по полочкам разложено о написании собственного класса с пояснениями, как и что. Автор использует struct, но кто вам мешает использовать class и вынести это в заголовочный файл. Там даже код есть, немного переделываем, если есть желание, и все готово.
Свою реализацию класса выложу после экзамена 18 июня с пояснениями. Еще раз спасибо тем, кто помог мне, и показал полезные ссылки...
G@leON
 Аватар для G@leON
6 / 6 / 1
Регистрация: 02.06.2009
Сообщений: 95
16.06.2012, 21:49  [ТС]     Длинная арифметика #11
Класс длинно-численной арифметики выставляю чуть раньше обещанного. Прошу сильно не ругать, если где то увидели корявую реализацию. Советы по оптимизации принимаются (как в части математической, так и в части реализации самого кода) - буду очень признателен. Все советы по исправлению и доработке буду обязательно использовать, что однозначно улучшит данный вариант.
Я описал только названия - что для чего. В принципе, очень похожий код вы найдете по ссылке из предыдущего сообщения + полное описание математики произходящего.
Вложения
Тип файла: rar big_int.rar (3.6 Кб, 34 просмотров)
Jupiter
Каратель
Эксперт C++
6542 / 3962 / 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 // в зависимости от задачи
лучше сделать как параметр шаблона

класс, функции друзья лучше завернуть в пространство, и заоодно все служебные константы
Avazart
 Аватар для Avazart
6900 / 5140 / 252
Регистрация: 10.12.2010
Сообщений: 22,591
Записей в блоге: 17
17.06.2012, 00:10     Длинная арифметика #13
А почему собственно вектор? Разве дек не оптимальнее?

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

В коде мне не нравится ограничение на максимальную длину чисел. Если использовать вектор, то таких ограничений не будет, можно и без вектора неограниченную длину сделать.
И еще нужно обернуть класс в отдельное пространство имен, и уже в этом пространстве написать все необходимые using'и. А то сейчас получается такая ситуация, что при включении вашего хедера автоматически раскрывается пространство имен std, а это не есть гуд.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.06.2012, 16:09     Длинная арифметика
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Avazart
 Аватар для Avazart
6900 / 5140 / 252
Регистрация: 10.12.2010
Сообщений: 22,591
Записей в блоге: 17
17.06.2012, 16:09     Длинная арифметика #15
Мне кажется, что вектор будет получше.
так как удалять элементы нужно только с конца.
Ну да, но это если расматривать только большие целые, а если большие с плавующей точкой?
Yandex
Объявления
17.06.2012, 16:09     Длинная арифметика
Ответ Создать тему
Опции темы

Текущее время: 00:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru