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

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

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

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

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

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

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

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

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

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

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

7
Renji
2105 / 1545 / 471
Регистрация: 05.06.2014
Сообщений: 4,484
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
2452 / 2089 / 216
Регистрация: 03.07.2012
Сообщений: 7,571
Записей в блоге: 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