Студент: Кирильчук В. Е. Руководитель: Кубенский А. А. - презентация

1 Студент: Кирильчук В. Е. Руководитель: Кубенский А. А.

2

3

4 1. Анализ существующей реализации в классе BigInteger. 2. Подбор и реализация наиболее эффективных алгоритмов умножения. 3. Оценка полученных результатов. Сравнение с начальной реализацией и сторонней библиотекой.

5 N = a 0 + a 1 * BASE 1 + a 2 * BASE 2 + … + a n-1 * BASE n-1 1. Каким выбрать основание? Большее основание – меньше коэффициентов. Должен быть базовый тип для контроля переполнения. 2. Как хранить? Массив – наиболее быстрая структура. Кэшируется процессором. Little-endian, или Big-endian нотация? 0

6

7

8

9 Ассимптотическая сложность алгоритма:

10

11

12

13

14

15

16

17 1. На криптографическом интервале(до 256 байт) не удалось увеличить эффективность. 2. В интервале от 256 байт до 1024 байт наблюдается небольшое уменьшение времени выполнения умножения. 3. После 1024 байт заметный рост скорости. Уже при 2048 байтах умножение выполняется в 4 раза быстрее.

18 1. Реализованы некоторые алгоритмы умножения чисел неограниченной разрядности. Впервые на Java реализован алгоритм умножения чисел неограниченной разрядности с использованием БПХ 2. Составлена новая операция умножения для класса BigInteger. 3. Полученная операция гораздо более эффективна, чем стандартная на достаточно больших числах и эффективнее, чем APFLOAT.

19 ?

20 Спасибо за внимание!