Когда-то давно меня заинтересовал вопрос решения тех или иных задач во сне. Мне показалось интересным то, что некоторые известные учёные видели идеи своих будущих открытий именно пока спали (вспомните Менделеева и его знаменитую таблицу). Не исключено, что некоторые музыканты слышали также музыку, которую потом могли перенести в реальный мир, а художники – видели картины. Каждый, кто пытался решать ту или иную задачу в своей жизни, наверняка видел сон, посвящённый этой задаче, хотя далеко не каждый при этом видел решение. И вот что меня интересует: можно ли специально заставить себя увидеть сон, в котором ваше подсознание решает поставленную задачу?

В этой статье рассказывается о том, как отыскать точное решение целочисленной системы линейных алгебраических уравнений на порядки быстрее, чем это делает метод Гаусса и любые его аналоги. Алгоритм работает для любых линейных систем с целыми числами, но требует, чтобы система имела единственное решение, то есть матрица системы должна быть невырожденной. Алгоритм использует для своей работы P-адические аппроксимации. Но для понимания его работы не обязательно знать, что это такое.

Конкурс на самое быстрое решение целочисленной системы линейных уравнений завершён. Вынужден признать, что это был самый скучный конкурс из всех, которые я проводил. Было довольно много участников, но у половины программы работали неправильно, а у остальных – слишком медленно и не укладывались в 600 с. Как минимум, предполагалось, что кто-то дойдёт то отметки в 5-10 с, но, к сожалению, этого не произошло. Значит я вынужден буду объяснить, как этого добиться. В этом посте подведём итоги, и я выскажу мои мысли по поводу данного мероприятия, а в следующем ждите подробного описания нормального метода решения поставленной задачи.

В честь дня рождения моего блога предлагаю принять участие в очередном любительском конкурсе для программистов-математиков. Я обещал в прошлый раз, что конкурс будет по параллельным вычислениям, однако по техническим причинам его придётся пока отложить на неопределённый срок. Вместо этого будет простой конкурс с простой (с точки зрения теории сложности) задачей.