Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 28 Feb 2011
Offline Last Active Today, 01:05 PM

#5173676 Pi decimals as a random number generator

Posted by Bacterius on 14 August 2014 - 01:48 PM

Given that you can actually find every sequence of bytes in PI no matter how long, which I doubt, (you can't find PI inside PI, for instance, since it is a transcendental number, and if you could, you would actually have an irrational number, which is algebraic numbers) I wonder the amount of metadata you would have to write down to "store your file in PI".


Yes, that is the joke, the metadata must be at least as large as the data itself, as expected from a simple pigeonhole argument (but some people still believe you can get something for nothing, which makes for some hilarious bug reports/issues) smile.png

#5173505 Pi decimals as a random number generator

Posted by Bacterius on 13 August 2014 - 11:25 PM

You could, but it's not particularly efficient. If I want to generate a thousand random numbers, I have to expand the Taylor series a painfully long way, which gets into numerical precision problems and other nastiness. There exist much more effective ways to get pseudo-random numbers.


The digits of pi can be generated more efficiently (and accurately) than by expanding one of its Taylor series. But, yes, it is not a particularly good idea, because it is slow (it gets slower and slower as you go) and the digits of pi are not known to be uniformly distributed anyway. Do not use it as a pseudorandom number generator, it has zero advantages and many disadvantages compared to a multiply-and-carry generator or a Mersenne twister, or a counter-mode pseudorandom permutation.

#5173223 Calculate number sequence

Posted by Bacterius on 12 August 2014 - 06:04 PM

In code, you can do this using the bitshift operator as well instead of using pow or something, courtesy of binary:

n = 5 << (level - 1);

Watch out for overflow though. Of course, if later on you want to have partial levels, e.g. level = 2.5 somewhere between level 2 and level 3, then just using pow is the better solution, since you're using floats anyway.

#5170220 Web Programming Proffession [ Need Advice] -

Posted by Bacterius on 29 July 2014 - 08:41 PM

PS: Reputation doesn't make you right.


I think he meant check his reputation log before accusing him of downvoting you. Also, chill out. I'm sure it's possible to have a civil discussion about PHP and web programming without resorting to ad hominems and accusations (right?)

#5169635 Weird problem reading file into buffer

Posted by Bacterius on 27 July 2014 - 06:26 PM


EDIT: my bad, my previous answer was incorrect. New one:


I don't know what the %#x format specifier does, but try '%.2x' instead. That should work. This is clearly a sign issue when your byte values are negative and then interpreted as unsigned integers...


I tried changing it to %.2x but it still displays the same. Also that wouldn't help me later in my code I don't think when I'm doing assignments like gif->Packed = buffer[10];


Btw my typdef for BYTE is char, not sure if that matters... I do that since char is a byte long and all I need is a byte for each variable in my gif struct.



Oh, ok, so in fact my previous (edited out) answer was correct (I thought you were using the Win32 BYTE type, which is defined as unsigned char). The char type is signed, and the %x format specifier expects an unsigned integer, so it is interpreting your (signed) char as an unsigned integer which makes it wrap around to some large positive value which is then displayed in hexadecimal.


Replace your typedef with unsigned char. To store binary data, use unsigned char. It is also a byte, but is unsigned, and so goes from 0 to 255 as you rightly expect. In these kinds of low-level binary manipulations, signed integer types should be used sparingly, if ever, because they are evil, and you will encounter only problems working with them in this context most of the time (like, say, now).

#5169280 Paint method not called

Posted by Bacterius on 26 July 2014 - 06:08 AM

What do you mean you "couldn't get the paint method to be called"? What is exactly the "paint" method? I don't see any method called "paint" in your code.


Uh, the paintComponent method has a big fat println that says "Paint Method Called". I agree about posting more information, but in this case it seems pretty clear what the paint method is.


Morrowa, the issue is (seems to be, I haven't tested) that you are creating a basic JFrame, which doesn't include your paint method (which belongs to Main, the class inheriting from JFrame you are in). In other words, you are never instantiating your own implementation of JFrame, and so it is not being used. Try this:

JFrame window = new Main();

Or something to that effect. Also, sleeping is probably not the most effective way of keeping a GUI running, since I believe it pauses the main (GUI) thread. Just leave the window open and add some code that quits the program when you click on it or press a key or whatever, that way you can test it more easily without worrying about blocking.

#5168611 C++ files organisation

Posted by Bacterius on 23 July 2014 - 04:50 AM

They are not mutually exclusive. You can have a main src or include folder which then branches off into a deep (but not too deep) file tree, with your modules neatly organized in separate files and folders. This is what I tend to do myself. In any case, if you are not designing a library or other code that could be reused by people other than you, I would just use whatever works best for you, such organizational concerns are not usually a major problem except to grumpy packagers used to doing things "their way" smile.png . Probably many of the large open source projects that you have seen have bureaucratic or architectural requirements (by virtue of being very large, or having lots of users and contributors) that would be very inappropriate in a smaller project, so many of the things you see in them would seem very strange from your perspective (though src/include is not really among them, but just saying). I don't think there is a widely accepted standard in C++ anyway, as long as your build system does not grow uncontrollably in complexity underneath you, you should not worry about it too much. C++ doesn't have a universal style guide that almost everybody follows like Java or C# do, far from that.


Some styles I've seen are "headers in include, source code in src", "only public headers in include, private headers and source code in src", "everything in src", "code dump with no folders at all (perhaps with e.g. a visual studio solution which already encodes the folder structure)", and so on... to be fair I do mostly C and not much C++, and I am personally not too comfortable with the idea of putting actual implementation code inside an "include" folder like a lot of the C++ projects seem to be doing with the advent of header-only libraries and templates (yes, I know it's not strictly required if you forward declare the different templated types you'll be using, but few bother to do that). But it's really no big deal - we are not machines, and can adapt when things don't go 100% as we expect. Really, it just goes to show that there is really no consensus on the right way to do it.


In any case, I can give a few insights on what I expect from a freshly checked out code repository:


* as a user (for libraries and other)


- is there an obvious build/install script (e.g. a solution file for visual studio for windows, a makefile or cmake/scons/autohell script for linux, a codeblocks project, etc..)?

- if not, is there a readme or install.txt I can look at?

- no? well, I don't know how to use it, if it's small enough and license permitting I might copy the source and headers inside my own code.. provided I can find them, e.g. an include or src folder

- if not, I give up and check out another library


* as a developer (contributing/etc)


- if the build system is a bit complex or there are things I should know or configuration options, are there notes about that somewhere? (not needed for small programs or obvious instructions e.g. a plain makefile)

- is it easy to build the software after changing code? does it make sure to always rebuild what needs to be (and, preferably, only what needs to be)?

- does it build out of source, or at least doesn't spew .o/.obj files everywhere in the source folder?

- are there tests I can run after making nontrivial changes?


As long as your project package provides these things, I don't see any problem. I've certainly seen far worse and I'm sure others have too.

#5168088 Hash Distance & Angle To Produce Unique Value

Posted by Bacterius on 21 July 2014 - 12:47 AM

What about multiplying the distance and the angle, suitably quantized, and handling angle wraparound properly? Should work, I think, and it takes into account the fact that spacing between angles gets larger as distance increases (if you don't want that, take the square root of the distance instead). Otherwise, you could just convert the distance + angle to an actual 2D point and go from there, it might be easier.

#5167794 Need help with a fuzzy Scoring algorithm.

Posted by Bacterius on 19 July 2014 - 08:05 AM

This is simply (reverse) linear interpolation. It tells you the relative "standing" of the input value relative to a minimum and a maximum (how far it is from them) taking into account the distance between the minimum and maximum, that is, the range (if the range is smaller, the input value will be more heavily penalized for being far away). An output value of 50% means the input value is "half a range" to the right of the minimum, i.e. halfway between the minimum of the maximum. An output value of -300% means the input value is "three ranges" to the left of minimum, an output value of 250% means the input value is "two and a half ranges" to the right of minimum, etc... so that only input values in [0, 100] fall in the [min, max] interval.

                       MIN                                      MAX               
                        +                                        +                
                        |                                        |                
                        |                                        |                
                        |                                        |                
       |                |                   |                    |           |    
       |                |                   |                    |           |    
       +                +                   +                    +           +    
     -40%               0%                 50%                 100%        125%   

#5167506 Functions

Posted by Bacterius on 17 July 2014 - 07:53 PM

I haven't seen it explicitly mentioned here but thought it might be useful to the OP as it may not be necessarily obvious to newbies - the important thing you must be aware of is that you don't need to know how a function is implemented in order to be able to call it. This is possibly the first introductory example of abstraction through separation of the interface (prototype, what it is/does) and implementation (definition, how it does it).

#5167339 Funniest line of code ever ?

Posted by Bacterius on 17 July 2014 - 03:31 AM


What is wrong with this preprocessor line? It just means to do stuff if this is gcc and we're on an x86 system... I'm not getting the joke.


It's basically saying "if your computer is really, really, really old.... or really new"


If you have a 486, pentium, or any modern 32 bit processor, you are out of luck.




Not really. I don't know what software the codebase is from, but x86 isn't the only processor architecture. For instance, if you wanted to run some code on a raspberry pi, or an arduino, this preprocessor condition would evaluate to zero. And those are hardly mythical machines like the PDP. So, some context would have probably been appropriate in this case, e.g. "windows game" smile.png 

#5167332 Funniest line of code ever ?

Posted by Bacterius on 17 July 2014 - 03:10 AM

What is wrong with this preprocessor line? It just means to do stuff if this is gcc and we're on an x86 system... I'm not getting the joke.

#5167120 Code Review(?) C++ OpenGL

Posted by Bacterius on 16 July 2014 - 04:44 AM

Use const for input parameters in functions that you know wont change.

Example "void UpdateWorld(const float deltaTime);"
For example in your planet constructor you have a int objtypes, thats a perfect case for where it should be const.
Const can be abit tricky to see the point of in the beginning. But for me, its really great. It makes the code more clean and it prevents mistakes.



That's not the best example though, since deltaTime is already copied by value (so const here might have some meaning to the programmer such as "there is no reason to ever modify the deltaTime variable inside UpdateWorld" and some people like to do it for this reason, while others think it's ridiculous, but it can't possibly affect the function's behaviour). There is no real consensus on this use of const.


Its real power comes from being used on parameters passed by reference (I don't mean a C++ reference here, just "not a deep copy") and a lot of people do it for the const-correctness benefit (despite it not being quite perfect) and to help guide their program's logical flow, while some prefer not to because it is fairly invasive by design (once you "const up" one function you pretty much have to make your entire codebase const-correct, and casting away const is often a slippery slope, so it can be a pain if you don't start upfront), or for other reasons. Almost everyone agrees that const-correctness is a good thing, so you should probably do it unless you have very compelling reasons not to.


There's also const member functions and some other stuff, which are a bit different but essentially work the same, etc... it's easy to work with it once you grasp the concept, and transfers easily to most other languages with const semantics.

#5166663 good random permutation?

Posted by Bacterius on 13 July 2014 - 09:56 PM

Here's my (heavily optimized) implementation of the algorithm I mentioned above, as a Java class with some test/benchmark code:


package permutation;

import java.util.*;

 * Provides a deterministic pseudorandom permutation of [0, 2^31).
 * WARNING: heavily tuned for the specific 2^31 - 1 case - do not edit
 *          the prime and expect it to work (you will at least have to
 *          update the reduce() method and the cofactor array and also
 *          make sure that the modPow() 2-ary algorithm still works)!
public class Permutation {
    private static final int p = 2147483647;         /* Prime = 2^31 - 1  */
    private static final int s = 31;                 /* Mersenne exponent */
    private static final int[] cofactors = {         /* List of cofactors */
        (p - 1) / 2,
        (p - 1) / 3,
        (p - 1) / 7,
        (p - 1) / 11,
        (p - 1) / 31,
        (p - 1) / 151,
        (p - 1) / 331

     * Computes the value of x mod p, where p = 2^s - 1 is prime.
     * This is a division-free optimization of the usual x % p
     * method, with performance improvements of around 10-20%.
     * Only works with p = 2147483647 (it can be implemented for
     * smaller Mersenne primes but it becomes less efficient, as
     * one needs to check more carefully for modular overflow).
    private static long reduce(long x) {
        long r = (x & p) + (x >> s);
        return r >= p ? r - p : r;

     * Computes the value of g^e mod p, using precomputed 2-ary
     * modular exponentiation. The generator array must contain
     * the 2-ary powers of the generator, beginning at g^1.
    private static int modPow(int[] generator, int e) {
        long r = 1;
        int k = 0;
        while (e != 0) {
            if ((e & 1) != 0) {
                r = reduce(r * generator[k]);

            e >>= 1;

        return (int)r;

     * Returns whether g (as a 2-ary power table) is a generator
     * modulo p. Does this efficiently via the factors of p - 1.
    private static boolean isGenerator(int[] g) {
        if (g[0] <= 1) return false;

        for (int cofactor : cofactors) {
           if (modPow(g, cofactor) == 1)
               return false;

        return true;

     * Deterministically converts a seed to a generator, and
     * returns it as a 2-ary power table (starting at g^1).
     * Note: a sizeable fraction of values in [2, p - 2] are
     *       generators of p so this will terminate quickly.
    private static int[] seedToGenerator(int seed) {
        Random random = new Random(seed);
        int[] powers = new int[31];

        while (true) {
            long g = powers[0] = 2 + random.nextInt(p - 3);

            for (int k = 1; k < 31; ++k) {
                powers[k] = (int)(g = reduce(g * g));

            if (isGenerator(powers))
                return powers;
     * The lower bound of the permutation (inclusive).
    public static final int Lower = 0;

     * The upper bound of the permutation (inclusive).
    public static final int Upper = p;

     * Precomputed values of g^(2^k) mod p, used for modular
     * exponentiation. The actual generator can be read from
     * generator[0] = g^1.
    private int[] generator;

     * Instantiates a new permutation of [0, p] using
     * the given seed (same seed = same permutation).
    public Permutation(int seed) {
        generator = seedToGenerator(seed);

     * Permutes the input in [0, p] and returns the
     * corresponding output - will throw an illegal
     * argument exception if x is out of bounds.
    public int permute(int x) {
        if ((x < Lower) || (x > Upper))
            throw new IllegalArgumentException();
        else {
            /* This is for randomizing the fixed points at 0 and p. Remember
             * that the composition of two permutations is a permutation. */
            x ^= generator[0];

            if ((x == 0) || (x == p))
                return x;
                return modPow(generator, x);

     * Little test driver for the class.
    public static void main(String[] args) {
        final int benchTrials = 5, benchSamples = 10000000;
        final int dupTrials   = 5, dupSamples   = 10000000;
        final int arbitrarySeed = 0xDEADBEEF;

        System.out.printf("Instantiating permutation on [%d, %d] (seed %d)\n",
                          Permutation.Lower, Permutation.Upper, arbitrarySeed);

        Permutation perm = new Permutation(arbitrarySeed);
        System.out.println("\nDisplaying first few values:");

        for (int x = 0; x < 20; ++x)
            System.out.printf("%d => %d\n", x, perm.permute(x));

        System.out.println("\nBenchmarking performance:");

        for (int t = 0; t < benchTrials; ++t) {
            long begin = System.nanoTime();

            for (int x = t * benchSamples; x < (t + 1) * benchSamples; ++x)

            double elapsed = (System.nanoTime() - begin) / 1000000000.0;
            System.out.printf(" [+] %.1f perms/s\n", benchSamples / elapsed);

        System.out.println("\nChecking for duplicates:");

        for (int t = 0; t < dupTrials; ++t) {
            Set<Integer> dups = new HashSet<Integer>();
            int dupCount = 0;

            for (int x = t * dupSamples; x < (t + 1) * dupSamples; ++x) {
                int output = perm.permute(x);

                if (!dups.contains(output))

            if (dupCount > 0)
                System.out.printf(" [!] Found %d duplicates!\n", dupCount);
                System.out.printf(" [+] No duplicates\n");


It meets all of your requirements:

- with the added xor operation the fixed points are gone, and the permutation can now be called pseudorandom (it is at least as good as an LCG, and probably much better - someone else can weigh in here)

- it can give you the output permuted integer for any input in the [0, 2^31 - 1] interval in constant time/memory

- it is rather fast (on the PC I am on I am getting between 15.5 and 17.5 million lookups per second across the entire input range, in Java)

- it is deterministic ("stable") and lets you specify a seed (note: not all seeds produce a unique permutation, but most do, i.e. you have around 1 billion seeds to play with)

- it is, in fact, a permutation (so each output corresponds to one, and only one, input)


You don't have to use it, but that's okay, I really enjoyed writing it anyway :)

#5166625 good random permutation?

Posted by Bacterius on 13 July 2014 - 04:00 PM

I don't think a stateless PRNG makes any sense. Is there not any way to store the state of a PRNG with the terrain generator?

Usually the go-to choice for alternative RNGs (if not already provided by the language's libraries) is usually mersenne twister.


He needs a random-access permutation, which is a different problem. But, yes, unless the seed is hardcoded, there is going to be state (by definition).


One possible candidate I can think of is the function:

\[f(x) = \begin{cases} x ~ ~ &\text{if} ~ ~ x = 0 ~ ~ \text{or} ~ ~ x = 2^{31} - 1 \\ g^x \bmod{2^{31} - 1} ~ ~ &\text{otherwise} \end{cases}\]

which has pretty good pseudorandom properties and is a permutation (there are a couple obvious fixed points by construction, which can be eliminated by e.g. multiplying the input with a suitable constant beforehand). Here g is supposed to be a generator of 2^31 - 1, the smallest one is 7 and about 25% of all possible bases are generators, so you won't run out of seeds (it is easy to test if you have a generator, which means you can efficiently find one by instantiating any PRNG with your seed and looking for a generator that way). It is also reasonably fast, because modular exponentiation can be implemented efficiently using modular square and multiply, and, furthermore, reducing an integer modulo 2^31 - 1 thankfully doesn't require a division. I might write up a full implementation this afternoon if anyone is interested (or just for fun)