02-resource1 (1238872), страница 2

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

Текст из файла (страница 2)

Есть очевидный способ это сделать: считать изаписать = ≫ &1 = ≫ &1 = & ~2 & ~2 | ≪ | ≪ •Гораздо менее очевидным способом является -обмен. Пусть > .Обозначим = − . Тогда обмен битов в x выглядит так:= ۩ ≫ = ۩۩ ≪ & 2Дельта-обмены•Пусть > . Обозначим = − . Тогда обмен битов в x выглядит так:= ۩ ≫& 2 = ۩۩ ≪ •-обмен выглядит не слишком интуитивно, но он окупается, если заметить,что теперь вместо 2 может стоять любая маска •Вопрос к математически настроенной части аудитории: какие параметры и надо подобрать, чтобы в 64-разрядном числе обменять верхние 25 битов снижними?•Заметьте, что прямая схема с прошлого слайда так хорошо не обобщается наэту задачу: там придётся высчитывать руками маску и анти-маскуProblem PE – побитовое решето•Сейчас решето Эратосфена, которое строит алгоритм S, хранит unsignedchar (то есть 8 бит) на каждый признак простоты числа.

Это немыслимыйрасход памяти•Вам предлагается оптимизировать построение решета таким образом, чтобыпризнак того является ли число простым хранился в каждом бите решета•Это позволит сократить расход памяти в 8 раз•Разумеется это несколько усложнит функции init_sieve и is_prime•Подумайте о тестировании вашего решетаДомашняя работа HWE•Результаты, полученные в Problem PE, могут быть улучшены далее: памятьможно сократить ещё в два раза, если хранить в каждом бите толькопризнаки простоты для нечётных чисел•На самом деле, память можно сократить ещё в полтора раза, если хранитьдва массива: первый для всех (6 − 1)-ых а второй для всех (6 + 1)-ыхбитовstruct sieve_t {unsigned size;unsigned char *plus1; // for 7, 13, 19, 25, ....unsigned char *minus1; // for 5, 11, 17, 23, ....};•Реализуйте такое решето. Поможет ли оно вам найти миллиардное простое?Problem CС – циркулярные простые*•Число 197 называется циркулярным простым, поскольку простыми являютсявсе циклические перестановки его разрядов: 197 → 971 → 719•Необходимо для заданного числа N определить ближайшее к немуциркулярное простое.

Например для числа 200 ближайшим циркулярнымпростым будет 197•Подумайте можно ли легко понять какого размера решето вам нужно?•В зависимости от математических свойств циркулярных простых чисел (еслиони встречаются часто) проверка алгоритмом P может быть эффективнеерешета. Ожидаете ли вы найти ближайшее циркулярное простое к 200000достаточно близко, чтобы решето не окупалось?•Подумайте о решении, которое будет комбинировать алгоритм P и решето*по мотивам project Euler, 35Тест Ферма•Чтобы протестировать большое число на простоту, построение решетабывает затруднительно.

Например чтобы проверить 250 + 7, решето должнозанимать много терабайт даже после всех оптимизаций.•Математический инсайт: малая теорема Ферма−1 ≡ 1 () если p простое и a не делится на p•К сожалению для многих составных , ∃, −1 ≡ 1 () это Fermat liar38220 ≡ 1(221) но 24220 ≡ 81(221) значит 221 составное•Такое , что −1 ≠ 1 () называется свидетелем (Fermat witness)непростоты, например 24 это witness для 221.•Обычно свидетеля выбирают случайно или ищут переборомПсевдослучайные числа•По настоящему случайные числа довольно сложны. Вместо них используютсяпсевдослучайные, то есть выглядящие как случайные, но сгенерированныедетерминированно•В языке C псевдослучайные числа проще всего генерировать функциейrand(). Эта функция возвращает равномерное число от 0 до _.Чтобы получить число от 0 до − 1, достаточо подсчитать rand() % N•Это не лучший, но распространённый способ•Чтобы не получать от запуска к запуску одинаковые числа, можно задать seedчерез функцию srand.

Обычным источником seed является текущее время вмикросекундах с 1970 года: srand(time(NULL))Problem FT – тест Ферма•Реализуйте тест Ферма.•Для тестирования можно использовать решето и небольшие простые.•Некоторые числа (они называются числами Кармайкла) не имеют свидетелей,а только лжецов и для них тест Ферма не работает. Сколько таких чисел вынашли во время тестирования?Problem PF – Фибоподобные простые•Некоторые числа Фибоначчи, например 5 и 13 являются также простымичислами. Разумеется, список простых чисел Фибоначчи не слишкоминтересен, его легко нагуглить•К счастью, в мире много других интересных последовательностей, похожихна числа Фибоначчи, например такая: = −1 + −2•Ваша задача, получив на вход числа и вычислить самое большое простоечисло , такое, что < 264 и входит в данную последовательность•Например для = 1 и = 1 (т.е.

для обычных чисел Фибоначчи) ответомявляется 99194853094755497•Напишите программу, которая ищет ответ для любых 0 < , < 256Дальнейшие направления•Работа с арифметическими объектами, такими как простые числа, можетбыть увлекательной и небезынтересной. Увы, не всё можно поместить впрограмму семинара•••••Улучшением теста Ферма является тест Миллера-Рабина, который можно дажесделать детерминированнымПотрясающе красивые задачи лежат в области факторизации чисел и дискретныхлогарифмовПростые числа используются в шифровании, в том числе алгоритм RSA оченьполезно знать каждомуХорошие случайные числа для криптографии мистически связаны с гигантскимипростыми числами МерсеннаВысокие уровни HW2 дают возможность потренироваться во всём этомЛитература•С11 ISO/IEC, "Information technology – Programming languages – C",ISO/IEC 9899:2011•& Brian W.

Kernighan, Dennis Ritchie – The C programminglanguage, 1988• Ronald L. Graham, Donald E. Knuth, Oren Patashnik – ConcreteMathematics: A Foundation for Computer Science, 1994• Donald E. Knuth – The Art of Computer Programming, 2011•Project Euler, problem 27:https://projecteuler.net/problem=27•Prime formulas:http://mathworld.wolfram.com/PrimeFormulas.html.

Характеристики

Список файлов лекций