арифметика

← →
картман © (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 две таких,

Я так понимаю, у вас не матрицы - а просто двумерные массивы. Матричное умножение не используется. Лучше так и писать, а то народ вон про обусловленности и сокращение операций при умножении строки на столбцы пишет.

> Думкин_ (02.09.12 04:49) [21]

и то, и то, выше я указывал:

> картман © (01.09.12 17:50) [6]

> в цикле есть перемножение матриц и перемножение и деление
> массивов(элемент на элемент).

← →
Думкин_ (2012-09-02 06:12) [23]

Если тебе требуется повысить производительность, т.е. ты не просто теоретический вопрос задал, то ускорить можно через SSE или например взяв за базу вот эту библиотеку: http://software.intel.com/en-us/intel-mkl

> картман
> при каждой итерации делитель меняется

совершенно очевидно, делитель меняется таким изощренным образом, что просто ничего невозможно сделать

← →
han_malign (2012-09-03 17:24) [26]

> получить из матрицы MxN две таких, что при их перемножении получается исходная

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

> как уравнения пишутся надеюсь рассказывать не надо...

А есть уравнения для нахождения обратной?

← →
han_malign (2012-09-03 18:18) [28]

> А есть уравнения для нахождения обратной?

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

> А есть уравнения для нахождения обратной?

Есть. Только вам нужно псевдо обращение так как матрицы не квадратные.

Алгоритмы псевдо обращения матрицы:

Метод Мура-Пенроуза для матриц с полным рангом

Метод Эрмита

Псевдо обращение на основе SVD

Метод Гревилля

Метод Бен-Израэля

арифметика Найти похожие ветки