Numbers

In this tutorial we introduce the natural numbers $\mathbb{N}$ and the data types available in a programming language used to represent them. We want to highlight the difference between a single digit and a number, and their connection to the used base. The picture demonstrates the different meanings of each of these parts.

A number is represented by several single digits, with each digit being a factor for a corresponding power of the base. The number is only complete when both the base (depicted with the blue color) and all of the digits (red color) are known. To use an example, the digit sequence 123 is calculated with the corresponding base, e.g. base = 10:

$123_{10} = 1 \cdot 10^{2} + 2 \cdot 10^{1} + 3 \cdot 10^{0}$

If the base is switched, e.g. base = 4, then the following numbers are derived:

$123_{4} = 1 \cdot 4^{2} + 2 \cdot 4^{1} + 3 \cdot 4^{0} = 27_{10}$

One of the drawbacks of the representation of numbers within the computer is the fact that the built-in types such as int and long can only use a finite number of bits and are hence limited in their range (the int can be omitted), e.g.:

short int:	-32768	..	+32767
long int:	-2147483648	..	+2147483647
unsigned long int:	0	..	+4294967295

Arbitrarily Sized Decimal Numbers

Write a single program for each of the following:

L2: Create an array of integers which can be used as an arbitrarily sized decimal number. Write functions to initalize, edit, and swap single elements of the array.

L2: Extend the previous program to include the operations of addition and subtraction of two arrays of integers.

L2: Extend the previous program with multiplication and division of two arrays of integers.

L2: Extend the previous program to include a prime test of an array of integers.

L3: Extend the previous program to include root calculations of an array of integers.

L3: Extend the previous program to include power of an array of integers.

Hints

	Root: what can you do if there is no root function available? Do not forget, that the computer can do a lot opertions per second.
	Power: Russion Peasant Algorithm

C++ Reference Implementation

The boost::lexical_cast function can be found at: www.boost.org/libs/conversion/index.html

#include<iostream>
#include<cmath>
#include<vector>
#include<boost/lexical_cast.hpp>
class arbitrary_decimal
{
  typedef arbitrary_decimal self;
 public:
  arbitrary_decimal(std::string number)
  {
    base_container.resize(number.size());
    for (unsigned long i =0; i < number.size(); ++i)
      {
	base_container[i] = boost::lexical_cast<long>(number[i]);
      }
  }
  long operator[](long index) 
  {
    return base_container.at(index);
  }
  long size()
  {
    return base_container.size();
  }
  self& operator+=(self& other)
  {
    for (long i =size()-1; i >= 0;--i)
      {
	base_container[i] += other[i];
	if ( base_container[i] > 9)
	  {
	    base_container[i-1] +=1;
	    base_container[i] -=10;
	  }
      }
    return *this;
  }
  friend std::ostream& operator<<(std::ostream& ostr, self& ad)
  {
    for (long i =0; i < ad.size(); ++i)
      {
	ostr << ad[i];
      }
    ostr << std::endl;
    return ostr;
  }
 private:
  std::vector<char> base_container;
};
int main()
{
  arbitrary_decimal   ad1("1234");
  arbitrary_decimal   ad2("5678");
  std::cout << "ad1: " << ad1 << std::endl;
  std::cout << "ad2: " << ad2 << std::endl;
  ad1 += ad2;
  std::cout << "ad1+ad2: " << ad1 << std::endl;
  return 0;
}