Конкурс - перемножение матриц

[Zealint]

Уважаемые программисты. Предлагаю принять участие в конкурсе, который проводится на моём сайте. Задача конкурса предельно простая - написать программу перемножения квадратных матриц, но она должна работать на матрицах размером до 5000x5000 и при этом укладываться в 15 минут. Победителем будет тот, чья программа работает быстрее. Конкурс бесплатный, поэтому приз всего 1000 р. Но это далеко не последний мой конкурс! Страница с правилами: http://zealint.ru/fast-matrix-multiplication-comp.html

[ds.Dante]

Полагаю, победит тот, кто владеет дополнительными наборами инструкций типа SSE. Мне это не по силам.

[VovanZ]

Возможно я поучавствую, потом.... Сейчас я пишу бота для игры Fortress, когда закончу может быть займусь этим....

[Levsha100]

Мой ассемблер не поддерживает столь большой адресации.
//Курсак или лаба?

[Zealint]

Сообщение от Levsha100

Мой ассемблер не поддерживает столь большой адресации.
//Курсак или лаба?

5000^2 * 4 = 100 000 000 - не так много вроде бы для адресации.
// Не курсак и не лаба - я даже исходников не требую. Просто конкурс - кто быстрее!

Полагаю, победит тот, кто владеет дополнительными наборами инструкций типа SSE. Мне это не по силам.

Ради Бога, можете и их использовать, я же процессор указал, на котором буду тестировать.

[mihali4]

Чепуха какая-то...
Ну, набросал я "втупую" за 2 минуты эту "задачу".
Перемножает матрицы 5000х5000 за 1-2 секунды. (Заполнение случайными числами - меньше полсекунды).
Проц 1,83 мгц, дуо...
Что-то тут нечисто, в ентом "конкурсе"...
Может, там числа с плавающей запятой ?

З.Ы. Правда, ввод-вывод в файл не делал, только вычисления...

И вообще, я так понял, что основная цель сего действа скрыта во фразах:

По мере проведения конкурса привлекайте новых участников. Мой блог не так сильно раскручен, поэтому участие хотя бы 10 человек я буду считать большим успехом.

То есть раскрутка.
А это бабла стоит. Вот товарищ и решил нашими руками раскрутиться... Есс-но, нахаляву.

[Alex Cones]

15 минут... Это ж чем надо забить программу, которая 100 кк байт перемножит...

[Zealint]

Сообщение от mihali4

Чепуха какая-то...
Ну, набросал я "втупую" за 2 минуты эту "задачу".
Перемножает матрицы 5000х5000 за 1-2 секунды. (Заполнение случайными числами - меньше полсекунды).
Проц 1,83 мгц, дуо...
Что-то тут нечисто, в ентом "конкурсе"...
Может, там числа с плавающей запятой ?

Я указал в правилах, какие там числа. 1-2 секунды??? Отлично! У вас есть шанс выиграть. На самом деле, если Ваша программа правильно работает, то это абсолютный рекорд. Я такого еще не видел и будет интересно проверить самому...

Сообщение от mihali4

То есть раскрутка.
А это бабла стоит. Вот товарищ и решил нашими руками раскрутиться... Есс-но, нахаляву.

Ну... Тов. mihali4, за эту 1000 р, я гораздо сильнее раскручу блог другими способами : ) Я вообще-то могу нахаляву получить PR4, если надо будет. Сейчас мне это просто не нужно. Тут нет подвоха, все честно. Да, я хочу, чтобы пользователи заходили, но не это цель. Мне нужны результаты именно по этой задаче и именно при тех ограничениях, которые я назвал.

Я тут подумал... Может вы перемножаете неправильно? Я имею в виду не произведения Адамара двух матриц (поэлементное), а алгебраическое произведение, которое и называется произведением матриц в стандартном курсе линейной алгебры. Кстати, в правилах есть пример, он у Вас правильно работает?

Сообщение от Alex Cones

15 минут... Это ж чем надо забить программу, которая 100 кк байт перемножит...

Это я специально захватил побольше времени, чтобы было с чего начинать. Один товарищ на соседнем форуме под Linux написал программу, которая за 3 минуты работает, но он пока не хочет под Windows делать.

[Ulex]

Меня другой вопрос интересует.
Как время будет засекаться?
И что значит нельзя пользоваться dll. И системными тоже?

Ну а вообще, я тут любопытства ради прикинул на калькуляторе (если где ошибся, поправьте)
Выходная матрица квадратная 5000*5000 элементов.
Для расчёта одного элемента вых. матрицы просто в лоб (строка на столбец) потребуется 5000 циклов умножения и сложения.
Итого, для расчёта всей матрицы потребуется таких циклов уже 5000*5000*5000=125 млрд.
Допустим, что один такой цикл будет выполняться 10 тактов проца. Тогда уже потребуется 1250*10^9 тактов машины.
Если у нас есть процессор, частотой 3ГГц, значит он (в первом приближении) выполняет 3 млрд. тактов в секунду.
Получается, что для вычисления такой матрицы потребуется ~ 7 мин.

И ещё.
А почему не сделать входные и выходные файлы бинарными? Тогда можно будет не напрягать программу разбором текстовых файлов.
А то может получиться так, что быстрее окажется не тот, кто матрицы перемножит, а тот, кто с входными/выходными файлами быстрее разберётся.
Файлы, кстати, (для матрицы 5000*5000) получаются input~2 Мбайт, output в два раза меньше.

[mihali4]

Не все так просто, уважаемый.
Вы не учли "накладные" расходы.