Pull to refresh

Тест простоты числа регулярным выражением

Reading time 3 min
Views 12K
Original author: Andrei Zmievski
Я видел множество проблем, связанных с регулярными выражениями, но в прошлую пятницу, спасибо Крису и Шону я нашел одну регулярку, которая позволяет проверить, является ли данное целое число простым. Оригинальные статьи предлагали следующее регулярное выражение для определения простоты числа:



/^1?$|^(11+?)\1+$/

Применять его следует не к самому целому числу. Вместо этого, нужно создать строку из единиц, где количество единиц соответствует самому числу и уже к этой строке применить регулярное выражение. Если совпадения нет — число простое. Это регулярное выражение содержит обратные ссылки и поэтому не будет работать на DFA-движке, таком, как функции PHP ereg*. Но оно прекрасно работает с функциями preg_*, или по меньшей мере я так думал (подробнее об этом ниже).

Так как же оно работает? Выглядит как настоящая головоломка, но на самом деле все просто. Проигнорируйте его часть до символа |, поскольку она предназначена просто для выяснения, является ли строка совсем пустой или состоит из одной единицы.

Подвыражение (11+?) совпадает со строками вроде 11, 111, и т.д… Часть "\1+" будет искать далее по строке совпадения с результатами поиска первого подвыражения. В первый раз совпадение произойдет по строке «11» и потом поиск строки «11» будет произведен снова, а затем снова до конца строки. Если поиск завершится успешно, число не является простым. Почему? Потому, что будет доказано, что длина строки делится на 2 и, соответственно, само число тоже делится на два. Если совпадения не произойдет, движок регулярных выражений начнет искать строку «111» и ее повторения (таким образом реализуя дальше решето Эратосфена — прим. пер). Если первое подвыражение становится достаточно длинным (n/2) и совпадений по-прежнему не будет обнаружено, число будет являться простым.

Недавно Шон написал плагин для выполнения кода для бота IRC, основанной на Phergie, который висит на том же, канале, в котором мы общаемся. Сам плагин суть просто прокси к ideone.com, но он полезен для быстрых тестов кода. Мы экспериментировали с этим шаблоном регулярного выражения и написали PHP функцию, которая возвращает простое число, следующее за переданным целым. Неприятности начались, когда Шон передал этой функции 99999999 и она возвратила 100000001. Похоже, произошла ошибка, поскольку 100000001 не является простым числом (=17 * 5882353). Wolfram Alpha это подтвердил.

После нескольких похожих тестов мы нашли еще числа, которые не являлись простыми, но проходили наш маленький тест. Мы задумались, где же может быть проблема? PHP код был слишком простым, чтобы иметь баг, достаточно много ответов, полученных от нашей функции, являлись верными. Похоже, пришло время воспользоваться методом грубой силы. Я быстро написал код для тестирования последовательности нечетных чисел нашему шаблону и стал проверять ответы нашей функции решетом Эратосфена, чтобы понять, где результаты становятся ошибочными. Первым ошибочно найденным числом стало 22201. Проверка нашей регуляркой сказала нам, что он должно быть простым, но вообще-то оно является квадратом 149. После этой границы количество ошибочно определенных простых возросло.

Вдруг меня осенило, что проблема может скрываться в самом механизме обратных ссылок в регулярных выражениях. В частности, в том, как именно он реализован в PCRE, сердце регулярных выражений в PHP. Как я уже упоминал в посте на Regex Clinic, неограниченное использование обратных ссылок ведет к сильному снижению скорости обработки текста регулярным выражением и поэтому следует хорошенько подумать, прежде чем использовать его для написания сложных регулярных выражений. Для того, чтобы устранить опасность злоупотребления этим механизмом, в PCRE несколько лет назад был реализован ограничительный параметр pcre.backtrack_limit. В нашем случае обратные ссылки использовались для разбивания текста из единиц на большое количество частей и с очень большими строками это могло привести к выходу за установленный лимит, который по умолчанию — 100000. Я подумал, что со строкой из 22201 символа этого лимита было недостаточно. Как только лимит достигался, совпадение отказывало и число объявлялось простым.

Я увеличил лимит до 200000 и, вуаля!.. 22201 уже не определялось, как простое. Для того, чтобы исправить работу регулярного выражения с совпадением №100000001, лимит пришлось серьезно поднять аж до 250000000! Прогон регулярного выражения при этом стал занимать около 14 секунд на моем новом i5 MacBook Pro.

Не стоит и говорить, что описанный мной подход к проверке числа на простоту не должен использоваться в реальной жизни. Просто оцените его элегантность. Я оценил. И я рад, что мое небольшое исследование показало, что абстрактные, чистые, хорошие идеи могут просто не работать в нашем сумасшедшем мире софта и железа.
Tags:
Hubs:
+84
Comments 31
Comments Comments 31

Articles