Здравствуйте, Хабрадруг.
Предлагаю принять участие в соревновании по решению целочисленных СНЛ на скорость.
Сразу хочу предупредить, что конкурс любительский и призов не предусмотрено, поэтому приглашаются те, кому такой конкурс интересен и у кого есть для него свободное время.
Конкурс может быть полезен с той точки зрения, что мало кто умеет достаточно эффективно решать такого рода задачи.
Продолжаю проводить любительские соревнования по спортивному программированию.
Прошедшие соревнования Многим оно понравилось и я даже пообещал, что следующий будет по параллельным вычислениям, но по техническим причинам я вынужден отложить такое соревнование на неопределенный срок.
Год назад я предложил задачу на умножение матриц на скорость.
Результаты оказались весьма интересными: мы добились ускорения более чем в 100 раз.
Теперь предлагается еще одна задача линейной алгебры – решение целочисленной системы линейных уравнений Ax=b. Матрица A и вектор b состоят из целых чисел, которые умещаются в 32 бита со знаком (от -2 31 до 2 31 -1).
Ответом на эту задачу является рациональный вектор x. Поскольку числитель и знаменатель ответа могут быть очень длинными, Нет Запрещено использовать библиотеки с длинной арифметикой.
Предполагается, что максимальный размер системы составит n=200. Но если один из участников напишет слишком быструю программу, этот лимит будет увеличен.
Дело в том, что обычный метод Гаусса в целых числах, написанный в лоб, с такими ограничениями на случайную матрицу работает около 10 минут. Конечно, можно написать быстрее.
Кому интересно, посмотрите пожалуйста подробности конкурса .
К сожалению, я продолжаю проводить соревнования один, поэтому для участников существуют серьезные ограничения.
У меня есть возможность тестировать программы только под Windows 7 (32 бит), поэтому я могу либо присылать EXE-файлы, либо исходники CPP, которые будут скомпилированы на рабочей машине (в этом случае доступна только библиотека MPIR).
У меня нет другого способа провести соревнование.
Однако аналогичное ограничение на конкурсе по умножению матриц участников не остановило.
Хорошим результатом конкурса я считаю реализацию за 5-10 секунд.
Почему это необходимо?
В процессе поиска информации о точном решении целочисленных систем я обнаружил, что мало кто знает, как решить такую задачу.Я сам не являюсь экспертом в этой области, но в своих исследованиях столкнулся с целочисленными SLN, которые нужно решать очень быстро.
Это соревнование может помочь нам понять, какого прогресса можно добиться в скорости решения целочисленных систем и чего вообще можно ожидать в этом случае.
Победитель конкурса сможет поделиться своим опытом, написав отдельную статью, которая будет очень полезна людям, работающим в области вычислительной линейной алгебры.
В Рунете найти статьи подобного рода не удалось, поэтому предлагается восполнить этот пробел.
Если выяснится (после завершения конкурса), что мои методы быстрее методов участников, то я сам напишу такую статью.
До конца конкурса я не буду в него вмешиваться.
Конечно, я не ищу для себя сугубо личной выгоды и не собираюсь воровать чужой код и использовать его в своих целях.
Я провожу соревнования уже не в первый раз, и, кажется, пока никто не жаловался.
Поэтому у тех, у кого есть комплексы по этому поводу, комплексов может и не быть :) Удачи! Теги: #соревнования #Система линейных уравнений #решение системы уравнений #программирование #спортивное программирование #целочисленная система уравнений #СЛУ #ЦЛУ #спортивное программирование
-
Магический Квадрат
19 Oct, 24 -
Слова На Бумаге
19 Oct, 24
