Tuesday, November 23, 2010

[DSA] General Maths Algo

Long long long time ago.....
Programs are written in C++ to solve mathematical problem, not much of user click here and there on the GUI. Mathematical problem can range from calculating relative distance, trajectory etc.

To make life simple, there was "math.h" in C(include math in c++) to help make the calculation. "math.h" alone might not be sufficient to cover each and every possible scenario, hence some programmer do have their custom class to do the math related to their program.

We have studied general maths routine such as converting from decimal to binary (d2b) and at least 2 method to calculate Greatest Common Divisor(GCD). Through the d2b function, we learned how to decompose the "steps" to get the binary from the decimal and translate the "steps" it into code.

The direct application of the GCD I could thought of is the computation of the public key and private key pairs in the RSA algorithm (http://en.wikipedia.org/wiki/RSA). Encryption is as simple as calling a function (java and C++ have the library), but behind the function call, these are the necessary code to calculate the key pairs.

Notice there are 2 possible way of programming the GCD, through the recursive method or the iterative method which we have discussed previously. Is it easier to understand the recursive code then the iterative code???




Below are the questions for the week.
IP address in the form of A.B.C.D, where each octet A,B,C,D range from 0 to 255 in decimal.
1. How many bits each octet hold?
2. What are the "steps" required to convert one octet to binary?
3. Write the function that would convert the IP and gives it equivalence in binary.


note: you could modify from the d2b function, or propose a simpler algorithm based on the characteristic of the IP address's octet

No comments: