Posts Tagged ‘C/C++’

Monte Carlo integration

I was reading a bit about random numbers and remembered that I wrote a simple Monte Carlo integrator in C++ a few years ago. I took a few minutes to cleanup and comment the code, which is presented below.

Monte Carlo integration is simple, but surprisingly powerful:

I=abf(x)dx
Ii=1nf(xi)p(xi)

xi is a random value within the range [a,b]

p(x) represents the distribution of random values, for a uniform distribution:

p(x)=1ba

This presentation by Fabio Pellacini provides a lot more details.

The test code in the main() method computes the integral of sin2(x) in the interval [3,5].

#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;

// Functor base class for encapsulating 1-dimensional function to be integrated
class Function1d
{
    
public:
        
virtual double operator()(double x)
        {
            
return x;
        }
};

// Functor for sine squared function
class SineSquared : public Function1d
{
    
public:
        
double operator()(double x)
        {
            
return pow(sin(x), 2);
        }
};

// Monte Carlo integrator class declaration
class MonteCarloIntegrator
{
    
public:
        
double Run(int numSamples, Function1d& func, double intervalMin, double intervalMax);
};

// Monte Carlo integrator implementation
// ::Run() method implementation
double MonteCarloIntegrator::Run(int numSamples, Function1d& func, double intervalMin, double intervalMax)
{
    
double sum = 0;
    
double div = 1.0 / (double)RAND_MAX;
    
double intervalScale = 1.0 / (intervalMax-intervalMin);

    
for(int i=0; i<numSamples; i++)
    {
        
double rnd1 = intervalMin + ( ((double)rand() * div) * (intervalMax-intervalMin) );
        sum += (func)(rnd1) / intervalScale;
    }

    
return (1.0/(double)numSamples) * sum;
}

// main() function with test code
void main()
{
    MonteCarloIntegrator    integrator;    
    
double output = integrator.Run(5000000, SineSquared(), 3, 5);

    srand(time(NULL));
    std::cout << output << endl;

    getchar();
}

C for Dummies

I snapped a photo of my C for Dummies books on a visit to my parents place (my apartment is tiny, so a lot of my old books are there). C was the first programming language I took a serious interest in learning. I knew a bit about code prior as I had toyed around with QBASIC and Visual Basic, but I was interested in video games and computer graphics, for which neither of those languages were well suited.

I spend maybe a month consuming these 2 books when I was about 16, going back-and-forth between the pages and MS Edit + DJGPP to write and compile code. When it all clicked (and there really was that moment of clarity as everything went from looking cryptic and indiscernible, to elegant and natural) it was incredibly exciting.

These books were a great introduction to the C language, and programming in general, and Dan Gookin deserves a lot of credit; technical writing is hard, even more-so when your audience is the absolute beginner.

C for Dummies

Flexible Binary Format

Another project I worked on a long time ago but never released. The goal of Flexible Binary Format was to create a file format and library for dealing with (tree) structured binary data (in the same vein of what XML does for textual data). This was a reaction both to the verbose and non-binary-friendly nature of XML and to the ugly chunk-based structuring done in many binary file formats.

The code for the C++ library is now up.

I’ll do a high-level, quick-and-dirty tutorial in this post to show how things work.


include FBF.h

#include "FBF.h"


Build a data tree

FlexibleBinaryFormat::DataTree        dt;
FlexibleBinaryFormat::TreeBuilder    dataTreeBuilder(&dt);


Attach a node to the data tree

dataTreeBuilder.AttachNode("root/vertex");


Make a vector of nodes and sub-nodes

dataTreeBuilder.AttachNode("root/vertex");
dataTreeBuilder.AttachNode(
"root/vertex");
dataTreeBuilder.AttachNode("root/vertex[0]/xyz");
dataTreeBuilder.AttachNode(
"root/vertex[1]/abc");

Note: We created 2 nodes on the same path (root/vertex). We access them individually using an index number within brackets.


Attach data to nodes

dataTreeBuilder.AttachDouble("root/vertex[0]/xyz", 0.12345);
dataTreeBuilder.AttachDouble(
"root/vertex[1]/abc", 54321.0);

Once data is attached to a node, you can’t attach a sub-node to it.
(i.e. data is stored on the leaves of the data tree)

The following methods of FlexibleBinaryFormat::TreeBuilder are available to attach data to a node:

  • AttachString()
  • AttachBool()
  • AttachByte()
  • AttachSByte()
  • AttachDouble()
  • AttachFloat()
  • AttachShort()
  • AttachUShort()
  • AttachInt()
  • AttachUInt()
  • AttachInt()
  • AttachUInt()
  • AttachLong()
  • AttachULong()


Write the data tree out to a file

FlexibleBinaryFormat::FlexibleIO    flexio(&dt);
flexio.WriteToFile(
"test.fbf");


Read a data tree from a file

FlexibleBinaryFormat::DataTree        dt2;
FlexibleBinaryFormat::FlexibleIO    flexio2(&dt2);
flexio2.ReadFromFile(
"test.fbf");


Read data from a node

double v0xyz = dt2.GetData<double>("root/vertex[0]/xyz", 0);
// second arg is always 0;
// arg is a leftover from some deprecated stuff in older versions and will be removed

SlashXML (C++ version)

The C++ code for SlashXML is now up, it’s in the /cpp folder within the repository. The C++ version supports most of the functionality the C# version does; maintaining multiple codebases is very difficult!

The C++ version also has 2 dependencies: TinyXML, an awesome, light weight XML parser, and AString, a not-so-lightweight UTF-8 string class. I know not everyone might be crazy about using AString, especially as it’s fairly bloated; I fucked around with things like custom numeric to string conversions with this class – unnecessary stuff, and it’s probably slower than using sprintf. However, it’s well encapsulated in it’s own namespace. I’ll try to have something more elegant in the future.


Load an XML document from a file

SlashXMLReader    xmlreader;
xmlreader.LoadXMLFile(
"test.xml");


Load an XML document from a string

SlashXMLReader    xmlreader;
std::vector<
unsigned char> xmlData;
// copy octets from string into xmlData here
xmlreader.LoadXMLData(xmlData);


Retrieve data from an element

SlashXMLString data = xmlreader.GetData("root/child");


Retrieve data from an indexed element

SlashXMLString data = xmlreader.GetData("root/child[2]");


Get the number of child nodes under an element

int numKids = xmlreader.GetNumChildren("root", "child");

The SlashXMLReader::LoadXMLData() method is kinda messed up and bizarre. I don’t even remember what was going thru my mind there.

The namespace-enum trick

Enums in C++ can be a pain in the ass once a project starts to grow in size. Enums are typically defined globally or within a fairly wide scope such that there’s usually a pretty high probability that you’ll get name clashes between enums (remember that in C++ the enum block is not a scope, so enum members must be unique across multiple enum declarations) unless, like with the DirectX or Win32 APIs, you give your enum members names which are detailed, prefixed, and very ugly looking. For example here’s some of the enum members for Direct3D render states:

typedef enum _D3DRENDERSTATETYPE {
    D3DRS_ZENABLE = 7,
    D3DRS_FILLMODE = 8,
    D3DRS_SHADEMODE = 9,
    D3DRS_ZWRITEENABLE = 14,
    D3DRS_ALPHATESTENABLE = 15,
    ...

Truthfully, the DirectX enums aren’t that bad, and most programmers (including myself) have seen worse, but is there a better way?

Recently, I’ve discovered a cool trick that I’ve started using in most of my C++ code. Just wrap the enum declaration inside of a namespace. So, as an example, you might have something like:

namespace Color
{
    
enum Color
    {
        Red,
        Green,
        Blue,
        Orange,
        Purple
    }
}

… and, because of the namespace wrapper, it’s also perfectly valid to have the following within the same scope as the code above (note the Orange enum member in both declarations):

namespace Fruit
{
    
enum Fruit
    {
        Apple,
        Orange,
        Purple
    }
}

You access an enum member by simply resolving the namespace first:

Color::Red
Color::Orange
Fruit::Orange

Simple and elegant!

The only oddity is that to declare variables that are of the enum type, you have a declaration that looks like:

Fruit::Fruit

or

Color::Color

… but overall I think that’s a small price to pay.

I am very surprised that this little trick is not mentioned much and in the few places where I have seen it mentioned (such as here), it is glossed over and its significance is not really highlighted.

EDIT: Note that C++11 introduces scoped enums which renders this trick unnecessary, if you have a compliant compiler.