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

до

матрицы перебераю следующим образом.
В цикде от 0 до максимального значения определенной размерности матрицы (в случае размерности 4 - это 65535), каждое число инвертирую в бинарную матрицу следующим образом:

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

а в каких пределах изменяется размерность матрицы ?
пояснение: показанная выше бинарная матрица может  быть представлена обычным 16ти битным числом,
и тогда перебор всех матриц будет заключаться в циклическом инкрементировании такой переменной.



Это сообщение отредактировал(а) mes - 5.6.2009, 21:19

эм, размерность..., Вообще несмотря на то что сделано для любой, но фактически только для размерности 4, потому что для размерности 8 это уже кластер нужен чтобы посчитать 2^64 матриц 

В приведённом примере вместо temp%2 нужно temp&1.
Но декорировать до битов нет необходимости.

Т.е. вычисляем целую строку за раз (вместо трёх for только два). 

ООП эт конечно хорошо, но тут оно излишне.
на счет & спс.
А вот приведеный вами код я чтото немогу понять, это ведь не перевод числа в матрицу, верно ? это умножение уже, а оно ненужно. 

Можно работать с числом напрямую, рассматривая его как матрицу.   

конечно можно если используетться или специальный алгоритм для чисел или извратиться для простого метода. Но для метода штрасена этого неполучиться.

И с чего это вдруг ?!

Добавлено через 1 минуту и 15 секунд
приведите ту часть кода, которая оперирует с готовой матрицей.

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

Это сообщение отредактировал(а) cupper - 6.6.2009, 10:10

Знаете сам алгоритм не при чем. Он использует базовые операции с матрицей. А их, в том числе и хранение матрицы, можно оптимизировать под задачу.
Но даже без оптимизации они в любом случае должны быть реализованы.

Вот в частности ваша реализация сложения бинарной развернутой (т.е каждый бит представлен числом) матрицы


не верна. Так как после такого сложения некоторые ячейки будут отличны от 0 и 1.


Добавлено через 2 минуты и 16 секунд
код кстати  (пока правда сильно не копался в нем) вызывает опасения, из за обильного использования new/delete и обилия переменных, которые вполне заменялись бы массивом.

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

В распаковке набора битов (числа) в набор чисел(массив) приведенной в Вашем примере фактически нечего оптимизировать. Все что можно (в частности замену модуля на and) там сумеет сделать сам компилятор.

Но с бинарной матрицей можно оперировать не разворачивая ее. И многие операции с упакованной матрицей могут быть быстрей, так как можно в реализации применять действие не к одному, а к набору битов.
  
    

Я и неспорю что можно, но либо для спец. алгоритмво либо для обычного переборного. В данном алгоритме помино операции * и + есть операция -, которую нельзя заменить на + (-matrix), мы пытались сначало оптимизировать этот алгоритм для бинарных матриц, но труды были бесполезны. В итоге данный алгоритм для бинарных матриц можно применять только следующим образом:
на вход поступает две бинарный матрицы, на выходе получаеться НЕ бинарная матрица, которая бинаризуеться, путем замены всех ненулевых элементов на 1. Это единственный выход который мы смогли найти (найти в интернете). 
Если вы горитите что метод перевода числа в матрицу иначе, более оптимально, никак низя сделать, то возможно так оно и должно быть.

Поскольку по крайней мере в промежуночных результатах могут быть не только 0 и 1, производить вычисления в запакованном виде нельзя.
Оптимизировать можно только убирая лишние копирования и выделения памяти.
Матрицу хранить в виде одномерного массива.
Поскольку программируешь на C++, отказываться от ООП не имеет смысла.


Добавлено через 14 минут и 10 секунд

При предложенной тобой бинаризации не будут выполняться законы:

Правильное бинаризирование матрицы - оставить отолько последнюю цифру результата.
Умножение (обычное) для таких матриц в  упакованном виде я привёл в своём первом посте - только код operator*=,  а не operator* и забыл return *this;
Кстати, тогда operator+ и operator- будут иметь один и тот же код.
 

ловите примерчик для матрицы 4х4 (для остальных аналогично), оптимальней вряд ли получится :



Это сообщение отредактировал(а) mes - 7.6.2009, 23:12