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.

Community
  • 1
  • 1
Daniel Rudy
  • 1,411
  • 12
  • 23
  • 2
    This is not language-specific. Bascially, you should think about how you learned division at school using pen and paper. – too honest for this site Oct 08 '15 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. – njuffa Oct 08 '15 at 14:52
  • You do know that integer division can give unexpected results? One reason for the unexpected results is the dropping of any fraction. I.E 5/3 results in 1 and 3/5 results in 0 – user3629249 Oct 08 '15 at 15:07
  • 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. – Mysticial Oct 08 '15 at 15:08
  • 1
    @njuffa's suggestion of thinking of words as digits in base 2**n is right on. Also "log to base 2", if rounded down, simply means "the position of the highest 1-bit". That should hopefully make some of the algorithms easier to understand. – j_random_hacker Oct 08 '15 at 15:13
  • 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`. – Weather Vane Oct 08 '15 at 15:13
  • Have a look at the source for the openJDK BigInteger code. http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/math/BigInteger.java – Salix alba Oct 08 '15 at 15:34
  • integer `y=log2(int x)` returns the number of bits used by `x` ,,, there are even assembly instructions for that on CPU or It can be done with something like this: `y=1; if (x) for (y=0;x;x>>=1,y++); ` (hope I did not miss some +/-1 somewhere). When you have array of words then do the loop just for the top nonzero value and add `8/16/32/64` for the rest. Also take a look at this similar question [What algorithm should I use for high-performance large integer division?](http://stackoverflow.com/q/32942466/2521214) – Spektre Oct 09 '15 at 14:58
  • @njuffa, j_random_hacker: That makes things easier to understand. I know about logs and ln, but it didn't occur to me that log2 is just the position of the MSB. &user3629249: I'm aware of that, 5/3 gives 1, with a remainder of 2. It's integer math. Floating point would give something like 1.666667 &Mystical: I tried to use Newton's method as shown on Wikipedia and it wouldn't work. A fast fourier transform was not even mentioned, so is the article wrong or what? – Daniel Rudy Oct 09 '15 at 16:10
  • 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. – njuffa Oct 09 '15 at 16:30
  • 2
    I don't understand what this question is asking. You've implemented a buggy implementation of large integer division; if you want help finding the bug then post the code along with a detailed explanation of everything you've tried so far to find the bug, and then ask a specific, targeted question about the code. – Eric Lippert Oct 11 '15 at 20:16
  • Try to find the file `divmnu.c` for an example of a simple basecase division (modelled after Knuth's code). If you get that working, you can go for the more sophisticated versions used for very large bigintegers. – Rudy Velthuis Oct 11 '15 at 21:48
  • @Eric Lippert I was looking for the technique. The implementation that I wrote simply doesn't work at all because the entire thing is a logic error. I'm going to rewrite it using the shift-subtract method and go from there. – Daniel Rudy Oct 14 '15 at 02:55
  • 1
    Well, I wrote a series of articles on a very simple implementation of big natural arithmetic, where the naturals are represented as linked lists of bits. I show how to do division on that data structure here: http://ericlippert.com/2013/10/14/math-from-scratch-part-seven-division-and-remainder/ – Eric Lippert Oct 14 '15 at 04:39

1 Answers1

1

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

Nitin Verma
  • 131
  • 4