An Insight into Algorithm Design - Research Paper Example

? This report provides an insight into Algorithm design. Two Algorithms have been covered which include Euclid’s and stein’s Algorithm. The report covers basics (mathematical approach) about the algorithms, procedures of each and implementation advantages and disadvantages. The trade-off factors considered for either design in view of cost and time. Illustration data on implementation of Algorithms to aid decision making about the best Algorithm. The report covers technology advancement on testing and available testing tools. The main difference of Algorithms both circuit implementation, testing and results expected. Modern processors that perform calculations need Algorithm design for present and future programmers. The paper also explains some key terms as used in the text in relation to computer design. It covers the need to maintain optimal code for future programmers due to complexity of testing circuits. Key words: Euclid’s Algorithm, Stein’s Algorithm, Built-In-Self-Test and Linear Feedback Shift Register. Algorithm Design Review of steps involved in solving time complexity problems 1. Euclidean algorithm Euclidean algorithm is an ancient efficient method used in computing the greatest common divisor (GCD) of two integers. The simplest Euclid’s algorithm starts with two positive integers. This then form a new pair that consists of the smaller number and the difference between the smaller and larger numbers. The process repeats until the numbers are equal. The resultant number then is the greatest common divisor of the original two integers. Euclid algorithm is described as GCD(a, 0) = a GCD(a, b) = GCD(b, a mod b) If and b>0, then GCD(a, a) = a GCD(a, b) = GCD(a - b, b) ; if b < a GCD(a, b) = GCD(a, b - a) ; if a < b For example, GCD(20, 0) is 20. Similarly, GCD(20, 10) is same as GCD((20-10), 10) = GCD(10, 10) = 10. 2. Stein’s Algorithm This algorithm is also a binary GCD algorithm. It computes the greatest common divisor of two nonnegative integers (Purdy, 1983). It is more efficient over the ancient Euclidean algorithm because it replaces multiplication and divisions with shifts, which are cheaper when operating on the binary representation used by modern computers. This is critical on embedded platforms available that do not have direct processor support for calculations of division. Stein’s algorithm is described as GCD(0, v) = v GCD(u, 0) = u GCD(0, 0) = 0 When v and u are even, then GCD(u, v) = 2.GCD(u/2, v/2) For an even u and an odd v, then GCD(u, v) = GCD(u/2 v) Similarly, if v is even and u is odd, then GCD(u, v) = GCD(u, v/2) In case, v and u are both odd, and if u ? v, then GCD(u, v) = GCD((u – v)/2, v) In case, both are odd, and u < v, then GCD(u, v) = GCD((v – u)/2, u) When initially solving a problem, how might one detect that a solution needs extra attention with respect to an efficient algorithm vs standard solutions where a highly efficient solution may be indistinguishable from an inefficient one? Identification of a problem is the first step towards solving a given mathematical equation. It involves examining for complexity to be able to simplify before any other complex operations take place. Time requirements spell complexity and attention are hence worth considering. Built-In Self Test (BIST) Modern computers have a built in IC for testing. This technique integrates the functionality of an automated test system within a chip. It is a Design where testing is accomplished by the help of built in hardware features. BIST has test controller, response verification and test generator. Test generator is responsible for generating test address sequence that compares the output from memory with the expected correct data. The BIST controller can be either hardwired logic, microcode controller or based on processor (Rekha Devi, 2011). Specifically discuss the potential tradeoff between an easy to understand inefficient solution vs a difficult to follow efficient solution. By employing Linear Feedback Shift Register (LFSR), the Stein’s Algorithm replaces multiplication and normal division by shifts. LFSR is consisted of a circuit that is designed using flip-flops in series to each other. A feedback polynomial determines feedback taps that will define the length of the random patterns generated. Output of one flip-flop is connected to be input of the next flip-flop in-line. They are usually made from XOR gates (Ratnaprabha W.Jasutkar, 2013). It is important noting that, a well-chosen feedback function has the ability to produce a sequence of bits. These bits appear random and have very long cycle. LFSR achieves application in generating pseudo-noise, pseudo-random number, fast digital counters and other whitening sequences (Pavel, 2011). This is a cheaper method when operating on modern computers. With this register, the best parameters found are effective for finding GCD; this collectively reduces total time used in calculating greatest common divisor, which is why it has achieved high use in communication applications. DEVICE XC3S50 XC3S200 XC3S400 XC3S1000 No. of slices 807 825 825 825 No. of slice flip flops 16 16 16 16 No. of 4 input LUT’s 1613 1613 1613 1613 No. of bounded IOB’s 35 35 35 35 Total Equivalent gate count for design 13503 13503 13503 13503 Additional JTAG gate count for IOB’s 1680 1680 1680 1680 Power Consumption (milli-watt) N/a 37 56 92 Table 1: Euclid’s Algorithm of an 8-bit input data DEVICE XC3S50 XC3S200 XC3S400 XC3S1000 No. of slices 74 74 74 74 No. of slice flip flops 48 48 48 48 No. of 4 input LUT’s 131 131 131 131 No. of bounded IOB’s 22 22 22 22 Total Equivalent gate count for design 1395 1395 1395 1395 Additional JTAG gate count for IOB’s 1056 1056 1056 1056 Power Consumption (milli-watt) 24 37 56 92 Table 2: Stein’s Algorithm for an 8-bit input data From the table above, Euclid’s algorithm has many Look-Up-Table than Stein’s Algorithm. Euclid’s Algorithm has many gates compared to Stein’s Algorithm. Steins’ Algorithm consumes less power than Euclid’s Algorithm. Stein’s Algorithm fewer gates makes it better for implementing processors that calculates greatest common divisor. Terms from the table Slice: two slices makeup a CLB in a Spartan-II and Virtex families. This computer corresponds to basic fabrication of the logic in entire FPGA’s. Look-Up-Table: they help implement function generators in CLBs IOB: this is a collection or grouping of the basic components, which are made use of in implementing the input and output functions of four inputs. Writing an optimal code for future programmers Complexity has been increasing over time making it difficult to test circuits. Reduction of this problem associated with testing, addition of another IC along with it which will test and correct errors by itself. This should be backed-up by the desire to achieve high quality level, which is a trade-off with cost, and time involvement. This architectural design allows coding of the procedure to solve a problem. Yes, I would agree with writing an optimal code. It is easier to work around a code than theoretical implementation of a solution. References Pavel, E. (2011). High-performance Polynomial GCD Computations on Graphics Processors. High-performance Polynomial GCD Computations on Graphics Processors, 215-224. Purdy, G. (1983). Computers and Math. New York: Harvard University press. Ratnaprabha W.Jasutkar, S. D. (2013). Algorithm design. Comparative Analysis of Stein’s and Euclid’s Algorithm, 1-5. Rekha Devi, J. S. (2011). VHDL Implementation of GCD Processor with Built in. International Journal of Computer, 50-54. Read More