10

I've been researching this the last few days and I have been unable to come up with an answer. I have come up with one algorithm that works if the divisor is only one word. But, if the divisor is multiple words then I get some strange answers. I know this question has been asked a few times on here, but there has been no definitive answer except use the schoolbook method or go get a book on the subject. I have been able to get every function in my big integer library to work except division. It seems that some individuals think big integer division is a NP hard problem, and with the trouble that I'm having with it, I'm inclined to agree.

The data is stored in a structure that contains a pointer to an array of either uint16_t or uint32_t based on if the long long data type is supported or not. If long long is not supported, then uint16_t is used for the capture of any carry/overflow from multiplication and addition operations. The current functions that I have are addition, subtraction, multiply, 2's complement negation, comparison, and, or, xor, not, shift left, shift right, rotate left, rotate right, bit reversal (reflection), a few conversion routines, a random number fill routine, and some other utility routines. All these work correctly (I checked the results on a calculator) except division.

typedef struct bn_data_t bn_t;
struct bn_data_t
  {
    uint32 sz1;         /* Bit Size */
    uint32 sz8;         /* Byte Size */
    uint32 szw;         /* Word Count */
    bnint *dat;         /* Data Array */
    uint32 flags;       /* Operational Flags */
  };

This is related to another question that I asked about inline assembler as this is what it was for.

What I have found so far:

Algorithm for dividing very large numbers

What is the fastest algorithm for division of crazy large integers?

https://en.wikipedia.org/wiki/Division_algorithm

Newton-Raphson Division With Big Integers

And a bunch of academic papers on the subject.

What I have tried so far:

I have a basic routine working, but it divides a multi-word big integer number by a single word. I have tried to implement a Newton-Raphson algorithm, but that's not working as I have gotten some really strange results. I know about Newton's method from Calculus on which it is based, but this is integer math and not floating point. I understand the math behind the Goldschmidt division algorithm, but I am not clear on how to implement it with integer math. Part of the problem with some of these algorithms is that they call for a base 2 logarithm function. I know how to implement a logarithm function using floating point and a Taylor series, but not when using integer math.

I have tried looking at the GMP library, but the division algorithm is not very well documented and it kinda goes over my head. It seems that they are using different algorithms at different points which adds to the confusion.

For the academic papers, I mostly understand the math (I have cleared basic calculus math, multi-variable calculus, and ordinary differential equations), but once again, there is a disconnect between my mathematical knowledge and implementation using integer math. I have seen the grade school method being suggested which from what I can ascertain is something similar to a shift-subtract method, but I'm not too sure how to implement that one either. Any ideas? Code would be nice.

EDIT:

This is for my own personal learning experience. I want to learn how it is done.

EDIT: 4-JUN-2016

It has been awhile since I have worked on this as I had other irons in the fire and other projects to work on. Now that I have revisited this project, I have finally implemented big integer division using two different algorithms. The basic one is the shift-subtract method outlined here. The high speed algorithm which uses the CPU divide instruction is called only when the divisor is one word. Both algorithms have been confirmed to work properly as the results that they produce has been checked with an online big number calculator. So now, all basic math and logic functions have been implemented. Those functions include add, subtract, multiply, divide, divide with modulus, modulus, and, or, not, xor, negate, reverse (reflection), shift left, shift right, rotate left, and rotate right. I may add additional functions as their need comes up. Thank you to everyone who responded.

Improve this question
14
  • 2
    This is not language-specific. Bascially, you should think about how you learned division at school using pen and paper. Commented Oct 8, 2015 at 14:52
  • 6
    Think of the big integer as comprising digits base 2**n, instead of base 2 or base 10. This is sometimes referred to as a "high-radix" approach. In your case, these digits appear to be stored in an array dat. If you start with longhand division as you learned it in grade school, you will have a reasonable starting point for your work. Once you have more experience working with big integers, you can progress to more advanced methods. Commented Oct 8, 2015 at 14:52
  • 10
    Integer division is definitely not NP-anything. It can be done provably correct in roughly O(N*log(N)). It involves using FFT and Newton's Method. To get the answer truncated correctly in a provably correct manner, it also needs a multiply-back + correction step. But that only adds to the big-O factor and doesn't increase the complexity. Commented Oct 8, 2015 at 15:08
  • 5
    If you are attempting the long-hand method: align both operands left before you start, so each one's ms bit is a 1. Commented Oct 8, 2015 at 15:13
  • 3
    The techniques Mysticial mentioned are advanced methods. One cannot expect a Wikipedia article to be the ultimate reference on such approaches. In general, division can be mapped back to multiplication (which also means that division is no more complex than multiplication from a big-O perspective), and fast multiplication methods for very long integers may involve FFTs. Commented Oct 9, 2015 at 16:30

1 Answer 1

Reset to default
3

The schoolbook division (long-division) algorithm, commonly used for base-10 operands, can be used for arbitrarily large operands too. I will assume we are implementing the large numbers by array of digits in base B.

When we perform long-division manually for decimal operands, we usually depend on trial-and-error to find each quotient-digit d. But this trial-and-error can be replaced with an efficient method (due to D. A. Pope and M. L. Stein) when using long-division for large operands in base B.

To guess d, we can use the first digit (e) of the divisor and first two digits (yz) of the "current remainder" (resulting from a subtraction step of long-division). Say, d1 is the estimate for d obtained by dividing the number yz by e. It can be proved that, if the divisor has certain properties (which are always achievable, refer the link below), either d1 or d1-1 or d1-2 must be the required digit d. Each of these three candidates can be checked for the desired properties of d one by one.

Thus the finding of each quotient-digit becomes efficient, and for the rest part we can follow the iterative long-division process. Please refer the below article (written by me) for details about this algorithm and implementation in C:

https://mathsanew.com/articles/implementing_large_integers_division.pdf

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

The site seems to be offline. Is there anywhere else I can obtain that pdf?
Sorry I didn't notice your question earlier. I have stopped hosting the site and moved all articles to github now: github.com/nitin-verma-github/mathsanew.com/tree/main/articles
Thanks a lot! I'll go give them a look. It looks like a treasure trove

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.