ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.05.2024
Просмотров: 8
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
цМИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего образования
«Дальневосточный федеральный университет»
(ДВФУ)
ИНСТИТУТ МАТЕМАТИКИ И КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ
Департамент математического и компьютерного моделирования
ДОКЛАД
на тему «Эффективная длинная арифметика»
дисциплина «Алгоритмы и структуры данных»
направление подготовки 09.03.03 «Прикладная информатика»
профиль «Прикладная информатика в компьютерном дизайне»
| | | Выполнил студент гр. Б9121-09.03.03пикд Жадик К.А.___________________ |
| Доклад защищен: с оценкой _______________________ | | (Ф.И.О.) (подпись) Преподаватель _____________________________ (должность, уч.звание) ____________________________ (Ф.И.О.) (подпись) «_____»______________2022г. |
| Рег. № ______ «____»__________________2022 г. | | |
Список литературы
(История, цели, развитие)
Формальная постановка задачи
Написать ограничения (одз, прочие ограничения)
-
https://brestprog.by/topics/longarithmetics/ - общие принципы реализации -
https://e-maxx.ru/algo/big_integer - хранение и создание чисел -
https://habr.com/ru/post/172285/ - деление -
https://habr.com/ru/post/124258/ - быстрое умножение -
https://wiki.fenix.help/matematika/algoritm-evklida - алгоритм евклида для реализации быстрого деления -
https://ru.wikibrief.org/wiki/Division_algorithm -быстрые алгоритмы деления -
https://www.stud24.ru/programming-computer/dlinnaya-arifmetika/22260-63531-page1.html -
http://comp-science.narod.ru/DL-AR/okulov.htm -
https://programforyou.ru/poleznoe/dlinnaya-arifmetika-kak-operirovat-chislami-ne-pomeshchayushchimisya-ni-v-odin-iz-chislovyh-tipov -
https://cppalgo.blogspot.com/2010/05/blog-post.html -
https://itnan.ru/post.php?c=1&p=578718 -
https://habr.com/ru/company/otus/blog/449996/ -
https://ru.wikipedia.org/wiki/Быстрое_преобразование_Фурье -
https://algorithmica.org/ru/fft -
https://algorithmica.org/ru/karatsuba -
https://translated.turbopages.org/proxy_u/en-ru.ru.36bc7c60-633f5d51-e01bf12c-74722d776562/https/en.wikipedia.org/wiki/The_Karatsuba_multiplication -
https://www.youtube.com/watch?v=m9yO12Zlb1g&ab_channel=КафедраБИС -
https://www.youtube.com/watch?v=21C5cfD6FOo&ab_channel=AGalilov -
https://www.youtube.com/watch?v=yL0I2g69EpM&ab_channel=PavelMavrin -
https://ru.wikipedia.org/wiki/Длинная_арифметика -
http://www.ccas.ru/personal/karatsuba/alg.htm -
https://neerc.ifmo.ru/wiki/index.php?title=Арифметика_чисел_в_b-ичной_системе_счисления_(Длинная_арифметика) -
https://orenstudent.ru/LongArifmAddSub.htm -
https://programforyou.ru/poleznoe/dlinnaya-arifmetika-kak-operirovat-chislami-ne-pomeshchayushchimisya-ni-v-odin-iz-chislovyh-tipov -
https://habr.com/ru/post/207754/ -
https://e-maxx.ru/algo/fft_multiply -
https://codeforces.com/blog/entry/1244
Длинная арифметика - набор алгоритмов для поразрядной работы с числами произвольной длины. Она применяется как с относительно небольшими числами, превышающими ограничения типа long long в несколько раз, так и с по-настоящему большими числами.
Передо мной стоит задача реализовать алгоритмы длинной арифметики, такие как сложение, вычитание, умножение и деление наиболее быстрыми способами.
Длинная арифметика используется:
-
При решении олимпиадных задач. -
В компьютерах низкой разрядности, микроконтроллерах (например, процессор умеет работать только с числами длиной 8 бит, 8 двоичных разрядов, в 8 битах можно представить только числа от 0 до $2^8-1=255$, а требуется обрабатывать большие числа). -
Криптография. -
Математическое и финансовое ПО, требующее, чтобы результат вычисления на компьютере совпал до последнего разряда с результатом вычисления на бумаге. В частности, калькулятор Windows (начиная с 95) -
«Спортивные» вычисления знаменитых трансцендентных чисел ("число Пи", "число e" и т. д.) с высокой точностью. Вещественное число - число, которое может возникать как результат измерения (Например: 4,31; 5,23432; корень из 2-х). Множество вещественных чисел больше, чем множество рациональных дробей (чисел представляющихся в виде дроби), но меньше, чем множество комплексных чисел. Комплексное число - расширение множества вещественных чисел за счёт добавления мнимой компоненты числа. Комплексное число представляется в виде: x+iy, где x и y - вещественные числа, а i-мнимая единица. -
Высококачественные изображения фракталов.
Реализация операций с длинными числами во многом определяется тем, как представить их в памяти компьютера. "Длинное" число можно записать, например, с помощью массива десятичных цифр, количество элементов в таком массиве равно количеству значащих цифр в "длинном" числе. При этом размер массива должен быть достаточным, чтобы разместить в нем и результат, например умножения.
Реализация:
Первое, что нужно решить — это то, как хранить число. Оно будет храниться в виде массива цифр, в обратном порядке (это позволяет проще реализовывать все операции), сразу по 9 цифр в одном элементе массива (что позволяет сэкономить память).
Для создания алгоритма сложения используется обычное сложение в столбик.
Для реализации вычитания используется алгоритм вычитания в столбик.
При выборе алгоритма для умножения сначала я склонялся к методу Карацубы. Это метод быстрого умножения со сложностью вычисления nlog23 в то время, как наивный алгоритм, умножение в столбик, требует n2 операций. Затем я нашел более эффективный алгоритм – Фурье. Этот алгоритм имеет сложность nlog(n), что делает его в разы более эффективным, чем метод Карацубы.
Для деления используется алгоритм обратного быстрого преобразования Фурье, так как среди всех алгоритмов он является самым быстрым и эффективным
История:
По рассказам одного из авторов алгоритма, Джеймса Кули, всё началось в конце 1963 года. Джеймс Кули был нанят в IBM Thomas J. Watson Research Center в Yorktown Heights, что в Нью-Йорке. Кули работал над своим собственным проектом, когда к нему обратился Ричард Гарвин (Richard Garwin) и показал некоторые заметки Джона Тьюки (John Tukey) об алгоритме, который теоретически способен вычислять быстрое преобразование Фурье со скоростью, пропорциональной nlog(n), а не n2. Гарвин, в отличие от Кули, хорошо понимал всю важность этого алгоритма и его огромную практическую значимость, и поэтому настаивал на разработке этого алгоритма.