StudentShare
Contact Us
Sign In / Sign Up for FREE
Search
Go to advanced search...
Free

An Insight into Algorithm Design - Research Paper Example

Cite this document
Summary
This paper 'An Insight into Algorithm Design' tells us that the Euclidean algorithm is the efficient method used in computing the GCD of two integers. The Euclid algorithm starts with two positive integers. This then forms a new pair that consists of the smaller number and the difference between the smaller and larger numbers…
Download full paper File format: .doc, available for editing
GRAB THE BEST PAPER94.5% of users find it useful
An Insight into Algorithm Design
Read Text Preview

Extract of sample "An Insight into Algorithm Design"

? 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
Cite this document
  • APA
  • MLA
  • CHICAGO
(“Algorithm design as it relates to time complexity problems like Research Paper”, n.d.)
Algorithm design as it relates to time complexity problems like Research Paper. Retrieved from https://studentshare.org/information-technology/1493609-algorithm-design-as-it-relates-to-time-complexity
(Algorithm Design As It Relates to Time Complexity Problems Like Research Paper)
Algorithm Design As It Relates to Time Complexity Problems Like Research Paper. https://studentshare.org/information-technology/1493609-algorithm-design-as-it-relates-to-time-complexity.
“Algorithm Design As It Relates to Time Complexity Problems Like Research Paper”, n.d. https://studentshare.org/information-technology/1493609-algorithm-design-as-it-relates-to-time-complexity.
  • Cited: 0 times

CHECK THESE SAMPLES OF An Insight into Algorithm Design

Efficiency of Clustering Algorithms for Mining Large Biological Data Bases

This paper ''Efficiency of Clustering Algorithms for Mining Large Biological Data Bases'' discusses that using Pro-PAM algorithm based on partitioning clustering techniques in the place of alignment methods in large data sets, increases efficiency and reduces execution time significantly.... The analysis highlights the weakness and shortcomings of the four and proposes a new algorithm based on the shortcomings of the four algorithms.... Consequently, local alignment algorithm proposed by Waterman and Smith (Bolten et al....
10 Pages (2500 words) Research Paper

Web Services. Design Patterns

DQ2: Other design Patterns This week we discussed and implemented the MVC design pattern for Web based database interfaces.... Find another design pattern which could be used for web based development and write a synopsis on it, pointing out whether it would be applicable for use within your project or not.... Comment as applicable on design patterns that other class membersprovide.... “A design pattern points to an issue that can take place repeatedly in a programming environment, and then points out the idea of the way out to that issue....
3 Pages (750 words) Essay

Fundamentals of Cryptology

Cryptography involves the design, creation, and implementation of cryptosystems (Bauer 2006).... This research proposal "Fundamentals of Cryptology" presents the basic functioning of ciphers because mostly ciphers fail because of improper and rushed use.... In this regard, it is important to note that for a cipher to work properly it is important to invest in resources....
8 Pages (2000 words) Research Proposal

Iris recognition system using principal component analysis

Project design 3.... Hardware design 3.... Software design 3.... Iris recognition system using principal component analysis Abstract Iris recognition has been a challenge in the past with the recognition accuracy being low.... This project has implemented an iris recognition system using image processing....
60 Pages (15000 words) Dissertation

Data Mining Process and Algorithms

For example – in the case that the algorithm –in the case of a database that contains millions of records, shows linear or close to linear time complexity, which demonstrates that the reliability of the algorithm is high.... The reliability of the algorithm can be determined throug...
5 Pages (1250 words) Essay

Discrete Mathematics and Mathematical Algorithms

In a broad sense, an algorithm can be thought of as instruction (or a set of commands or course of actions) according to that a specific procedure has to take place.... We can say that a computer program is an illustration or an accomplishment of an algorithm.... This command/instruction has to be organized in such an accurate manner so that it is proficient to be executed by an operator that is capable to comprehend as well as efficiently run the algorithm's commands....
9 Pages (2250 words) Research Paper

The Efficiency of Clustering Algorithms for Mining Large Data Bases

his study focuses on evaluating the efficiency of various types of sequencing data mining algorithms with respect to protein sequence data sets, and on the basis of their shortcomings, design and develops an efficient clustering algorithm on the basis of the partitioning method.... The paper "The Efficiency of Clustering Algorithms for Mining Large Data Bases" highlights that using Pro-PAM algorithm based on partitioning clustering techniques in the place of alignment methods in large data sets, increases efficiency and reduces execution time significantly....
7 Pages (1750 words) Coursework

Optimizing Subsea Tie-in Spools Design Using Different Mathematical Approaches

The review "Optimizing Subsea Tie-in Spools design Using Different Mathematical Approaches" focuses on the critical, thorough, and multifaceted analysis of the different mathematical approaches used in optimizing the design of subsea tie-in spools.... Therefore, the authors insist that it is imperative to understand the effects associated with the effective axial force to achieve a reliable and safe design.... Furthermore, it was observed that the effective axial force can be utilized in simplifying the design criterion....
6 Pages (1500 words) Literature review
sponsored ads
We use cookies to create the best experience for you. Keep on browsing if you are OK with that, or find out how to manage cookies.
Contact Us