Pro Programming

Professional way of Programming

  • Home
  • C MCQs
  • C
  • C++
  • C#
  • Java
  • Python
  • MySQL
  • Topics
    • Arrays
    • Strings
    • Link Lists
    • Trees
    • Shapes
  • Projects
  • Articles
  • Games
You are here: Home / Archives for Digital Electronics & Logic Design

Restoring Division Algorithm For Unsigned Integer

Leave a Comment


A division algorithm provides a quotient and a remainder when we divide two number. They are generally of two type slow algorithm and fast algorithm. Slow division algorithm are restoring, non-restoring, non-performing restoring, SRT algorithm and under fast comes Newton–Raphson and Goldschmidt.

In this article, will be performing restoring algorithm for unsigned integer. Restoring term is due to fact that value of register A is restored after each iteration.

Here, register Q contain quotient and register A contain remainder. Here, n-bit dividend is loaded in Q and divisor is loaded in M. Value of Register is initially kept 0 and this is the register whose value is restored during iteration due to which it is named Restoring.

Let’s pick the step involved:

  • Step-1: First the registers are initialized with corresponding values (Q = Dividend, M = Divisor, A = 0, n = number of bits in dividend)
  • Step-2: Then the content of register A and Q is shifted right as if they are a single unit
  • Step-3: Then content of register M is subtracted from A and result is stored in A
  • Step-4: Then the most significant bit of the A is checked if it is 0 the least significant bit of Q is set to 1 otherwise if it is 1 the least significant bit of Q is set to 0 and value of register A is restored i.e the value of A before the subtraction with M
  • Step-5: The value of counter n is decremented
  • Step-6: If the value of n becomes zero we get of the loop otherwise we repeat fro step 2
  • Step-7: Finally, the register Q contain the quotient and A contain remainder

Examples:

Perform Division Restoring Algorithm 
Dividend = 11
Divisor  = 3

nMAQOperation
400011000001011initialize
0001100001011_shift left AQ
0001111110011_A=A-M
00011000010110Q[0]=0 And restore A
30001100010110_shift left AQ
0001111111110_A=A-M
00011000101100Q[0]=0
20001100101100_shift left AQ
0001100010100_A=A-M
00011000101001Q[0]=1
10001100101001_shift left AQ
0001100010001_A=A-M
00011000100011Q[0]=1

Remember to restore the value of A most significant bit of A is 1. As that register Q contain the quotient, i.e. 3 and register A contain remainder 2.



If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.


Post navigation









Source link

Filed Under: c programming Tagged With: •   Dynamic Programming, About Us, Addressing Modes, Advanced Data Structure, Advanced Data Structures, Advanced Topics, Algo ▼, Algorithm Paradigms ►, Algorithms, All Algorithms, All Data Structures, Amazon, Analysis of Algorithms, Aptitude, Array, Arrays, Backtracking, BFS, Binary Search, Binary Search Tree, Binary to Decimal Conversion, Binary to Hexadecimal Conversion, Binary to Octal Conversion, Binary Tree, Bit Algorithms, Bit Magic, Branch & Bound, C, C++ Quiz, Cache Memory, Cache Organization, Campus Ambassador Program, Careers, Clusters In Computer Organisation, Company Prep, Company-wise, Competitive Programming, Compiler Design, Computer Architecture | Flynn’s taxonomy, Computer Arithmetic | Set – 1, Computer Arithmetic | Set – 2, Computer Networks, Computer Organization, Computer Organization & Architecture, Computer Organization | Booth’s Algorithm, Computer Organization | Different Instruction Cycles, Computer Organization | Hardwired v/s Micro-programmed Control Unit, Computer Organization | Micro-Operation, Contact Us, Contests, contribute.geeksforgeeks.org, contributed articles, CPP-Library, CS Subjects, CS Subjects ▼, CS Subjectwise ►, Data Structures, DBMS, Decimal to Binary Conversion, Dependencies and Data Hazard, Design Patterns, Detect a negative cycle., DFS, Dictionary, Difference between 1’s complement and 2’s complement, Digital Electronics, Digital Electronics & Logic Design, Divide & Conquer, Divide and Conquer, DS ▼, Engg. Mathematics, Execution, Experienced, Experienced Interviews, Explore More..., Floating Point Representation, Game Theory, GATE ▼, Gate 2018 Important Dates and Links, GATE CS, GATE CS Corner, GATE CS Notes, GATE Notes, GBlog, Geek of the Month, Geek on the Top, Geometric, Geometric Algorithms, Graph, Graph Algorithms, Greedy Algorithms, Hash, Hashing, Heap, HeapSort, How to begin with Competitive Programming?, How to prepare for ACM-ICPC?, HTML & XML, I/O Interface (Interrupt and DMA Mode), ide.geeksforgeeks.org, Insertion Sort, Internship, Internship Interviews, Interview ▼, Interview Experiences, Introduction to quantum computing, ISRO, Java, java-stream, JavaScript, Languages, Languages ►, Languages ▼, Last Minute Notes, Linked Lists, LinkedList, Login, Longest Palindromic Subsequence, Longest Repeated Subsequence, Machine Instructions, Mathematical, Mathematical Algorithms, Matrix, MCQ / Quizzes, MergeSort, Microsoft, MongoDB Python | Insert and Update Data, Multiple Choice Quizzes, Number System and Base Conversions, Number Theory, number-digits, Octal to Decimal Conversion, Official Papers, Operating Systems, Pattern Searching, PHP, Placement Course, Practice Company Questions, Practice Problems, Priority Interrupts | (S/W Polling and Daisy Chaining), Privacy Policy, Program Output, Project, Puzzles, Python, Python List, QA - Placement Quizzes, Queue, QuickSort, Quizzes ▼, Randomized Algorithms, Recent Articles, Recursion, Reverse a linked list, School Programming, Searching, Searching Algorithms, series, Set, Set to Array in Java, Simplified Instructional Computer (SIC), Skip to content, Software Engineering, Some rights reserved, Sorting, Sorting Algorithms, SQL, Stack, Stages and Throughput, Statistical Algorithms, Step by Step Guide for Placement Preparation, STL, Strings, Students ▼, Subjective Questions, Technical Scripter, Testimonials, Theory of Computation, Top 10 Algorithms and Data Structures for Competitive Programming, Top 10 algorithms in Interview Questions, Top Topics, Topic-wise, Topicwise ►, Tree based DS ►, Trees, Tuple, Types and Stalling, UGC-NET, Video Tutorials, Videos, Web Technologies, Web Technology, What’s difference between CPU Cache and TLB?, What’s Difference?, What’s New?, Write an Article

Popular Posts

  • C++ program to implement Stack using Linked List 2,280 views
  • Patterns and Shapes C++ 1,179 views
  • Heap Sort Implementation in C++ 997 views
  • Free Download W3Schools Offline Version 2017 959 views
  • Solution for Tower of Hanoi C++ 945 views
  • TutorialsPoint Offline Version Download 2017 [Full Website] 875 views
  • Program to implement Binary Search Tree C++ 814 views
  • Program to implement RSA algorithm in C 808 views
  • Program to find LCM and HCF of 3 numbers in C++ 739 views
  • Program to convert Decimal to Hexadecimal C++ 702 views

© 2017 ProProgramming
 Privacy Policy About Contact Us