Department with really big numbers

Question

I'm just wondering what different strategies exist for dividing when dealing with large numbers. By large numbers, I mean ~ 50 digits.

eg. 9237639100273856744937827364095876289200667937278/8263744826271827396629934467882946252671

When both numbers are large, a long division seems to lose its usefulness ...

I thought one possibility was to count the divisor multiplications until you switch to a dividend, but if it were the dividend in the above example, divided by a small number, for example. 4, then this is a huge amount of computation.

So, is there a simple, clean way to do this?

Answer 1

What language / platform are you using? This is most likely already resolved, so you don't need to implement it from scratch. For instance. Haskell has an Integer type, Java class java.math.BigInteger , .NET System.Numerics.BigInteger structure, etc.

If your question is truly theoretical, I suggest you read Knuth, The Art of Computer Programming, Volume 2, Section 4.3.1. What you are looking for is called Algorithm D. Here is an implementation of this C algorithm along with a short explanation: http://hackers-delight.org.ua/059.htm

Answer 2

Long separation is not very difficult if you are working with binary representations of your numbers and probably the most efficient algorithm.

Answer 3

if you don’t need a very accurate result, you can use logarithms and indicators. The exponent is the function f (x) = e ^ x, where e is the mathematical constant equal to 2.71828182845 ...
The logarithm (indicated by ln) is the opposite of the exponent.

Since ln (a / b) = ln (a) -ln (b), to calculate a / b you need:
Calculate ln (a) and ln (b) [By library function, logarithmic table or other methods]
tune them: temp = ln (a) -lb (b)
calculate exponent e ^ temp