$1254 calcBinominal Question

[searle]

I've been staring at the code for over an hour now and I just don't get it

I just don't see the "binominal" in the function. What the function does for me is:
- find a random r number between -1530; 1530
- if Y==0, r /= 2
- if Y==2, r *= 2
- cut off the lower byte (r >>= 8 )

Conclusions:
- As Y is either 0, 1 or 2, loc_1295 is even never reached.
- r is [-5 .. 5] ( ... * Y )
- not binominal, same chance for every possible result

What am I missing?

Cheers,
searle

[Kroah]

Hi Searle,

- find a random r number between -1530; 1530

Here, you can't say this straight because [-1530; 1530] are the bounds of the sum of random numbers, not the random number itself.

The distribution is not linear:
When you take 12 random numbers between [0;255] ([0; 1.0] because fixed) and you sum them up, you obtain a gaussian distribution. In fact, the result follows a "normal law" when the number of dices (here 12) tends to infinite.

So, you can't say that taking a number between [0;8] is the same as the sum of 4 random numbers between [0;2] because the distribution (the probability to have a 4 for example) is not the same.

After the sum, the result is centered at 0 by substracting 1530. And finally, it's divided according to Y like you said.

The result is a fixed number on two bytes (a word) where the fixed part is in the low byte. So the result is between [-5.98...; 5.98...].

Does this help you ?

Cheers,
Kroah

[searle]

Great, thanx! I knew I was missing something...

Searle

[searle]

Hmm I wish my maths were better...

This Java implementation:

Code: Select all

package mule;

import java.util.*;

public class Test {

   static Random random= new Random();

   static int calcBinominal(int value, int fluctuation) {

      if (fluctuation == 0) return value;

      int r= -255 * 6;
      for(int i= 0; i < 12; i++) {
         r += random.nextInt(256);
      }
      
      if (fluctuation == 1) return value + r / 512;
      return value + r * (fluctuation - 1) / 256;
   }

   public static void main(String[] args) {
      int[] res= new int[12];
      
      for (int i= 0; i < 10000000; i++) {
            res[calcBinominal(0, 2) + 5]++;
      }
      
      for (int i= 0; i < 11; i++) {
         System.out.print(res[i]);
         System.out.print(" ");
      }
      System.out.println();
   }
}


outputs

Code: Select all

0 84 10170 213806 1388504 6775051 1388989 213374 9946 76 0


which differs from your numbers:

Code: Select all

1254 ; Répartition:
1254 ; -4:  0.013%
1254 ; -3:  0.562%
1254 ; -2:  6.248%
1254 ; -1: 24.303%
1254 ;  0: 37.748%
1254 ;  1: 24.303%
1254 ;  2:  6.248%
1254 ;  3:  0.562%
1254 ;  4:  0.013%


Do you see the cause of the difference?

Cheers,
Searle

[searle]

For fluctuation == 1 I get

Code: Select all

0 0 0 82 224460 9550955 224438 65 0 0 0


Searle

[Kroah]

You seem to have an error in your program. I've translated it to Javascript (I haven't another language at work) and it gives me the same result as the presumed probabilities:

Computed probabilities (Amplitude 1):

Code: Select all

0: 0
1: 0
2: 0
3: 0
4: 0.1
5: 15.925
6: 67.855
7: 16.019
8: 0.101
9: 0
10: 0
11: 0
12: 0
Somme: 100%
Amplitude: 1
Factor: 0.5

Javascript program (from yours) (Amplitude 1):

Code: Select all

0 0 0 0.089 15.855 68.076 15.876 0.104 0 0 0

Computed probabilities (Amplitude 2):

Code: Select all

0: 0
1: 0
2: 0.012
3: 0.543
4: 6.164
5: 24.271
6: 37.885
7: 24.356
8: 6.209
9: 0.549
10: 0.012
11: 0
12: 0
Somme: 100.001%
Amplitude: 2
Factor: 1

Javascript program (from yours) (Amplitude 2):

Code: Select all

0.001 0.013 0.499 5.931 24.446 38.048 24.396 6.098 0.553 0.015 0

Here's the Javascript program (from yours) (launch it from IE):

Code: Select all

<script>
function calcBinominal (value, fluctuation) {
  if (fluctuation == 0) {
    return value;
  }

  var r= -255 * 6;
  for (var i= 0; i<12; i++) {
    r += Math.round (255*Math.random ());
  }

  if (fluctuation == 1) {
    return (value + Math.round (r / 512));
  }
  return (value + Math.round (r * (fluctuation - 1) / 256));
}


var res = new Array ();
for (var i=0; i<12; i++) {
 res [i] = 0;
}

for (var i=0; i<100000; i++) {
  res [calcBinominal(0, 2) + 5] += 1;
}

for (var i= 0; i<11; i++) {
  document.write (res[i]/1000);
  document.write (" ");
}
</script>

Here's my Javascript program to compute probabilities:

Code: Select all

<script>

var nbDices = 12;
var maxOnDice = 255;
var amplitude = 2;



var factor = null;
if (amplitude == 0) {
  factor = 0;
}
else if (amplitude == 1) {
  factor = 0.5;
}
else {
  factor = amplitude-1;
}

var tab = InitDice (maxOnDice);
var result = AddDices (tab, nbDices);


for (var i=0; i<result.length; i++) {
  document.write (i + ": " + result [i] + "<br />");
}

var result2 = new Array ();
for (var i=0; i<=nbDices; i++) {
  result2 [i] = 0;
}

var somme = 0;
for (var i=0; i<result.length; i++) {
  var i2 = (i - 1530) * factor + 1530;
  result2 [Math.round((i2+6)/256)] += result [i];
  somme += result [i];
}

var somme2 = 0;
for (var i=0; i<result2.length; i++) {
  var nb = Math.round ((result2 [i] / somme)*100000)/1000;
  document.write (i + ": " + nb + "<br />");
  somme2 += nb;
}
document.write ("Somme: " + somme2 + "%<br />");
document.write ("Amplitude: " + amplitude + "<br />");
document.write ("Factor: " + factor + "<br />");


function InitDice (max) {
  var tab = new Array ();
  for (var i=0; i<=max; i++) {
    tab [i] = 1;
  }
  return (tab);
}

function AddDices (tabDice, nb) {
  var result = null;
  for (var i=0; i<nb; i++) {
    document.write ('Dice ' + (i+1) + '...');
    result = AddDice (tabDice, result);
    document.write (' Done<br />');
  }
  return (result);
}

function AddDice (tabDice, tabPrev) {
  var tabNext = new Array ();
  if (tabPrev == null) {
    for (var i=0; i<tabDice.length; i++) {
      tabNext [i] = tabDice [i];
    }
  }
  else {
    for (var i=0; i<=(tabDice.length-1+tabPrev.length-1); i++) {
      tabNext [i] = 0;
    }
    for (var i=0; i<tabDice.length; i++) {
      for (var j=0; j<tabPrev.length; j++) {
        tabNext [i+j] += tabDice [i] * tabPrev [j];
      }
    }
  }
  return (tabNext);
}
</script>

If you have any idea why we don't have the same result... good luck
Cheers

[searle]

Maybe the problem is that there is no proper cast to int in JavaScript?
I think that using Math.round and Math.floor is not correct, mainly because Math.floor(-0.2) == -1 (and not 0). I changed your script to what I think is a closer adaption of the 6502 code. (And, closer to the Java version which doesn't use floats aniway.)

Code: Select all

<script>
function int(a) {
    if (a < 0) return -Math.floor(-a);
    return Math.floor(a);
}
function calcBinominal (value, fluctuation) {
  if (fluctuation == 0) {
    return value;
  }
  var r= -255 * 6;
  for (var i= 0; i<12; i++) {
    r += int(256*Math.random ());
  }
  if (fluctuation == 1) {
    return (value + int(r / 512));
  }
  return (value + int(r * (fluctuation - 1) / 256));
}


var res = new Array ();
for (var i=0; i<12; i++) {
 res [i] = 0;
}

for (var i=0; i<100000; i++) {
  res [calcBinominal(0, 2) + 5] += 1;
}

for (var i= 0; i<11; i++) {
  document.write (res[i]/1000);
  document.write (" ");
}
</script>


This results in

Code: Select all

0 0.001 0.111 2.032 13.955 67.745 13.887 2.171 0.098 0 0


So maybe there's a problem in your calculations?

What do you think?

Cheers,
Dietrich

[Kroah]

Some points:

- I don't understand why you say to not use Math.floor, since i've never used it. Even if you talked about the 'bug' in Math.floor, i've checked Math.round and it works correctly with negative numbers (Math.round (-0.4) gives 0 and Math.round (-0.6) gives -1).

- In your script, you floor the number instead of rounding it, i don't understand why, can you give me more informations? The 6502 code rounds the divisions when casting from fixed to int, it never truncates it (or i've missed it).

- If you change Math.floor with a Math.round (like in my first program), you get the 'good' result. I think it's the good one because it's the same as the result from the second program which computes all the possible distributions (and not a sample) and in this one.

- I think if you put a round up in your Java code, you should get the 'correct' result (Java seems to truncate when casting from float to int, doesn't it ?).

- I've corrected a minor bug i've done: Math.random chooses a number between [0; 1[ (0 inclusive, 1 exclusive). So to choose a number between [0; 255], the code must be: Math.floor (256*Math.random ())

If you can light me on those points, i could look deeper in my algorithms.
Thanks in advance,
Pascal

Edit: just to mention that my first program (translated from yours), computes a sample whereas my second program computes the exact probabilities by enumerating all possible combinations (beside an eventual bug).

[searle]

Ok, I must have been too tired or something obviously. Sorry for asking you rubbish questions. Anyway, i finally understood the subject and have a running version which produces the correct results:

Code: Select all

package mule;

import java.util.*;

public class Test {

   static Random random= new Random();
   

   static int calcBinominal(int value, int fluctuation) {

      if (fluctuation == 0) return value;

      int r= -6 * 255;
      for(int i= 0; i < 12; i++) {
         r += random.nextInt(256);
      }
      if (fluctuation == 1) {
         r >>= 1;
      }
      else if (fluctuation > 2) {  // For completeness, it never happens...
         r *= fluctuation - 1;
      }

      // Round, see $12AA
      if ((r & 255) > 128) r += 256;
      
      return value + r >> 8;
   }

   /**
    * @param args
    */
   public static void main(String[] args) {

      int[] res= new int[11];
      
      for (int i= 0; i < 10000000; i++) {
            res[calcBinominal(0, 2) + 5]++;
      }
      
      for (int i= 0; i < 11; i++) {
         System.out.print(" - ");
         System.out.printf("%.1f", res[i] / 100000f);
      }
      System.out.println();
   }
}


results:

Code: Select all

 - 0,0 - 0,0 - 0,6 - 6,2 - 24,3 - 37,9 - 24,3 - 6,2 - 0,5 - 0,0 - 0,0
 - 0,0 - 0,0 - 0,0 - 0,1 - 16,1 - 67,9 - 15,8 - 0,1 - 0,0 - 0,0 - 0,0


Thanx for your help!!!

Cheers,
Searle

P.S.: Price calculation and Land grant AI seem to work...
Sneak preview: http://www.mediafire.com/?8bzjykj111s

[Kroah]

Glad we've found the source of the problem.

Have a nice coding!
Pascal

[Kroah]

Could you attach the file to your post? I've put back file attachment.

Thanks!
Pascal

[searle]

Sure? It's 12 MB...

Cheers,
Searle

[Kroah]

Yeah, i've lot of disk space. But i hope uploading 11MB will not give a time out on the server. Let's see

PS: I'm unable to download from mediafire, dunno why. After the page is loaded and i click on start, i receive a timeout... tried several times.

[searle]

Got a 500 error..

Try this:
http://rapidshare.com/files/33141399/muledist.zip.htm

or that:
http://www.sendspace.com/file/cbpfae

Did it work? (Which one?)

Cheers,
Searle

[Kroah]

Rapidshare works great, thanks.

Nice work. I see you use JMonkeyEngine, good library.

Keep up coding and good luck!
Pascal