Быстрый Perl 6
Я написал для пробы компилятор Perl 6, способный распарсить и скомпилировать простую программу, которая проверяет, является ли переданное число простым или нет.
Простое число — положительное целое число, большее единицы, которое без остатка делится только на единицу и самого себя. Алгоритм, реализованный в программе — намеренно неэффективен: делается простой перебор чисел до тех пор, пока либо не найдется делитель, либо не будет достигнуто само число.
say is_prime(@*ARGS[0]);
sub is_prime($n) { for 2 .. $n - 1 -> $d { return 0 unless $n % $d; }
return 1; }
Не существует формулы, по которой можно было бы сразу определить, простое ли это число, однако есть несколько способов упростить поиски. Очевидное предположение — число должно оканчиваться на 1, 3, 7 или 9 (во всех остальных случаях оно делится на 2 или 5). Кроме того, нет смысла подбирать делители, превышающие sqrt(n). И, наконец, известно, что любое простое число удовлетворяет соотношению n = 6k ± 1. Здесь эти факты никак не используется чтобы заставить программу работать как можно дольше.
Если выполнить код под Rakudo, то уже на пятизначном числе (15511, например) время выполнения превышает 20 секунд, даже если предварительно оттранслировать код на Perl 6 в PIR. Компилятор, который я попробовал написать, дает исполнимый файл, находящий ответ для того же числа за 2 миллисекунды. На странице perl6.ru/p6c находится веб-интерфейс к скомпилированной программе.
О том, как это устроено работает, я расскажу в ближайшее время на блиц-докладе сначала на Хайлоаде++ 12 октября, а затем на итальянском Perl-воркшопе в Пизе 22 октября.