Время: 2 недели (4 апреля — 18 апреля 2012 г.)
Конкурс завершён. Смотрите итоги.

Таблица участников.

После вынужденного перерыва продолжаем проводить любительские конкурсы по программированию. На этот раз конкурс связан с одним из предыдущих конкурсов, посвященных точному решению целочисленной системы уравнений. Первым шагом при использовании алгоритма, основанного на p-адических аппроксимациях, является обращение исходной матрицы по модулю простого числа P. Требуется максимально ускорить эту операцию. С этой целью и проводится конкурс. В качестве P выбрано число 231-1 (максимальное простое число, которое умещается в 32 бита со знаком).

Сразу предупреждаю, как и в конкурсе по перемножению матриц, участвуем только под Win-32.

Целочисленная матрица C назвается обратной по модулю P к целочисленной матрице A, если A⋅C≡C⋅A≡I (mod P). Гарантируется, что матрицы в тестах конкурса будут невырожденными по модулю P.

Положения

Общие правила и ограничения

  1. Операционная система — Windows 7 — 32 бит.
  2. Тестирование производится на компьютере с процессором Intel Core 2 Duo 8400 (3000 MHz) 4GB DDR2-800.
  3. Программа должна использовать не более одного процесса и одного потока в нём. Несмотря на то, что процессор двухъядерный, разрешается использовать только одно ядро на 100% его мощности.
  4. Программа должна быть представлена в виде одного только исполняемого EXE файла и работать корректно без необходимости установки дополнительного ПО.
  5. Программа должна использовать не более 2Gib (231 байт) оперативной памяти. Хотя больше выделить все равно не получится.
  6. Время работы программы на каждом тесте не должно превышать 2400 секунд (почему? — столько работает написанный в лоб метод Гаусса, в котором деление заменено на умножение на обратный по модулю P элемент). Разумеется, программа победителя будет работать куда быстрее.
  7. Максимальный порядок матрицы в тесте n = 5000.
  8. Элементы матрицы будут задаваться специальной формулой (см. ниже). Это целые числа, не превосходящие по модулю 231-1.
  9. Ответом к задаче является матрица, числа в которой находятся в диапазоне [0,231-1].
  10. Программа должна работать в консольном режиме, то есть никаких графических интерфейсов писать не нужно. Ваша программа считывает данные из входного файла (который будет находится в той же директории), генерирует матрицу, обращает её, и выводит ответ в другой файл (в ту же директорию). Подробнее о формате ввода / вывода см. ниже.
  11. Конкурс завершается 18 апреля 2012 г. ровно в 12 ч. 00 м.
  12. Я оставляю за собой право менять правила проведения конкурса, если в них обнаружатся неточности.

Порядок проведения конкурса

  1. Во время проведения конкурса участники посылают на электронный адрес «zealint.comp@gmail.com» письмо с темой «Обратная по Модулю Матрица — Конкурс». В теме необходимо указать свой ник, язык программирования и название компилятора, которым вы пользовались, укажите какими надстройками вы пользовались (boost, atlas, blas, fflas и т. д.) или вы реализовали алгоритм самостоятельно (ручная реализация). Прикрепите к письму исполняемы файл, который будет тестироваться. Файл назовите «<ваш ник>.mp3» (gmail не пропускает EXE файлы даже в сжатом виде)
  2. По мере тестирования поступающих программ, результат их работы будет указываться в таблице рейтинга, внизу этой страницы. Участник может присылать новые версии программы не более одного раза в сутки. Тестирование не быстрое, поэтому ожидание результата может затянуться.
  3. Победившим считается тот участник, программа которого оказалась самой быстрой на момент завершения конкурса.
  4. Я НЕ принимаю участия в конкурсе.

Формат входных и выходных данных

  1. Программа должна считывать данные из файла «input.txt».
  2. Программа должна записывать ответ в файл «output.txt» (и должна сама создавать его по мере необходимости).

Во входном файле содержатся 5 чисел: n, a, b, x, m. Первое число n — порядок матрицы. Остальные числа нужны для генерации матрицы. Элементы матрицы заполняются слева направо от первой строки к последней последовательностью чисел, получаемых по рекуррентной формуле

x0=x,
xk=(a⋅xk-1+b) mod m,      k>0.

То есть после считывания этих пяти чисел нужно сгенерировать в программе саму матрицу. Например, у меня в программе на Си это выглядит так:


/* Функция получения очередного числа */
int nextNumber ( ) {
  return x = int ( ( int64 ( a ) * x + b ) % m );
}
/* Заполнение матрицы слева направо, начиная от первой строки */
for ( i = 0; i < n; i ++ )   for ( j = 0; j < n; j ++ )     A [ i ] [ j ] = nextNumber ( );

После того, как матрица сгенерирована, её нужно обратить по модулю P=231-1. Полученную матрицу нужно вывести в файл «output.txt» (каждую строку матрицы в отдельной строке файла).

ПРИМЕР

Файл input.txt:
2 6 4 1 5

Это означает, что матрица имеет порядок 2.
x0=1.
x1=(6⋅1+4) mod 5 = 0,
x2=(6⋅0+4) mod 5 = 4,
x3=(6⋅4+4) mod 5 = 3,
x4=(6⋅3+4) mod 5 = 2,

Таким образом, матрица имеет вид
0 4
3 2

Обратная к ней по модулю P=231-1 будет
357913941 1431655765
536870912 0

Именно эти две строки и должны оказаться в выходном файле.

Пожелания

После окончания конкурса я, по вашему желанию, установлю ссылки с этой страницы на главные страницы вашего сайта, при условии, что вы установите ссылку со своей не главной страницы на эту. Все ссылки без noindex и nofollow. Также любой участник может поделиться своим исходным кодом, который я выложу для общего доступа вместе с моими тестами и программами всех участников.

Если Вы новый участник, то прочитайте, пожалуйста, FAQ (кроме вопросов, связанных с призами, так как их здесь не будет).

Рейтинговая таблица

Конкурс завершён.

Таблица ниже будет постоянно обновляться по мере поступления новых программ.

  1. alexBlack :: Delphi :: 14.04.12 :: 267,8 с.
  2. зщл [v3] :: g++ 4.6.2 :: 16.04.12 :: 836,0 с.
  3. Sher :: Visual C++ / Asm :: 16.04.12 :: 1001,5 с.
  4. зщл [v2] :: g++ 4.6.2 :: 15.04.12 :: 1018,7 с.
  5. Student :: Visual C++ :: 16.04.12 :: 1691,8 с.
  6. зщл [v1] :: g++ 4.5.2 :: 14.04.12 :: 1999,7 с.

Следите за конкурсами на моём блоге, дальше будет сложнее и интереснее.

Информационные спонсоры

dxdy - Научный форум.

Обсуждение конкурса на форуме в этой теме.