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[0]$.

——-

Discrete Math 101: Fun with Combinatorics – 2

3. ${n \choose k} = {{n-1} \choose {k-1}) + {{n-1} \choose k}}$

Our task is to select a team of k players from among n players. Now, we have 2 options – Either select player 1 to be part of the team, or leave him out of the team.

If we select player 1 to be part of the team, our task is reduced to selecting $k-1$ players from among $n-1$ players.

And if player 1 is not part of the team, our task is reduced to selecting $k$ players from among $n$ players.

Hence we have the above result.

———

4. ${n \choose k} = {{n-1} \choose {k-1}} + {{n-2} \choose {k-1}} + { {n-3} \choose {k-1}} + \ldots.$

Again our task is to select a team of k players from among n players – $P_1, \ldots, P_n$.

If $P_1$ is part of the team: We can select such a team in ${{n-1} \choose {k-1}}$ ways.

If $P_1$ is not part of the team, and $P_2$ is part of the team: The problem is reduced to selecting k-1 players from among n-2 players.

If $P_1$ and $P_2$ are not in the team, and $P_3$ is in the team: The problem is reduced to that of selecting k-1 players from among n-3 players.

Proceeding in this manner, we get the above result.

———–

5. ${n \choose k} = \frac {n}{k} {{n-1} \choose {k-1}}$

Again, we have n players at our disposal from among whom we wish to select a team of k players.

Say we select $P_1$ to be the 1st player in our team. (Note that the term “first” actually means nothing since we wish to select a “set” of objects and not an “ordered list”. However the usage of such terminology is useful for the purposes of exposition.)

Now, all we need to do is to select $k-1$ players from among $n-1$ players.

Now, let’s go back a step. What if we select $P_2$ to be the 1st player of the team, and select the remaining players for the team in ${{n-1} \choose {k-1}}$ ways.

We can see that we have n choices for the 1st player of a team.

Hence, we can select a team of k players in $n \times {{n-1} \choose {k-1}}$.

But again some teams are being repeated.

Given a fixed team, say T, we select that team k times (with each of the k players in the team being selected as the 1st player of the team). Hence we need to divide the previous result by k.

Hence we get the above result.

———-

Discrete Math 101 : Fun with Combinatorics -1

$n \choose k$ is the number of ways we can select k items from a group of n items. Say the number of players in India’s world cup squad is 14. Only 11 players can play in any particular match. Hence, on match-day, the coach has $14 \choose 11$ possibilities for selecting a team of 11 players from his squad. (Of course, such a situation is simply a theoretical conjecture, and no sane coach would actually list down each of $14 \choose 11$ possible teams and pick one from among them.)

We can easily derive some interesting results using the above meaning of $n \choose k$.

1. ${n \choose k} = { n \choose {n-k}}$

Our task is to select a team of k players from among n players. We can do this by directly selecting which players are to be part of the team, or by selecting which players are to be left out, giving the above result.

2. $n \choose k$ = $\frac { n! } {k! (n-k)! }$

Look at it this way. We have n players, say $P_1, \ldots, P_n$, and we want to select a team of k players from among them.

Let us select the players one by one.

For selecting the first player, we have n possible options.

Now having selected one player, we have n-1 possible options for selecting the 2nd player.

Similarly, given that we have selected i players, we have n-i options for selecting the i+1 th player.

Thus, we get that we can select k players from among n players in $n \times (n-1) \times (n-2) \times \ldots \times (n-k)$ ways.

But wait!

There are many repetitions in the teams of 11 players that we selected. Consider any particular fixed team of k players. That team is selected by us in $k!$ ways.

Therefore, we have: ${n \choose k} = \frac {n \times \ldots \times (n-k)} {k!} = \frac {n!} {k! (n-k)!}$.

——-

Note that given a list of k items, we can have k! permutations of those items. (This can be easily derived recursively.)

——-

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.

——–