Representation of integers

 

• integers are standardly represented by one computer word of bits; in such a representation, the size of an integer is limited by ; for example,

  if ,

  if and

  if

• however, we also need to represent arbitrarily big integers; e.g., see pseudo-remainders during calculation of GCDs

• one possibility to to represent a big integer by an array where all elements of the array are limited by and

• thus, the big integer is expressed in a number system with base

• of course, memory is finite and so we can store only a number of a limited size, however using this representation we can work with quite large integers, e.g., in 1 kB of memory we can store an integer of size