Wednesday 28 November 2012

Bike-riding & Math: My bike’s odometer makes me ‘crazy’

My bike’s odometer is not working properly. If all is well, it should get incremented properly to show the total distance that the bike travelled. It has five digits. Third digit from left stopped at ‘2’. By that time the first two digits (from left) were showing 4 and 8 respectively. As a result, the first three digits are not moving ahead from the figure ‘482’ even if the last two digits are working properly (I mean, last two digits getting incremented properly). This faulty meter is always running in the range: ‘48200’ to ‘48299’.

It reminds me about the decimal number system. What might be the logic behind the implementation of odometer’s functionality?
It has five digits. Each digit can take numbers from 0 to 9. Each digit gets incremented by one number starting from ‘0’ up to ‘9’ and returns back to ‘0’ after ‘9’. Each digit follows a cycle of 10 numbers (‘0’ to ‘9’ and back to ‘0’). When a digit reaches 9, and in the next instance, when it moves to ‘0’, its adjacent digit (digit at its immediate left) gets incremented by 1. This logic seems okay for all the digits except for the left most one as it doesn’t have a digit to its left. For the extreme left digit, when the turn comes that it moves from 9 to 0, all the other four digits also change to ‘0’ (by that time all those digits show 9’s), such that the meter gets reset and all-zeroes figure appears. It can be explained in a better way like this: When the magic figure 99999 appears on the meter, the next turn is initiated from the right most digit. The right  most digit changes from ‘9’ to ‘0’ and initiates movement of second-right digit from ‘9’ to ‘0’, which triggers third-right digit to change to ‘0’, which very action triggers fourth-right digit to change to ‘0’ and all this cascading effect triggers finally the fifth-right (or left-most) digit to change to ‘0’. In all, the range of the meter is from ‘00000’ to ‘99999’.

That’s fine. But the odometer continues to haunt me. It reminds me about the frequency with which each digit changes. In the meter’s overall journey from 00000 to 99999, how many times does the left-most digit change? What about the right-most digit?

The key lies in the very fact that “when each digit completes its full turn of 10 levels (0-to-9) and changes from 9 to 0, its immediate-left digit changes by 1 level”.  Here I stress upon the usage of numbers 10 and 1. I can say it in the other way like this: “By the time a digit turns up 1 level, its immediate-right digit turns by 10 levels”. So if the frequency of a digit is ‘f’ then the frequency of its immediate right digit is ‘10f’.

Now let us start with the left most digit. By the time meter runs from 00000 to 99999, the left most digit runs through its full turn (ie, from 0 to 9) by one time. So if we define ‘frequency’ as ‘number of times a digit changes through’, the frequency of left most digit can be taken as ‘10’. From then on we can easily calculate the frequencies of other successive digits by simply going for successive 10-multiples. The frequency of second-left digit is 10*10=100, that of third-left digit is 1000, that of fourth-left digit is 10000 and that of fifth-left (or right-most) digit is 100000.

If all is well, by the time my bike completes ‘99999’ kilometres of journey, the right most digit of odometer completes ‘100000’ turns.

When you go for next ride and when you casually look at the odometer, I hope it would not make you think about all this and that and go crazy.

Happy bike riding... 

Sunday 18 November 2012

Math @Work: Importance of 'weightage' in finding averages

I have come across the concept of ‘score card’ for employees in an organization. It is an employee performance-assessment tool. Each employee’s work is categorized in to some parts and each part is given some weightage depending on its significance. The employee is allotted with a score in each part of the work depending on his performance in that work. Part-wise performance-percentages and overall performance-percentage are calculated and based on these parameters, his salary-hike is decided for the coming fiscal. Can we take the average of all the part-performance percentages to get the overall-performance figure?

Let us consider the following scenario:

The deciding parameters are Work Efficiency, Punctuality, Analysation skills and Problem solving skills each having equal weightage of 25%. And an employee has got the following scores:
Parameter
Weightage
Employee score
Part %
Work efficiency
25
20
80%
Punctuality
25
25
100%
Analyzation skills
25
15
60%
Problem solving skills
25
20
80%

The overall performance can be calculated straight-away like

Total score achieved by employee/ total max. Score = (20+25+15+20)/(25+25+25+25)

= 80%
I can also find it by taking average of part percentages:
(80+100+60+80)/4 = 320/4 = 80%
Now I change the weightages allotted to the parameters like this:
Parameter
Weightage
Employee score
Part %
Work efficiency
50
40
80%
Punctuality
20
20
100%
Analyzation skills
10
6
60%
Problem solving skills
20
16
80%
Overall performance % = (40+20+6+16)/(50+20+10+20) = 82%
But if I do it by taking average of individual percentages, I will get (80+100+60+80)/4 = 320/4 = 80%
Where has it gone wrong?
Here comes the concept of weightages. I need to take care of the weightage of each part. In the first problem, the weightage given to each part is 25 and hence weightage fraction for each part is 25/100 = ¼. So when I say that the overall average is (80+100+60+80)/4, it really meant this:
“(1/4)*80 +(1/4)*100 +(1/4)*60 +(1/4)*80” Here I multiply the part-percentages with the respective weightage.
Coming to the second problem, the weightage for the first part is 50/100 = ½, weightage for second part is 20/100 = 1/5, weightage for third part is 10/100 = 1/10 and weightage for fourth part is 20/100 = 1/5.
So the overall-performance = (1/2)*80 + (1/5)*100 + (1/10)*60 + (1/5)*80 = 40+20+6+16 = 82%

Monday 5 November 2012

Programming &Math: Wherever you go, “number theory” follows....

I was in to a perl script and some part of my code required this logic:
For a particular mobile number, if data (customer name, address etc) is available in MySQL table and if image (scanned application form) is also available in the server, then display data and image. If data is available and image is not available, then display data. If data is not available and image is available, then display nothing. Here the point is more precedence is given for ‘data’.
Algorithm:
If(data is available)
{
if(image is available)
Display ‘data’ and ‘image’
Else
Display ‘data’
}
Else
                                    {
                                    // no action
                                    }
This is the simple algorithm for the program.
I want to relate this to a mathematical model. Let us assume a simulator which assigns values to two variables X and Y and adds them up. This assignment depends on the availability of ‘data’ and ‘image’ respectively. The default value of X and Y is ‘0’.
If ‘data’ is available, then X can be assigned ‘2’ and if ‘image’ is available, then Y can be assigned ‘1’. Here as I have more precedence for ‘data’, I design the simulator to assign a higher value (ie ‘2’ as against ‘1’ which is assigned to Y if ‘image’ is available).
Now the simulator adds up X and Y and depending on the Sum, it decides which is to be displayed. If Sum is ‘3’, then both ‘data’ and ‘image’ are displayed. If the Sum is ‘2’, then only ‘data’ is displayed. If the Sum is ‘1’ or ‘0’, then nothing is displayed.
Now to design a circuit for this logic, I need to talk in ‘binary’ language (0’s and 1’s):
Default value of X and Y is binary ‘00’. If ‘data’ is available, then X can be assigned ‘10’ and if ‘image’ is available, then Y can be assigned ‘01’. If Sum is ‘11’, then both ‘data’ and ‘image’ are displayed. If the Sum is ‘10’, then only ‘data’ is displayed. If the Sum is ‘01’ or ‘00’, then nothing is displayed. We can implement the whole thing with some logic gates (like a ‘Full Adder’ or whatever it may be). I don’t want to go more in to the circuit designing stuff.

Coming back to the mathematical model, let us extend the logic to three variables with three different weightages. If we assign weightages 1,2,3 to X,Y,Z then the possible outcomes are:
X
Y
Z
Sum
0
0
0
0
0
2
0
2
0
0
3
3
0
2
3
5
1
0
0
1
1
2
0
3
1
0
3
4
1
2
3
6

But there is an ambiguity here. Sum is same for two different scenarios (0,0,3) and (1,2,0). So we can’t assume 1,2,3 for X,Y,Z. Then what else...
Let us try with 1,2,4...
X
Y
Z
Sum
0
0
0
0
0
2
0
2
0
0
4
4
0
2
4
6
1
0
0
1
1
2
0
3
1
0
4
5
1
2
4
7
Yes, here it works.
Now if we have four variables, then what is the sequence of weightages a circuit designer considers?
We can easily guess...
“1,2,4,8” – this gives all possible 16 combinations (0 to 15).
I say it again.....
Wherever you go, “number theory” follows.....

My cousin Mr.Aditya, a chip designer commented like this:
"When implemented in hardware though we do it somewhat differently. When we want to implement a priority encoder like this, we usually come up with a truth table first and minimize the terms using a karnaugh map."

A chip designer would not worry about assigning priorities. He depends on truth table and k-map to arrive at appropriate Boolean expression. What are these truth table and  k-map doing here???
Truth table maps the inputs into either 0-to-3 or 0-to-7 or 0-to-15 etc... possible values and assigns one out put (0 or 1) to each input. K-map arranges the output values (0's or 1's) of truth table into cells (each cell corresponds to one possible input combination) arranged in a mesh-form of size 2X2 or 2X4 or 4X4 etc.. So, every time, the total number of cells in the k-map is either 4 or 8 or 16 etc...
My insistence on importance of "number theory" originates exactly from here. If I take 1,2,3 as inputs, I can have the following possible sums: 1, 2, 3, 4(1+3), 5(2+3) and 6(1+2+3). For three inputs we have six outputs. 
But if we consider 1,2,4 as inputs, we can have the following possible sums:  1, 2, 3(1+2), 4, 5(1+4), 6(2+4) and 7(1+2+4). For three inputs here we have seven outputs. And this advantage is more clear  as the number of inputs increases. If I consider 1,2,4,8 as inputs, I can have all possible values from 1 to 15. Using binary logic in truth-table & k-map concept naturally takes this advantage as 1,2,4,8,16,... are the respective place-values of the binary-system.
Relating this to our discussion of assigning priorities... Is not the k-map internally assigning 1,2,4 priorities to X,Y and Z terms respectively???