значит так, есть у нас в университете такой предмет "Параллельные алгоритмы".
на зачет программа:
"Реализуйте линейный конгруэнтный генератор псевдослучайных чисел, распараллелив его на два процессора методом блочного разбиения. В качестве модуля генератора m сгенерируйте простое трехзначное число. На базе полученного генератора псевдослучайных чисел реализуйте поточное шифрование, путем побитового «ИСКЛЮЧАЮЩЕГО ИЛИ» псевдослучайной последовательности с исходным текстом. Процесс шифрования также необходимо распараллелить на два процессора."

главная "оценка" программы состоит в оценке времени её работы на 1-м и 2-х процессорах соответственно. (Нужно показать что на 2-х как-никак быстрее)

ну закодил вот я (fasm):


в общем запускаю я её с аргументами "1" или "2".
программа правильно определяет ск-ка потоков надо запустить (0 или 1 соответственно), запускает и считает случайные числа и даже шифрует/дешифрует правильно

но одна проблема: никакого прироста в скорости при запуске на 2-х потоках не ощущается, даже наоброт.
даже не знаю что делать   
ка бы так её изменить чтобы и задачу она выполняла правильно и время работы на 2-х было бы хотя на чуток больше чем на 1-м. 

Как вариант написать на Си и проверить, если время будет попробую реализовать

Основное время уходит на обращение к памяти и винту(чем больше обращений, тем медленнее работает ессно), поэтому распараллеливание здесь до фени. 

это я понимаю, задача не в этом, именно распарралелить генератор, и засечь именно это время.
на си - не вариант.

передумал

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

Если проц одноядерный и без HyperThreaing, то два потока скорее всего будут работать медленнее. Потестируй на двухядерном компе.

собственно и тестировал на 2-х ядерном, главна проблема - нахождение зерна для 2-го потока.

формула вот такая U(n) = a^n * U(0) + c*(a^n - 1)/(a - 1) mod M

M = 2^32;

вычисление степени  a^n я сделал "эффктивно", осталась проблема с (a^n - 1)/(a - 1) mod M, как по мне именно это вычисление занимает меного времени

Это сообщение отредактировал(а) turbanoff - 2.6.2009, 20:45

mod M тоже можно сделать эффективно - с помощью сдвигов, если M - степень двойки

Не болтайте ерундой! если M - степень двойки, то x mod M = x AND (M-1) и где здесь сдвиги?  

точно, чё-то я ещё не проснулся. Хотя сдвигами тоже можно было сделать, но наверно немного менее эффективно:
x mod (2^y) = (x << y) >> y;

А вообще если программа 32-битная, то надо ещё посмотреть, есть ли там вообще смысл вычислять остаток от деления на 2^32.

Наверное, если x 32-разрядное, тогда x mod (2^y) = (x << (32-y)) >> (32-y)   

проблема не в вычислении модулю, а в нахождении
(a^n - 1)/(a - 1) mod M

если пользоваться формулой, которую я использовал

(a^n - 1)/(a - 1)  = a^0 + a^1 + a^2 + ... + a^(n-2) + a^(n-1)

то прироста скорости по сравнению с обычный линейным конгруэнтным генератором почти нет - теже самые N шагов

Это сообщение отредактировал(а) turbanoff - 7.6.2009, 13:08

turbanoff, 
"Реализуйте линейный конгруэнтный генератор псевдослучайных чисел, распараллелив его на два процессора методом блочного разбиения. В качестве модуля генератора m сгенерируйте простое трехзначное число. На базе полученного генератора псевдослучайных чисел реализуйте поточное шифрование, путем побитового «ИСКЛЮЧАЮЩЕГО ИЛИ» псевдослучайной последовательности с исходным текстом. Процесс шифрования также необходимо распараллелить на два процессора."

"проблема не в вычислении модулю, а в нахождении: (a^n - 1)/(a - 1) mod M"

"нашел обсуждение этого вопроса и решение в книжке: "Алгоритмические трюки для программистов" Генри Уоррен
PS. всем советую"