Numerical computations in C++ : Converting from Decimal to Binary

Converting from decimal to binary notation is fairly standard and straightforward.

Let’s say we need to find the binary representation of $100_{10}$.

The method that most of us would have been taught in school is the following:

– Divide 100 by 2. You get 50, with remainder = 0. Write 0.

– Divide 50 by 2, to get 25 and remainder = 0. Write 0.

– Divide 25 by 2 to get 12 and remainder = 1. Write 1.

– Continue doing so until the number (which is 25 at present) becomes 0.

– The binary representation of 100 is the reverse of what you have written.

——

We can write a recursive function to compute the binary representation of a decimal number. Using the power of recursion, we can avoid having to reverse the output as is necessitated by the above method.

——-

// Function dec_to_bin outputs the binary equivalent of the decimal number n.

void dec_to_bin ( int n)

{

if ( n < 0)

{

cout << “-“;

n = -n;

}

if (n == 0)

return;

dec_to_binary (n/2);

cout << n%2;

}

——–

dec_to_bin will take time proportional to the number of bits in the binary equivalent of n.

——–

Numerical computations in C++ : Converting from Decimal to Binary – 2

Earlier we looked at a recursive method for conversion from decimal to binary. We can also achieve the conversion in an iterative manner, however adding to the task the additional overhead of reversing the answer that we obtain.

The underlying method is the one discussed at the beginning of the previous post. At each iteration, we divide a number by 2 and store the corresponding remainder in an array. At the end of the process, we reverse the contents of the array.

Now, we are faced with a small problem. How do we know what the size of our array should be? Fortunately, we can proceed without knowing that, using the resizeable vector container class. (A vector is like a dynamic array. We need not specify its size at the time of definition.)

In order to reverse the vector, we can simply use the reverse algorithm defined in the algorithm header. Or if we simply want to output the binary representation (without needing to store it anywhere), we may simply use a reverse_iterator to iterate through our vector.

———–

// function dec_to_bin outputs the binary equivalent of the decimal input n.

#include <iostream>

#include <vector>

using namespace std;

void dec_to_bin ( int n )

{

vector <int> v; // vector of ints to store the binary representation.

int temp = n;

if ( n < 0)

temp = -n;

while ( temp != 0)

{

v.push_back (temp%2);

temp / = 2;

}

vector<int> reverse_iterator i;

if ( n < 0)

cout << ” – ” ;

for ( i = v.rend ( ); i != v.rbegin ( ); ++i)

cout << *i;

}

——-

If we used a list or a deque instead of a vector, we wouldn’t be faced with the task of having to reverse the values computed by us. We can do this by storing successive numbers that we generate at the front of the data structure instead of at the end.

We may do that using the push_front member function for lists and deques. (Note that we cannot use push_front for a vector. We can only insert and delete elements (efficiently i.e. in constant time) at the back of a vector.)

——

The above program using a deque along with push_front would look as follows:

——

#include <iostream>

#include <deque>

#include <algorithm>

using namespace std;

void dec_to_bin ( int n )

{

deque <int> v;

int temp = n;

if ( n < 0)

temp = -n;

while (temp != 0)

{

v.push_front ( temp%2);

temp /=2;

}

if ( n < 0)

cout << “-“;

copy (v.begin( ), v.end ( ), ostream_iterator<int> (cout,””);

}

——-

Instead of using an iterator to iterate through the deque, we can use the copy algorithm defined in the header algorithm to directly output the contents of the deque. (Note that the statement #include <algorithm> though written as part of the above program is not necessary, since algorithm.h automatically gets included when we write #include <deque>. )

——-

Numerical computations in C++ – Exponentiation by repeated squaring

Let’s say that we have to compute the power of a number without using the inbuilt pow function. We can compute the answer using the method of repeated squaring.

Firstly, we assume that the exponent is an integer.

For example. let us compute (13.5)^5.

Now, we know that 5 is 101 in binary notation.

Hence, what we need to compute is $13.5^4 \times 13.5^0 \times 13.5^1$

We also observe that $13.5^4 = (13.5^2)^2$ and that $13.5^2 = (13.5^1)^2$.

From these observations, we can deduce that repeated squaring of $13.5$ and multiplication of the appropriate intermediate results would lead us to the desired answer. (i.e. Compute $13.5^1, 13.5^2, 13.5^4$ and take the product of $13.5^1$ and $13.5^4$.)

Here, prior to the repeated squaring, we calculated the binary representation of the given exponent. We need not necessarily do that. We can do the squaring and the computation of the binary representation simultaneously.

———

Here is a C++ code fragment to illustrate that:-

//function f takes a computes x^e (where e >= 0)  and returns a long value.

long f (int x, int e)

{

int temp = e, rem; //rem stands for remainder.

long answer = 1, term = 1;

while ( temp != 0)

{

term = term * x;

rem = temp%2;

if (rem == 1)

{

}

temp / = 2;

}

}

——–

If we assume that all arithmetic operations take O(1) time, then the above function takes O(n) time where n represents the number of bits in the binary representation of the exponent, e.

———

Dynamic programming – Probability, gambling and a die

Let’s say we have a fair 6-sided die. Player A can earn money based on what shows up when the die is rolled. The rule of the game is as follows: Player A will roll a die upto 3 times. After each roll, Player A has two choices: (1) He can take money in dollars equal to the number showing on the upturned face of the die. (i.e. if 5 shows on the die, he can take $5.) In this case, the die is not rolled any more, and the game ends. (2) He can decide to discard this roll of the die, and decide to roll the die again. Note that the die can be rolled at most 3 times. Question — What is the expected payoff for Player A? ——– Let’s say that instead of 3 rolls of the die, the game allowed only for 1 roll. What is the expected payoff for Player A in this case? It is clearly equal to the expected value of the number that shows up when the die is rolled. And since the die is fair, this expectation is equal to $(1 + 2 + 3 + 4 + 5 + 6)/6 = 3.5$. And Player A has no choice but to accept whatever shows up on the die because there is only one roll possible. Hence, in this game, the expected payoff for Player A is$3.5.

Now, consider what happens if instead of 1 roll, we allow for upto 2 rolls.

Now, if the 1st roll is a 6, obviously Player A would pocket $6 and decide to end the game there itself. Also, if the 1st roll is a 1, Player A can always decide to roll again [because irrespective of what shows up on the 2nd roll, it cannot be less than$1, and hence Player A has nothing to lose by deciding to discard the 1st roll and opting to roll again.]

Now consider what happens if the 1st roll is a 3. Now, Player A is faced with a predicament. What should he do? Should he decide to stop there and go home with $3, or should he discard this 3 in the hope of higher returns in the 2nd and final roll? This is where having learnt probability well in school helps. We know that the expected value of the number that shows up when the die is rolled once is 3.5. Hence, if in the 1st roll, Player A gets a number greater than 3.5 i.e. either 4, 5 or 6, he can decide to stop there and take the corresponding amount of money. However, if he gets either 1, 2 or 3 in his 1st roll, he should discard that, and decide to roll again, because the expected value of the 2nd roll is 3.5. Hence, the expected payoff for Player A from a game which allows for at most 2 rolls is: $\frac{3}{6} 3.5 + \frac {1}{6} 4 + \frac{1}{6} 5 + \frac{1}{6} 6 = 4.25$. (Here, $3/6$ is the probability of getting a 1, 2 or 3 on the 1st roll, in which case the expected payoff becomes 3.5. ) ——- Now, coming back to our original game, we can decide as to how we should proceed after the die is rolled once. We know that the expected payoff from 2 rolls of the die is$4.25.

Hence the strategy of Player A should be the following:

– If the 1st roll of the die yields either a 5 or a 6, take the money, and end the game.

– Else, discard the 1st roll, and continue the game.

The expected payoff can be computed easily based on the preceding observations:

Expected payoff for Player A = $\frac{4}{6} 4.25 + \frac{1}{6} 5 + \frac{1}{6} 6 = \frac {14}{3}$.

———-

This is a classic question using the principle of dynamic programming. Let’s say the the game allows for the die to be tossed upto $n$ times.

Let $E[k]$ denote the expected payoff for Player A in a game that allows upto $n-k$ rolls of the dice.

The strategy for Player A after roll $k$ should be the following:

— If the number showing on the dice is greater than $E[k]$, take the money and stop the game.

— Else, discard that roll, and decide to continue on to the next roll.

——-

The recurrence relation for computing the $E[k]$ values can be derived in terms of $E[k+1]$ as was done in the case of the 3-roll example that we saw earlier. Once we have done that, we can calculate the values in the order, $E[n-1]$, $E[n-2]$ and so on uptil $E$.

——-

Probability and Stochastic processes – Gambler’s ruin problem

Let’s say there are 2 tennis players, A and B. Now, A is a better player than B and hence wins 2/3 of the matches that they play. However, they don’t just play tennis – they also gamble on the results. Initially, let’s say that A has $1 and B has$2. The rule is that whoever loses a tennis match must give $1 to the other. They keep on playing tennis matches until one of them becomes bankrupt, at which point they stop. What is the probability that B will become bankrupt? —— We note that whatever handing over of the money takes place between A and B, the total amount of money remains constant at$3.

There are 4 possible states —

State 0 — A has $0 State 1 — A has$1

State 2 — A has $2 State 3 — A has$3.

(Note that the amount of money that B has, in each of the above states, is completely determined by simply stating the amount of money with A since the total amount of money remains constant.)

We get the following transition diagram with probabilities depicted besides the arrows. The probability that we wish to compute is the probability of reaching State 3 starting initially at State 1.

We can compute that quite easily. Let $p_{i}$ denote the probability of reaching State 3 from State $i$.

We directly get the following from the above transition probabilities — $p_2 = \frac{2}{3} + \frac{1}{3} p_1$ $p_1 = \frac{1}{3} p_0 + \frac{2}{3} p_2$. $p_0 = 0$.

——-

Therefore, our desired probability, $p_1 = 4/7$, which means that there is 4/7 probability that the series of tennis matches would end with B becoming bankrupt.

——–

Probability – Monty Hall problem

Our friend Monty Hall is a game show host. Every week he asks one person from his audience to come onto the stage. On the stage are 3 closed doors. Behind one is a brand new car, and behind the other 2 are goats. The car is equally likely to be behind any of the 3 doors. The contestant selected from the audience obviously wants to win the car.

Monty Hall explains the rules of the game to the contestant — In front of you are 3 closed doors. Behind one of them is a car, and there are goats behind the other 2. I know what is behind each door. Your first task is to select a door.

Our contestant selects door 1.

—-

Monty now again starts expounding on probability — You have selected door 1. Now, I will select either door 2 or 3 to open. Note that I know what is behind each of the doors. I will decide which door to open based on the following rules:

– If door 2 has a car behind it, I will open door 3.

– If door 3 has a car behind it, I will open door 2.

– If neither of the above conditions hold true, i.e. both doors 2 and 3 have goats behind them, I will randomly select one among these 2 doors with probability 0.5 and open that door.

—-

Now, having explained thus to our contestant, the omniscient Monty goes and opens door 3, and reveals to the world (including our contestant) the goat standing behind it.

—-

Now, Monty turns to the contestant for the endgame and speaks thus — As you can can see, door 3 has a goat behind it. Doors 1 and 2 are still closed. Whichever door you select, you will get whatever is behind that door. You can either decide to stay with your original choice i.e. door 1, or you could decide to switch i.e. select door 2. What do you want to do — stay or switch?

As the music in the recording studio rises to a crescendo, our dear contestant is faced with this question on probability to answer. What should he do?

————

At first glance, it does seem that it is immaterial as to what the contestant chooses. One could argue that there are 2 doors (doors 1 and 2) one of them having a goat behind it, and the other having a car behind it. The car is equally likely to be behind either of the 2 doors. So, the contestant could as well flip a fair coin, and choose which door he wants to go with.

—-

However there is a flaw in the above reasoning.

— The probability that there is a goat behind door 1 is 2/3, and the probability that there is a car behind door 1 is 1/3.

To see why this is so, consider the following argument — Initially there were 3 doors. Two of them had goats behind them and one of them had a car behind it. Door 1 was one among these 3 doors. Therefore, the probability that door 1 has a car behind it is 1/3 and the probability that it has a goat behind it is 2/3.

Now, you could argue against the above explanation this way : ” What you said about the probability of a car being behind door 1 being 1/3, and that probability of a goat being behind door 1 being 2/3 was true initially, and not after Monty went and opened door 3, and showed everyone the goat standing behind it. Once Monty did that, we were left with 2 doors, and 1 goat and 1 car, and hence the probability that there is a car behind door 1 is 1/2 and the probability that there is a goat behind door 1 is also 1/2.”

But again, the argument that you presented above is not wholly correct. We can see it this way — we agree that initially i.e. before Monty opened door 3 and showed a goat behind that, the probability of these being a car behind door 1 is 1/3. My claim is that this remains the same even after what Monty did.

To better understand that, consider the following situation —

Assume that there are 100,000 doors instead of just 3. Also, behind 99,999 of these doors are goats and behind a single one is a car. The car is equally likely to be behind any of the 100,000 doors. So, what we have here is a 100,000-door version of Monty’s 3-door problem.

Now, you select a door, say door 385.

Now, Monty has been asked to open 99,998 doors, i.e. he has been asked to keep 2 doors closed. It is also specified in the rules that one of these closed doors should be door 385 since that was the one you selected. Further, Monty knows what is behind each of the doors, and Monty has been specifically instructed that the 99,998 doors that he opens should all reveal goats behind them.

So Monty goes and opens 99,998 doors. He leaves door 385 and one other door, say door 6724 closed. Now, as we said earlier, behind each of the 99,998 doors that Monty opened, was a goat.

Now, what do you think is the probability that there is a goat behind your selection door 385?

It is 1/100,000 and not 1/2.

The reason as to why door 385 remained closed even when just 2 doors remained (i.e. 385 and 6724) was because Monty had been instructed not to open 385 as part of the rules.

There is 1/100,000 probability that door 385 contained a car behind it, and Monty selected door 6724 uniformly at random from the remaining 99,999 doors for keeping closed. In such a situation, staying with your original selection (i.e. door 385) would win you the car.

However, it is much much more likely (99,999/100,000) that your initial selection (385) had a goat behind it, and that Monty knowing that 6724 had a car behind it, opened the remaining 99,998 doors. In this situation, switching (i.e. selecting door 6724) would get you the car.

—-

Coming back to our 3 door version, we can argue that switching would win you the car with probability 2/3, while staying with your original selection would get you the car with a probability of 1/3.

Hence, one who has a working knowledge of probability should advise the contestant to switch.

Probability and Statistics – 1 : coin flips

Question 1. I toss a fair coin until I obtain Heads. How many times am I expected to toss the coin (this number includes the coin toss which resulted in the Head)? What is the variance of the number of coin tosses?

Solution. This is exactly the geometric distribution with p = 0.5. Hence, I am expected to toss the coin 1/p = 2 times.

We can derive it as follows:

Let $X$ be the random variable denoting the number of coin tosses.

If we get a H in the 1st toss, we are done. —- $Pr [ X = 1 ] = 1/2$. ( the probability is 1/2 since it is a fair coin.)

For us to have $X = 2$, the 1st toss must result in a T, and the 2nd in a H. —- $Pr [X=2]=0.5^2$.

Similarly, $X = 3$ only if we get the sequence T T H in our 1st 3 coin tosses. —- $Pr [ X = 3] = 0.5^3$.

Thus, we have that, $E [ X ] = 1 \times 0.5 + 2 \times 0.5^2 + 3 \times 0.5^3 \ldots$ $\Rightarrow 0.5 E[X] = 0.5^2 + 2 \times 0.5^3 + \ldots$

Subtracting the 2nd equation from the 1st, we get: $0.5 E [X] = 0.5 + 0.5^2 + 0.5^3 + \ldots$ $\Rightarrow E[X] = 2$.

—-

Variance of X: $Var (X) = E[X^2] - (E[X])^2$

We have that, $E[X^2] = 1 \times 0.5 + 4 \times 0.5^2 + 9 \times 0.5^3 + \ldots$ $\Rightarrow 0.5 E[X^2] = 0.5^2 + 4 \times 0.5^3 + 9 \times 0.5^4 + \ldots$

Subtracting the 2nd equation from the 1st: $0.5 E[X^2] = 0.5 + 3 \times 0.5^2 + 5 \times 0.5^3 + \ldots$ $\Rightarrow 0.25 E [X^2] = 0.5^2 + 3 \times 0.5^3 + \ldots$ $\Rightarrow 0.25 E[X^2] = 0.5 + 2 (o.5^2 + 0.5^3 +\ldots)$ $\Rightarrow E[X^2] = 6$.

Therefore, $Var (X) = 6 - 4 = 2$.

—–

Question 2.I toss a fair coin until I get either HH or TT. Let X be the number of coin tosses I make. Find E[X].

Solution.

The 1st coin toss can result in either a H or a T. If we are given that X = k, then the remaining k-1 coin tosses are uniquely determined given the result of the 1st toss. The fixed sequence occurs with probability $0.5^{k-1}$.

Thus, we have that, $E [X] = 2 \times 0.5 + 3 \times 0.5^2 + 4 \times 0.5^3 + \ldots$

Solving, we get, $E[X] = 3$.

—-