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

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



/^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.

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

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 31

    +35
    Мсье знает толк в извращениях
      +5
      Кстати, интересно написать регулярку для подсчета на Хабре постов,
      в которых первый комментарий равен «Мсье знает толк в извращениях»
      +9
      Простите, я правильно понял, что вы регуляркой разбирали строку длиной в 100 мегабайт?
        +1
        Не он а Andrei Zmievski )
          0
          100 000 001 / 1024 / 1024 = 95.38 мегабайт :)
          +4
          абстрактные, чистые, хорошие идеи могут просто не работать в нашем сумасшедшем мире софта и железа
          у вас опечатка: сумасшедшие идеи могут просто не должны работать в нашем чистом, хорошем мире софта и железа
            0
            Почему опечатка? В оригинале там «can still fail». Разве это стоит переводить как «не должны»?
              +1
              это не вам, это автору
            0
            Это перевод, смотрите внимательнее. А идея красивая, в сферическом таком применении: )
              +1
              Идея, как идея, красива.
                +3
                Настоящий хак (в исходном смысле этого слова)!
                  +5
                  Элегантно!
                    +10
                    Прочитав про борьбу с лимитами, вспомнилась цитата с баша, про то, что «оказывается, компилятор VC игнорит конструкции if...else...if со вложенностью больше 128… пришлось переписывать на switch...case» :)
                      0
                      А не фейк ли это? Я в спецификации ничего такого не нашел.
                        +1
                        А вы проверьте :-)
                          0
                          Промазал — ответил ниже
                          0
                          Вы как бы тоже пошутили?
                            0
                            Да нет, я серьезно
                        +1
                        Да я бы с радостью :) Но оригинальная цитата сформулирована вот так: «наткнулись на багу VS2005 — после 128-го вложенного if-else-if условия просто напросто игнорируются. Пришлось переделать в switch-case». Очевидно, что это баг (если не фейк) не Студии, а компилятора. Но вот какого…
                        0
                        КРУТО!!!
                          –4
                          Тест простоты числа регулярным выражением не нужен.
                            +4
                            gvsmirnov не нужен :)
                              –1
                              ок.
                                +3
                                Это шутка была, если что ;)
                            +1
                            первый пример однострочников на перле в википедии, правда без проверки на одну 1
                              0
                              Гениально! Не практично, но гениально. :)
                                +2
                                Ага, когда-то ещё был популярен такой однострочник на Перле:
                                perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number]
                                  0
                                  Чисто искусство, столкнувшееся с ограниченностью мира :)
                                    0
                                    К сожалению, прим. пер. про решето Эратосфена неверно.

                                    Only users with full accounts can post comments. Log in, please.