What up dudes! First programming assignment has been completed. This was kind of a warm up exercise more than a challenging task, but there's always new tricks to be learned, so stay tuned. The assignment consisted of four (4) "simple" problems, and here is what they were all about:
1 - Polynomial Evaluation: You have a 5th-grade polynomial and would like to evaluate it in the fastest possible way. So, you ask yourself: what's the most expensive operation when you evaluate a polynomial? Exponentiation! Solution: instead of using expensive math operations like POW, we use Horner's Method and reduce the number of math operators to n multiplications and n additions. Therefore our evaluation ends up looking like this " ((((A5*x+A4)*x+A3)*x+A2)*x+A1)*x+A0 ".
2 - Vector Normalization: The most expensive operations in this method are the Square Root and Division by it. What can we do about them? Reduce the number of times they are used. First, we only execute the Square Root once and if the vector's components multiplication is greater than a threshold (to avoid precision problems), and second, we store in a temporal variable the result of diving 1 by the vector's magnitude and multiply each component by it, instead of dividing each one by the magnitude (reducing the number of divisions from 3 to 1).
3 - Double-Linked List Node Removal: This function removes a given node from a double-linked list, so the tricky part was covering the especial cases. As parameters for the function we received the pointer to the head of the list and the node to be removed. Probably the trickiest case is when the node to be removed is the head of the list, therefore to cover this case we passed a double-pointer to the head, that way we can modify where it actually points to. Aside from that, the rest is all about fixing the pointers of the previous and next nodes correctly, and freeing the memory of the removed node at the end (no memory leaks allowed for a code ninja).
4 - Minimum and Maximum Distance Calculation: Given an array of player positions, we want to calculate the minimum and maximum distance among them. As we mentioned before, calculating distance involves using Square Root, so the first possible optimization revolves around not using it too much, therefore we leave it for the end, we do all our comparisons using squared distances and just before returning the final values we calculate the Square Root of them. Another important improvement is to compare only once each pair of positions, so in the inner loop of the function we only iterate from i+1 to n (being i the iterator variable for the outer loop) instead of from 0 to n.
Well, I hope this was helpful. See you soon!
Adios!
