A Random Dispersion Array - C++ console

Chapter One : Using GNU g++, bash and UPX to compile

This is a rehash of some code I had posted at GIDForums™ with some explanations to the functioning of it all. It is a simple console application that I compile with g++ using the command line,

g++ -Wall random_dispersion.cpp -s -o RandomDisp

or to stay away from the cygwin1.dll

g++ -Wall array_size.cpp -mno-cygwin -s -o ArraySize_win

When preparing for upload I will usually run the EXE through UPX before compressing. I have had good luck with this so far, but if you have problems with one of my binaries that could be it. The reason is simple, here is the output from both the CygWin version and the MS version.

$ upx *.exe
                     Ultimate Packer for eXecutables
         Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002
UPX 1.24w        Markus F.X.J. Oberhumer & Laszlo Molnar         Nov 7th 2002

        File size         Ratio      Format      Name
   --------------------   ------   -----------   -----------
    289280 ->     91136   31.50%    win32/pe     ArraySize.exe
    268288 ->     82944   30.91%    win32/pe     ArraySize_win.exe
   --------------------   ------   -----------   -----------
    557568 ->    174080   31.22%                 [ 2 files ]

Packed 2 files.

Due to my wanting to run (and rerun) the tests it uses variable length arrays set at runtime. If your compiler will not support these, you have a few choices,

• Get a compiler that supports it

• Rewrite the routines

• Delete the whole mess and go watch some TV.

I will try to provide a link to compiled binaries when possible but I can't promise anything now. Anyhow, here is a breakdown of the code.

Now, a few words of warning -- I am by no means a professional. My testing may be laughable to some, but it serves my purposes. I have tried to catch any glaring possiblities for errors but as always, use at your own risk.

I have run both controlled and semi-random tests to see how things react. If you find something that should be addressed, let me know.

My limits are arbitrarily chosen. I don't know what someone may want to use this for, so if you make changes you do so at your own peril. I do periodically have to go through my working directories with that good old trusty,

rm *.stack*

rake, to get rid of the leaves piling up in the corners. You know the drill.

On with the show...

Copyright, Contact and Disclaimer

// copyright © 2005 Mark Roth Nescopeck PA
// MRothCode[at]gmail[dot]com
// No warrenty, no nothing.  If you don't like it don't run it.
// If you do, use it in any way your imagination can come up with.

Ok, I love the idea of Open Source. I truly think that if an author wants something to be free it should be free. Unfortunately, I sometimes feel that the people preaching about freedom have become as problematic as those trying to keep freedom from people.

Putting something into the GPL can be restrictive for the long term life of code. I don't mean to suggest that my code is so great it will be desired by the masses. What I think is that true freedom allows for freedom of choice. My idea of Freedom is this:

• If you use someone else's code, give them credit and a copy of your software. What's the harm in a free unlocked version of your software going to someone who may have, even in a tiny way, contributed to your project. It's most likely to be hacked apart anyhow.

• Some people don't believe in Open Source as a viable commercial alternative. I do, but I also hate when people show up at my door on a Saturday or Sunday morning just to tell me I should do as they do. No thank you very much.

• Do as you would like done unto you. Period. If you can contribute code from your commercial product because it is clever or cool, do so. If it could serve as a learning experience, do so. Otherwise, who really cares what you wrote.

• Free software should come without entanglements, otherwise, it really is not free now, is it?

Includes for the Standard Library

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::getline;
using std::atoi;

Nothing stunning here, just some standard includes from the standard and the required items being using(ed). That kind of cracks me up.

FUNCTION : RNDseed() and RNDgen() using srand(), time() and rand()

static bool seeded = false;

// a one shot random seed
void RNDseed(){
  
  srand(time(NULL));
  seeded = true;
}

// a simple random number generator
// returns a number from 0 to MAX-1
const unsigned RNDgen(const unsigned MAX) {
    
  return (rand() % MAX);
}

Everyone knows that random numbers aren't really random, right? Well, I'm pretty sure this stuff isn't going to end up being used for an Enigma type of thing so this should do just fine. Seed the generator once and only once with your clock and be done with it. I could have wrapped this global and these simple routines in a local sense but, hey, if a single boolean global is going to cause you grief, do it yourself. This works well for my purpose.

RNDgen() could be beefed up a bit to allow for a minimum and maximum as well as a check against RAND_MAX (or whatever it might be called) but this will give you a positive number somewhere from zero to 4 billion (or maybe 2 billion). Look elsewhere if you need more than that. After all, what's a billion if not 1,000 millions, or 10 thousand 100 thousands. There is always a way.

FUNCTION : GetUnsigned() Controlling Index Value Input, constants and unsigned integers

// returns an number within a given range
const unsigned GetUnsigned(const string text, const unsigned hi, const unsigned low){
  
  string buf;
  unsigned atoi_buf;

  do{
    cout << "Enter " << text << " : ";
    getline(cin, buf);
    atoi_buf = atoi(buf.c_str());

  }while ( (atoi_buf > hi) || (atoi_buf < low) );

  return atoi_buf;
}

This routine assumes that you want a constant unsigned integer to be used for creating an array on the fly. In practice, I have found that a number larger than ~250 million could be a problem, at least on my ~192MB PentiumIII.

You pass a text string to be used as a prompt and GetUnsigned() will get you just that, an unsigned integer that also happens to be constant. It should filter out foolishness like negative numbers and non numerics. To do this I use atoi() from the standard library. This is the basis for my generic input routine that cages cin using getline().

Man I love <string>s.

FUNCTION : GetPer100() and GetMagic100 Integer Math to get Real Percentages

// gets a count less than or equal to 100.  It is the per/100 number
const unsigned GetPer100(const unsigned DefPercent, const unsigned OtherIDs){

  const unsigned per100units = DefPercent + (((100-DefPercent)/OtherIDs)*OtherIDs);
  return per100units;
}

// gets the number that will set the size of the random index array
const unsigned GetMagic100(const unsigned Per100units, const unsigned OtherID){
  
  unsigned magic100;
  const unsigned per100remain = 100 - Per100units;

  for(magic100 = 1; ((per100remain * magic100) % OtherID) != 0; magic100++);
  return magic100;
}

Jeepers Creepers, finally getting to some meat Mark! :)

These two routines are, in my opinion, clever. GetPer100() will figure out just how many numbers you can use every 100. Therefore, it can be use to get a basis for a true percentage of undividable items (in our case, publishers) based on two factors. The first is what percentage will the house hold back. That is the DefPercent. The OtherIDs is how many publishers will divide up the remainder of that percentage. Since 1% is 1 out of 100 and you can't divide a publisher into smaller pieces (even if you would like to from time to time) the final number will not be 100 but some number less than or equal to 100 that takes both those numbers into consideration.

The second function GetMagic100() takes that information and returns a number to you that will be 1/100th of the array's size. This number can also be used in some other ways to figure out some nifty things about the set.

I found this easiest to do in two stages. Using integer math in the first stage gets around any problems using floats and the second stage doesn't need to consider coming up with a portion of an integer. All in all, a good way to get around losing precision in a float.

FUNCTION : BuildRndList() A Randomized Weighted Percentage List

// does the work of building the weighted list
void BuildRndList( unsigned array[], const unsigned size,
                   const unsigned OtherIDs, const unsigned OtherIDamt ){
  
  if (seeded == false) RNDseed();
  // set array to all '0'
  for ( unsigned i = 0; i < size; i++ ) array[i] = 0;
  for ( unsigned i = 1; i <= OtherIDs; i++) {
    for (unsigned j = 0; j < OtherIDamt; j++) {
      bool loop = true;
      do{
        const unsigned RNDnum = RNDgen(size);
        if ( array[RNDnum] == 0 ) {
          array[RNDnum] = i;
          loop = false;
        }
      }while ( loop );
    }
  }
}

This silly thing looks complicated but it really is not. All it does is sets the array that is passed by reference all to 0 and then randomly places an index for the publisher ID array. It assumes that the publisher ID array follows this convention.

• The default ID is at 0

• There are no "holes" in the array.

Simply put, if you have 4 additional publishers, it will create a random dispersion array that contains 0, 1, 2, 3 and 4. 0 will be weighted as the default percentage dictates and the additional publishers will have an even split.

Here is the process :

1. Set the entire array to index 0 - the default publisher

2. OtherIDs loop - this is the publisher index number currently being inserted into the array.

3. OtherIDamt loop - how many times should this publishers index be inserted.

4. Find a location still set to zero and put the current index there. If it finds any other number it tries again until successful.

5. And so on until done.

Since the address of the actual array is passed in there is no need to pass anything back. Once word of warning. I accidentally set the random number generator to return a number from 1 to max array value -1 when I was first working on this. Setting the default publisher ID percentage to 0 sent it off on a wild goose chase since it never could insert at index 0. Just another reason for solid testing.

FUNCTION : main() testing the routines

Since this is not really a C++ tutorial but documentation of code that will become PHP code I am not going to describe each and every last bit of this code. It will be left as an exercise to the reader. I'll just give it a quick pass through and see if there is anything that should be expanded on.

int main(){

  string buffer;
  
  do{
    unsigned magic_number;

    const unsigned defID = GetUnsigned("DefID percentage ", 100, 0);
    const unsigned otherIDs = GetUnsigned("OtherID number   ", 50, 1);
    const unsigned per100units = GetPer100( defID, otherIDs);
    unsigned ASpubID[1 + otherIDs];

    for ( unsigned i = 0; i < (otherIDs + 1); i++ ) ASpubID[i] = 100 + i;

    magic_number = GetMagic100(per100units, otherIDs);
    const unsigned array_size = magic_number * 100;
    cout << "units per 100 unused = " << 100 - per100units << endl;
    cout << "array_size = " << array_size << endl << endl;
    unsigned rndASpubID[array_size];
    const unsigned otherIDamt = (array_size - (defID * magic_number)) / otherIDs;
    
    BuildRndList( rndASpubID, array_size, otherIDs, otherIDamt );
    
    // at this point the array rndASpubID has a list of publisher indexes
    // that can be used by a stack system to actually access the proper
    // ID.  Everything below is just for testing and display.

    unsigned counter[51];
    for ( unsigned i = 0; i <= 51; i++ ) counter[i] = 0;
    for ( unsigned i = 0; i < array_size; i++) {
      cout << ASpubID[rndASpubID[i]] << "  ";
      counter[rndASpubID[i]]++;
    }
    cout << endl;
    for ( unsigned i = 0; i < (otherIDs + 1); i++ ) {
      cout << endl << "number of " << ASpubID[i] << "'s = " << counter[i] << endl;
    }
    cout << endl;

    cout << "try another combo (y/n) : ";
    getline(cin, buffer);
  }while (buffer == "y");

  return 0;
}

Ok, nothing much to say that the code doesn't already say. There is a testing loop that assigns value to the counter array. That just looks through the entire array and counts the values that are placed, incrementing the proper index each time.

Then the next loop outputs what it found. If everything is working correctly you should see a number for index zero that is equal to the magic number times the default publisher percentage and identical values for all the additional publishers. If you so desire you could figure out what each publisher's percentage but I didn't see a need for it, just the AdCode instances.

Conclusion Documentation and the Future

Hopefully this will help anyone wanting to use this code for something other than what I wrote it for. Documentation is the key to that process so this has been informative for me as well. While going through each bit, I found some minor modifications that I made along the way.

The next three chapters are going to deal with taking everything in this chapter and breaking it into pieces that can be digested for web use. For one, it will help keep the chapters to a reasonable length. More importantly, it will divide the functionality a bit so when it comes time to put things into classes you should be able to see how and why things are seperated.

• Chapter 2 - porting the code to PHP

• Chapter 3 - an HTML display form

• Chapter 4 - make the form interactive