A number system is represented by a sequence of characters which represent its digits. For example, the decimal number system (also called the base-10 number system) has the characters '0', '1', '2', '3', '4', '5', '6', '7', '8' and '9' as its digits. Representing the number system in this sequence also means the following:
- The first digit (for decimal system, it's '0') is the additive idempotent number. In other words, the effect of adding it to any other number is the same number. In more worldly language, it represents the smallest natural number, or simply, the zero.
- The first number is the multiplicative idempotent number. Which means that by multiplying it to any number, you get back the same number. Also, the difference between any two successive numbers in this number system is this number. In simplest possible terms, its value is one.
- Definition of one gives the definition of the successor function. succ(x) = x + one.
- Addition is repetitive application of the succ function. For instance, in decimal system:
add(3, 4) = succ (succ (succ (succ (3)))) = succ(succ(succ(4))) = succ(succ(5)) = succ(6) = 7.
- Multiplication is a repetitive application of addition function between the number and itself.
multiply(3, 4) = add(3, add(3, add(3, 3))) = add(3, add(6))) = add(3, 9) = 12.
add and multiply functions to simulate the algorithms generally used in manual calculations.Interface:
#ifndef NUMBERSYSTEM_H
#define NUMBERSYSTEM_H
#include <vector>
#include <map>
#include <string>
using namespace std;
class NumberSystem
{
private:
string m_Digits;
map< pair <char, char>, string> m_AddMap;
map< pair <char, char>, string> m_MultiplyMap;
public:
NumberSystem (string);
string add (string, string);
string add (char, char);
string add (string, char);
string multiply (char, char);
string multiply (string, string);
string succ (string);
string prev (string);
string getDigits ();
string getZero ();
char operator[] (unsigned int);
unsigned int size ();
};
string reverse (string);
#endif
#include "NumberSystem.h"
NumberSystem::NumberSystem (string aDigits)
: m_Digits (aDigits)
{
// set up a lookup table to to speeden up the addition of two
// single digit numbers. Currently not used anywhere.
for (unsigned int i = 0; i < m_Digits.size (); i++)
{
for (unsigned int j = 0; j < m_Digits.size (); j++)
{
char a = m_Digits[i];
char b = m_Digits[j];
string sum = add (a, b);
pair <char, char> p = pair <char, char>(a, b);
m_AddMap[p] = sum;
}
}
// set up a lookup table to to speeden up the multiplication of two
// single digit numbers. Currently not used anywhere.
for (unsigned int i = 0; i < m_Digits.size (); i++)
{
for (unsigned int j = 0; j < m_Digits.size (); j++)
{
char a = m_Digits[i];
char b = m_Digits[j];
string product = multiply (a, b);
pair <char, char> p = pair <char, char>(a, b);
m_MultiplyMap[p] = product;
}
}
}
// Adds two single digit numbers.
string
NumberSystem::add (char a, char b)
{
string sum(" ");
sum[0] = a;
sum[1] = m_Digits[0];
int j = m_Digits.find (b);
for (unsigned int k = 1; k <= j; k++)
{
sum = succ (sum);
}
return sum;
}
// adds two numbers, one single digit, and another non-single digit.
string
NumberSystem::add (string a, char b)
{
string sum = a;
unsigned int j = m_Digits.find (b);
for (unsigned int k = 1; k <= j; k++)
{
sum = succ (sum);
}
return sum;
}
// adds two non-single digit numbers.
string
NumberSystem::add (string n1, string n2)
{
string a;
string b;
if (n1.size () >= n2.size ())
{
a = n1;
b = n2;
}
else
{
a = n2;
b = n1;
}
string sum;
char carry = m_Digits[0];
for (unsigned int i = 0; i < b.size (); i++)
{
string digitSum = add (a[i], b[i]);
digitSum = add (digitSum, carry);
sum = sum + digitSum[0];
if (digitSum.size () == 2)
{
carry = digitSum[1];
}
else
{
carry = m_Digits[0];
}
}
for (unsigned int i = b.size (); i < a.size (); i++)
{
string digitSum = add (add (a[i], m_Digits[0]), carry);
sum = sum + digitSum[0];
if (digitSum.size () == 2)
{
carry = digitSum[1];
}
else
{
carry = m_Digits[0];
}
}
if (carry != m_Digits[0])
{
sum = sum + carry;
}
return sum;
}
// given any number, it returns the successor of it.
string
NumberSystem::succ (string aNum)
{
if (aNum[0] == m_Digits[m_Digits.size () - 1])
{
aNum[0] = m_Digits[0];
}
else
{
aNum[0] = m_Digits[m_Digits.find (aNum[0]) + 1];
return aNum;
}
for (unsigned int i = 1; i < aNum.size (); i++)
{
if (aNum[i - 1] == m_Digits[0])
{
if (aNum[i] == m_Digits[m_Digits.size () - 1])
{
aNum[i] = m_Digits[0];
}
else
{
aNum[i] = m_Digits[m_Digits.find (aNum[i]) + 1];
return aNum;
}
}
}
if (aNum[aNum.size () - 1] == m_Digits[0])
{
aNum = aNum + m_Digits[1];
}
return aNum;
}
// given any number, this function returns a previous number. Not implemented
// as yet.
string
NumberSystem::prev (string aNum)
{
return aNum;
}
// multiplies two single-digit numbers.
string
NumberSystem::multiply (char aa, char bb)
{
string product (1, m_Digits[0]);
for (string counter (1, m_Digits[0]); counter != string (1, aa); counter = succ (counter))
{
product = add (product, bb);
}
return product;
}
//multiplies two non-single digit numbers.
string
NumberSystem::multiply (string a, string b)
{
vector <string> Products;
for (unsigned int i = 0; i < a.size (); i++)
{
char carry = m_Digits[0];
string product1;
for (unsigned int j = 0; j < i; j++)
{
product1 = product1 + (m_Digits[0]);
}
for (unsigned int j = 0; j < b.size (); j++)
{
string digitProduct = multiply (a[i], b[j]);
digitProduct = add (digitProduct, carry);
product1 = product1 + digitProduct[0];
if (digitProduct.size () == 2)
{
carry = digitProduct[1];
}
else if (digitProduct.size () == 1)
{
carry = m_Digits[0];
}
else
{
exit (1);
}
}
if (carry != m_Digits[0])
{
product1 = product1 + carry;
}
Products.push_back (product1);
}
string product (1, m_Digits[0]);
for (unsigned int i = 0; i < Products.size (); i++)
{
product = add (product, Products[i]);
}
return product;
}
// returns the digits of the number system.
string
NumberSystem::getDigits ()
{
return m_Digits;
}
// returns the zero value of the number system.
string
NumberSystem::getZero ()
{
return string (1, m_Digits[0]);
}
// returns the apos-th digit of the number system
char
NumberSystem::operator [] (unsigned int apos)
{
return m_Digits[apos];
}
// returns the number of digits in the number system.
unsigned int
NumberSystem::size ()
{
return m_Digits.size ();
}
// reverses a string. Used for user-interface purposes.
string reverse (const string s)
{
string o;
if (s.size ())
{
for (unsigned int i = 0; i < s.size (); i++)
{
o = o + s[s.size () - i - 1];
}
}
return o;
}
That's it!
No comments:
Post a Comment