Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2013.03.22;
Скачать: CL | DM;

Вниз

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

 
картман ©   (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;
Скачать: CL | DM;

Наверх




Память: 0.54 MB
Время: 0.144 c
15-1350457839
pasha_golub
2012-10-17 11:10
2013.03.22
Течет память. Кто виноват и что делать?


6-1264712145
Vatokat
2010-01-28 23:55
2013.03.22
Обработка исключительных ситуаций indy в потоке


15-1335247067
99999
2012-04-24 09:57
2013.03.22
Проверить синтаксис.


1-1300622372
Gu
2011-03-20 14:59
2013.03.22
Ресурсы x64 Dll


15-1353270605
Юрий
2012-11-19 00:30
2013.03.22
С днем рождения ! 19 ноября 2012 понедельник