| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Быстрое умножение булевых матриц
D-alone © (2005-01-18 22:03:00)Необходимо перемножить большое число булевых матриц в различных последовательностях. Булева матрица - это матрица из нулей и единиц, где умножение и сложение - логические, размерность 6*6 в моем случае. Всего необходимо обсчитать 2^36 штук матриц. Сейчас моя программа умножает матрицы стандартным способом, что очень медленно (19 дней необходимо). Есть идея но не знаю как реализовать. Идея следующая: каждую матрицу закодировать десятичным числом (построчное выписывание нулей и единиц - получим битовое представление некоторого числа) - т.е. не придется генерировать матрицу, для умножения имеет смысл отдельно разбивать матрицу на строки и столбцы.
можно сделать 2 массива чисел: 1 массив - это строки - это просто число, являющееся кодом, разбитое на блоки по нескольку бит (несколько=размерности), 2 массив - столбцы.0-й бит, нный бит, 2нный бит, 3нный бит и т.д.
Теперь, в цикле, где матрицы перемножаются результат для ячейки [i,j]=строка AND столбец.
Кол-во сдвигов уменьшается с N^3 до N^2
первая (или 0-я) строка
s[0]=M AND (2^n-1)
s[1]=(M SHR n) AND (2^n-1)
s[2]=(M SHR 2n) AND (2^n-1)
и т.д.
со столбцами посложнее
их надо выделять побитово. как не знаю.
лучше бы конечно это на асме накидать, но я в нем уже почти ноль.
Помогите это все как-то нормально оформить буду очень благодарен.
palva (2005-01-18 23:34:00) [21]Предлагаю хранить матрицу следующим образом: Первые 6 байтов матрица по строкам, т. е. каждая строка в младших битах байта. Следующие 6 байтов матрица по столбцам, т. е. каждый столбец в младших битах байта. Первое представление используется, когда матрица является левым множителем, второе представление - когда правым.
При перемножении никаких сдвигов не будет. Нужно взять AND соответствующих байтов, представляющих строку левой матрицы и столбец правой и сразу после этого проверить флаг четности. Если он установлен, то элемент произведения равен 1, иначе 0. Это надо делать на ассемблере, но тут будет буквально три команды.
MBo (2005-01-18 22:14:00) [22]Определи, что означает умножение таких матриц.
Например, обычное матричное умножение A*B=C, где Cij=Sum (по к) Aik*Bkj
Что будет в твоем случае?
Приведи пример для матриц 2*2
| |
Страницы: 