Bigint division algorithm

[modesto916]

Hi,

My teacher asked us to implement the bigint data type in C, C++ or Java, we must also implement the basic operations (assignment, addition, subtracion, multiplication and division). I'm implementing in C, my ADT is implemented as an array of chars, the first char is used to represent the signal (+ or -) and the number is inserted using big endian notation and it has a fixed size, for example, representing the number 128 and 8 as the array size:

[phone]

I've already implemented addition, subtraction e multiplication, the problem is that we cannot use the repeated subtraction algorithm, we must implement something faster, for multiplication I used individual digit multiplication and left shifts, but for division I couldn't figure anything out yet.

Any suggestions?

Regards.

[rubberman]

Well, at least you only have to worry about remainers to decide whether to round up or down for the final product of the division - no floating point required. Since division is basically the inverse of multiplication, try adapting that algorithm, using right shifts instead of left shifts for example.

[bguild]

You don't need to do any thinking in order to find a division algorithm. You can just borrow a division algorithm that is in common usage, such as long division.