views:

1177

answers:

4

So far I've been using the C# Mersenne Twister found here to generate random numbers:

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

I just discovered SFMT which is supposed to be twice as fast here:

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

Can anyone point me at a C# implementation of SFMT?

My requirements are to generate an integer between (and including) 0 and 2^20 (1048576).

I need to do this trillions of times everyday for a simulation running on a 24 hour clock so I am prepared to spend days tweaking this to perfection.

Currently I've tweaked the Center Space Mersenne Twister by adding a new method to fit my requirements:

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

Using the method genrand_int32() I'd like to produce my own version, genrand_int20(), that generates an integer between (and including) 0 and 2^20 to save on the cast above and shift but I don't understand the mathematics. Exactly how can I do this?

Also is using an uint going to be faster that int, or is just a matter of addressable numbers? Because I only need up to 1048576, I am only concerned with speed.

Also this will be running on a Windows Server 2003 R2 SP2 (32bit) box with .NET 2. Processor is AMD Opteron 275 (4 core).

A: 

I don't really see your problem with speed here. On my machine (Core 2 Duo T7200 @ 2 GHz) generating a random integer with MT19937 or MT19937-64 takes around 20 ns (on average, when drawing 50000 numbers). So that'd be around 4,32 × 1012 (so around 4 trillion numbers) a day. And that's for one core. With Java. So I think you can expect the performance to be more than adequate for your needs.

To actually answer your question: I don't know of a C# implementation of SFMT, but conversion of the C code to C# should be fairly straightforward. However, you're not gaining much, as SFMT is optimized for SIMD and C# currently doesn't support this directly.

Joey
I've calculated daily Random Number requirements for this simulation to support the business at 1,645,668,000,000. The simulation does a lot of other things mainly matrix multiplication so I can't devote all CPU time to random number generation, obviously I want to minimise each random number gen as much as possible, hence the Stackoverflow Question.
m3ntat
Well, you still have multiple cores and Monte Carlo simulations tend to be pretty parallelizable. I'd say you should first go ahead and solve your problem and revisit individual parts of the solution if they prove to be a performance problem.
Joey
For SFMT I didn't realise that, perhaps my best approach is to try compile the c version here: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/bin/dl/dl.cgi?SFMT:SFMT-src-1.3.3.zip and then make use of it from my C# monte carlo simulation somehow. I'm not familiar withe c/c++ how to compile their src and how to use it from C#.
m3ntat
Thanks @Johannes, my implementation can use 3 cores (of the 4 on the box) so yes it will be a parallel implementation even then (with a 3 fold win) I am getting close to hitting the 24 hours daily execution time limit in the app. I've put in a request for a newer Server, more cpu etc but the pace this bank works it's a very slow process and I've been asked to optimise now.
m3ntat
Sounds like you could use a good case of the Quake Optimization Rule.
FryGuy
If you plan on taking advantage of multiple cores, be aware that cache lines can ruin this for you. Take a look at this article: http://www.ddj.com/go-parallel/article/showArticle.jhtml?articleID=217500206
yodaj007
A: 

Is there a reason you can't compile the C implementation into a DLL and call this from your C# code?

EDIT:

I'm sorry, but I have only a very limited knowledge of C (and indeed C#), but the "How to create a C dll" may be answered here: http://www.kapilik.com/2007/09/17/how-to-create-a-simple-win32-dll-using-visual-c-2005/ and the how fast can be checked by profiling the code.

Patrick McDonald
Hi Patrick, I have never used c, not sure how to do this? and use from C#, am I likely to loose much performance win by what I assume .net does some wrapping of my calls from C# to the underlying c DLL?
m3ntat
I'd guess that P/Invoke repeatedly into non-managed code does incur a pretty hefty performance overhead.
Joey
I just discovered this: http://www.codeproject.com/KB/DLL/SFMT_dll.aspx?msg=3130186 am wondering if it could prove useful for my situation
m3ntat
I also noticed a F# implementation at the botttom here http://en.wikipedia.org/wiki/Mersenne_twister no idea how to use F# but might be worth learning and benchmarking.
m3ntat
Well, both F# and C# target the CLR and I'd expect the F# code to be actually slower than C#. You can always look at the generated code with Reflector, however.
Joey
A: 

Maybe this is what you're looking for? There is a list of several implementations.

Specifically, this one (by Cory Nelson) might be useful.

Good luck

Francisco
+2  A: 

What you can do is download the source from the link you discovered on Code Project. Unzip it, load the solution in Visual Studio and compile it. This will give you source, an unmanaged c dll and a .lib file.

You can P/Invoke the functions in this dll, (there are only 5 simple functions exported, of which you need only two) or you can use this dll, lib, and the SFMT header file to create a managed wrapper dll you can use in C# without P/Invoke. I just tried this method and it was very simple to do. There was no explicit marshalling involved.

Here's how. Once you have downloaded and compiled the source (you need the header and the lib file that is created in addition to the dll) create a new C++ CLR Class Library project. Call it WrapSFMT or something. Go the project properties. Under C++/Precompiled Headers, change to "Not using precompiled headers." Under the Linker/General/Additional Library Directories, enter the path to the SFMT.lib. Under Linker/Input/Additional Dependencies, add SFMT.lib. Close the property pages. Copy SFMT.h to your project folder and include it in the project.

Edit WrapSFMT.h to read as follows:

#pragma once
#include "SFMT.H"

using namespace System;

namespace WrapSFMT {

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

These declare the methods that will be in your class. Now edit WrapSFMT.cpp to read:

#include "WrapSFMT.h"

namespace WrapSFMT {

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

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

These implement the methods you declared in the header file. All you are doing is calling functions from the SFMT.dll, and C++/CLI is automatically handling the conversion from unmanaged to managed. Now you should be able to build the WrapSFMT.dll and reference it in your C# project. Make sure the SFMT.dll is in the path, and you should have no problems.

R Ubben
I downloaded his DLLs and tried to add them as reference to my C# project I get:---------------------------Microsoft Visual Studio---------------------------A reference to 'SFMTc.dll' could not be added. Please make sure that the file is accessible, and that it is a valid assembly or COM component.---------------------------OK ---------------------------Any ideas? on how to use this and call it in the most efficient manner from Visual Studio
m3ntat
Ok I've place the DLL in my bin folder, and have code:[DllImport("SFMTc.dll")]static extern UInt32 gen_rand32();This call with no errors but all I get back is 0, never any other number.
m3ntat
If you want to use P/Invoke, you will need to invoke two functions, init_gen_rand(UInt32), initializing the generator with a seed, and then you can call gen_rand32() as much as you like. (but you probably should not exceed the Mersenne Twister's period)
R Ubben
To your first comment, if you want to reference the dll in your C# project and avoid P/Invoke, you will need to create a wrapper dll with C++/CLI and reference that. It is not difficult. I will edit the answer to show you how.
R Ubben
Awesome @R Ubben exactly what I'm looking for, I am trying the DllImport route for the moment, which is likely to be faster? Also what is my best way to seed this? and how to seed for multithreaded code? or could I just init_gen_rand once for the life of the program before spinning up threads, then each independent thread can make calls to gen_rand32() provided calling gen_rand32() is thread safe? else I don't see how to separate this and effectively give each thread it's own Random Number generator so they are independent?
m3ntat
Hmm I've benchmarked this using DLLImport of the SFMT and it's about twice as slow as my c# MT, I wonder if a C++/CLI version would be much quicker.
m3ntat
For the seed, I think most people use something like System.Environment.TickCount or System.DateTime.Now.Ticks - just remember, initializing with the same number will give you the same sequence of random numbers. A better seed would come from RNGCryptoServiceProvider, check MSDN for details. As far as threading goes, why not give each thread its own random number generator? Just make sure they get different seeds.
R Ubben
I have not benchmarked the SFMT dll, but it could be your machine does not support SSE2, which is what this dll uses. Check the Wikipedia article on SSE2.
R Ubben