Форум: "Прочее";
Текущий архив: 2013.03.22;
Скачать: [xml.tar.bz2];
Внизарифметика Найти похожие ветки
← →
картман © (2012-09-01 16:11) [0]x, y, z: double;
1)
x = 0.1;
y = 0.2;
for i = 1 to 10000000
z = x * y;
2)
x = 0.2353245356;
y = 0.948376598359395;
for i = 1 to 10000000
z = x * y;
с одинаковой скоростью выполнится?
← →
brother © (2012-09-01 16:15) [1]имхо нет, разрядов разное количество...
← →
Anatoly Podgoretsky © (2012-09-01 16:44) [2]> brother (01.09.2012 16:15:01) [1]
Разрядов одинаковое количестве, все типы double
Или ты думаешь, что
1+ 1 выполнится в миллион раз быстрее, чем 1000000+1000000
← →
Inovet © (2012-09-01 17:04) [3]> [2] Anatoly Podgoretsky © (01.09.12 16:44)
> > brother (01.09.2012 16:15:01) [1]
>
> Разрядов одинаковое количестве, все типы double
> Или ты думаешь, что
> 1+ 1 выполнится в миллион раз быстрее, чем 1000000+1000000
Возиожно об ускоренном завершении умножения, но сейчас оно полностью аппаратно за 1 так выполняется.
← →
brother © (2012-09-01 17:06) [4]> 1+ 1 выполнится в миллион раз быстрее, чем 1000000+1000000
нет
← →
brother © (2012-09-01 17:36) [5]> с одинаковой скоростью выполнится?
что показали тесты?
← →
картман © (2012-09-01 17:50) [6]умножение одинаково, а деление дробей, которые можно выразить конечными в двоичной системе(в [0] я ошибся: х=0.5, у=0.25) раза в три быстрей бесконечных.
Вопрос отсюда: в цикле есть перемножение матриц и перемножение и деление массивов(элемент на элемент). Скорость вычислений постепенно замедляется(с отрицательным ускорением) - на глаз, раз в 5-7. Память выделяется один раз, утечек нет. Единственное, что приходит в голову - разные числа вычисляются с разной скоростью - в начале цикла матрицы содержат либо целые числа, либо много кратных степени двойки - вот только значения матриц поменяются на совсем другие уже после первой итерации(а вот в этом не уверен - под рукой кода нет, проверить не могу).
← →
Sha © (2012-09-01 18:56) [7]А ты не дели, умножай.
И формулы подлиннее.
И зависимостей поменьше, пачками.
И если размеры приличные, то кусками.
← →
картман © (2012-09-01 19:01) [8]
> А ты не дели, умножай.
как?
← →
Sha © (2012-09-01 19:03) [9]на обратный
← →
картман © (2012-09-01 19:30) [10]где его взять-то, обратный?
← →
Sha © (2012-09-01 19:39) [11]вычислить: 1/x
общая идея - уменьшить количество операций деления:
вместо 100 операций a[i]/x, сначала вычисляем y:=1/x; а потом 100 раз a[i]*y
вместо a/b/c/d вычисляем a/(b*c*d)
← →
картман © (2012-09-01 19:42) [12]увы, не получится:
c[i][j] = a[i][j]/b[i][j];
на каждой итерации a и b меняются
← →
Jeer © (2012-09-01 19:43) [13]
> Sha © (01.09.12 19:39) [11]
>
> вычислить: 1/x
>
Народ давно не в теме оптимизации алгоритмов :(
← →
Sha © (2012-09-01 19:50) [14]> на каждой итерации a и b меняются
1. но ведь b[i,j] не сами родились, ты же их вычислил раньше - вот и надо было там вычислять не x, а 1/x
2. а что, размеры какие-то невероятно большие?
← →
картман © (2012-09-01 20:36) [15]уже забыл, как они в точности рождаются, но, думаю, все равно тож на тож выйдет
максимальный размер примерно 5000х100000
← →
Pavia © (2012-09-01 23:50) [16]Если хотите ускорить, то распишите задачу целиком.
Если деление целочисленное. То его скорость зависит от размера числа.
> максимальный размер примерно 5000х100000
При такой размерности обусловленность матрицы страдает.
← →
картман © (2012-09-02 01:12) [17]
> Pavia © (01.09.12 23:50) [16]
>
> Если хотите ускорить, то распишите задачу целиком.
неотрицательная матричная факторизация
> При такой размерности обусловленность матрицы страдает.
с этим ничего сделать нельзя, по крайней мере я не представляю что, да и хрен с ней - результат более-менее устраивает
← →
Sha © (2012-09-02 02:37) [18]> картман © (01.09.12 20:36) [15]
> уже забыл, как они в точности рождаются,
> но, думаю, все равно тож на тож выйдет
Не факт:
1. Если деление поэлементное и повторяется в цикле для K изменений матрицы,
то достаточно одного инвертирования в начале работы и мы сэкономим
K-1 деление.
2. Если элемент=строка*столбец, то деление на один и тот же элемент
повторится в цикле N раз; и инвертирование сэкономит нам как минимум
N-1 деление.
← →
Sha © (2012-09-02 02:41) [19]В итоге можешь выиграть почти порядок, т.к. экономия будет на каждом элементе.
← →
картман © (2012-09-02 03:38) [20]
> Sha © (02.09.12 02:37) [18]
> 1. Если деление поэлементное и повторяется в цикле для K
> изменений матрицы,
спасибо, но нет, при каждой итерации делитель меняется. Общий смысл алгоритма - получить из матрицы MxN две таких, что при их перемножении получается исходная, вот итеративно подгоняются элементы двух искомых
← →
Думкин_ (2012-09-02 04:49) [21]> получить из матрицы MxN две таких,
Я так понимаю, у вас не матрицы - а просто двумерные массивы. Матричное умножение не используется. Лучше так и писать, а то народ вон про обусловленности и сокращение операций при умножении строки на столбцы пишет.
← →
картман © (2012-09-02 05:50) [22]
> Думкин_ (02.09.12 04:49) [21]
и то, и то, выше я указывал:
> картман © (01.09.12 17:50) [6]
> в цикле есть перемножение матриц и перемножение и деление
> массивов(элемент на элемент).
← →
Думкин_ (2012-09-02 06:12) [23]> картман © (02.09.12 05:50) [22]
Да, заметил уже.
← →
Rouse_ © (2012-09-02 12:40) [24]Если тебе требуется повысить производительность, т.е. ты не просто теоретический вопрос задал, то ускорить можно через SSE или например взяв за базу вот эту библиотеку: http://software.intel.com/en-us/intel-mkl
← →
Sha © (2012-09-02 13:02) [25]> картман
> при каждой итерации делитель меняется
совершенно очевидно, делитель меняется таким изощренным образом, что просто ничего невозможно сделать
← →
han_malign (2012-09-03 17:24) [26]
> получить из матрицы MxN две таких, что при их перемножении получается исходная
- эээ - берешь произвольную матрицу подходящую по оптимизационному условию, находишь обратную...
как уравнения пишутся надеюсь рассказывать не надо...
← →
Дмитрий С © (2012-09-03 17:55) [27]
> как уравнения пишутся надеюсь рассказывать не надо...
А есть уравнения для нахождения обратной?
← →
han_malign (2012-09-03 18:18) [28]
> А есть уравнения для нахождения обратной?
- для нахождения искомых, имея исходную, произвольную и обратную...
Для обратной тоже, как ни странно, есть - с участием единичной. Другое дело что вычисление чуток посложнее будет.
← →
Pavia © (2012-09-03 19:26) [29]
> А есть уравнения для нахождения обратной?
Есть. Только вам нужно псевдо обращение так как матрицы не квадратные.
Алгоритмы псевдо обращения матрицы:
Метод Мура-Пенроуза для матриц с полным рангом
Метод Эрмита
Псевдо обращение на основе SVD
Метод Гревилля
Метод Бен-Израэля
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2013.03.22;
Скачать: [xml.tar.bz2];
Память: 0.52 MB
Время: 0.07 c