C # Mersenne Twister реализация генератора случайных целых чисел (SFMT) моделирование Монте-Карло

До сих пор я использовал C # Mersenne Twister, найденный здесь, для генерации случайных чисел:

http://www.centerspace.net/resources.php

Я только что обнаружил SFMT, который должен быть в два раза быстрее здесь:

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/

Может ли кто-нибудь указать мне на реализацию SFMT на C #?

Мои требования - создать целое число от 0 до 2 ^ 20 (включительно) (1048576).

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

В настоящее время я настроил Center Space Mersenne Twister, добавив новый метод в соответствии с моими требованиями:

public uint Next20()
{            
    return (uint)(genrand_int32() >> 12);
}

Используя метод genrand_int32(), я хотел бы создать свою собственную версию genrand_int20(), которая генерирует целое число от 0 до 2 ^ 20 (включительно), чтобы сэкономить на приведенном выше приведении и сдвиге, но я не разбираться в математике. Как я могу это сделать?

Кроме того, будет ли использование uint быстрее, чем int, или это просто вопрос адресных чисел? Поскольку мне нужно только до 1048576, меня интересует только скорость.

Также это будет работать в системе Windows Server 2003 R2 SP2 (32-разрядная версия) с .NET 2. Процессор AMD Opteron 275 (4 ядра).


person m3ntat    schedule 22.07.2009    source источник
comment
20-битное число будет представлять диапазон от 0 до 2 ^ 20-1 включительно, 2 ^ 20 требует 21 бит для представления (1 с 20 нулями)   -  person Patrick McDonald    schedule 22.07.2009
comment
Nifle: не путайте период генератора (который является длиной последовательности) с интервалом, в котором вам нужны случайные числа.   -  person Joey    schedule 22.07.2009
comment
@Patrick спасибо, что вы правы 2 ^ 20-1 - это то, что мне нужно, мне нужно случайным образом индексировать в массив длиной 2 ^ 20.   -  person m3ntat    schedule 22.07.2009
comment
@Nifle да, я знаю, я спросил, может ли кто-нибудь указать мне на реализацию SFMT на C #.   -  person m3ntat    schedule 22.07.2009


Ответы (5)


Что вы можете сделать, так это загрузить исходный код по обнаруженной вами ссылке на Code Project. Разархивируйте его, загрузите решение в Visual Studio и скомпилируйте его. Это даст вам исходный код, неуправляемую dll c и файл .lib.

Вы можете P / Invoke функции в этой dll (экспортируется только 5 простых функций, из которых вам нужны только две), или вы можете использовать эту dll, lib и файл заголовка SFMT для создания управляемой dll-оболочки, которую вы можете использовать в C # без P / Invoke. Я просто попробовал этот метод, и это оказалось очень просто. Явной сортировки не было.

Вот как. После того, как вы загрузили и скомпилировали исходный код (вам понадобится заголовок и файл библиотеки, который создается в дополнение к dll), создайте новый проект библиотеки классов C ++ CLR. Назовите это WrapSFMT или что-то в этом роде. Зайдите в свойства проекта. В разделе «C ++ / Предварительно скомпилированные заголовки» измените значение на «Не использовать предварительно скомпилированные заголовки». В Linker / General / Additional Library Directories введите путь к SFMT.lib. В Linker / Input / Additional Dependencies добавьте SFMT.lib. Закройте страницы свойств. Скопируйте SFMT.h в папку вашего проекта и включите его в проект.

Отредактируйте WrapSFMT.h следующим образом:

#pragma once
#include "SFMT.H"

using namespace System;

namespace WrapSFMT {

public ref class SRandom
{
public:SRandom(UInt32);
public:UInt32 Rand32(void);
};
}

Они объявляют методы, которые будут в вашем классе. Теперь отредактируйте WrapSFMT.cpp, чтобы он читался:

#include "WrapSFMT.h"

namespace WrapSFMT {

SRandom::SRandom(UInt32 seed)
{
    init_gen_rand(seed);
}

UInt32 SRandom::Rand32()
{
    return gen_rand32();
}
}

Они реализуют методы, которые вы объявили в файле заголовка. Все, что вы делаете, это вызываете функции из SFMT.dll, а C ++ / CLI автоматически обрабатывает преобразование из неуправляемого в управляемое. Теперь у вас должна быть возможность собрать WrapSFMT.dll и сослаться на него в своем проекте C #. Убедитесь, что SFMT.dll находится в пути, и у вас не должно возникнуть проблем.

person R Ubben    schedule 22.07.2009
comment
Я загрузил его библиотеки DLL и попытался добавить их в качестве ссылки в свой проект C #, который я получил: --------------------------- Microsoft Visual Studio - ------------------------- Не удалось добавить ссылку на 'SFMTc.dll'. Убедитесь, что файл доступен и является допустимой сборкой или компонентом COM. --------------------------- В ПОРЯДКЕ ---------------------- ----- Любые идеи? о том, как использовать это и вызывать его наиболее эффективным способом из Visual Studio - person m3ntat; 23.07.2009
comment
Хорошо, я поместил DLL в свою папку bin и получил код: [DllImport (SFMTc.dll)] static extern UInt32 gen_rand32 (); Этот вызов без ошибок, но все, что я получаю, - это 0, и никогда не было другого номера. - person m3ntat; 23.07.2009
comment
Если вы хотите использовать P / Invoke, вам нужно будет вызвать две функции, init_gen_rand (UInt32), инициализировать генератор семенем, а затем вы можете вызывать gen_rand32 () сколько угодно. (но вы, вероятно, не должны превышать период Мерсенна Твистера) - person R Ubben; 23.07.2009
comment
К вашему первому комментарию, если вы хотите ссылаться на dll в своем проекте C # и избегать P / Invoke, вам нужно будет создать dll-оболочку с C ++ / CLI и ссылаться на нее. Это не сложно. Я отредактирую ответ, чтобы показать вам, как это сделать. - person R Ubben; 23.07.2009
comment
Потрясающий @R Ubben именно то, что я ищу, я сейчас пробую маршрут DllImport, который, вероятно, будет быстрее? И как мне лучше всего засеять это? а как засеять многопоточный код? или я мог бы просто init_gen_rand один раз на всю жизнь программы, прежде чем запускать потоки, тогда каждый независимый поток может вызывать gen_rand32 () при условии, что вызов gen_rand32 () является потокобезопасным? иначе я не вижу, как разделить это и эффективно дать каждому потоку собственный генератор случайных чисел, чтобы они были независимыми? - person m3ntat; 23.07.2009
comment
Хм, я протестировал это с помощью DLLImport SFMT, и он примерно в два раза медленнее, чем мой c # MT, мне интересно, будет ли версия C ++ / CLI намного быстрее. - person m3ntat; 23.07.2009
comment
Я думаю, что в качестве начального числа большинство людей используют что-то вроде System.Environment.TickCount или System.DateTime.Now.Ticks - просто помните, что инициализация с тем же номером даст вам ту же последовательность случайных чисел. Лучшее семя будет исходить от RNGCryptoServiceProvider, подробности см. В MSDN. Что касается потоковой передачи, почему бы не дать каждому потоку собственный генератор случайных чисел? Просто убедитесь, что они получают разные семена. - person R Ubben; 23.07.2009
comment
Я не тестировал библиотеку SFMT dll, но, возможно, ваша машина не поддерживает SSE2, что и использует эта dll. Посмотрите статью в Википедии о SSE2. - person R Ubben; 23.07.2009

Вы можете найти реализацию SFMT на C # (плюс другие алгоритмы ГСЧ) по адресу ... http://rei.to/random.html Комментарии к странице и исходному коду написаны на японском языке, но вы должны уметь это понять.

Вы также можете найти переведенную Google (на английский) версию страницы по адресу ... http://translate.google.com/translate?hl=ru&sl=ja&u=http://rei.to.

person QZ1    schedule 24.03.2011

Я действительно не вижу здесь вашей проблемы со скоростью. На моей машине (Core 2 Duo T7200 @ 2 ГГц) генерация случайного целого числа с помощью MT19937 или MT19937-64 занимает около 20 нс (в среднем при отрисовке 50000 чисел). Таким образом, это будет около 4,32 × 10 12 (то есть около 4 триллионов чисел) в день. И это для одного ядра. С Java. Так что я думаю, вы можете ожидать, что производительность будет более чем адекватной вашим потребностям.

Чтобы ответить на ваш вопрос: я не знаю реализации SFMT на C #, но преобразование кода C в C # должно быть довольно простым. Однако вы не получите многого, поскольку SFMT оптимизирован для SIMD, а C # в настоящее время не поддерживает это напрямую.

person Joey    schedule 22.07.2009
comment
Я рассчитал ежедневные требования к случайным числам для этого моделирования, чтобы поддержать бизнес на уровне 1 645 668 000 000. Симуляция выполняет множество других функций, в основном матричное умножение, поэтому я не могу посвятить все время процессора генерации случайных чисел, очевидно, я хочу минимизировать каждое генерирование случайных чисел в максимально возможной степени, отсюда вопрос о Stackoverflow. - person m3ntat; 22.07.2009
comment
Что ж, у вас все еще есть несколько ядер, и симуляции Монте-Карло, как правило, довольно распараллеливаемы. Я бы сказал, что вы должны сначала решить вашу проблему и пересмотреть отдельные части решения, если они окажутся проблемой производительности. - person Joey; 22.07.2009
comment
Что касается SFMT, я не понимал, что, возможно, мой лучший подход - это попробовать скомпилировать версию c здесь: math.sci.hiroshima-u.ac.jp/~m-mat/bin/dl /, а затем как-нибудь использовать его из моей симуляции C # monte carlo. Я не знаком с c / c ++, как компилировать их src и как использовать его из C #. - person m3ntat; 22.07.2009
comment
Спасибо @Johannes, моя реализация может использовать 3 ядра (из 4 на коробке), так что да, это будет параллельная реализация даже тогда (с трехкратной победой), я приближаюсь к достижению 24-часового суточного лимита времени выполнения в приложение. Я отправил запрос на более новый сервер, больше процессора и т. Д., Но скорость работы этого банка очень медленная, и меня попросили оптимизировать сейчас. - person m3ntat; 22.07.2009
comment
Похоже, вы могли бы использовать хороший пример правила оптимизации Quake. - person FryGuy; 22.07.2009
comment
Если вы планируете использовать несколько ядер, имейте в виду, что строки кэша могут испортить это для вас. Взгляните на эту статью: ddj.com/go-parallel / article / - person ; 22.07.2009

Есть ли причина, по которой вы не можете скомпилировать реализацию C в DLL и вызвать ее из своего кода C #?

РЕДАКТИРОВАТЬ:

Извините, но у меня очень ограниченные знания C (и, конечно, C #), но на «Как создать C dll» можно ответить здесь: http://www.kapilik.com/2007/09/17/how-to-create-a-simple-win32-dll-using-visual-c-2005/ и насколько быстро можно проверить с помощью профилирования кода.

person Patrick McDonald    schedule 22.07.2009
comment
Привет, Патрик, я никогда не использовал c, не уверен, как это сделать? и использование из C #, я, вероятно, потеряю большую производительность из-за того, что, как я предполагаю, .net выполняет некоторую упаковку моих вызовов с C # в базовую c DLL? - person m3ntat; 22.07.2009
comment
Я предполагаю, что многократное использование P / Invoke в неуправляемом коде влечет за собой довольно большие накладные расходы на производительность. - person Joey; 22.07.2009
comment
Я только что обнаружил это: codeproject.com/KB/DLL/SFMT_dll.aspx ? msg = 3130186 мне интересно, может ли это оказаться полезным в моей ситуации - person m3ntat; 22.07.2009
comment
Я также заметил реализацию F # внизу здесь en.wikipedia.org/wiki/Mersenne_twister нет идея, как использовать F #, но, возможно, стоит изучить и протестировать. - person m3ntat; 22.07.2009
comment
Что ж, и F #, и C # нацелены на CLR, и я ожидал, что код F # будет на самом деле медленнее, чем C #. Однако вы всегда можете посмотреть сгенерированный код с помощью Reflector. - person Joey; 22.07.2009

Возможно, это это то, что вы ищете? Есть список из нескольких реализаций.

В частности, этот (автор Кори Нельсон) может оказаться полезным.

person Francisco    schedule 22.07.2009