ALGORITHMS

FROM WIKIPEDIA

This article covers some of the most common

algorithms used in mathematics.

Contents
Short division .................................................. 2

Example ...................................................... 3

Modulo division ............................................ 5

Long division ................................................... 5

Method ........................................................ 5

Basic procedure for long division of n ÷ m ..... 9

Example with multi-digit divisor..................... 9

Interpretation of decimal results.................. 10

Non-decimal radix ...................................... 11

Generalizations .......................................... 12

Mixed mode long division ........................... 12

Polynomial long division ................................ 13

Algorithm ................................................... 14

Applications ............................................... 15

Factoring polynomials ............................. 15

Finding tangents to polynomial functions . 16

Synthetic division .......................................... 16

Regular synthetic division ........................... 16

 Expanded synthetic division ....................... 17

For non-monic divisors ............................... 19

Compact Expanded Synthetic Division ........ 21

Fast division methods .................................... 23

Newton–Raphson division .......................... 23

Goldschmidt division .................................. 25

Binomial theorem .................................... 26

Euclidean algorithm ....................................... 27

Worked example ........................................ 28

SHORT DIVISION

In arithmetic, short division is a division

algorithm which breaks down a division problem
into a series of easy steps. It is an abbreviated
form of long division. Short division relies on
mental arithmetic, which necessarily limits the
size of the divisor; Though some people can use
the procedure for larger divisors.

As in all division problems, a number called the

dividend is divided by another, called the
divisor. The answer to the problem is called the
quotient.

Using short division, one can solve a division

problem with a very large dividend by following
a series of easy steps.

Short division does not use the slash (/) or

obelus (÷) symbols. Instead, it displays the
dividend, divisor, and quotient (when it is found)
in a tableau. An example is shown below,
representing the division of 500 by 4. The
quotient is 125.
125
4) 500

Alternatively, the bar may be placed below the

number which means the sum proceeds down
the page.
4) 500
125

EXAMPLE
The procedure involves several steps. As an
example, consider 950 divided by 4:

1. The dividend and divisor are written in the

short division tableau:

4) 950
Dividing 950 by 4 in a single step would
require knowing the multiplication table up
to 238 × 4. Instead, the division is reduced
to small steps. Starting from the left,
enough digits are selected to form a
number (called the partial dividend which
is always at most 2 digits) from 1×4 to
10×4-1 (4 being the divisor in this
problem). Here, the partial dividend is 9.

2. The first number to be divided by the

divisor (4) is the partial dividend (9). We
write the integer part of the result (2)
above the division bar over the leftmost
digit of the dividend, and we write the
remainder (1) as a small digit above and to
the right of the partial dividend (9).
2
4) 91 50
 3. Next we repeat step 2, using the small
digit just written along with the next digit of
the dividend to form a new partial dividend
(15). Dividing the new partial dividend by
the divisor (4), we write the result as
before — the quotient above the next digit
of the dividend, and the remainder as a
small digit to the upper right. (Here 15
divided by 4 is 3, with a remainder of 3.)
23
4) 91 53 0

4. We continue repeating step 2 until there

are no digits remaining in the dividend. In
this example, we see that 30 divided by 4
is 7 with a remainder of 2. The number
written above the bar (237) is the quotient,
and the last small digit (2) is the
remainder.
237
4) 9 53 02
1

5. The answer in this example is 237 with a

remainder of 2. Alternatively, we can
continue the above procedure if we want to
produce a decimal answer. We do this by
adding a decimal point and zeroes as
necessary at the right of the dividend, and
then treating each zero as another digit of
the dividend. Thus, the next step in such a
calculation would give the following:
237.5
4) 9 53 0.2 0
1

A second example:
500035
7 )350 00 00 22 43 50
MODULO DIVISION
When one is interested only in the remainder of
the division, this procedure (a variation of short
division) ignores the quotient and tallies only the
remainders. It can be used for manual modulo
calculation or as a test for even divisibility. The
quotient digits are not written down.

For example, what is the remainder of

16762109 divided by 7?

7)162 76 63 24 16 04 90

The remainder is zero, so 16762109 is exactly

divisible by 7.

LONG DIVISION

In arithmetic, long division is a standard division

algorithm suitable for dividing multidigit numbers
that is simple enough to perform by hand. It
breaks down a division problem into a series of
easier steps. As in all division problems, one
number, called the dividend, is divided by
another, called the divisor, producing a result
called the quotient. It enables computations
involving arbitrarily large numbers to be
performed by following a series of simple steps.
The abbreviated form of long division is called
short division, which is almost always used
instead of long division when the divisor has
only one digit.

METHOD
The process is begun by dividing the left-most
digit of the dividend by the divisor. The quotient
(rounded down to an integer) becomes the first
digit of the result, and the remainder is
calculated (this step is notated as a
subtraction). This remainder carries forward
when the process is repeated on the following
digit of the dividend (notated as 'bringing down'
the next digit to the remainder). When all digits
have been processed and no remainder is left,
the process is complete.

An example is shown below, representing the

division of 500 by 4 (with a result of 125).

125
4 ) 500 In the above example, the first
-4 step is to find the shortest
10 sequence of digits starting from
-8 the left end of the dividend, 500,
20 that the divisor 4 goes into at least
-20 once; this shortest sequence in
00 this example is simply the first
digit, 5. The largest number that
the divisor 4 can be multiplied by
without exceeding 5 is 1, so the
digit 1 is put above the 5 to start
constructing the quotient.

Next, the 1 is multiplied by the divisor 4, to

obtain the largest whole number (4 in this case)
that is a multiple of the divisor 4 without
exceeding the 5; this product of 1 times 4 is 4,
so 4 is placed underneath the 5. Next the 4
under the 5 is subtracted from the 5 to get the
remainder, 1, which is placed under the 4 under
the 5. This remainder 1 is necessarily smaller
than the divisor 4. Next the first as-yet unused
digit in the dividend, in this case the first digit 0
after the 5, is copied directly underneath itself
and next to the remainder 1, to form the number
10. At this point the process is repeated enough
times to reach a stopping point: The largest
number by which the divisor 4 can be multiplied
without exceeding 10 is 2, so 2 is written above
the 0 that is next to the 5 – that is, directly
above the last digit in the 10. Then the latest
entry to the quotient, 2, is multiplied by the
divisor 4 to get 8, which is the largest multiple of
4 that does not exceed 10; so 8 is written below
10, and the subtraction 10 minus 8 is performed
to get the remainder 2, which is placed below
the 8. This remainder 2 is necessarily smaller
than the divisor 4. The next digit of the dividend
(the last 0 in 500) is copied directly below itself
and next to the remainder 2, to form 20. Then
the largest number by which the divisor 4 can
be multiplied without exceeding 20 is
ascertained; this number is 5, so 5 is placed
above the last dividend digit that was brought
down (i.e., above the rightmost 0 in 500). Then
this new quotient digit 5 is multiplied by the
divisor 4 to get 20, which is written at the
bottom below the existing 20. Then 20 is
subtracted from 20, yielding 0, which is written
below the 20. We know we are done now
because two things are true: there are no more
digits to bring down from the dividend, and the
last subtraction result was 0.

If the last remainder when we ran out of

dividend digits had been something other than
0, there would have been two possible courses
of action. (1) We could just stop there and say
that the dividend divided by the divisor is the
quotient written at the top with the remainder
written at the bottom; equivalently we could
write the answer as the quotient followed by a
fraction that is the remainder divided by the
divisor. Or, (2) we could extend the dividend by
writing it as, say, 500.000... and continue the
process (using a decimal point in the quotient
directly above the decimal point in the dividend),
in order to get a decimal answer, as in the
following example.

31.75
4 )127.00 In this example, the decimal part
-12 of the result is calculated by
07 continuing the process beyond
-4
the units digit, "bringing down"
3.0
-2.8 zeros as being the decimal part
20 of the dividend.
-20
00 This example also illustrates that,
at the beginning of the process, a
step that produces a zero can be
omitted. Since the first digit 1 is
less than the divisor 4, the first
step is instead performed on the
first two digits 12. Similarly, if the
divisor were 13, one would
perform the first step on 127
rather than 12 or 1.
BASIC PROCEDURE FOR LONG
DIVISION OF N ÷ M

1. Find the location of all decimal points in

the dividend n and divisor m.

2. If necessary, simplify the long division

problem by moving the decimals of the
divisor and dividend by the same number
of decimal places, to the right, (or to the
left) so that the decimal of the divisor is to
the right of the last digit.

3. When doing long division, keep the

numbers lined up straight from top to
bottom under the tableau.

4. After each step, be sure the remainder for

that step is less than the divisor. If it is not,
there are three possible problems: the
multiplication is wrong, the subtraction is
wrong, or a greater quotient is needed.

5. In the end, the remainder, r, is added to

the growing quotient as a fraction, r/m.

EXAMPLE WITH MULTI-DIGIT

DIVISOR

A divisor of any number of digits can be used. In

this example, 37 is to be divided into 1260257.
After setting up the problem, do as follows:
Digits of the number 1260257 are taken until a
number greater than or equal to 37 occurs. So 1
and 12 are less than 37, but 126 is greater.
Next, the greatest multiple of 37 less than or
equal to 126 is computed. So 3 × 37 = 111 <
126, but 4 × 37 > 126. The multiple 111 is
written underneath the 126 and the 3 is written
on the top where the solution will appear.

Note carefully which place-value column these

digits are written into. The 3 in the quotient goes
in the same column (ten-thousands place) as
the 6 in the dividend 1260257, which is the
same column as the last digit of 111.

The 111 is then subtracted from the line above,

ignoring all digits to the right. Now the digit from
the next smaller place value of the dividend is
copied down appended to the result 15. The
process repeats: the greatest multiple of 37 less
than or equal to 150 is subtracted. This is 148 =
4 × 37, so a 4 is added to the solution line.

34061
37 )1260257 Then the result of the
-111 subtraction is extended by
150 another digit taken from the
-148 dividend. The greatest
225
-222 multiple of 37 less than or
37 equal to 22 is 0 × 37 = 0.
-37 Subtracting 0 from 22 gives
00 22, we often don't write the
subtraction step. Instead, we
simply take another digit
from the dividend. The
process is repeated until 37
divides the last line exactly.

INTERPRETATION OF DECIMAL
RESULTS

When the quotient is not an integer and the

division process is extended beyond the decimal
point, one of two things can happen. (1) The
process can terminate, which means that a
remainder of 0 is reached; or (2) a remainder
could be reached that is identical to a previous
remainder that occurred after the decimal points
were written. In the latter case, continuing the
process would be pointless, because from that
point onward the same sequence of digits would
appear in the quotient over and over. So, a bar
is drawn over the repeating sequence to
indicate that it repeats forever.

NON-DECIMAL RADIX
The same method and layout is used for binary,
octal and hexadecimal.

0d8f45
12 )f412df
-ea
a1 1110
-90 1101 )10111001
112 -1101
-10e 10100
4d -1101
-48 1110
5f -1101
-5a 11
5
GENERALIZATIONS
Long division of integers can easily be extended
to include non-integer dividends, as long as
they are rational. This is because every rational
number has a recurring decimal expansion. The
procedure can also be extended to include
divisors which have a finite or terminating
decimal expansion (i.e. decimal fractions). In
this case the procedure involves multiplying the
divisor and dividend by the appropriate power of
ten so that the new divisor is an integer – taking
advantage of the fact that a ÷ b = (ca) ÷ (cb) –
and then proceeding as above.

MIXED MODE LONG DIVISION

For non-decimal currencies and measures
mixed mode division must be used. Consider
dividing 50 miles 600 yards into 37 pieces:

miles(m) yards(y) feet(f) inches(i)

1 634 1 9 R. 15i
37) 50 600 00 000
-37 +22880 +66 +348
13m 23480 66 348
=22880y -222 -37 -333
128 29f 15i
-111 =348i
170
-148
22y
=66f

Each of the four columns is worked in turn.

Starting with the miles: 50/37 = 1 remainder 13.
No further division is possible, so perform a long
multiplication by 1,760 to convert miles to yards,
the result is 22,880 yards. Carry this to the top
of the yards column and add it to the 600 yards
in the dividend giving 23,480. Long division of
23,480 / 37 now proceeds as normal yielding
634 with remainder 22. The remainder is
multiplied by 3 to get feet and carried up to the
feet column. Long division of the feet gives 1
remainder 29 which is then multiplied by twelve
to get 348 inches. Long division continues with
the final remainder of 15 inches being shown on
the result line.

POLYNOMIAL LONG DIVISION

In algebra, polynomial long division is an

algorithm for dividing a polynomial by another
polynomial of the same or lower degree, a
generalized version of the familiar arithmetic
technique called long division. It can be done
easily by hand, because it separates an
otherwise complex division problem into smaller
ones. Sometimes using a shorthand version
called synthetic division is faster, with less
writing and fewer calculations.

Polynomial long division is an algorithm that

implements the Euclidean division of
polynomials, which starting from two
polynomials A (the dividend) and B (the divisor)
produces, if B is not zero, a quotient Q and a
remainder R such that A = BQ + R, and either R
= 0 or the degree of R is lower than the degree
of B. These conditions define uniquely Q and R,
which means that Q and R do not depend on the
method used to compute them.
ALGORITHM
Find the quotient and the remainder of the
division of x3 - 2x2 - 4, the dividend, by x - 3, the
divisor.

1. Divide the first term of the dividend by the

highest term of the divisor (meaning the
one with the highest power of x, which in
this case is x). Place the result above the
bar (x3 ÷ x = x2 ).

2. Multiply the divisor by the result just

obtained (the first term of the eventual
quotient). Write the result under the first
two terms of the dividend (x2 · (x − 3) = x3
− 3x2 ).

3. Subtract the product just obtained from the

appropriate terms of the original dividend
(being careful that subtracting something
having a minus sign is equivalent to
adding something having a plus sign), and
write the result underneath ((x3 − 2x 2 ) − (x3
− 3x2 ) = −2x 2 + 3x 2 = x2 ). Then, "bring
down" the next term from the dividend.

4. Repeat the previous three steps, except

this time use the two terms that have just
been written as the dividend.

5. Repeat step 4. This time, there is nothing

to "pull down".

6. The polynomial above the bar is the

quotient q(x), and the number left over (5)
is the remainder r(x).

The long division algorithm for arithmetic is very

similar to the above algorithm, in which the
variable x is replaced by the specific number 10.
Note that this works equally well when
degree(dividend) < degree(divisor); in that case
the quotient is zero with the dividend left over.

APPLICATIONS

FACTORING POLYNOMIALS
Sometimes one or more roots of a polynomial
are known, perhaps having been found using
the rational root theorem. If one root r of a
polynomial P(x) of degree n is known then
polynomial long division can be used to factor
P(x) into the form (x − r)(Q(x)) where Q(x) is a
polynomial of degree n − 1. Q(x) is simply the
quotient obtained from the division process;
since r is known to be a root of P(x), it is known
that the remainder must be zero.

Likewise, if more than one root is known, a

linear factor (x − r) in one of them (r) can be
divided out to obtain Q(x), and then a linear
term in another root, s, can be divided out of
Q(x), etc. Alternatively, they can all be divided
out at once: for example the linear factors x − r
and x − s can be multiplied together to obtain
the quadratic factor x2 − (r + s)x + rs, which can
then be divided into the original polynomial P(x)
to obtain a quotient of degree n − 2. For
example, if the rational root theorem can be
used to obtain a single (rational) root of a
quintic polynomial, it can be factored out to
obtain a quartic (fourth degree) quotient; the
explicit formula for the roots of a quartic
polynomial can then be used to find the other
four roots of the quintic.
FINDING TANGENTS TO
POLYNOMIAL FUNCTIONS

Polynomial long division can be used to find the

equation of the line that is tangent to the graph
of the function defined by the polynomial P(x) at
a particular point x = r. If R(x) is the remainder
of the division of P(x) by (x – r) 2 , then the
equation of the tangent line at x = r to the graph
of the function y = P(x) is y = R(x), regardless of
whether or not r is a root of the polynomial.

SYNTHETIC DIVISION

In algebra, synthetic division is a method of

performing polynomial long division, with less
writing and fewer calculations. It is mostly
taught for division by binomials of the form x - a,
but the method generalizes to division by any
monic polynomial, and to any polynomial.

The advantages of synthetic division are that it

allows one to calculate without writing variables,
it uses few calculations, and it takes
significantly less space on paper than long
division. Also, the subtractions in long division
are converted to additions by switching the
signs at the very beginning, preventing sign
errors.

Synthetic division for linear denominators is also

called division through Ruffini's rule.

REGULAR SYNTHETIC DIVISION

The first example is synthetic division with only
a monic linear denominator x - a.
 𝑥𝑥 3 − 12𝑥𝑥 2 − 42
𝑥𝑥 − 3

Write the coefficients of the polynomial that is to

be divided at the top (the zero is for the unseen
0x).

Negate the coefficients of the divisor. Write in

every coefficient of the divisor but the first one
on the left.

Drop the first coefficient after the bar to the last

row.

Multiply the dropped number by the number

before the bar, and place it in the next column.

Perform an addition in the next column.

Repeat the previous two steps and the following

is obtained:

1 -12 0 -42
3 ↓ 3 -27 -81
1 -9 -27 -123

Count the terms to the left of the bar. Since

there is only one, the remainder has degree
zero. Mark the separation with a vertical bar. “1
-9 -27 | -123“
The terms are written with increasing degree
from right to left beginning with degree zero for
both the remainder and the result (1x2 -9x -27
| -123). The result of our division is:
x 3 − 12x 2 − 42 127
= 𝑥𝑥 2 − 9𝑥𝑥 − 27 −
x−3 𝑥𝑥 − 3

EXPANDED SYNTHETIC DIVISION

This method generalizes to division by any
monic polynomial with only a slight modification
with changes in bold. Using the same steps as
before, let's try to perform the following division:
𝑥𝑥 3 − 12𝑥𝑥 2 − 42
𝑥𝑥 2 + 𝑥𝑥 − 3

1. We concern ourselves only with the

coefficients. Write the coefficients of the
polynomial to be divided at the top.

Negate the coefficients of the divisor. Write in

every coefficient but the first one on the left in
an upward right diagonal (see next diagram).

1 -12 0 -42
3
-1

Drop the first coefficient after the bar to the last

row.

Multiply the dropped number by the diagonal

before the bar, and place the resulting entries
diagonally to the right from the dropped entry.

1 -12 0 -42

-1
3
↓ -1
3

Perform an addition in the next column.

Repeat the previous two steps until you would

go past the entries at the top with the next
diagonal.

Then simply add up any remaining columns.

1 -12 0 -42

-1
3
↓ -1
3
13
-39

1 -13 16 -81

Count the terms to the left of the bar. Since

there are two, the remainder has degree one.
Mark the separation with a vertical bar. “1 -13 |
16 -81”
The terms are written with increasing degree
from right to left beginning with degree zero for
both the remainder and the result (1x -13 | 16x
-81). The result of our division is:
𝑥𝑥 3 − 12𝑥𝑥 2 − 42 16𝑥𝑥 − 81
= 𝑥𝑥 − 13 +
𝑥𝑥 2 + 𝑥𝑥 − 3 𝑥𝑥 2 + 𝑥𝑥 − 3

FOR NON-MONIC DIVISORS

With a little prodding, the expanded technique
may be generalized even further to work for any
polynomial, not just monics.

Suppose that for a polynomial division of

f(x)/g(x) where g(x) is a monic polynomial, by
the division algorithm we get:

𝑓𝑓(𝑥𝑥) = 𝑔𝑔(𝑥𝑥)𝑄𝑄(𝑥𝑥) + 𝑅𝑅(𝑥𝑥) 𝐷𝐷𝐷𝐷𝐷𝐷�𝑅𝑅(𝑥𝑥)� < 𝐷𝐷𝐷𝐷𝐷𝐷�𝑔𝑔(𝑥𝑥)�

Suppose we want “f(x)/h(x)” where “h(x)=ag(x)”

and “a” is hence, the leading coefficient of h(x).
Then since “g(x)=h(x)/a” we get:

𝑄𝑄(𝑥𝑥)
𝑓𝑓(𝑥𝑥) = ℎ(𝑥𝑥) + 𝑅𝑅(𝑥𝑥) 𝐷𝐷𝐷𝐷𝐷𝐷�𝑅𝑅(𝑥𝑥)� < 𝐷𝐷𝐷𝐷𝐷𝐷�ℎ(𝑥𝑥)�
𝑎𝑎

But using the above method, often produces

unsightly fractions which get removed later, and
is thus more prone to error. It is possible to do it
without first dividing the coefficients of h(x) by a.

As can be observed by first performing long

division with such a non-monic divisor, the
coefficients of f(x) are divided by the leading
coefficient of g(x) after "dropping", and before
multiplying.

Let's illustrate by performing the following

division:
 6x 3 + 5x 2 − 7
3x 2 − 2x − 1

A slightly modified table is used. Note the extra

row at the bottom. This is used to write values
found by dividing the "dropped" values by the
leading coefficient of h(x) (in this case,
indicated by the /3; note that, unlike the rest of
the coefficients of h(x), the sign of this number
is not changed).

Next, the first coefficient of f(x) is dropped as

usual:

6 5 0 -7

1
2
/3

Note the extra row at the bottom. This is used to

write values found by dividing the "dropped"
values by the leading coefficient of g(x) (in this
case, indicated by the /3; note that, unlike the
rest of the coefficients of g(x), the sign of this
number is not changed). Next, the first
coefficient of f(x) is dropped as usual and then
the dropped value is divided by 3 and placed in
the row below. Next, the new (divided) value is
used to fill the top rows with multiples of 2 and
1, as in the expanded technique. The 5 is
dropped next, with the obligatory adding of the 4
below it, and the answer is divided again. Then
the 3 is used to fill the top rows. At this point, if,
after getting the third sum, we were to try and
use it to fill the top rows, we would "fall off" the
right side, thus the third sum is the first
coefficient of the remainder, as in regular
synthetic division. But the values of the
remainder are not divided by the leading
coefficient of the divisor:
 6 5 0 -7
2 3
1 ↓ 4 6
2 6 9 8 -4
/3 2 3

Now we can read off the coefficients of the

answer. As in expanded synthetic division, the
last two values (2 is the degree of the divisor)
are the coefficients of the remainder, and the
remaining values are the coefficients of the
quotient (2x 3 | 8x -4). So the result is:

6𝑥𝑥 3 + 5𝑥𝑥 2 − 7 8𝑥𝑥 − 4

= 2𝑥𝑥 + 3 +
3𝑥𝑥 2 − 2𝑥𝑥 − 1 3𝑥𝑥 2 − 2𝑥𝑥 − 1

COMPACT EXPANDED SYNTHETIC

DIVISION
However, the diagonal format above becomes
less space-efficient when the degree of the
divisor exceeds half of the degree of the
dividend. It is easy to see that we have
complete freedom to write each product in any
row, as long as it is in the correct column. So
the algorithm can be compactified by a greedy
strategy, as illustrated in the division below.

𝑎𝑎𝑥𝑥 7 + 𝑏𝑏𝑥𝑥 6 + 𝑐𝑐𝑥𝑥 5 + 𝑑𝑑𝑥𝑥 4 + 𝑒𝑒𝑥𝑥 3 + 𝑓𝑓𝑥𝑥 2 + 𝑔𝑔𝑔𝑔 + ℎ

𝑖𝑖𝑥𝑥 4 − 𝑗𝑗𝑥𝑥 3 − 𝑘𝑘𝑥𝑥 2 − 𝑙𝑙𝑙𝑙 − 𝑚𝑚
3 2
𝑟𝑟𝑥𝑥 3 + 𝑠𝑠𝑥𝑥 2 + 𝑡𝑡𝑡𝑡 + 𝑢𝑢
= 𝑛𝑛𝑥𝑥 + 𝑜𝑜𝑥𝑥 + 𝑝𝑝𝑝𝑝 + 𝑞𝑞 + 4
𝑖𝑖𝑥𝑥 − 𝑗𝑗𝑥𝑥 3 − 𝑘𝑘𝑥𝑥 2 − 𝑙𝑙𝑙𝑙 − 𝑚𝑚

qj
pj pk qk
oj ok ol pl ql
nj nk nl nm om pm qm
a b c d e f g h
j k l m a o0 p0 q0 r s t u
/i n o p q
The following describes how to perform the
algorithm; this algorithm includes steps for
dividing non-monic divisors:

1. Write the coefficients of the dividend on a

bar.

Ignoring the first (leading) coefficient of the

divisor, negate each coefficients and place them
on the left-hand side of the bar.

From the number of coefficients placed on the

left side of the bar, count the number of
dividend coefficients above the bar, starting
from the rightmost column. Then place a vertical
bar to the left, and as well as the row below, of
that column. This vertical bar marks the
separation between the quotient and the
remainder.

j k l m a b c d e f g h

/i

Drop the first coefficient of the dividend below

the bar.

Do as follows.

a. Divide the previously

dropped/summed number by the
leading coefficient of the divisor and
place it on the row below (this
doesn't need to be done if the
leading coefficient is 1). In this case
n = a/i.

b. Multiply the previously

dropped/summed number (or the
divided dropped/summed number) to
each negated divisor coefficients on
the left (starting with the left most);
 skip if the dropped/summed number
is zero. Place each product on top of
the subsequent columns.

Perform a column-wise addition on the next

column.

Repeat the previous two steps. Stop when you

performed the previous two steps on the
number just before the vertical bar.
Let o = o 0/i, p = p 0/i, q = q 0 /i.

Perform the remaining column-wise additions on

the subsequent columns (calculating the
remainder).

The bottommost results below the horizontal bar

are coefficients of the polynomials, the
remainder and the quotient. Where the
coefficients of the quotient is to the left of the
vertical bar separation, and the coefficients of
the remainder to the right. These coefficients
would be interpreted with increasing degree
from right to left beginning with degree zero for
both the remainder and the quotient.

FAST DIVISION METHODS

NEWTON–RAPHSON DIVISION
Newton–Raphson uses Newton's method to find
the reciprocal of D, and multiply that reciprocal
by N to find the final quotient Q.

The steps of Newton–Raphson division are:

1. Calculate an estimate X 0 for the reciprocal

1/D of the divisor D.
 2. Compute successively more accurate
estimates X 1 ,X 2, …, X S of the reciprocal.
This is where one employs the Newton–
Raphson method as such.

3. Compute the quotient by multiplying the

dividend by the reciprocal of the divisor: Q
= N×X S .

In order to apply Newton's method to find the

reciprocal of D, it is necessary to find a function
f(X) which has a zero at X=1/D. The obvious
such function is f(X)=DX-1, but the Newton–
Raphson iteration for this is unhelpful since it
cannot be computed without already knowing
the reciprocal of D. Moreover, multiple iterations
for refining reciprocal are not possible since
higher order derivatives do not exist for f(X). A
function which does work is f(X)=(1/X)-D, for
which the Newton–Raphson iteration gives:

𝑓𝑓(𝑋𝑋𝑖𝑖 ) 1/𝑋𝑋𝑖𝑖 − 𝐷𝐷
𝑋𝑋𝑖𝑖+1 = 𝑋𝑋𝑖𝑖 − = 𝑋𝑋𝑖𝑖 −
𝑓𝑓 ′ (𝑋𝑋𝑖𝑖 ) −1/𝑋𝑋𝑖𝑖2
= 𝑋𝑋𝑖𝑖 + 𝑋𝑋𝑖𝑖 (1 − 𝐷𝐷𝑋𝑋𝑖𝑖 ) = 𝑋𝑋𝑖𝑖 (2 − 𝐷𝐷𝑋𝑋𝑖𝑖 )

which can be calculated from X i using only

multiplication and subtraction, or using two
fused multiply–adds.

From a computation point of view the

expressions X i+1 = X i + X i (1 - DX i ) and X i+1 = X i (2
- DX i ) are not equivalent. To obtain a result with
a precision of n bits while making use of the
second expression one must compute the
product between X i and (2 - DX i ) with double the
required precision (2n bits). In contrast the
product between X i and (1 - DX i ) need only be
computed with a precision of n bits.

If the error is defined as 𝜖𝜖𝑖𝑖 = 𝐷𝐷𝑋𝑋𝑖𝑖 − 1 then:

 𝜖𝜖𝑖𝑖+1 = 𝐷𝐷𝑋𝑋𝑖𝑖+1 − 1 = 𝐷𝐷�𝑋𝑋𝑖𝑖 (2 − 𝐷𝐷𝑋𝑋𝑖𝑖 )� − 1
= 2𝐷𝐷𝑋𝑋𝑖𝑖 − 𝐷𝐷2 𝑋𝑋𝑖𝑖 2 − 1 = −�𝐷𝐷2 𝑋𝑋𝑖𝑖 2 − 2𝐷𝐷𝑋𝑋𝑖𝑖 + 1�
= −(𝐷𝐷𝑋𝑋𝑖𝑖 − 1)2 = −𝜖𝜖𝑖𝑖 2

This squaring of the error at each iteration step

— the so-called quadratic convergence of
Newton–Raphson's method — has the effect
that the number of correct digits in the result
roughly doubles for every iteration, a property
that becomes extremely valuable when the
numbers involved have many digits (e.g. in the
large integer domain). But it also means that the
initial convergence of the method can be
comparatively slow, especially if the initial
estimate X 0 is poorly chosen.

Use other division algorithms to compute an

initial estimation to initialize Newton–Raphson's
method.

GOLDSCHMIDT DIVISION
Goldschmidt (after Robert Elliott Goldschmidt)
division uses an iterative process of repeatedly
multiplying both the dividend and divisor by a
common factor Fi , chosen such that the divisor
converges to 1. This causes the dividend to
converge to the sought quotient Q.

The steps for Goldschmidt division are:

1. Generate an estimate for the multiplication

factor F i .

2. Multiply the dividend and divisor by Fi .

3. If the divisor is sufficiently close to 1,

return the dividend, otherwise, loop back
to step 1.
Assuming N/D has been scaled so that 0 < D <
1, each Fi is based on D:
𝐹𝐹𝑖𝑖+1 = 2 – 𝐷𝐷𝑖𝑖

Multiplying the dividend and divisor by the factor

yields:

𝑁𝑁𝑖𝑖+1 𝑁𝑁𝑖𝑖 𝐹𝐹𝑖𝑖+1

=
𝐷𝐷𝑖𝑖+1 𝐷𝐷𝑖𝑖 𝐹𝐹𝑖𝑖+1

After a sufficient number k of iterations Q = N k.

BINOMIAL THEOREM
The Goldschmidt method can be used with
factors that allow simplifications by the binomial
theorem. Assuming N/D has been scaled by a
1
power of two such that 𝐷𝐷 ∈ � , 1�. We choose D
2
2𝑖𝑖
= 1 - x and 𝐹𝐹𝑖𝑖 = 1 + 𝑥𝑥 . This yields:

𝑁𝑁 𝑁𝑁 ⋅ (1 + 𝑥𝑥) 𝑁𝑁 ⋅ (1 + 𝑥𝑥) ⋅ (1 + 𝑥𝑥 2 )
= = =⋯
1 − 𝑥𝑥 1 − 𝑥𝑥 2 1 − 𝑥𝑥 4
(𝑛𝑛−1)
𝑁𝑁 ′ = 𝑁𝑁 ⋅ (1 + 𝑥𝑥) ⋅ (1 + 𝑥𝑥 2 ) ⋅⋅⋅ �1 + 𝑥𝑥 2 �
= 𝑄𝑄′ = 𝑛𝑛
𝐷𝐷′ = 1 − 𝑥𝑥 2 ≈ 1
1
After n steps (𝑥𝑥 ∈ �0 , �), the denominator 1 −
2
𝑛𝑛
𝑥𝑥 2 can be rounded to 1 with a relative error

𝑄𝑄′ − 𝑁𝑁 ′ 𝑛𝑛
ϵ𝑛𝑛 = ′
= 𝑥𝑥 2
𝑄𝑄
𝑛𝑛
which is maximum at 2−2 when x = 1/2, thus
providing a minimum precision of 2 n binary
digits.
EUCLIDEAN ALGORITHM

In mathematics, the Euclidean algorithm, or

Euclid's algorithm, is an efficient method for
computing the greatest common divisor (GCD)
of two numbers, the largest number that divides
both of them without leaving a remainder.

It is an example of an algorithm, a step-by-step

procedure for performing a calculation
according to well-defined rules, and is one of
the oldest algorithms in common use. It can be
used to reduce fractions to their simplest form,
and is a part of many other number-theoretic
and cryptographic calculations.

The Euclidean algorithm is based on the

principle that the greatest common divisor of
two numbers does not change if the larger
number is replaced by its difference with the
smaller number. For example, 21 is the GCD of
252 and 105 (252 = 21 × 12 and 105 = 21 × 5),
and the same number 21 is also the GCD of 105
and 147 = 252 − 105. Since this replacement
reduces the larger of the two numbers,
repeating this process gives successively
smaller pairs of numbers until one of the two
numbers reaches zero. When that occurs, the
other number (the one that is not zero) is the
GCD of the original two numbers. By reversing
the steps, the GCD can be expressed as a sum
of the two original numbers each multiplied by a
positive or negative integer (as a linear
combination), e.g., 21 = 5 × 105 + (−2) × 252.

The version of the Euclidean algorithm

described above (and by Euclid) can take many
subtraction steps to find the GCD when one of
the given numbers is much bigger than the
other. A more efficient version of the algorithm
shortcuts these steps, instead replacing the
larger of the two numbers by its remainder when
divided by the smaller of the two. With this
improvement, the algorithm never requires more
steps than five times the number of digits (base
10) of the smaller integer.

The Euclidean algorithm has many theoretical

and practical applications. It is used for
reducing fractions to their simplest form and for
performing division in modular arithmetic. The
Euclidean algorithm may be used to solve
Diophantine equations, such as finding numbers
that satisfy multiple congruences according to
the Chinese remainder theorem, to construct
continued fractions, and to find accurate rational
approximations to real numbers. Finally, it can
be used as a basic tool for proving theorems in
number theory such as Lagrange's four-square
theorem and the uniqueness of prime
factorizations. The original algorithm was
described only for natural numbers and
geometric lengths (real numbers), but the
algorithm was generalized in the 19th century to
other types of numbers, such as Gaussian
integers and polynomials of one variable. This
led to modern abstract algebraic notions such
as Euclidean domains.

WORKED EXAMPLE
For illustration, the Euclidean algorithm can be
used to find the greatest common divisor of a =
1071 and b = 462. To begin, multiples of 462
are subtracted from 1071 until the remainder is
less than 462. Two such multiples can be
subtracted, leaving a remainder of 147: 1071 =
2 × 462 + 147.
Then multiples of 147 are subtracted from 462
until the remainder is less than 147. Three
multiples can be subtracted, leaving a
remainder of 21: 462 = 3 × 147 + 21.

Then multiples of 21 are subtracted from 147

until the remainder is less than 21. Seven
multiples can be subtracted, leaving no
remainder: 147 = 7 × 21 + 0.

Since the last remainder is zero, the algorithm

ends with 21 as the greatest common divisor of
1071 and 462.