Numeral System Change in Arithmetic and Matricial Formalism
Raoelina Andriambololona, Ravo Tokiniaina Ranaivoson, Hanitriarivo Rakotoson
Theoretical Physics Department, Institut National des Sciences et Techniques Nucléaires (INSTN-Madagascar), Antananarivo, Madagascar
Email address:
To cite this article:
Raoelina Andriambololona, Ravo Tokiniaina Ranaivoson, Hanitriarivo Rakotoson. Numeral System Change in Arithmetic and Matricial Formalism. Pure and Applied Mathematics Journal. Vol. 5, No. 3, 2016, pp. 87-92. doi: 10.11648/j.pamj.20160503.15
Received: May 12, 2016; Accepted: May 25, 2016; Published: June 7, 2016
Abstract: The main goal of this paper is to present a method to tackle the numeral system change problem using matricial formalism. In a previous work, we have described an approach which permits to use matricial formalism and matricial calculation in writing numeration and arithmetic. The present paper is focused on the study of the problem of numeral system change in the framework of this approach. The cases of integer numbers and of more general numbers are given.
Keywords: Numeral System, Arithmetic, Radix, Matricial Formalism, Basis Change
1. Introduction
In a previous paper [1] we have presented an approach which permits the introduction of some tools of linear algebra like matricial formalism and matricial calculation [2], [3], [4] in the problem of writing numeration and arithmetics [5], [6], [7], [8]. This approach is based on the work performed by Raoelina Andriambololona since 1986 [9] [10], [11]. In the present work, our goal is to study the problem of numeral system change in the framework of this approach.
It was shown in our work [1] that, considering a numeral system with the radix , a number can be considered as the product of a row matrix and a column matrix built with the successive powers of
(1)
The row matrix is the writing or the representation of the intrinsic number in the numeral system with radix .
Another numeral system corresponding to another radix can be considered. Then in this new numeral system, the number will be represented by another row matrix .
(2)
In general and when . The problem of numeral system change, that we tackle in the present paper, is to establish the relationship between and on one hand and and on another hand.
2. System Change: Case of Integers
Let us consider two systems of numeration corresponding respectively to two different radices and . Let be an integer number. Let us denote respectively and the row matrices representing the number respectively in each of those numeral systems and let and be the column matrices representing respectively the powers of and
(3)
(4)
(5)
(6)
As previously mentioned in the introduction, our goal is to find the relationship between and on one hand and and on another hand.
Let us consider the relations (3), (4), (5) and (6). The numbers and are not necessary equal. The choice of and is fixed by the basis change matrix defined by the relation
Generally, the matrix has an indefinite dimension. However, as it will be shown below, a rectangular matrix can be chosen.
The expressions of the number is
As and are basis, it can be deduced that
The writing of in the numeral system with the radix is obtained immediately from the numeral system with the radix using matricial calculation.
Many elements of the matrix are null but in practical calculation, this matrix can be reduced to a rectangular matrix with elements . The numbers and are chosen such as we take into account all of non-null contributions in the calculations of and .
and are row matrices respectively with and columns; we complete with zeros if necessary.
There are two cases.
1^{st}case: the term
is less than . is obtained immediately without performing any calculation.
2^{nd} case: the term
is such as
Then
with
in the numeral system with the radix , we have
The remainder is to be brought into the column from the right handside and is the figure to be put at the column from the right handside.
Generalization: let us consider
where
then
It means that
-the number at the column from the right handside is
-the number at the column from the right handside is
-the number at the column from the right handside is
The are the "remainders" which must be added to the other contributions. The calculation rules which must be utilized can be seen immediately. We are led to perform additions and multiplications in respecting the places of the figures and to add the necessary remainders (it is the current rules for addition in arithmetic). The simplicity of the method will be illustrated by some examples. The calculations may be performed with a microcomputer.
Remarks: There is one and only one matrix such that
(7)
(8)
Generalizing the notion of matrix inverse in the case of finite dimension, and are inverses in the case of indefinite dimension. More rigorously, (respectively) is the left handside inverse (respectively the right handside inverse) of (respectively of ). They are linked by the relations (see appendix)
(9)
in which and are the and identity matrices respectively in the numeral systems with the radices and .
3. Examples: Case of Integer Numbers
Example 1: let be the number in the system of numeration with the radix . Let us look for the writing of in the decimal system (radix).
The basis change matrix is deduced from the relation
The elements of the basis change matrix which contribute are indicated below
The terms which don’t contribute were represented by zeros or dots or blanks when necessary.
It is easy to check
or
We obtain immediately the writing in the numeral system with the radix 10 without remainder because each obtained term is less than . It will not be the case in the examples 3 and 4.
Example 2: let be the number in the numeral system with the radix. Let us look for the writing of in the decimal system
The terms designed by and
are greater than . Then, there are remainders.
By taking the dispositions which respects for (A) and (B) the succession of in the basis, we add the elements in the same column in bringing the remainder if necessary to the left handside column which follows immediately (it is the classical rule for addition). Then
The answer is 208 861. It is easy to check
Example 3: Find the writing of the binary number in the decimal system.
The formalism is particularly interesting for the system change concerning the binary system because we have only two figures 0 and 1.
The basis and are writen explicitly for a better undestanding. But in practical calculation, it is sufficient to write the basis change matrix and to take into account the terms which contribute to the calculation
The term gives 7 in the first column from the right handside with remainder 1 which is to be added to the number 1 of the second column at the left handside to give the number 2.
It is easy to check
or
Example 4: Find the decimal writing of the octal number
The basis change matrix is given by the relation
The decimal writing of the given octal number can be obtained immediately by performing the matricial product
The disposition of the figures of the partial sums that we have indicated between brackets should be noted. The figures are added column by column beginning from the right handisde to the left handside and bringing the remainder when needed. It is easy to check that
Or
4. Generalization
4.1. Number with Radix Point But with Finite Numbers After the Radix Point
We have considered the basis with for then generalization can be made by taking . In the writing of the number, the figures corresponding to and are separated by a point (the radix point)
Example: the number
is written in the numeral system with the radix as the row matrix .
For instance, in the numeral system with the radix , the number 101.101 is the row matrix
representing the expansion
Applying the method described above, we obtain
which is written in the decimal system.
Let be the finite maximum number of the figures not appearing after the point. Multiplying by , we are taken back to the previous case.
4.2. Number with Radix Point But with Infinite Number After the Radix Point
Although the number of figures after the radix point is infinite, the method may again be applied by using approached values by excess and by less: the given number is framed between two finite fixed point numbers. We are taken back to the case 4.1.
4.3. Infinite Number at the Left of the Figure Corresponding to b^{0}
The number itself is infinite and has no sense. The method is of course not applicable.
5. Conclusion
It is shown in our first paper [1] that the use of matricial formalism can be introduced to deal with the problem of writing numeration and arithmetics. In this second paper, our approach is extended for the study of the problem of numeral system change.
The above results show that our method is very efficient. It gives directly the writing of the number in the new system by a more simple and more swift way than the classical method using successive euclidian divisions. The used rules are the current ones of addition, multiplication and matrix calculation (row-column product).
Our method may be applied in the framework of computer science [12].
All along this paper, the basis was represented by a column matrix by decreasing order from the highest values to the lowest ones so that we obtain the current writing of a number as a row matrix, writing from left handside to right handside, following to the ordinary writing by decreasing order (LRd disposition). However, this current writing is inconsistent with adding the remainders from the right handside to the left handside. This inconsistency may be overcome by adopting the writing as row matrix from the left handside to the right handside by increasing order LRi [1]
Appendix: practical calculation
In the paragraph 2, the relationship between the basis and and the basis changes matrices and was written (relations 7, 8 and 9)
where (respectively is unity matrix in the basis (respectively ).
We give more details about this remark by expliciting the practical calculation in the case of the example 4 in the paragraph 3. Then the simplicity of the obtention of the results utilizing matricial formalism is shown.
The numeration basis change matrix from the decimal system to the octal system is such that
Inversely
In practical calculation, we leave void the places occupied by zeros.
Let us perform the products and . For the product
By performing the calculation in the decimal basis, we find
where is obviously the identity matrix in the decimal system.
For the calculation of the product , there are two possible methods:
i) We may perform the matrix product in decimal basis and after convert the result in the octal system.
ii) We may convert the elements of the matrices in octal system and then perform the matrix product in the octal system (using octal multiplication and addition tables: see below.)
The two possible methods lead to the same result with the identity matrix in the octal system. If the calculation is performed in the octal system, we need the octal system multiplication and addition tables.
For octal system multiplication table
For the octal system addition table
The results in the example 4 can be verified as well. We can show that the number in octal system is written in decimal system and reciprocally. The basis change matrices are respectively and .
All operations are, of course, performed in the decimal system. Inversely, we can also find after performing calculation in the octal system that
References