HOME

TheInfoList



OR:

The quater-imaginary numeral system is a
numeral system A numeral system (or system of numeration) is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using Numerical digit, digits or other symbols in a consistent manner. The same s ...
, first proposed by
Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
in 1960. Unlike standard numeral systems, which use an integer (such as 10 in decimal, or 2 in binary) as their bases, it uses the
imaginary number An imaginary number is a real number multiplied by the imaginary unit , is usually used in engineering contexts where has other meanings (such as electrical current) which is defined by its property . The square of an imaginary number is . Fo ...
2''i'' (equivalent to \sqrt) as its base. It is able to (
almost In set theory, when dealing with sets of infinite size, the term almost or nearly is used to refer to all but a negligible amount of elements in the set. The notion of "negligible" depends on the context, and may mean "of measure zero" (in a me ...
) uniquely represent every
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
using only the digits 0, 1, 2, and 3. Numbers less than zero, which are ordinarily represented with a minus sign, are representable as digit strings in quater-imaginary; for example, the number −1 is represented as "103" in quater-imaginary notation.


Decomposing the quater-imaginary

In a
positional system Positional notation (or place-value notation, or positional numeral system) usually denotes the extension to any base of the Hindu–Arabic numeral system (or decimal system). More generally, a positional system is a numeral system in which th ...
with base b, \ldots d_3d_2d_1d_0.d_d_d_\ldots represents\dots + d_3\cdot b^3+d_2\cdot b^2+d_1\cdot b+d_0+d_\cdot b^+d_\cdot b^+d_\cdot b^\dots In this numeral system, b = 2i, and because (2i)^2=-4, the entire series of powers can be separated into two different series, so that it simplifies to \begin & dots+d_4\cdot(-4)^2 +d_2\cdot(-4)^1+d_0+d_\cdot(-4)^+\dots \end for even-numbered digits (digits that simplify to the value of the digit times a power of -4), and \begin 2i\cdot dots+d_3\cdot(-4)^1+d_1+d_\cdot (-4)^+d_\cdot (-4)^ + \dots\end for those digits that still have an imaginary factor. Adding these two series together then gives the total value of the number. Because of the separation of these two series, the real and imaginary parts of complex numbers are readily expressed in base −4 as \ldots d_4d_2d_0.d_\ldots and 2\cdot(\ldots d_5d_3d_1.d_d_\ldots) respectively.


Converting from quater-imaginary

To convert a digit string from the quater-imaginary system to the decimal system, the standard formula for positional number systems can be used. This says that a digit string \ldots d_3d_2d_1d_0 in base ''b'' can be converted to a decimal number using the formula :\cdots + d_3\cdot b^3+d_2\cdot b^2+d_1\cdot b+d_0 For the quater-imaginary system, b = 2i. Additionally, for a given string d in the form d_, d_,\dots d_0, the formula below can be used for a given string length w in base b :Q2D_w \vec d \equiv \sum_^ d_k \cdot b^k


Example

To convert the string 1101_ to a decimal number, fill in the formula above: :1\cdot(2i)^3 + 1\cdot(2i)^2 + 0\cdot(2i)^1 + 1\cdot(2i)^0 = -8i - 4 + 0 + 1 = -3 - 8i Another, longer example: 1030003_ in base 10 is :1\cdot(2i)^6 + 3\cdot(2i)^4 + 3\cdot(2i)^0 = -64 + 3\cdot 16 + 3 = -13


Converting into quater-imaginary

It is also possible to convert a decimal number to a number in the quater-imaginary system. Every
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
(every number of the form ''a''+''bi'') has a quater-imaginary representation. Most numbers have a unique quater-imaginary representation, but just as 1 has the two representations 1 = 0. in decimal notation, so, because of 0.2''i'' = , the number has the two quater-imaginary representations 0.2''i'' = 3· = = 1 + 3· = 1.2''i''. To convert an arbitrary complex number to quater-imaginary, it is sufficient to split the number into its real and imaginary components, convert each of those separately, and then add the results by interleaving the digits. For example, since −1+4''i'' is equal to −1 plus 4''i'', the quater-imaginary representation of −1+4''i'' is the quater-imaginary representation of −1 (namely, 103) plus the quater-imaginary representation of 4''i'' (namely, 20), which gives a final result of −1+4''i'' = 1232''i''. To find the quater-imaginary representation of the imaginary component, it suffices to multiply that component by 2''i'', which gives a real number; then find the quater-imaginary representation of that real number, and finally shift the representation by one place to the right (thus dividing by 2''i''). For example, the quater-imaginary representation of 6''i'' is calculated by multiplying 6''i'' × 2''i'' = −12, which is expressed as 3002''i'', and then shifting by one place to the right, yielding: 6''i'' = 302''i''. Finding the quater-imaginary representation of an arbitrary real
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
number can be done manually by solving a system of
simultaneous equations In mathematics, a set of simultaneous equations, also known as a system of equations or an equation system, is a finite set of equations for which common solutions are sought. An equation system is usually classified in the same manner as single e ...
, as shown below, but there are faster methods for both real and imaginary integers, as shown in the
negative base A negative base (or negative radix) may be used to construct a non-standard positional numeral system. Like other place-value systems, each position holds multiples of the appropriate power of the system's base; but that base is negative—that i ...
article.


Example: Real number

As an example of an integer number we can try to find the quater-imaginary counterpart of the decimal number 7 (or 710 since the base of the decimal system is 10). Since it is hard to predict exactly how long the digit string will be for a given decimal number, it is safe to assume a fairly large string. In this case, a string of six digits can be chosen. When an initial guess at the size of the string eventually turns out to be insufficient, a larger string can be used. To find the representation, first write out the general formula, and group terms: : \begin 7_& = d_+d_\cdot b+d_\cdot b^+d_\cdot b^+d_\cdot b^+d_\cdot b^ \\ & = d_+2id_-4d_-8id_+16d_+32id_ \\ & = d_-4d_+16d_+i(2d_-8d_+32d_) \\ \end Since 7 is a real number, it is allowed to conclude that ''d1'', ''d3'' and ''d5'' should be zero. Now the value of the coefficients ''d0'', ''d2'' and ''d4'', must be found. Because d0 − 4 d2 + 16 d4 = 7 and because—by the nature of the quater-imaginary system—the coefficients can only be 0, 1, 2 or 3 the value of the coefficients can be found. A possible configuration could be: ''d0'' = 3, ''d2'' = 3 and ''d4'' = 1. This configuration gives the resulting digit string for 710. :7_ = 010303_ = 10303_.


Example: Imaginary number

Finding a quater-imaginary representation of a purely imaginary integer number is analogous to the method described above for a real number. For example, to find the representation of 6''i'', it is possible to use the general formula. Then all coefficients of the real part have to be zero and the complex part should make 6. However, for 6''i'' it is easily seen by looking at the formula that if ''d1'' = 3 and all other coefficients are zero, we get the desired string for 6''i''. That is: :\begin6i_ = 30_\end


Another conversion method

For real numbers the quater-imaginary representation is the same as negative quaternary (base −4). A complex number ''x''+''iy'' can be converted to quater-imaginary by converting ''x'' and ''y''/2 separately to negative quaternary. If both ''x'' and ''y'' are finite binary fractions we can use the following algorithm using repeated
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
: For example: 35+23i=121003.22i 35 23i/2i=11.5 11=12−0.5 35÷(−4)=−8, remainder 3 12/(−4)=−3, remainder 0 (−0.5)×(−4)=2 −8÷(−4)= 2, remainder 0 −3/(−4)= 1, remainder 1 2÷(−4)= 0, remainder 2 1/(−4)= 0, remainder 1 20003 + 101000 + 0.2 = 121003.2 32i+16×2−8i−4×0+2i×0+1×3−2×i/2=35+23i


Radix point "."

A
radix point A decimal separator is a symbol used to separate the integer part from the fractional part of a number written in decimal form (e.g., "." in 12.45). Different countries officially designate different symbols for use as the separator. The choi ...
in the decimal system is the usual . (dot) which marks the separation between the
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
part and the
fraction A fraction (from la, fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight ...
al part of the number. In the quater-imaginary system a radix point can also be used. For a digit string \dots d_d_d_d_d_d_ . d_d_d_ \dots the radix point marks the separation between non-negative and negative powers of ''b''. Using the radix point the general formula becomes: :d_5 b^5 + d_4 b^4 + d_3 b^3 + d_2 b^2 + d_1 b + d_0 + d_ b^ + d_ b^ + d_ b^ or :\begin 32id_+16d_-8id_-4d_+2id_+d_+\fracd_+\fracd_+\fracd_\\ =32id_+16d_-8id_-4d_+2id_+d_-\fracd_-\fracd_+\fracd_ \end


Example

If the quater-imaginary representation of the complex unit ''i'' has to be found, the formula without radix point will not suffice. Therefore, the above formula should be used. Hence: : \begin i & = 32id_+16d_-8id_-4d_+2id_+d_+\fracd_+\fracd_+\fracd_\\ & = i(32d_-8d_+2d_-\fracd_+\fracd_)+16d_-4d_+d_-\fracd_\\ \end for certain coefficients ''dk''. Then because the real part has to be zero: ''d''4 = ''d''2 = ''d''0 = ''d''−2 = 0. For the imaginary part, if ''d''5 = ''d''3 = ''d''−3 = 0 and when ''d''1 = 1 and ''d''−1 = 2 the digit string can be found. Using the above coefficients in the digit string the result is: :i = 10.2_.


Addition and subtraction

It is possible to
add Addition (usually signified by the plus symbol ) is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or '' sum'' of ...
and
subtract Subtraction is an arithmetic operation that represents the operation of removing objects from a collection. Subtraction is signified by the minus sign, . For example, in the adjacent picture, there are peaches—meaning 5 peaches with 2 taken ...
numbers in the quater-imaginary system. In doing this, there are two basic rules that have to be kept in mind: # Whenever a number exceeds 3, ''subtract'' 4 and "carry" −1 two places to the left. # Whenever a number drops below 0, ''add'' 4 and "carry" +1 two places to the left. Or for short: "If you add four, carry +1. If you subtract four, carry −1". This is the opposite of normal long addition, in which a "carry" in the current column requires ''adding'' 1 to the next column to the left, and a "borrow" requires subtracting. In quater-imaginary arithmetic, a "carry" ''subtracts'' from the next-but-one column, and a "borrow" ''adds''.


Example: Addition

Below are two examples of adding in the quater-imaginary system:
   1 − 2i                1031             3 − 4i                 1023
   1 − 2i                1031             1 − 8i                 1001
   ------- +     <=>     ----- +          ------- +      <=>   ------- +
   2 − 4i                1022             4 − 12i               12320
In the first example we start by adding the two 1s in the first column (the "ones' column"), giving 2. Then we add the two 3s in the second column (the "2''i''s column"), giving 6; 6 is greater than 3, so we subtract 4 (giving 2 as the result in the second column) and carry −1 into the fourth column. Adding the 0s in the third column gives 0; and finally adding the two 1s and the carried −1 in the fourth column gives 1. In the second example we first add 3+1, giving 4; 4 is greater than 3, so we subtract 4 (giving 0) and carry −1 into the third column (the "−4s column"). Then we add 2+0 in the second column, giving 2. In the third column, we have 0+0+(−1), because of the carry; −1 is less than 0, so we add 4 (giving 3 as the result in the third column) and "borrow" +1 into the fifth column. In the fourth column, 1+1 is 2; and the carry in the fifth column gives 1, for a result of 12320_.


Example: Subtraction

Subtraction is analogous to addition in that it uses the same two rules described above. Below is an example:
         − 2 − 8i                       1102
           1 − 6i                       1011
           -------           <=>        -----
         − 3 − 2i                       1131
In this example we have to subtract 1011_ from 1102_. The rightmost digit is 2−1 = 1. The second digit from the right would become −1, so add 4 to give 3 and then carry +1 two places to the left. The third digit from the right is 1−0 = 1. Then the leftmost digit is 1−1 plus 1 from the carry, giving 1. This gives a final answer of 1131_.


Multiplication

For
long multiplication A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the de ...
in the quater-imaginary system, the two rules stated above are used as well. When multiplying numbers, multiply the first string by each digit in the second string consecutively and add the resulting strings. With every multiplication, a digit in the second string is multiplied with the first string. The multiplication starts with the rightmost digit in the second string and then moves leftward by one digit, multiplying each digit with the first string. Then the resulting partial products are added where each is shifted to the left by one digit. An example:
              11201
              20121  ×
        ---------------
              11201      ←––– 1 × 11201
             12002       ←––– 2 × 11201
            11201        ←––– 1 × 11201
           00000         ←––– 0 × 11201
          12002      +   ←––– 2 × 11201
        ---------------
          120231321
This corresponds to a multiplication of (9-8i)\cdot(29+4i) = 293-196i.


Tabulated conversions

Below is a table of some decimal and complex numbers and their quater-imaginary counterparts.


Examples

Below are some other examples of conversions from decimal numbers to quater-imaginary numbers. :5 = 16 + (3\cdot-4) + 1 = 10301_ :i = 2i + 2\left(-\fraci\right) = 10.2_ :7 \frac - 7 \fraci = 1(16) + 1(-8i) + 2(-4) + 1(2i) + 3\left(-\fraci\right) + 1\left(-\frac\right) = 11210.31_


Z-order curve

The representation :z = \sum_ z_k \cdot (2i)^ of an arbitrary complex number z\in \Complex with z_k\in \ gives rise to an
injective In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
mapping :\textstyle \begin \varphi \colon & \Complex & \to & \R \\ & \sum_ z_k \cdot (2i)^ & \mapsto & \sum_ z_k \cdot r^\\ \end with some suitable r \in \Z. Here r = 4 cannot be taken as base because of :\textstyle \sum_ 3\cdot (2i)^ = \tfrac5 \; \; \; \; \ne \; \; \; \; 1 = \sum_ 3 \cdot 4^. The
image An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
\varphi(\Complex) \subset \R is a
Cantor set In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of unintuitive properties. It was discovered in 1874 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883. Thr ...
which allows to linearly order \Complex similar to a
Z-order curve In mathematical analysis and computer science, functions which are Z-order, Lebesgue curve, Morton space-filling curve, Morton order or Morton code map multidimensional data to one dimension while preserving locality of the data points. It i ...
. Since the image is disconnected, \varphi is not
continuous Continuity or continuous may refer to: Mathematics * Continuity (mathematics), the opposing concept to discreteness; common examples include ** Continuous probability distribution or random variable in probability and statistics ** Continuous ...
.


See also

*
Quaternary numeral system A quaternary numeral system is base-. It uses the digits 0, 1, 2 and 3 to represent any real number. Conversion from binary is straightforward. Four is the largest number within the subitizing range and one of two numbers that is both a sq ...
*
Complex-base system In arithmetic, a complex-base system is a positional numeral system whose radix is an imaginary (proposed by Donald Knuth in 1955) or complex number (proposed by S. Khmelnik in 1964 and Walter F. Penney in 1965W. Penney, A "binary" system for co ...
*
Negative base A negative base (or negative radix) may be used to construct a non-standard positional numeral system. Like other place-value systems, each position holds multiples of the appropriate power of the system's base; but that base is negative—that i ...


References


Further reading

* * {{Donald Knuth navbox Non-standard positional numeral systems Donald Knuth Complex numbers