4.3. Multiple-Precision Arithmetic

LET US NOW consider operations on numbers that have arbitrarily high precision. For simplicity in exposition, we shall assume that we are working with integers, instead of with numbers that have an embedded radix point.

4.3.1. The Classical Algorithms

In this section we shall discuss algorithms for

  1. addition or subtraction of n-place integers, giving an n-place answer and a carry;

  2. multiplication of an m-place integer by an n-place integer, giving an (m + n)-place answer;

  3. division of an (m + n)-place integer by an n-place integer, giving an (m + 1)-place quotient and an n-place remainder.

These may be called the classical algorithms, since the word “algorithm” was used only in connection with these processes ...

Get Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial