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

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

Войти
Регистрация
Восстановить пароль
 
mihey1993
322 / 48 / 19
Регистрация: 07.09.2014
Сообщений: 217
#1

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

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

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

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

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

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

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

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

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

Предложить эффективный алгоритм умножения числа на дробь в длинной арифметике - C++
Нам дано длинное натуральное число, представленное в виде динамического массива: 1) разряды числа записываются от старшего к младшему;...

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

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

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

Система классов визуального интерфейса - C++
Тема по ООП такая: "Система классов визуального интерфейса" Использовать процедуры полиморфного объекта... я не знаю какой пример...

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

целочисленной арифметике - C++
Определить, сколько цифр в каждом числе n из заданной последовательности чисел. Если количество цифр чётное, то получить из него число...

Тренажер по арифметике с++ - C++
Пользователь-учитель вводит с клавиатуры разрядность операндов, тип операции: + – * / (на множестве натуральных чисел) и количество...


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

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

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