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
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.
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
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.
