How can I divide a big number with another big number? Is there some way I can break the divisor in smaller chunks too?

Question

Suppose I have to a big number like 1234567897531 with another big number like 23456789, the long division method would be algorithmically expensive as it involves intuition to find appropriate multiple for portions for the divisors.

Conventionally Scientific Programming languages would strip divisor down to precision system's ALU can handle in a single shot (could be the 64-bit value at most in conventional PCs).

What am I doing this? I am trying to develop an open-source Package for Performing operations on Big numbers. Check out my work : My Github Repos for Big Numbers

Answer 1

Note that that if $n_1=m_1\cdot 10^{e_1}$ and $n_2=m_2\cdot 10^{e_2}$, then $\dfrac{n_1}{n_2}=\dfrac{m_1}{m_2}\cdot 10^{e_1-e_2}$.

Answer 2

It is much easier in the base $2$ representation that computers use. We have $1234567897531_{10}=10001111101110001111110110010000110111011_2$ and $23456789_{10}=1011001011110110000010101_2$ The first is $41$ bits long and the second $25$. We can just look at the leading bits to see that we cannot multiply the second by $2^{16}$ and have it less than the first, so our first partial quotient is $2^{15}$. That doesn't take intuition at all. We then subtract $2^{15}$ times the divisor from the dividend and repeat.

Answer 3

You might want to take a look at how cryptographic libraries operate on large numbers

Standard techniques are using long division or some form of the Eucledian algorithm.

For faster floating point division, usually approximate methods like Newton-Raphson Method can be used

For fast integer division, something like Montgomery reduction is usually used