请输入您要查询的百科知识：

　

词条 Negative base
释义

  1. Example

  2. History

  3. Notation and use

  4. Calculation

      Example implementation code    To negabinary    C#    C++    To negaternary    C#    Visual Basic .NET    Python    Common Lisp    To any negative base    Java    AutoLisp    PHP    Visual Basic .NET    Shortcut calculation   To negabinary  To negaquaternary 

  5. Arithmetic operations

     Addition   Another method    Negabinary full adder    Incrementing negabinary numbers   Subtraction  Multiplication and division  Comparing negabinary numbers  Divisibility tests  Root extraction 

  6. Fractional numbers

     Non-unique representations 

  7. Imaginary base

  8. See also

  9. References

  10. Further reading

  11. External links

{{numeral systems}}

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 is to say, the base {{mvar|b}} is equal to {{mvar|−r}} for some natural number {{mvar|r}} ({{mvar|r ≥ 2}}).

Negative-base systems can accommodate all the same numbers as standard place-value systems, but both positive and negative numbers are represented without the use of a minus sign (or, in computer representation, a sign bit); this advantage is countered by an increased complexity of arithmetic operations. The need to store the information normally contained by a negative sign often results in a negative-base number being one digit longer than its positive-base equivalent.

The common names for negative-base positional numeral systems are formed by prefixing nega- to the name of the corresponding positive-base system; for example, negadecimal (base −10) corresponds to decimal (base 10), negabinary (base −2) to binary (base 2), negaternary (base −3) to ternary (base 3), and negaquaternary (base −4) to quaternary (base 4).[1][2]

Example

Consider what is meant by the representation {{val|fmt=none|12243}} in the negadecimal system, whose base {{mvar|b}} is −10:

 Multiples of
(−10)4 {{=}} 10,000}}(−10)3 {{=}} −1,000}}(−10)2 {{=}} 100}}(−10)1 {{=}} −10}}(−10)0 {{=}} 1}}
1 2 2 4 3

Since 10,000 + (−2,000) + 200 + (−40) + 3 = {{val|fmt=commas|8163}}, the representation {{val|fmt=commas|12243|s={{sub|−10}}}} in negadecimal notation is equivalent to {{val|fmt=commas|8,163|s={{sub|10}}}} in decimal notation, while {{val|fmt=commas|−8163|s={{sub|10}}}} in decimal would be written {{val|fmt=commas|9,977|s={{sub|−10}}}} in negadecimal.

History

Negative numerical bases were first considered by Vittorio Grünwald in his work Giornale di Matematiche di Battaglini, published in 1885.[3] Grünwald gave algorithms for performing addition, subtraction, multiplication, division, root extraction, divisibility tests, and radix conversion. Negative bases were later independently rediscovered by A. J. Kempner in 1936[4] and Zdzisław Pawlak and A. Wakulicz in 1959.[5]

Negabinary was implemented in the early Polish computer BINEG (and UMC), built 1957–59, based on ideas by Z. Pawlak and A. Lazarkiewicz from the Mathematical Institute in Warsaw.[6] Implementations since then have been rare.

Notation and use

Denoting the base as {{mvar|−r}}, every integer {{mvar|a}} can be written uniquely as

where each digit {{mvar|dk}} is an integer from 0 to {{math|r - 1}} and the leading digit {{mvar|dn}} is {{math|> 0}} (unless {{math|n=0}}). The base {{mvar|−r}} expansion of {{mvar|a}} is then given by the string {{math|dndn-1…d1d0}}.

Negative-base systems may thus be compared to signed-digit representations, such as balanced ternary, where the radix is positive but the digits are taken from a partially negative range. (In the table below the digit of value −1 is written as the single character T.)

Some numbers have the same representation in base {{mvar|−r}} as in base {{mvar|r}}. For example, the numbers from 100 to 109 have the same representations in decimal and negadecimal. Similarly,

and is represented by 10001 in binary and 10001 in negabinary.

Some numbers with their expansions in a number of positive and corresponding negative bases are:

Decimal Negadecimal Binary Negabinary Ternary Negaternary Balanced Ternary Nega Balanced Ternary Quaternary Negaquaternary
−15 25 −1111 110001 −120 1220 T110 11T0 −33 1301
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
−5 15 −101 1111 −12 21 T11 TT1 −11 23
−4 16 −100 1100 −11 22 TT 1T −10 10
−3 17 −11 1101 −10 10 T0 10 −3 11
−2 18 −10 10 −2 11 T1 11 −2 12
−1 19 −1 11 −1 12 T T −1 13
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1
2 2 10 110 2 2 1T TT 2 2
3 3 11 111 10 120 10 T0 3 3
4 4 100 100 11 121 11 T1 10 130
5 5 101 101 12 122 1TT 11T 11 131
6 6 110 11010 20 110 1T0 110 12 132
7 7 111 11011 21 111 1T1 111 13 133
8 8 1000 11000 22 112 10T 10T 20 120
9 9 1001 11001 100 100 100 100 21 121
10 190 1010 11110 101 101 101 101 22 122
11 191 1011 11111 102 102 11T 1TT 23 123
12 192 1100 11100 110 220 110 1T0 30 110
13 193 1101 11101 111 221 111 1T1 31 111
14 194 1110 10010 112 222 1TTT TT1T 32 112
15 195 1111 10011 120 210 1TT0 TT10 33 113
16 196 10000 10000 121 211 1TT1 TT11 40 100
17 197 10001 10001 122 212 1T0T TT0T 41 101
18 198 10010 10110 200 200 1T10 TTT0 42 102

Note that, with the exception of nega balanced ternary, the base {{mvar|−r}} expansions of negative integers have an even number of digits, while the base {{mvar|−r}} expansions of the non-negative integers have an odd number of digits.

Calculation

The base {{mvar|−r}} expansion of a number can be found by repeated division by {{mvar|−r}}, recording the non-negative remainders , and concatenating those remainders, starting with the last. Note that if {{math| a / b = c}}, remainder {{mvar|d}}, then {{math| bc + d = a}} and therefore {{math| d = a - bc}}. To arrive at the correct conversion, the value for {{mvar|c}} must be chosen such that {{mvar|d}} is non-negative and minimal. This is exemplified in the fourth line of the following example wherein –5 ÷ –3 must be chosen to equal 2 remainder 1 instead of 1 remainder –2.

For example, to convert 146 in decimal to negaternary:

Reading the remainders backward we obtain the negaternary representation of 14610: 21102–3.

Proof: (((2·(–3)+1)·(–3)+1)·(–3)+0)·(–3)+2 = 14610.

Note that in most programming languages, the result (in integer arithmetic) of dividing a negative number by a negative number is rounded towards 0, usually leaving a negative remainder. In such a case we have {{math|a = (−r)c + d = (−r)c + d − r + r = (−r)(c + 1) + (d + r)}}. Because {{math|{{!}}d{{!}} < r}}, {{math|(d + r)}} is the positive remainder. Therefore, to get the correct result in such case, computer implementations of the above algorithm should add 1 and {{mvar|r}} to the quotient and remainder respectively.

Example implementation code

To negabinary

C#

static string ToNegabinary(int value)

{

string result = string.Empty;

while (value != 0)

{

int remainder = value % -2;

value = value / -2;

if (remainder < 0)

{

remainder += 2;

value += 1;

}

result = remainder.ToString() + result;

}

return result;

}

C++

auto to_negabinary(int value)

{
    std::bitset result;    std::size_t bit_position = 0;
    while (value != 0)    {        const auto div_result = std::div(value, -2);
        if (div_result.rem < 0)            value = div_result.quot + 1;        else            value = div_result.quot;
        ++bit_position;    }

}

To negaternary

C#

static string negaternary(int value)

{

string result = string.Empty;

while (value != 0)

{

int remainder = value % -3;

value = value / -3;

if (remainder < 0)

{

remainder += 3;

value += 1;

}

result = remainder.ToString() + result;

}

return result;

}

Visual Basic .NET

Private Shared Function ToNegaternary(value As Integer) As String

Dim result As String = String.Empty

While value <> 0

Dim remainder As Integer = value Mod -3

value /= -3

If remainder < 0 Then

remainder += 3

value += 1

End If

result = remainder.ToString() & result

End While

Return result

End Function

Python

def negaternary(i):

    if i == 0:        digits = ['0']    else:        digits = []        while i != 0:            i, remainder = divmod(i, -3)            if remainder < 0:                i, remainder = i + 1, remainder + 3            digits.append(str(remainder))    return ''.join(digits[::-1])
Common Lisp

(defun negaternary (i)

  (if (zerop i)      "0"      (let ((digits "")

(rem 0))

(loop while (not (zerop i)) do

(progn

(multiple-value-setq (i rem) (truncate i -3))

(when (minusp rem)

(incf i)

(incf rem 3))

(setf digits (concatenate 'string (write-to-string rem) digits))))

digits)))

To any negative base

Java 
    public List negativeBase(int integer, int base) {        List digits = new ArrayList<>();        while (integer != 0) {            int i = integer % base;            integer /= base;            if(i < 0) {                i += Math.abs(base);                integer++;            }            digits.add(0, i);        }        return digits;    }
AutoLisp

from [-10 -2] interval:

(defun negabase (num baz / dig rst)

;num=any number in base 10.
;If num is a decimal one, it will be considered integer.
;14.25 will be considered 14; -123456789.87 will be considered -123456789.
;baz=any number from [-10 -2] interval.
;If baz is a decimal one, it will be considered integer.
    (if        (and (numberp num)(numberp baz)(<= (fix baz) -2)(> (fix baz) -11))        (progn            (setq                baz (float (fix baz))                num (float (fix num))                dig (if (= num 0) "0" "")            )            (while (/= num 0)                (setq rst (- num (* baz (setq num (fix (/ num baz))))))                (if                    (minusp rst)                    (setq                        num (1+ num)                        rst (- rst baz)                    )                )                (setq dig (strcat (itoa (fix rst)) dig))            )            dig        )        (progn            (prompt                (cond                    ((and (not (numberp num))(not (numberp baz)))   "\Wrong number and negabase.")                    ((not (numberp num))                            "\Wrong number.")                    ((not (numberp baz))                            "\Wrong negabase.")                    (T                                              "\Negabase must be inside [-10 -2] interval.")                )            )            (princ)        )    )

)

PHP

The conversion from integer to some negative base:

function toNegativeBase($no, $base)

{

$digits = array();

$base = intval($base);

while ($no != 0) {

$temp_no = $no;

$no = intval($temp_no / $base);

$remainder = ($temp_no % $base);

if ($remainder < 0) {

$remainder += abs($base);

$no++;

}

array_unshift($digits, $remainder);

}

return $digits;

}

Visual Basic .NET

Function toNegativeBase(Number As Integer , base As Integer) As System.Collections.Generic.List(Of Integer)

Dim digits As New System.Collections.Generic.List(Of Integer)

while Number <> 0

Dim remainder As Integer= Number Mod base

Number = CInt(Number / base)

if remainder < 0 then

remainder += system.math.abs(base)

Number+=1

end if

digits.Insert(0, remainder)

end while

return digits

end function

Shortcut calculation

To negabinary

The conversion to negabinary (base −2; digits ) allows a remarkable shortcut

(C implementation):

unsigned int toNegaBinary(unsigned int value) // input in standard binary

{

unsigned int Schroeppel2 = 0xAAAAAAAA; // = 2/3*((2*2)^16-1) = ...1010

return (value + Schroeppel2) ^ Schroeppel2; // eXclusive OR

// resulting unsigned int to be interpreted as string of elements ε {0,1} (bits)

}

Due to D. Librik (Szudzik). The bitwise XOR portion is originally due to Schroeppel (1972).[7]

JavaScript port for the same shortcut calculation:

function toNegaBinary( number ) {

    var Schroeppel2 = 0xAAAAAAAA;    // Convert to NegaBinary String    return ( ( number + Schroeppel2 ) ^ Schroeppel2 ).toString(2);

}

To negaquaternary

The conversion to negaquaternary (base −4; digits ) allows a similar shortcut (C implementation):

unsigned int toNegaQuaternary(unsigned int value) // input in standard binary

{

unsigned int Schroeppel4 = 0xCCCCCCCC; // = 4/5*((2*4)^8-1) = ...11001100 = ...3030

return (value + Schroeppel4) ^ Schroeppel4; // eXclusive OR

// resulting unsigned int to be interpreted as string of elements ε {0,1,2,3} (pairs of bits)

}

JavaScript port for the same shortcut calculation:

function toNegaQuaternary( number ) {

    var Schroeppel4 = 0xCCCCCCCC;    // Convert to NegaQuaternary String    return ( ( number + Schroeppel4 ) ^ Schroeppel4 ).toString(4);

}

Arithmetic operations

The following describes the arithmetic operations for negabinary; calculations in larger bases are similar.

Addition

Adding negabinary numbers proceeds bitwise, starting from the least significant bits; the bits from each addend are summed with the (balanced ternary) carry from the previous bit (0 at the LSB). This sum is then decomposed into an output bit and carry for the next iteration as show in the table:

SumOutputComment
BitCarry
−2 −2}} 0 1 −2}}−2 occurs only during subtraction.
−1 −2}} 1 1 −2}}
0 −2}} 0 0 −2}}
1 −2}} 1 0 −2}}
2 −2}} 0 −1 −2}}
3 −2}} 1 −1 −2}}3 occurs only during addition.

The second row of this table, for instance, expresses the fact that −1 = 1 + 1 × −2; the fifth row says 2 = 0 + −1 × −2; etc.

As an example, to add 1010101{{sub|−2}} (1 + 4 + 16 + 64 = 85) and 1110100{{sub|−2}} (4 + 16 − 32 + 64 = 52),

 Carry:          1 −1  0 −1  1 −1  0  0  0 First addend:         1  0  1  0  1  0  1 Second addend:        1  1  1  0  1  0  0 +                -------------------------- Number:         1 −1  2  0  3 −1  2  0  1 Bit (result):   1  1  0  0  1  1  0  0  1 Carry:          0  1 −1  0 −1  1 −1  0  0

so the result is 110011001{{sub|−2}} (1 − 8 + 16 − 128 + 256 = 137).

Another method

While adding two negabinary numbers, every time a carry is generated an extra carry should be propagated to next bit. Consider same example as above

 Extra carry:       1  1  0  1  0  0  0      Carry:          1  0  1  1  0  1  0  0  0 First addend:         1  0  1  0  1  0  1 Second addend:        1  1  1  0  1  0  0 +                -------------------------- Answer:         1  1  0  0  1  1  0  0  1

Negabinary full adder

A full adder circuit can be designed to add numbers in negabinary. The following logic is used to calculate the sum and carries:[8]

Incrementing negabinary numbers

Incrementing a negabinary number can be done by using the following formula:[9]

Subtraction

To subtract, multiply each bit of the second number by −1, and add the numbers, using the same table as above.

As an example, to compute 1101001{{sub|−2}} (1 − 8 − 32 + 64 = 25) minus 1110100{{sub|−2}} (4 + 16 − 32 + 64 = 52),

 Carry:          0  1 −1  1  0  0  0 First number:   1  1  0  1  0  0  1 Second number: −1 −1 −1  0 −1  0  0 +                -------------------- Number:         0  1 −2  2 −1  0  1 Bit (result):   0  1  0  0  1  0  1 Carry:          0  0  1 −1  1  0  0

so the result is 100101{{sub|−2}} (1 + 4 −32 = −27).

Unary negation, {{math|−x}}, can be computed as binary subtraction from zero, {{math|0 − x}}.

Multiplication and division

Shifting to the left multiplies by −2, shifting to the right divides by −2.

To multiply, multiply like normal decimal or binary numbers, but using the negabinary rules for adding the carry, when adding the numbers.

 First number:                   1  1  1  0  1  1  0 Second number:                  1  0  1  1  0  1  1 ×               -------------------------------------                                 1  1  1  0  1  1  0                              1  1  1  0  1  1  0                         1  1  1  0  1  1  0                     1  1  1  0  1  1  0                1  1  1  0  1  1  0                   +               ------------------------------------- Carry:        0 −1  0 −1 −1 −1 −1 −1  0 −1  0  0 Number:       1  0  2  1  2  2  2  3  2  0  2  1  0 Bit (result): 1  0  0  1  0  0  0  1  0  0  0  1  0 Carry:           0 −1  0 −1 −1 −1 −1 −1  0 −1  0  0

For each column, add carry to number, and divide the sum by −2, to get the new carry, and the resulting bit as the remainder.

Comparing negabinary numbers

It is possible to compare negabinary numbers by slightly adjusting a normal unsigned binary comparator. When comparing the numbers and , invert each odd positioned bit of both numbers.

After this, compare and using a standard unsigned comparator.[10]

Fractional numbers

Base {{mvar|−r}} representation may of course be carried beyond the radix point, allowing the representation of non-integral numbers.

As with positive-base systems, terminating representations correspond to fractions where the denominator is a power of the base; repeating representations correspond to other rationals, and for the same reason.

Non-unique representations

Unlike positive-base systems, where integers and terminating fractions have non-unique representations (for example, in decimal 0.999… = 1) in negative-base systems the integers have only a single representation. However, there do exist rationals with non-unique representations. For the digits {0, 1, …, t} with the biggest digit and

we have

    as well as

So every number with a terminating fraction added has two distinct representations.

For example, in negaternary, i.e. and , there is

.

Such non-unique representations can be found by considering the largest and smallest possible representations with integral parts 0 and 1 respectively, and then noting that they are equal. (Indeed, this works with any integral-base system.) The rationals thus non-uniquely expressible are those of form

with

Imaginary base

{{main|Complex-base system}}

Just as using a negative base allows the representation of negative numbers without an explicit negative sign, using an imaginary base allows the representation of Gaussian integers. Donald Knuth proposed the quater-imaginary base (base 2i) in 1955.[11]

See also

  • Quater-imaginary base
  • Binary
  • Balanced ternary
  • Quaternary numeral system
  • Numeral systems

References

1. ^{{citation|first=Donald|last=Knuth|title=The Art of Computer Programming, Volume 2|year=1998|edition=3rd|pages=204–205}}. Knuth mentions both negabinary and negadecimal.
2. ^The negaternary system is discussed briefly in {{Citation | last1=Petkovšek | first1=Marko | author1-link=Marko Petkovšek | title=Ambiguous numbers are dense | doi=10.2307/2324393 | mr=1048915 | year=1990 | journal=The American Mathematical Monthly | issn=0002-9890 | volume=97 | issue=5 | pages=408–411}}.
3. ^Vittorio Grünwald. Giornale di Matematiche di Battaglini (1885), 203-221, 367
4. ^{{citation | last = Kempner | first = A. J. | authorlink = Aubrey J. Kempner | doi = 10.2307/2300532 | issue = 10 | journal = American Mathematical Monthly | mr = 1523792 | pages = 610–617 | title = Anormal Systems of Numeration | volume = 43 | year = 1936}}.
5. ^{{citation | last1 = Pawlak | first1 = Z. | last2 = Wakulicz | first2 = A. | journal = Bulletin de l'Académie Polonaise des Sciences |series = Classe III | pages = 233–236 | title = Use of expansions with a negative basis in the arithmometer of a digital computer | volume = 5 | year = 1957}}.
6. ^Marczynski, R. W., "The First Seven Years of Polish Computing" {{webarchive|url=https://web.archive.org/web/20110719192337/http://chc60.fgcu.edu/images/articles/Marczynski.pdf |date=2011-07-19 }}, IEEE Annals of the History of Computing, Vol. 2, No 1, January 1980
7. ^See the MathWorld Negabinary link
8. ^{{cite book |last=Francis, Suganda, Shizuhuo |first=Yu, Jutamulia, Yin |date=4 September 2001 |title=Introduction to Information Optics |publisher=Academic Press |page=498 |isbn=9780127748115}}
9. ^{{cite web |url=http://math.stackexchange.com/questions/1878151/why-does-the-following-formula-increment-a-negabinary-number-number-in-base-2 |title=Archived copy |accessdate=2016-08-29 |deadurl=no |archiveurl=https://web.archive.org/web/20160913101620/http://math.stackexchange.com/questions/1878151/why-does-the-following-formula-increment-a-negabinary-number-number-in-base-2 |archivedate=2016-09-13 |df= }}
10. ^{{cite journal |last=Murugesan |first=San|date=1977|title=Negabinary arithmetic circuits using binary arithmetic |journal=Electronic Circuits and Systems, IEE Journal on |publisher=IET |volume=1 |issue=2 |pages=77–78 |doi= }}
11. ^D. Knuth. The Art of Computer Programming. Volume 2, 3rd Edition. Addison-Wesley. pp. 205, "Positional Number Systems"

Further reading

  • {{cite book |title=Hacker's Delight |title-link=Hacker's Delight |first=Henry S. |last=Warren Jr. |date=2013 |orig-year=2002 |edition=2 |publisher=Addison Wesley - Pearson Education, Inc. |isbn=978-0-321-84268-8 |id=0-321-84268-5}}

External links

  • {{mathworld|title=Negabinary|urlname=Negabinary}}
  • {{mathworld|title=Negadecimal|urlname=Negadecimal}}

3 : Non-standard positional numeral systems|Computer arithmetic|Negative concepts
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/9/22 3:50:02