Álvaro

You can make your terrain be the product of two noise functions: One low-frequency noise function determines whether we are in a flat region or a mountain region (with smooth transitions between them), and the other one has the usual shape to generate mountains. I believe some people refer to this as a "multifractal".

You should try to find some material on bit manipulations in C or C++ somewhere else, for a more complete understanding.

Let's analyze the expression ((x << 16) + y).

(x << 16) means "take the value of x and shift it 16 bits to the left", or equivalently "multiply x by 65,536". This means that (1, 65536) and (2, 0) map to the same number. I don't know if this is acceptable to you, but my guess is that it's fine. The magic constant I used is simply a random odd 64-bit number. You should use a random odd 32-bit number if you are using 32-bit arithmetic. The advantage of using a large random number instead of 65,536 here is that you can generalize the procedure to hash more information into the seed like this:

unsigned long seed = x;
 seed = seed * 10366439865051156459ul + y;
 seed = seed * 10366439865051156459ul + z;
 seed = seed * 10366439865051156459ul + w;
 // ...

If you were to do that by shifting alone, the information about x would eventually get lost in overflow.

There are situations where you need to hash information down to a single number and you need the result to look much more random (e.g., cryptographically signing a document), but I don't think you have to go crazy for your particular application.

Thanks for suggestions guys.

Int=(int)short << 16 & short2

???

So short is the x coord and short2 is the y. You are bit shifting the x by 16 and adding it to the y, to make it a unique single value? This is so the point {1;2} will not result in the same seed as {2;1}, am I right?

And alvaro, you are doing something similar.

I am doing something similar, but my code works. What Waterlimon posted has several issues. He probably meant to say `(short1 << 16) + short2' or `(short1 << 16) | short2'. With '&' you'll get 0. And you can't use `short' as a variable name.

VS2010 seems to be using exponentiation by squaring. My gcc 4.6.1 (the C compiler) seems to only know the trick for powf(x,2), and it makes a function call for all other cases. g++ 4.6.1 (the C++ compiler) optimizes any constant positive integer power. The resulting code is very amusing. For std::pow(x,241):

        movaps  %xmm0, %xmm1
        mulss   %xmm0, %xmm1 // 1 + 1 = 2                                       
        mulss   %xmm0, %xmm1 // 1 + 2 = 3                                       
        movaps  %xmm1, %xmm2
        mulss   %xmm1, %xmm2 // 3 + 3 = 6                                       
        mulss   %xmm2, %xmm1 // 6 + 3 = 9                                       
        mulss   %xmm2, %xmm1 // 6 + 9 = 15                                      
        mulss   %xmm1, %xmm1 // 15 + 15 = 30                                    
        mulss   %xmm1, %xmm1 // 30 + 30 = 60                                    
        mulss   %xmm1, %xmm1 // 60 + 60 = 120                                   
        mulss   %xmm1, %xmm1 // 120 + 120 = 240                                 
        mulss   %xmm0, %xmm1 // 1 + 240 = 241                                   
        movaps  %xmm1, %xmm0
        ret

What SiCrane says. Also, the idea that powf is slow probably comes from times when compilers did something very naive with it. These days, a compiler will probably issue the same code for powf(x,2) as for x*x.

Actually they very probably don't. We went through this recently on a different forum.
To back that statement I just tried it in VS2008 Express with full optimisations on in release build and with code written such that it cannot be optimised out. There was a 14x speed difference between using powf(x, 2) and x*x.

I checked shortly after I posted that comment, just to make sure that I am not spreading false information. gcc 4.6.1 seems to be smarter about this.

In C:

#include <math.h>

float f(float x) {
  return powf(x, 2);
}

The assembly produced is:

.file	"kk.c"
	.text
	.p2align 4,,15
	.globl	f
	.type	f, @function
f:
.LFB3:
	.cfi_startproc
	mulss	%xmm0, %xmm0           // Hard to optimize beyond this
	ret
	.cfi_endproc
.LFE3:
	.size	f, .-f
	.ident	"GCC: (Ubuntu/Linaro 4.6.1-9ubuntu3) 4.6.1"
	.section	.note.GNU-stack,"",@progbits

What SiCrane says. Also, the idea that powf is slow probably comes from times when compilers did something very naive with it. These days, a compiler will probably issue the same code for powf(x,2) as for x*x.

Also,

Merge sort's most common implementation does not sort in place

That's because it's usually implemented on arrays. In the case of linked lists, it's easy to write it just moving pointers around, without copying or moving any of the data.

[...] If I comment out  the "array[ctr] = v;" line, I get 600fps, if not I lose over 200fps and  drop down to ~350 fps.

If you comment out the "array[ctr] = v;" line, your compiler may decide that the whole piece of code doesn't have any effect and just optimize it into nothing. It's really not a good indication that the array access is slow. Array accesses are usually not slow at all. Also, the code you posted only ever writes to array[0], so I don't see the point.

I like low-tech factory functions like this:

// base.cpp

#include "base.h"
#include "derived1.h"
#include "derived2.h"

std::shared_ptr<Base> factory(std::string const &description) {
  if (description == "DERIVED1")
    return std::shared_ptr<Base>(new Derived1());
  if (description == "DERIVED2")
    return std::shared_ptr<Base>(new Derived2());
  // Otherwise issue some error complaining about an unkown type of Base
}

It works every time, and everyone can understand what's going on. Automatic registration might seem neat, but I don't think it's worth the pain.

At some low level, an object is a data structure, and functions are not part of it (virtual functions make this statement less true, but let's ignore that for a minute). Non-static member functions are just functions that take a first parameter which is a pointer to the object on which they are called, whose name is `this' (a `const' method is one where the `this' pointer is a `const' pointer). Static member functions are the same thing as regular functions. The language allows member functions access to private and protected data, but this is in some sense a higher layer.

The description of objects as being something that contains both the data and the code that operates on the data is misleading and you should try to forget it. As a tool to organize your program, a class does provide a single entity that describes the data and how you operate with it, but individual objects only contain the data.

Virtual functions are a bit different, in that the object itself will have some mechanism to retrieve the appropriate version of the function to be called in a dynamic dispatch. The most common mechanism to do this is a so-called vtable.

While we are at it, you can think of a class that inherits from another class as having a data member of that class. If the inheritance is public, protected or private, think of it as that data member being public, protected or private. If the inheritance is virtual, the member is actually a pointer to the parent class. But I have never ever needed virtual inheritance for anything. If you find yourself needing it, you probably went too far with your inheritance hierarchy.

This is basically how I think of objects in C++. There are some layers of syntactic sugar on top of that (for instance, the way you invoke a member function hides the passing of the `this' pointer). I hope this makes things a bit more clear.

1)  What advantages are gained by negating the value in:  (x - ((x >> 1) &0x55555555)?

That's a clever way of computing the bit count of every 2-bit box. It's probably not better in practice than

x = ((x & 0x55555555) + ((x >>  1) & 0x55555555));

2)  Why the multiplication of 0x1010101, and the r-shift of 24?

If you think of your 32-bit number as a 4-digit number in base 256, you are computing

      a b c d
    * 1 1 1 1
      -------
      a b c d
    a b c d
  a b c d
a b c d
-------------
e f g h i j k

e, f and g are lost in overflow, so by shifting 24 places to the right, you recover h, and h = a + b + c + d. Notice that a, b, c and d are at most 8, so you won't have carry problems.

3)  Does this trickery scale to 64-bit integers?

Yes, and if you understand the 32-bit code, you should be able to write the 64-bit version yourself.

Here's a few I've seen asked:
* Reverse a linked list.
* Test if a number is prime.
* Binary search.
* Compute the median of an array of integers.

I think Project Euler is a very good way to practice writing little programs that do clever things.

You probably should avoid using a global PRNG anyway. If there is nothing preventing two threads from querying it at the same time, you could get really weird results out. For instance, you could get the same number returned to two threads, or even weirder things, depending on how the PRNG is implemented. At the very least, you should put a lock around access to the PRNG.

It is also nice to be able to reproduce the results of a Monte Carlo simulation, for instance so you can debug a problem, or so you can test that a reimplementation of some part of the program doesn't change results. You could achieve this by replacing the PRNG with a hash function (where you feed i, j and some other numbers from the guts of some_function). That's probably the cleanest method.

It sounds like your program has global state that's messing with the parallelization. Try to find any global variables (or static local variables, or static class members) that some_function might be using. Then there are several things you can do to make the problem go away:
* Use a lock.
* Replace the global object with one instance per thread.
* Refactor the code so the global object is no longer needed.

You should prefer to declare variables in the smallest context you can. This is particularly important in this situation, because otherwise OpenMP doesn't know which variables are thread-specific and which are shared.

  double sum = 0;

#pragma omp parallel for reduction(+:sum)
  for(int i = 1; i < ne; i++) {
	for(int j = 1; j < nx; j++) {
  	double quantity= some_function(i,j);
  	sum = sum + quantity;
  	Iij[i *nx + j] = quantity;
	}
  }