Is there a way to implement a long division algorithm in java, not on numbers bu

Question

Is there a way to implement a long division algorithm in java, not on numbers but on array representations of numbers?

for example, if I have 320 as the dividend and 4 as the divisor, they would be represented as follows:

short[] dividend = {0,2,3}

short[] divisor = {4}

So the quotient is 80 remainder 0

then I would want the quotient to be represented as either an array with {0,8} and a short holding the remainder 0

(unless there is a better way)

******THE OPERATIONS CANNOT BE DONE ON NUMBERS BECAUSE THERE WILL BE RISK OF OVERFLOW THAT IS WHY WE ARE USING ARRAYS*******

assume that we already have algorithms that can perform addition, subtraction, and multiplication on arrays of type short.

Explanation / Answer

computer is very capable of dealing with 8-bit quantities (bytes). An 8-bit number can range from 0 to 255. If you work with 8-bit quantities, you're effectively working in base 256. If you store your arbitrary-precision numbers as arrays of 8-bit numbers, you're essentially representing them as strings of base-256 digits. Here's an example: bytes: 00100101 11010001 01010101 digits: (37) (209) (85) place values: 256^2 256^1 256^0 This three-byte number is composed of three base-256 "digits." To figure out what the whole number means, just as in any other base, you multiply each digit by the value of its place. The digit (37) is in the 256^2 place. The total number is 37*256^2 + 209*256 + 85, or 2,478,421. Now, as I said, there's no limit to what base you can do your arithmetic in. You can do long division on base-256 numbers exactly the same way as you do it on base-10 numbers. So here's the algorithm written up in pseudocode: DIVIDE(a by b) { LET current_segment = most signifcant digit of a; WHILE there are digits left in a LET accumulator = 0; LOOP WITH i FROM 0 TO N-1 LET previous_accumulator = accumulator; LET accumulator = accumulator + b; IF (accumulator > current_segment) { OUTPUT i; BREAK OUT OF LOOP; } END LOOP LET remainder = current_segment - previous_accumulator; LET current_segment = remainder followed by next digit of a; END WHILE END DIVIDE (Make sure that you completely understand this pseudocode algorithm before you begin to code it in real code. Test it out on a base-16 problem by hand!)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.