Problem in Calculator for great integers in C

Discussion in 'C' started by Manarg, Jun 18, 2007.

  1. Manarg

    Manarg New Member

    Joined:
    Jun 18, 2007
    Messages:
    10
    Likes Received:
    0
    Trophy Points:
    0
    Hello everybody. I have developped a program that can manage calculations with great integers (integers that cannot be stored in a simple int or long type). For this purpose I use double - linked cyclic lists. All the operations work fine and fast for me, except from the division. I was wondering if you know any algorithms that can calculate either the quotient or the modulo of a division between integers (no matter their size) without using the division operation. In simple words, I mean that i want to find the modulo or quotient of a/b using only subtraction, multiplication and/or adding. Do you have any idea?
    Thanx in advance :)
     
  2. DaWei

    DaWei New Member

    Joined:
    Dec 6, 2006
    Messages:
    835
    Likes Received:
    5
    Trophy Points:
    0
    Occupation:
    Semi-retired EE
    Location:
    Texan now in Central NY
    Home Page:
    http://www.daweidesigns.com
    If you're learning how to do it, see division algorithms such as are used in assembly language programs (repeated subtractions combined with shifts). One of the problems with replicating these operations in C is the lack of access to the carry/borrow flag.

    If you're just wanting to do it, check out a bignum library.
     
  3. Manarg

    Manarg New Member

    Joined:
    Jun 18, 2007
    Messages:
    10
    Likes Received:
    0
    Trophy Points:
    0
    I don't want just to do it, but learn through it... so i guess i have to study the assembly division algorithms.
    Thanx for your response
    :)
     
  4. DaWei

    DaWei New Member

    Joined:
    Dec 6, 2006
    Messages:
    835
    Likes Received:
    5
    Trophy Points:
    0
    Occupation:
    Semi-retired EE
    Location:
    Texan now in Central NY
    Home Page:
    http://www.daweidesigns.com
    Obviously, you only have to subtract the divisor from the dividend until the dividend is smaller than the divisor. The rest is remainder. Just as obviously, this could take a long time if you're dividing a billion by 1. The deal is to shift the divisor left until it can't be shifted any more without becoming larger than the dividend. Subtracting this larger value amounts to subtracting the original number x times, where x is the number determined by shifting left, according to the base you're working with.

    When you reach that first limit, you make the subtraction, shift right, and do it all again. This gives you a rapid way to subtract the divisor a large number of times with a minimal number of operations.

    In reality, microprocessors cannot do anything but logical operations, and add. Addition is nothing but an XOR with carry. Subtraction is obtained by adding complements. Multiplication is accomplished by adding, division by subtracting. Even higher operations are merely mixtures, with maybe some algorithmic shortcuts stuck in for efficiency.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice