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

[ROD]

Да ладно придираться, обычную винду не видели?

Какая из них "обычная" (это все официальные варианты Икспишки)?

Windows XP Professional Edition
Windows XP Home Edition
Windows XP Tablet PC Edition
Windows XP Media Center Edition
Windows XP Embedded
Windows Embedded for Point of Service
Windows XP Professional x64 Edition
Windows XP 64-bit Edition
Windows XP Edition N
Windows XP Starter Edition
Windows Fundamentals for Legacy PCs

[Zealint]

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

Какая из них "обычная" (это все официальные варианты Икспишки)?

Товарищи, вам делать нечего? Я буду тестировать на
Microsoft Windows XP Professional Версия 5.1.2600 (WinXP RTM) Multiprocessor Free (32-bit) Service Pack 3, однако это не означает, что вам нужно писать именно под эту систему. Главное, чтобы под этой работало.

[LeBron]

Может, после области сяду свои силы попробую, а то там писанины много, а у меня исходника готового нету, есть только близкие к лобовым реализации.
Только не понятно, зачем такие ограничения временные?
1 минуты должно хватать "с запасом".

[Zealint]

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

Только не понятно, зачем такие ограничения временные? 1 минуты должно хватать "с запасом".

Да, должно. Я уже отвечал на этот вопрос: специально сделал запас, чтобы было, с чего начинать. Решение в лоб без единой оптимизации работает именно столько. Дальше я жду, что хоть кто-то сможет написать что-то более стоящее : ) Даже решение в лоб может быть доведено до 3 минут, мне в соседнем форуме показали. Один даже уже предложил реализацию за 30 секунд работающую, но сейчас переписывает, чтобы для всех n работало. Я так полагаю, он и победит... если допишет. Еще человек пять мне тоже что-то пишут, но пока не видно... И нормально, конкурс идет всего чуть больше суток.

[akasex]

The Algorithm

[Zealint]

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

The Algorithm

Товарищи, я надеюсь, что вы прекрасно понимаете разницу между теоретически эффективным алгоритмом и практически эффективным при указанных ограничениях. Тов. akasex, если вы этот алгоритм реализуете так, чтобы он еще и обогнал реализацию "в лоб" (на таких небольших матрицах), то это будет прорыв в области эффективной реализации алгоритмов.

[Levsha100]

Хрюша не полностью поддерживает много процессорные компьютеры.
Для любителей оптимизации: делайте цикл нисходящим.

[akasex]

спасибо за предложение, но у меня есть чем заняться...

[LeBron]

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

Товарищи, я надеюсь, что вы прекрасно понимаете разницу между теоретически эффективным алгоритмом и практически эффективным при указанных ограничениях. Тов. akasex, если вы этот алгоритм реализуете так, чтобы он еще и обогнал реализацию "в лоб" (на таких небольших матрицах), то это будет прорыв в области эффективной реализации алгоритмов.

5000*5000 - не совсем маленькая матрица. Для Штрассена с более-менее прямой реализацией выиграш уже должен быть заметным, я молчу об Винограде. У Винограда и асимптотика значительно лучше, и константа не такая большая, чтоб можно было говорить, что на 5000*5000 он хуже лобовика.

[akasex]

к сожалению Виноград здесь не поможет.....матрица слишком мала для него...а вот Штрассен (для нашей матрицы это будет матрица 2^13) должен обойти лобовой метод по-любому....