Напишите программу сборки GOLF, которая читает целое число из стандартного ввода (за которым следует завершающий символ новой строки), и выводит его простые множители, разделенные символами новой строки, после чего следует конечный символ новой строки в стандартном выводе.
Главные факторы не должны быть в определенном порядке. 1
это не главный фактор.
Ваш двоичный файл GOLF (после сборки) должен умещаться в 8192 байта.
Ваша программа будет оценена, запустив ее 10 раз, каждый с одним из следующих входов:
8831269065180497
2843901546547359024
6111061272747645669
11554045868611683619
6764921230558061729
16870180535862877896
3778974635503891117
204667546124958269
16927447722109721827
9929766466606501253
Эти цифры примерно отсортированы по сложности. Первый должен легко решаться методом пробного деления.
Оптимизация в отношении этого набора чисел противоречит духу вопроса, я могу изменить набор чисел в любой момент. Ваша программа должна работать с любым положительным 64-битным входным числом, а не только с этим.
Ваша оценка - это сумма циклов ЦП, использованных для расчета приведенных выше чисел.
Поскольку GOLF очень новый, я включу несколько указателей здесь. Вы должны прочитать в ГОЛЬФ спецификацию со всеми инструкциями и расходов цикла . В репозитории Github можно найти примеры программ. В частности, посмотрите на пример программы-факториала , которая демонстрирует ввод / вывод.
Скомпилируйте вашу программу в двоичный файл, запустив python3 assemble.py your_source.golf
. Затем запустите вашу программу с помощью python3 golf.py your_source.bin
, это должно также напечатать счетчик циклов. Смотрите значения содержимого регистра при выходе из программы с -d
флагом - используйте, --help
чтобы увидеть все флаги.
1
это не главный фактор, должен ли он печатать только целое число ввода?Ответы:
2 279 635 циклов - 7373 байта (детерминированные)
По одному:
Резюме:
Я использую комбинацию пробного деления и алгоритма Брента-Полларда для разложения на множители и поиска в таблице, а также Миллера-Рабина для проверки первичности. Я добавлю еще несколько объяснений завтра.
Обратите внимание, что из-за ограничения на длину сообщения длина второй таблицы данных усекается. Эта суть включает в себя полную таблицу.
источник
mov o, 42
.Всего 36 757 269 913 циклов
830B в сборе
Факторизация по пробному разделению с несколькими оптимизациями. Вероятно, не самый быстрый, но, поскольку еще никто не опубликовал, я начну.
Полный вывод из моего цикла синхронизации, на случай, если кто-нибудь захочет проверить результаты и / или мою копию-вставку и математику.
источник
divu
: stackoverflow.com/questions/5558492/… . Что касается вашего ответа - этот вопрос не предназначался для решения с использованием пробного деления: Pfactor * factor < number
- ни у одного числа не может быть факторов больше, чем квадратный корень.оценка = 378 867 816 циклов
[рандомизировано - ваши результаты могут отличаться]
Используется критерий первичности Миллера-Рабина (детерминированная версия, которая может обрабатывать до 2 ^ 64), немного пробного факторинга и факторизации ECM . Здесь есть все алгебраические операции, включая модульное сложение, вычитание, умножение, возведение в степень и инверсию (mod n <2 ^ 64).
Модульное умножение неоптимально - оно выполняет бинарный поиск по частному. Вычислить остаток от деления 128 на 64 сложно без соответствующей встроенной инструкции. Ускорьте это, и все пойдет быстрее.
Составлено 2290 байт
Выход:
источник