Division algorithm without using the representation

Question

I am trying to find a division algorithm that does not use the representation of numbers; similar to the repeated subtraction algorithm, but faster! Is there any such algorithm?

Edit 1: We already have a subroutine for solving a/b if a<10b. We also have a subroutine for division by constant 10.

Edit 2: What I meant by "not using the representation" is that we do not have to process individual digits in a say 5 digit whole number. For example, if we have two integers say a=150 and b=27, I have to find a/b just using the variables a and b, not the digits 1,5,0 in a.

Answer 1

The algorithm for this turned out to be quite simple.

Divide(int a, int b){
   if (a <10*b) return divSubRoutine(a, b);
   int q = Divide (divbyConst(a,10), b);
   int r = a - 10*b*q;
   return Divide(r, b) + 10*q;
}

Answer 2

Your question isn't very clear on what you are looking for. If you don't allow any representation of numbers, how do you store numbers in the first place, not to say compute anything with them? So you've to specify what operations you allow on numbers (basic operations).

Say you want to find $x \div y$ for positive integers $x,y$.

If you allow only addition, subtraction and comparison, then just use repeated doubling to find the largest power of two that is not greater than the $x$. Then you can imitate the long division algorithm in base $2$. This takes a total of $O(\log_2(x))$ basic operations. Since the basic operations take $O(\log_2(x))$ time each, the total time would be $O(\log_2(x)^2)$.

Answer 3

You can compute $x = \frac{1}{y}$ for given $y$ as follows. We write $x$ as the solution of the nonlinear equation:

$$y - \frac{1}{x} = 0$$

The Newton-Raphson method then yields the successive approximations:

$$x_{n+1} = 2 x_n - y x_n^2$$

In each step the number of correct digits is doubled.