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

Система остаточных классов в длинной арифметике - C++

Восстановить пароль Регистрация
 
mihey1993
314 / 40 / 16
Регистрация: 07.09.2014
Сообщений: 190
24.09.2015, 09:31     Система остаточных классов в длинной арифметике #1
Добрый день, коллеги.

Занялся реализацией длинной арифметики (так, чисто для тренировки) и у меня возник вопрос. Пробовал ли кто-нибудь реализовать базовые арифметические операции (хотя бы сложение и умножение) через систему остаточных классов. То есть понятно, что в данной ситуации операции осложняются необходимостью считать остатки и наличием какого-то базиса из простых чисел(простейший вариант), но все-таки возможно этот метод более оптимален, чем реализация "в лоб" столбиком?

З.Ы.: На всякий случай ссыль на описание СОК на вики Система остаточных классов
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2015, 09:31     Система остаточных классов в длинной арифметике
Посмотрите здесь:

Система классов визуального интерфейса C++
C++ система классов
C++ целочисленной арифметике
C++ Перевод чисел из системы остаточных классов в десятичную систему счисления
Тренажер по арифметике с++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Renji
1532 / 980 / 238
Регистрация: 05.06.2014
Сообщений: 2,950
24.09.2015, 10:48     Система остаточных классов в длинной арифметике #2
Зачем вам там столбики понадобились? Каждый остаток складывается/умножается независимо от остальных, ради этого все и затевается. Вот при попытке привести все это в более традиционный вид как раз и начинаются пляски с бубном.
mihey1993
314 / 40 / 16
Регистрация: 07.09.2014
Сообщений: 190
24.09.2015, 11:17  [ТС]     Система остаточных классов в длинной арифметике #3
Renji, я и имел ввиду, что хочу сравнить СОК и классический "столбик"
SerVal
 Аватар для SerVal
17 / 17 / 2
Регистрация: 16.04.2015
Сообщений: 166
24.09.2015, 13:15     Система остаточных классов в длинной арифметике #4
"Возможность представления только ограниченного количества чисел."(с)
Тут какбэ непонятно получается: 2 умножать на 2 - можно, а на 3 - низя.

Реализация "в лоб" столбиком..
Дык, реально, никто столбиком не умножает... понапридумывали всяких штучек.
mihey1993
314 / 40 / 16
Регистрация: 07.09.2014
Сообщений: 190
24.09.2015, 14:04  [ТС]     Система остаточных классов в длинной арифметике #5
Цитата Сообщение от SerVal Посмотреть сообщение
"Возможность представления только ограниченного количества чисел."(с)
Имеется ввиду что для операции из 2 чисел надо определять базис по большему из них. Т.е. в базисе (2;3) можно представить только числа то 0 до 5, поэтому нужен динамический базис и хранение массива взаимнопростых чисел(проще всего взять простые числа). Тут как бы все в принципе понятно. Мне интересно следующее - существует хоть какое-то значимое число кейсов в которых СОК как параллельное сложение эффективнее чем классическое "последовательное" сложение?
SerVal
 Аватар для SerVal
17 / 17 / 2
Регистрация: 16.04.2015
Сообщений: 166
24.09.2015, 14:35     Система остаточных классов в длинной арифметике #6
Цитата Сообщение от mihey1993 Посмотреть сообщение
нужен динамический базис
Э... подозреваю, что до сложения дело таки не дойдёт.
Прикиньте, во что обойдутся операторы "больше-меньше-равно" двух чисел в СОК.
Это базовые операторы. Только на них можно голову сломать...
* а про производительность можно вообще забыть.
zer0mail
2176 / 1859 / 187
Регистрация: 03.07.2012
Сообщений: 6,615
Записей в блоге: 1
24.09.2015, 18:17     Система остаточных классов в длинной арифметике #7
Мое мнение насчет СОК: "месье знает толк в извращениях"
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.09.2015, 09:35     Система остаточных классов в длинной арифметике
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
mihey1993
314 / 40 / 16
Регистрация: 07.09.2014
Сообщений: 190
25.09.2015, 09:35  [ТС]     Система остаточных классов в длинной арифметике #8
zer0mail, о да, однозначно знает. Однако идея которая мне не даёт покоя - возможность выполнять арифметические операции в параллельном режиме. Если найти как хранить в удобном виде представления чисел, это же должно дать знатный прирост в производительности
Yandex
Объявления
25.09.2015, 09:35     Система остаточных классов в длинной арифметике
Ответ Создать тему
Опции темы

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