Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
mihey1993
322 / 48 / 28
Регистрация: 07.09.2014
Сообщений: 217
#1

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

24.09.2015, 09:31. Просмотров 478. Ответов 7
Метки нет (Все метки)

Добрый день, коллеги.

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

З.Ы.: На всякий случай ссыль на описание СОК на вики Система остаточных классов
http://www.cyberforum.ru/cpp-beginners/thread1287369.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2015, 09:31
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Система остаточных классов в длинной арифметике (C++):

Подскажите литературу по длинной арифметике
Длинная арифметика — это набор программных средств (структуры данных и...

Совет в написании/использовании длинной арифметике на примере чисел Фибоначчи
Доброго времени суток. Недавно передо мною появилось задание использование...

Числа Фибоначчи в длинной арифметике (код почти готов, но я застолбил)
Здравствуйте, дорогие форумчане. Есть такое задание, как написать код для 100...

Перевод чисел из системы остаточных классов в десятичную систему счисления
Братья, нужна помощь по переводу чисел из системы остаточных классов в...

Очень нужна работающая программа по "Длинной арифметике вычитания"
Очень нужна работающая программа по "Длинной арифметике вычитания"

7
Renji
2127 / 1486 / 453
Регистрация: 05.06.2014
Сообщений: 4,325
24.09.2015, 10:48 #2
Зачем вам там столбики понадобились? Каждый остаток складывается/умножается независимо от остальных, ради этого все и затевается. Вот при попытке привести все это в более традиционный вид как раз и начинаются пляски с бубном.
0
mihey1993
322 / 48 / 28
Регистрация: 07.09.2014
Сообщений: 217
24.09.2015, 11:17  [ТС] #3
Renji, я и имел ввиду, что хочу сравнить СОК и классический "столбик"
0
SerVal
23 / 23 / 8
Регистрация: 16.04.2015
Сообщений: 208
24.09.2015, 13:15 #4
"Возможность представления только ограниченного количества чисел."(с)
Тут какбэ непонятно получается: 2 умножать на 2 - можно, а на 3 - низя.

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

Предложить эффективный алгоритм умножения числа на дробь в длинной арифметике
Нам дано длинное натуральное число, представленное в виде динамического...

система классов
Здравствуйте)помогите пожалуйста с задачей:необходимо реализовать систему...

Система классов визуального интерфейса
Тема по ООП такая: "Система классов визуального интерфейса" Использовать...

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


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

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