Конгруэнтный метод

[hirosimarider]

Приветствую!

Задался вопросом реализации своего ГСЧ и нашел прекрасный метод предложенный Кнутом. Также нашел его реализацию для плюсов - прирост быстродействия был такой: стандартный рандом ~5.3 сек., конгруэнтный метод ~0.2 сек. (сравнение на 10000 итерациях).

Для C# нашел также реализацию этого метода, но... не только прироста нет, но и, наоборот, работает медленнее..

Может кто-то реализовывал свои более быстрые варианты рандома??

Вот код реализации конгруэнтного метода ГСЧ:

    public class Rnd
    {
        private Int64 _seed;
        public Rnd()
        {
            _seed = Int64.Parse(DateTime.Now.Ticks.ToString());
        }
        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        public Int64 Next()
        {
            const int m = 1065353216;
            const int k = 1664525;
            const int b = 1013904223;
            Math.DivRem(k * _seed + b, m, out _seed);
            return _seed;
        }
    }
}

[ds.Dante]

Int64.Parse(DateTime.Now.Ticks.ToSt ring());
А зачем ты переводишь число в строку и обратно?

Метод можно чуть оптимизировать:

        const int m = 1065353216;
        const int k = 1664525;
        const int b = 1013904223;

        public Int64 Next()
        {
            return (k * _seed + b) % m;
        }

Покажи код, где ты сравниваешь скорость рандомов.

[hirosimarider]

А зачем ты переводишь число в строку и обратно?

Ну это инициализация - она не так важна))а вообще да, скопировал не глядя)) тупость вышла...))

return (k * _seed + b) % m;

те же яйца, только в профиль ХД
проблему это не решает, ибо целочисленное деление остается и занимает 90% всего времени выполнения функции...(((

var sw = new Stopwatch();
            sw.Start();
            testSpeedRandStandart();
            sw.Stop();
            MessageBox.Show(sw.Elapsed.ToString());
            sw.Reset();
            sw.Start();
            testSpeedRand();
            sw.Stop();
            MessageBox.Show(sw.Elapsed.ToString());

       private void testSpeedRandStandart()
        {
            var rnd = new Random();
            for (var n = 0; n < 1000000; n++)
                rnd.Next();
        }
        private void testSpeedRand()
        {
            var rnd = new Rnd();
            for (var n = 0; n < 1000000; n++)
                rnd.Next();
        }

На плюсах это выглятит так:

float getRandomFast()
{
    static unsigned long iran;
    unsigned long temp;
    float fran;
    static unsigned long jflone=0x3f800000;
    static unsigned long jflmsk=0x007fffff;
    iran=1664525L*iran+1013904223L;
    temp=jflone|(jflmsk&iran);
    fran=(*(float *)&temp)-1.F;
    return fran;
}

[ds.Dante]

Может, просто стандартный рандом в плюсах такой тормозной?

Можно посмотреть, как он реализован в дотнете (исходники можно скачать NetMassDownloader-ом).

[alexBlack]

Сообщение от hirosimarider

... ибо целочисленное деление остается и занимает 90% всего времени выполнения функции...(((

Вообще-то советуют брать m = степени двойки

А код, который Вы для C++ привели отсюда взят: http://algolist.manual.ru/maths/generator/fastest.php ?
Там jflone=0x3f800000=1065353216 не то-же самое, что m в формуле конгруэнтного метода.

[hirosimarider]

Там jflone=0x3f800000=1065353216 не то-же самое

Ой, тут да, не кратно степени двойки.. поленился проверить))
ну.. даже заменив на 65536 вот такие результаты получаются:

С#
standart = 00:00:03.0421518
kongr = 00:00:02.6766811

C++(переписал немного, чтобы честнее было)
kongr = 0.383354
standart = 1.14874

Да, в плюсах рандом в 3 раза быстрее конечно...

Кстати, может знает кто, время выполнения участка замеряемого кода(привел выше) и время которое тратится на сам рандом, показываемое Intel Parallel Amplifier, очень сильно разнится. Т.е.:

	        rnd->getRandomFast();  	35.606ms
	        rand();                       	852.911ms

При том, что остальной код одинаков:

double timeStart;

	timeStart = omp_get_wtime();
	RandomGenerator* rnd = new RandomGenerator();
	rnd->initialize();
	for(int j = 0; j < 30000000; j++)
		rnd->getRandomFast();
	cout << "time     = " << omp_get_wtime() - timeStart << endl << endl;

	timeStart = omp_get_wtime();
	srand(time(NULL));
	for (int i = 0; i < 30000000; i++)
		rand();
	cout << "time     = " << omp_get_wtime() - timeStart << endl << endl;

Почему так??

[alexBlack]

Сообщение от hirosimarider

Ой, тут да, не кратно степени двойки.. поленился проверить))
ну.. даже заменив на 65536 вот такие результаты получаются:

Не торопитесь. Почему именно степень двойки и как это связано с mod ?
(это для C#)

Почему в коде C++ нет операции mod и как используется jflone.

Отвечать не нужно, просто разберитесь для себя. Иначе получается, что Вы сравниваете по времени два различных генератора и делаете неверный вывод о том, что в C++ быстрее.