Category Archives: Mathematics

Mathematics in web pages

Online editors:








Full Binary Tree Theorem


The theorem

Let T be a nonempty, full binary tree.

The theorem claims that the number of nodes N, the number of leaves L, and the number of internal nodes I are related in such a way that if you know any one of them, you can determine the other two. Continue reading Full Binary Tree Theorem


Gambler’s fallacy


Continue reading Gambler’s fallacy


Generate random weighted variables

In this post I describe the common problem how to generate random weighted variables. For example you have a die with 6 faces that is fixed, so the probability of an 1 is not the same with the probability of a 2 etc.

The table below shows an example:

Face Probability
1  25
2  25
3  20
4  20
5  5
6  5

One easy solution is to reduce the problem to another one with a die with 100 faces that is not fixed.

You generate a random value from 0-99 that follows the uniform distribution. Do not use the modulo function to do that. See this post instead.

Once you have that value you perform the following steps:

You check the space within which that value relies.

  1. between 0 and 24, you generate 1 as the weighted variable
  2. between 25 and 49, you generate 2 as the weighted variable
  3. between 50 and 69, you generate 3 as the weighted variable
  4. between 70 and 89, you generate 4 as the weighted variable
  5. between 90 and 94, you generate 5 as the weighted variable
  6. between 95 and 99, you generate 6 as the weighted variable





Generate uniformly distributed random variables

Formulas shown below generate values that follow uniform distribution.

Using simple modulo methods is not considered as a good solution (although used a lot by students) as the module function does not generate all the variables with the same frequency.

Random integer between [ 0, 1 ]

int r = (int) (rand()/(RAND_MAX + 0.0));

Random integer between [ 0, 1 )

int r = (int) (rand()/(RAND_MAX + 1.0));

Random integer between [ 0, N ]

int r = (int) (N * (rand() / (RAND_MAX + 0.0)));

Random integer between [ 0, N )

int r = (int) (N * (rand()/(RAND_MAX + 1.0)));

Random integer between [ M, N ]

int r = (int) (Μ + (rand()/(RAND_MAX + 0.0))*(N-M+1));

Random integer between [ M, N )

int r = (int) (Μ + (rand()/(RAND_MAX + 1.0))*(N-M+1));


The general formula is:

int r = (int) (A + (rand()/(RAND_MAX + C))*B);

Values of M, N, K are shown in the following table:

Range A B  C
 [ 0, 1 ]  0  1  0.0
 [ 0, N ]  0  N  0.0
 [ M, N ]  M  N – M + 1  0.0
 [ 0, 1 )  0  1  1.0
 [ 0, N )  0  N  1.0
 [ M, N )  M  N – M + 1  1.0

Generating values of normal distribution – Marsaglia method

Assuming you can already produce variables of uniform distribution, you can produce variables of normal distribution using various formulas. Two of the most important are:

  1. Box–Muller method
  2. Marsaglia polar method

Most methods are based on Box-Muller method.

The Marsaglia method is my favorite since it does not require using sin() or cos() functions and the steps are very easy to implement.

Here is a sequence of the steps:

  1. Generate a value that follows uniform distribution in any space you want (eg: [ 0 , 1 ))
  2. Map that value to space (-1, +1) and assign it to variable U
  3. Repeat steps 1 and 2 and assign the result to variable V
  4. Calculate S = U*U + V*V
  5. if S = 0 or S >= 1 then free all variables if needed and restart from the beginning
  6. The following two variables will be independent and standard normally distributed (mean = 0, variance = 1):


Optionally you can add m to the quantities above to change the mean value of the distribution.



Color Cube





Distance between point and rectangular box without case logic

Assuming you have a point (x,y) and a rectangle parallel to x and y axis defined by its upper left and lower right corner. How can we calculate its distance without using case logic?

P = (x,y)
A = { (x1,y1), (x2,y2) }

The answer is:

dx = max(A.x1 - p.x, 0, p.x - A.x2)
dy = max(A.y1 - p.y, 0, p.y - A.y2)
distance = sqrt(dx*dx + dy*dy)

Its very tricky.

Here is a great analysis here by MultiRRomero:


Determine if two rectangles intersect without case logic

Assuming you have two rectangles A and B that exist parallel to the x and y axis and are defined by their upper left (x1,x2) and lower right corners (x2,y2). How can you calculate if A and B intersect without using case logic?

A = { (x1,y1), (x2,y2) }
B = { (x1,y1), (x2,y2) }




The answer is:

if (A.x1 < B.x2 && 
    A.x2 > B.x1 &&  
    A.y1 < B.y2 && 
    A.y2 > B.y1) {
  then A and B intersect

There is a great analysis here:

And an awesome interactive visualization by Matthew Crumley here: