Quater-imaginary base

From Wikipedia, the free encyclopedia

Numeral systems by culture
Hindu-Arabic numerals
Indian Eastern Arabic Khmer	Indian family Brahmi Thai
East Asian numerals
Chinese Counting rods	Japanese Korean
Alphabetic numerals
Abjad Armenian Cyrillic Ge'ez	Hebrew Greek (Ionian) Āryabhaṭa
Other systems
Attic Babylonian Egyptian Etruscan	Mayan Roman Urnfield
List of numeral system topics
Positional systems by base
Decimal (10)
2, 4, 8, 16, 32, 64
1, 3, 9, 12, 20, 24, 30, 36, 60, more…
v • d • e

The quater-imaginary numeral system was first proposed by Donald Knuth in 1955, in a submission to a high-school science talent search. It is a non-standard positional numeral system which uses the imaginary number 2i as base. By analogy with the quaternary numeral system, it is able to represent every complex number using only the digits 0, 1, 2, and 3, without a sign.

1 From quater-imaginary to decimal
- 1.1 Example
2 Powers of 2i
3 From decimal to quater-imaginary
4 Radix point "."
- 4.1 Example
5 Addition and subtraction
- 5.1 Example: Addition
- 5.2 Example: Subtraction
6 Multiplication
7 Tabulated conversions
8 Examples
9 See also
10 References

[edit] From quater-imaginary to decimal

To convert a digit string from the quater imaginary system to the decimal system, the standard formula for non-standard positional systems can be used. This says that a digit string $d 3 d 2 d 1 d 0$ in the quater imaginary system can be converted to a decimal number using the formula:

$d_3\cdot b^3+d_2\cdot b^2+d_1\cdot b+d_0$ .

In this formula b = 2i for the quater-imaginary system.

[edit] Example

To convert the string $1101 2 i$ to a decimal number, fill in the formula above:

$1\cdot (2i)^3+1\cdot (2i)^2+0\cdot (2i)+1=-8i-4+0+1=-3-8i$

The formula to calculate the decimal number from the quater-imaginary number can be extended when larger strings are used. So to find the decimal counterpart of $1030003 2 i$ use the formula extended to 7 digits.

$d_6\cdot b^6+d_5\cdot b^5+d_4\cdot b^4+d_3\cdot b^3+d_2\cdot b^2+d_1\cdot b+d_0$

So for $1030003 2 i$ and with b = 2i this gives:

$1\cdot (2i)^6+0+3\cdot (2i)^4+0+0+0+3=-64+3\cdot 16+3=-13.$

[edit] Powers of 2i

When trying to find representations of the numbers from the quater-imaginary system to the decimal system, or vice-versa, the following table is useful:

Powers of 2i
$n$	-8	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7	8
$(2 i) n$	1/256	1/128i	−1/64	−1/32i	1/16	1/8i	−1/4	−1/2i	1	2i	−4	−8i	16	32i	−64	−128i	256

[edit] From decimal to quater-imaginary

It is also possible to convert a decimal number to a number in the quater-imaginary system. There are three different forms of decimal numbers that can be represented: real numbers, purely imaginary numbers and numbers of the form a+bi.

[edit] Example: Real number

As an example of a real 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{align} 7_{10}& = d_{0}+d_{1}\cdot b+d_{2}\cdot b^{2}+d_{3}\cdot b^{3}+d_{4}\cdot b^{4}+d_{5}\cdot b^{5} \\ & = d_{0}+2id_{1}-4d_{2}-8id_{3}+16d_{4}+32id_{5} \\ & = d_{0}-4d_{2}+16d_{4}+i(2d_{1}-8d_{3}+32d_{5}) \\ \end{align}$

Since 7 is a real number, it is allowed to conclude that d₁, d₃ and d₅ should be zero. Now the value of the coefficients d₀, d₂ and d₄, must be found. Because d₀ - 4 d₂ + 16 d₄ = 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: d₀ = 3, d₂ = 3 and d₄ = 1. This configuration gives the resulting digit string for 7₁₀.

$\begin{align} 7_{10} = 010303_{2i} = 10303_{2i}.\end{align}$

[edit] Example: Imaginary number

Finding a quater-imaginary representation of a purely complex number is analogous to the method described above for a real number. For example, to find the representation of 6i, 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 6i it is easily seen by looking at the formula that if d₁ = 3 and all other coefficients are zero, we get the desired string for 6i. That is:

$\begin{align}6i_{10} = 30_{2i}\end{align}$

[edit] Example: Complex number

To find a digit string representing a complex number of the form a+bi again it is possible to use the general formula, group terms and choose coefficients. To find the quater-imaginary counterpart of 7 + 6i use:

$\begin{align} 7+6i &= d_{0}+d_{1}\cdot b+d_{2}\cdot b^{2}+d_{3}\cdot b^{3}+d_{4}\cdot b^{4}+d_{5}\cdot b^{5} \\ &= d_{0}+2id_{1}-4d_{2}-8id_{3}+16d_{4}+32id_{5} \\ &= d_{0}-4d_{2}+16d_{4}+i(2d_{1}-8d_{3}+32d_{5}) \\ \end{align}$

Then, as before, if d₄ = 1, d₂ = 3 and d₀ = 3 we get the real part, and if d₅ = 0, d₃ = 0 and d₁ = 3 the imaginary part can be found. Hence the resulting digit string for the complex number is:

$\begin{align}7+6i = 10333_{2i} \end{align}$

[edit] Radix point "."

A radix point in the decimal system is the usual . (dot) which marks the separation between the integral part and the fractional part of the number. In the quater-imaginary system a radix point can also be used. For a digit string $... d 5 d 4 d 3 d 2 d 1 d 0 . d - 1 d - 2 d - 3 ...$ the radix point marks the separation between positive and negative powers of b. Using the radix point the general formula becomes:

$d_5\cdot b^5+d_4\cdot b^4+d_3\cdot b^3+d_2\cdot b^2+d_1\cdot b+d_0+d_{-1}\cdot b^{-1}+d_{-2}\cdot b^{-2}+d_{-3}\cdot b^{-3}$

$32id_{5}+16d_{4}-8id_{3}-4d_{2}+2id_{1}+d_{0}+\frac{1}{2i}d_{-1}+\frac{1}{-4}d_{-2}+\frac{1}{-8i}d_{-3}$

[edit] 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{align}i & = 32id_{5}+16d_{4}-8id_{3}-4d_{2}+2id_{1}+d_{0}+\frac{1}{2i}d_{-1}+\frac{1}{-4}d_{-2}+\frac{1}{-8i}d_{-3}\\ & = i(32d_{5}-8d_{3}+2d_{1}-\frac{1}{2}d_{-1}+\frac{1}{8}d_{-3})+16d_{4}-4d_{2}+d_{0}-\frac{1}{4}d_{-2}\\ \end{align}$

For certain coefficients d_k. Then because the real part has to be zero: d₄ = d₂ = d₀ = d_-2 = 0. For the imaginary part, if d₅ = d₃ = d _-3 = 0 and when d₁=1 and d_-1=2 the digit string can be found. Using the above coefficients in the digit string the result is:

$\begin{align}i = 10.2_{2i}\end{align}$ .

[edit] Addition and subtraction

It is possible to add and subtract numbers in the quater-imaginary system, in doing this, there are 2 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 is negative, 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". When adding or subtracting keep in mind that one has to start at the most right digit in the string. Below are two examples of these rules.

[edit] 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 left example we first add the two ones on the right, this gives 2. Then add the two threes, this would be 6, however since 6 is not allowed, subtract 4 and carry -1 two places to the left. This gives a two on the second place from right and a one at the leftmost digit.

Similarly in the second example (on the right), we have to add a 3 and a 1 at the most right digit, this would be a four, which is not allowed. Hence, subtract four and carry a "-1" two places to the left. Since the third digit from right is zero, this would give -1. So add 4 and carry "+1" two places to the left. These operations give the resulting digit string, as shown above.

[edit] 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 the strings 1102_2i and 1011_2i. The most right digit is 2-1=1, the second digit from the right would become -1, so add 4 to get 3 and then carry +1 two places to the left. The third digit from the right is 1-0=1. Then the most left digit is 1-1+1=1 because we had to carry a +1. This gives 1131_2i as above.

[edit] Multiplication

For multiplication 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 (this is multiplication by partial products). With every multiplication, a digit in the second string is multiplied with the first string. The multiplication starts with the most right 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  x
             --------
             11201      <--- 1 x 11201
            12002       <--- 2 x 11201
           11201        <--- 1 x 11201
          00000         <--- 0 x 11201
         12002      +   <--- 2 x 11201
         ------------
         120231321

This corresponds to a multiplication of (9 - 8i )(29 + 4i ) = 293 - 196i.

[edit] Tabulated conversions

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

Base 10	Base 2i
1	1
2	2
3	3
4	10300
5	10301
6	10302
7	10303
8	10200
9	10201
10	10202
11	10203
12	10100
13	10101
14	10102
15	10103
16	10000

Base 10	Base 2i
−1	103
−2	102
−3	101
−4	100
−5	203
−6	202
−7	201
−8	200
−9	303
−10	302
−11	301
−12	300
−13	1030003
−14	1030002
−15	1030001
−16	1030000

Base 10	Base 2i
1i	10.2
2i	10.0
3i	20.2
4i	20.0
5i	30.2
6i	30.0
7i	103000.2
8i	103000.0
9i	103010.2
10i	103010.0
11i	103020.2
12i	103020.0
13i	103030.2
14i	103030.0
15i	102000.2
16i	102000.0

Base 10	Base 2i
−1i	0.2
−2i	1030.0
−3i	1030.2
−4i	1020.0
−5i	1020.2
−6i	1010.0
−7i	1010.2
−8i	1000.0
−9i	1000.2
−10i	2030.0
−11i	2030.2
−12i	2020.0
−13i	2020.2
−14i	2010.0
−15i	2010.2
−16i	2000.0

[edit] Examples

Below are some other examples of conversions from decimal numbers to quater-imaginary numbers.

$5 = 16 + (3\cdot-4) + 1 = 10301_{2i}$

$i = 2i + 2\left(-\frac{1}{2}i\right) = 10.2_{2i}$

$7 \frac{3}{4} - 7 \frac{1}{2}i = 1(16) + 1(-8i) + 2(-4) + 1(2i) + 3\left(-\frac{1}{2}i\right) + 1\left(-\frac{1}{4}\right) = 11210.31_{2i}$

[edit] See also

Complex base systems

[edit] References

D. Knuth. The Art of Computer Programming. Volume 2, 3rd Edition. Addison-Wesley. pp. 205, "Positional Number Systems"

Quater-imaginary base

From Wikipedia, the free encyclopedia

Contents

[edit] From quater-imaginary to decimal

[edit] Example

[edit] Powers of 2i

[edit] From decimal to quater-imaginary

[edit] Example: Real number

[edit] Example: Imaginary number

[edit] Example: Complex number

[edit] Radix point "."

[edit] Example

[edit] Addition and subtraction

[edit] Example: Addition

[edit] Example: Subtraction

[edit] Multiplication

[edit] Tabulated conversions

[edit] Examples

[edit] See also

[edit] References

Views

Navigation

Interaction

Search

Languages