Is long division the most optimal "effective procedure" for doing division problems?

(Motivation: I am going to be working with a high school student next week on long division, which is a subject I strongly dislike.)

Consider: $\frac{1110}{56}=19\frac{46}{56}$.

This is really a super easy problem, since once you realize $56*20=1120$ its trivial to write out $1110=56*19+46$.

You can work out the long division for yourself if you want; needless to say it makes an otherwise trivial problem into a tedious, multi-step process.

Long division is an "effective procedure", in the sense that a Turing machine could do any division problem once it's given the instructions for the long division procedure. To put it another way, an effective procedure is one for which given any problem of a specific type, I can apply this procedure systematically to this type of problem, and always arrive at a correct solution.

Here are my questions:

1) Are there other distinct effective procedures for doing division problems besides long division?

2) Is there a way to measure how efficient a given effective procedure is for doing division problems?

3) Does there exist an optimal effective procedure for division problems, in the sense that this procedure is the most efficient?

Methods for division and the other basic arithmetic operations are explained in Knuth's ACP vol. 2, Seminumerical Algorithms. For the sake of humans doing longhand division, perhaps the most relevant point is the discussion of trial divisors.

As you will recall, when faced with a problem like $1110/56$ (asked to find the quotient and remainder, which amounts to giving the fraction in mixed form), the basic instruction is to use the leading digit of the divisor to "guess" (estimate) the next digit of the quotient.

It is often the case that this "guess" will be an overestimate, i.e. that the trial divisor proves to be too big for the divisor as a whole. For example, here when trying to tell how many times the divisor as a whole $56$ will go into the leading digits $111$ of the dividend, we would "guess" $2$ times, because leading digit $5$ certainly goes into $11$ two times.

This turns out, frustratingly, to be a wrong guess in that $56$ times two gives $112$ (over the limit of $111$), and our trial divisor has to be reduced by one and checked again.

Knuth's explanation covers arbitrary (fixed positive integer) radix b > 1. Reading down to the radix ten (decimal) case, the point would be this. If the divisor's leading digit is "normalized" to be greater than or equal to half the radix (at least 5 in the decimal case, as was true in the example $1110/56$), then the trial divisor obtained in the usual way (estimating by using the leading digit of the divisor) will be at worst $2$ more than the correct next digit in the quotient. [It is suggested that the desired normalization can be arranged by repeatedly doubling both numerator and denominator as necessary, until the leading digit of the denominator (divisor) reaches at least $b/2$.]

An alternative method for getting the trial divisor is then explained that has a better worst case behavior. If the next-to-leading digit of the divisor is at least $b/2$, then for the purpose of the trial divisor we round up the leading digit! Now using that digit (or possible $b=10$ if the rounding takes us to the next "place" value) we will get an estimate for the next digit of the quotient that is off by at most $1$. In the case where no rounding up took place, this means the trial divisor is either correct or too big by one, and in the case where we did round up, this means the trial divisor is either correct or too small by one.

I've seen a monograph where this alternative technique for longhand division was tried with a group of (if memory serves) high school math teachers, as a Master's Thesis in Education that someone did. As it happens I'm in St. Augustine FL where I saw this monograph years ago in a used bookstore. I'll go by there today and if it remains on the shelf post the reference details later.

Added: I found the book (the bookstore itself had moved about five years ago!). My memory of it was not perfect but here are some details:

An Experimental Study of Two Methods of Long Division by Kenneth G. Fuller
Bureau of Publications/Teachers College/Columbia University New York, 1949 (hardback, 76 pages)

The author refers in his acknowledgments to Prof. Clifford B. Upton, and in an early footnote refers to a paper by the same:

"Making Long Division Automatic," Tenth Yearbook, National Council of Teachers of Mathematics, 1935

where the percentages of correcting estimated quotients using a) a trial divisor that consists simply of a leading digit, and b) a trial divisor that is rounded up just when the following divisor digit is greater than five.

According to this account Upton had shown method a) "gives the correct quotient figure on the first trial in only 66.70 per cent of all cases." With method b) one gets "the correct quotient figure on the first trial in 80.43 per cent of all cases, a quotient figure requiring one correction in 19.29 per cent of all cases, and a quotient figure requiring two corrections in .28 per cent of all cases." Method b) did not require "more than two corrections" in any circumstance.

The study then proceeds to compare method b), the variant of our usual approach to trial divisors, and an "experimental method" that builds a table of multiples 1 through 9 of the actual divisor. Fuller points out that the history of both methods can be followed back to Roberte Recorde's Arithmetike (1579, orig. edition 1542).

Building the table of multiples eliminates "trial divisors" and is certainly economical if there are to be several digits in the quotient; table construction can be done by alternate doubling and adding in the divisor. Fuller's approach entailed checking the table of multiples with casting out 9's.

Fuller's comparison of methods was carried out with three fifth grade class during the school year 1946-47 in Connecticut. If I have read the statistical summary properly, the approach using a table of multiples proved more accurate (less error prone), though not in a statistically significant way except for certain longer problems (more digits in the divisor or quotient). The table of multiples also took longer for the students to do, though this was in part because of extra checks involved on the answer and in part because of the modest sizes of problems (2-3 digits in the divisor, 2-4 digits in the quotient).

1) yes, http://en.wikipedia.org/wiki/Division_%28digital%29#Fast_division_methods

2) yes, http://en.wikipedia.org/wiki/Big_O_notation

3) ?, This is an open problem.

The OP asks

Are there other distinct effective procedures for doing division problems besides long division?

You can certainly tweak the long division algorithm to make it better. Here, we will describe one such 'tweak improvement', motivated by the OP's sample problem.

Problem: Divide $1,110$ by $56$.

$560 \times 1 = 560 \le 1,110 \; \checkmark \; \text{OVERSHOOT: } 560 \times 2 = 1,120 \text{, } 1,120 - 1,110 = 10$

Algorithm detects that the overshoot is less than or equal to $56$, so takes this path:

$\frac {1,110}{560} = 2 - \frac{10}{560} \text{ iff }$
$\tag ! \frac {1,110}{56} = 20 - \frac{10}{56} = 19 + \frac{(56-10)}{56} = 19 + \frac{46}{56}$

To better understand this approach, please see this link; it describes a way of organizing your $\text{Base-}10$ long division work that is amenable to tweaks.

For the purpose of comparison, we solve the problem without the above 'one off' enhancement:

$560 \times 1 = 560 \le 1,110 \; \checkmark \; \text{OVERSHOOT: } 560 \times 2 = 1,120 \gt 1,110$

$\frac {1,110}{560} = 1 + \frac{550}{560} \text{ iff }$
$\tag 1 \frac {1,110}{56} = 10 + \frac{550}{56}$

$56 \times 9 = 504 \le 550 \; \checkmark \; \text{OVERSHOOT: } 560$

$\tag 2 \frac {550}{56} = 9 + \frac{46}{56}$

Combining (1) and (2),

$\tag 2 \frac {1,110}{56} = 19 + \frac{46}{56}$

Here we would have to build the entire multiplication table $56 \times n \; | \; 1 \le n \le 9$.

I'm fairly confident that an algorithm could be created that would be able to divide by $D$ with only a $D \times n \; | \; 1 \le n \le 5$ table. The table could be expanded as necessary, using addition to get us up to, if necessary, $D \times 5$.

In binary computing multiplying by $2$ is a shift. But humans also like to double numbers.

An efficient algorithm can be constructed that only multiplies by $2$, subtracts numbers, compares numbers and adds numbers.

Here is this division algorithm applied to $\frac{1110}{56}$.

Create the table:

$56 \times 2^0 \quad \;\, \quad \quad\quad = \;\, 56;\quad 2^0 = 1$
$56 \times 2^1 = 56 \times 2 \;\,= 112;\quad 2^1 = 2$
$56 \times 2^2 = 112 \times 2 = 224;\quad 2^2 = 4$
$56 \times 2^3 = 224 \times 2 = 448;\quad 2^3 = 8$
$56 \times 2^4 = 448 \times 2 = 896;\quad 2^4 = 16$
$56 \times 2^5 = 896 \times 2 \gt 1110 \text{ == STOP == }$

From this point on all that is needed to complete the calculation are the subtraction, comparison and addition operators.

$1110 = 56 \, 2^4 + (1110 - 896) = 56 \, 2^4 + 214 = 56 \, 2^4 +56 \, 2^1 + (214 - 112) = $
$\quad 56 \, 2^4 +56 \, 2^1 + 102 = 56 \, 2^4 + 56 \, 2^1 + 56 \, 2^0 + (102-56) =$
$\quad 56 \, 2^4 + 56 \, 2^1 + 56 \, 2^0 + 46 =$
$\quad (2^4 + 2^1 + 2^0)\,56 + 46 =$
$\quad (16 + 2 + 1)\,56 + 46 =$
$\quad 19\times 56 + 46 $