Podstawa ujemna - Negative base

Podstawy ujemny (lub ujemny podstawa ) może być stosowany do konstruowania innych niż standardowe pozycyjnym systemie liczbowym . Podobnie jak inne systemy wartości miejsca, każda pozycja zawiera wielokrotności odpowiedniej mocy bazy systemu; ale ta podstawa jest ujemna — to znaczy podstawa b jest równa -r dla pewnej liczby naturalnej r ( r ≥ 2 ).

Systemy o podstawie ujemnej mogą pomieścić wszystkie te same liczby, co standardowe systemy wartości miejsc, ale zarówno liczby dodatnie, jak i ujemne są reprezentowane bez użycia znaku minus (lub, w reprezentacji komputerowej, bitu znaku ); tej przewadze przeciwdziała zwiększona złożoność operacji arytmetycznych. Konieczność przechowywania informacji normalnie zawartych w znaku ujemnym często powoduje, że liczba o podstawie ujemnej jest o jedną cyfrę dłuższa niż jej odpowiednik o podstawie dodatniej.

Nazwy zwyczajowe pozycyjnych systemów liczbowych o ujemnej podstawie są tworzone przez przedrostek nega- przed nazwą odpowiedniego systemu o dodatniej podstawie; na przykład negadecimal (podstawa -10) odpowiada dziesiętna (podstawa 10), negabinary (baza-2) do binarnego (podstawa 2) negaternary (baza-3) do trójskładnikowego (zasada 3) i negaquaternary (podstawa -4) do czwartorzędu (podstawa 4).

Przykład

Zastanów się, co oznacza reprezentacja 12243 w systemie negadecymalnym, którego podstawa b wynosi -10:

Ponieważ 10 000 + (−2000) + 200 + (−40) + 3 = 8163 reprezentacja12 243 _-10 w zapisie negacymalnym jest równoważne8163 ₁₀ w notacji dziesiętnej, podczas gdy-8,163 ₁₀ w postaci dziesiętnej zostanie zapisane9977 _-10 w negadzie.

Historia

Ujemne podstawy liczbowe zostały po raz pierwszy uwzględnione przez Vittorio Grünwalda w monografii opublikowanej w 1885 roku w Giornale di Matematiche di Battaglini . Grünwald podał algorytmy wykonywania dodawania, odejmowania, mnożenia, dzielenia, ekstrakcji pierwiastków, testów podzielności i konwersji podstaw. Podstawy negatywne zostały później mimochodem wymienione przez AJ Kempnera w 1936 r., a dokładniej zbadane przez Zdzisława Pawlaka i A. Wakulicza w 1957 r.

Negabinary zaimplementowano we wczesnym polskim komputerze BINEG (i UMC ), zbudowanym w latach 1957-59, na podstawie pomysłów Z. Pawlaka i A. Lazarkiewicza z Instytutu Matematycznego w Warszawie . Wdrożenia od tego czasu były rzadkie.

Notacja i użycie

Oznaczając bazę jako −r , każdą liczbę całkowitą a można zapisać jednoznacznie jako

${\ Displaystyle a = \ suma _ {i = 0} ^ {n} d_ {i} (-r) ^ {i}}$

gdzie każda cyfra d _k jest liczbą całkowitą od 0 do r − 1, a wiodąca cyfra d _n jest > 0 (chyba że n = 0 ). Podstawa −r rozwinięcia a jest następnie dana przez łańcuch d _n d _{n −1} ... d ₁ d ₀ .

Systemy o podstawie ujemnej można zatem porównać z reprezentacjami cyfr ze znakiem , takimi jak zrównoważona trójka , gdzie podstawa jest dodatnia, ale cyfry są pobierane z zakresu częściowo ujemnego. (W poniższej tabeli cyfra wartości -1 jest zapisana jako pojedynczy znak T.)

Niektóre liczby mają taką samą reprezentację w podstawie -r jak w podstawie r . Na przykład liczby od 100 do 109 mają te same reprezentacje w postaci dziesiętnej i negadziesiętnej. Podobnie,

${\ Displaystyle 17 = 2 ^ {4} +2 ^ {0} = (-2) ^ {4} + (-2) ^ {0}}$

i jest reprezentowane przez 10001 w postaci binarnej i 10001 w negabinarnej.

Niektóre liczby wraz z rozwinięciami w wielu dodatnich i odpowiadających im podstawach ujemnych to:

Zauważ, że z wyjątkiem trójskładnikowych zrównoważonych ujemnie, rozwinięcia przy podstawie -r ujemnych liczb całkowitych mają parzystą liczbę cyfr, podczas gdy rozwinięcia przy podstawie -r liczb całkowitych nieujemnych mają nieparzystą liczbę cyfr.

Obliczenie

Podstawę -r rozwinięcia liczby można znaleźć, powtarzając dzielenie przez -r , zapisując nieujemne reszty w i łącząc te reszty, zaczynając od ostatniej. Zauważ, że jeśli a /  b jest c z resztą d , wtedy bc + d = a , a zatem d = a − bc . Aby uzyskać prawidłową konwersję, wartość c musi być tak dobrana, aby d było nieujemne i minimalne. Jest to zilustrowane w czwartym wierszu poniższego przykładu, w którym –5 ÷ –3 musi być wybrane tak, aby równało się 2 reszcie 1 zamiast 1 reszcie 2. ${\ Displaystyle \ {0,1, \ ldots, r-1 \}}$

Na przykład, aby przekonwertować 146 z liczb dziesiętnych na negatroniczne:

${\ Displaystyle {\ zacząć {array} {rr} 146 \ div (-3) = i 48 ~ \ operatorname {reszta} ~ 2 \ \-48 \ div (-3) = i 16 ~ \ operatorname {reszta} ~ 0\\16\div (-3)=&-5~\nazwa operatora {pozostała} ~1\\-5\div (-3)=&2~\nazwa operatora {pozostała} ~1\\2\div (-3 )=&0~\nazwa operatora {reszta} ~2\end{tablica}}}$

Czytając resztę wstecz otrzymujemy negaternarną reprezentację 146 ₁₀ : 21102 _–3 .

Dowód: ((( 2  · (–3) + 1 ) · (–3) + 1 ) · (–3) + 0 ) · (–3) + 2 = 146 ₁₀ .

Zauważ, że w większości języków programowania wynik (w arytmetyce liczb całkowitych) dzielenia liczby ujemnej przez liczbę ujemną jest zaokrąglany do 0, zwykle pozostawiając ujemną resztę. W takim przypadku mamy a = (− r ) c + d = (− r ) c + d − r + r = (− r )( c + 1) + ( d + r ) . Ponieważ | d | < r , ( d + r ) to reszta dodatnia. Dlatego, aby uzyskać poprawny wynik w takim przypadku, komputerowe implementacje powyższego algorytmu powinny dodać 1 i r odpowiednio do ilorazu i reszty.

Przykładowy kod implementacji

Do negabinatu

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<sizeof(int) * CHAR_BIT > 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;

        result.set(bit_position, div_result.rem != 0);

        ++bit_position;
    }

    return result;
}

Do negacji

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

Pyton

def negaternary(i: int) -> str:
    """Decimal to negaternary."""
    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])

>>> negaternary(1000)
'2212001'

Wspólne seplenienie

(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)))

Do jakiejkolwiek negatywnej podstawy

Jawa

public String negativeBase(int integer, int base) {
    String result = "";
    int number = integer;
    while (number != 0) {
        int i = number % base;
        number /= base;
        if (i < 0) {
            i += Math.abs(base);
            number++;
        }
        result = i + result;
    }
    return result;
}

AutoLisp

od [-10 -2] przedział:

(defun negabase (num baz / dig rst)
  ;; NUM is any number. BAZ is any number in the interval [-10, -2].
  ;;
  ;; NUM and BAZ will be truncated to an integer if they're floats (e.g. 14.25
  ;; will be truncated to 14, -123456789.87 to -123456789, etc.).
  (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)))
            "\nWrong number and negabase.")
           ((not (numberp num))
            "\nWrong number.")
           ((not (numberp baz))
            "\nWrong negabase.")
           (t
            "\nNegabase must be inside [-10 -2] interval.")))
        (princ))))

PHP

Konwersja z liczby całkowitej na jakąś ujemną podstawę:

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

Obliczanie skrótów

Poniższe algorytmy zakładają, że

1. wejście jest dostępne w ciągach bitów i zakodowane (podstawa +2; cyfry w ) (jak w większości współczesnych komputerów cyfrowych),${\ Displaystyle \ {0,1 \}}$
2. są operacje add (+) i xor (^), które operują na takich bitstringach (jak w większości współczesnych komputerów cyfrowych),
3. zestaw cyfr wyjściowych jest standardowy, tj. mi. z podstawą ,${\ Displaystyle D}$${\ Displaystyle D = \ {0, | b | -1 \}}$${\displaystyle b\w \{-2,-4\}}$
4. dane wyjściowe są zakodowane w tym samym formacie ciągu bitów, ale znaczenie miejsc jest inne.

Do negabinatu

Konwersja na negabinarny (podstawa -2; cyfry w ) pozwala na niezwykły skrót (implementacja w C): ${\ Displaystyle \ {0,1 \}}$

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)
}

Ze względu na D. Librika (Szudzika). Bitowa część XOR pochodzi od Schroeppela (1972).

Port JavaScript dla tego samego obliczenia skrótu:

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

Do negaczwartorzędu

Konwersja na negaczwartorzędową (podstawa -4; cyfry w ) pozwala na podobny skrót (implementacja w C): ${\ Displaystyle \ {0,1,2,3\}}$

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)
}

Port JavaScript dla tego samego obliczenia skrótu:

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

Działania arytmetyczne

Poniżej opisano operacje arytmetyczne dla negabinary; obliczenia w większych bazach są podobne.

Dodatek

Dodawanie liczb negabinarnych przebiega bitowo, zaczynając od najmniej znaczących bitów ; bity z każdego dodatku są sumowane z ( zrównoważonym trójskładnikowym ) przeniesieniem z poprzedniego bitu (0 w LSB). Suma ta jest następnie rozkładana na bit wyjściowy i przenoszona do następnej iteracji, jak pokazano w tabeli:

Na przykład drugi wiersz tej tabeli wyraża fakt, że -1 = 1 + 1 × -2; piąty rząd mówi 2 = 0 + -1 × -2; itp.

Jako przykład, aby dodać 1010101 _-2 (1 + 4 + 16 + 64 = 85) i 1110100 _-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

więc wynik to 110011001 _-2 (1 - 8 + 16 - 128 + 256 = 137).

Inna metoda

Podczas dodawania dwóch liczb negabinarnych za każdym razem, gdy generowane jest przeniesienie, dodatkowe przeniesienie powinno być propagowane do następnego bitu. Rozważ ten sam przykład jak powyżej

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

Negabinarny pełny sumator

Sumator pełny obwód może być tak zaprojektowane, aby dodać numery w negabinary. Do obliczenia sumy i przenoszenia używa się następującej logiki:

${\ Displaystyle s_ {i} = a_ {i} \ oplus b_ {i} \ oplus c_ {i} ^ {+} \ oplus c_ {i} ^ {-}}$

${\ Displaystyle c_ {i + 1} ^ {+} = {\ overline {a_ {i}}} {\ overline {b_ {i}}} {\ overline {c_ {i} ^ {+}}} c_ { ja}^{-}}$

${\ Displaystyle c_ {i + 1} ^ {-} = a_ {i} b_ {i} {\ overline {c_ {i} ^ {-}}} + (a_ {i} \ oplus b_ {i}) c_ {i}^{+}{\overline {c_{i}^{-}}}}$

Zwiększanie liczb negabinarnych

Zwiększenie liczby negabinarnej można wykonać za pomocą następującego wzoru:

${\ Displaystyle 2x \ oplus ((2x \ oplus x) + 1)}$

Odejmowanie

Aby odjąć, pomnóż każdy bit drugiej liczby przez -1 i dodaj liczby, korzystając z tej samej tabeli, co powyżej.

Jako przykład, aby obliczyć 1101001 ₋₂ (1 − 8 − 32 + 64 = 25) odjąć 1110100 ₋₂ (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

więc wynik to 100101 _-2 (1 + 4 -32 = -27).

Negację jednoargumentową − x , można obliczyć jako binarne odejmowanie od zera, 0 − x .

Mnożenie i dzielenie

Przesunięcie w lewo mnoży przez -2, przesunięcie w prawo dzieli przez -2.

Aby pomnożyć, pomnóż jak normalne liczby dziesiętne lub dwójkowe , ale stosując zasady negabinacji dotyczące dodawania przeniesienia podczas dodawania liczb.

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

Dla każdej kolumny dodaj przeniesienie do number i podziel sumę przez -2, aby uzyskać nowe przeniesienie i wynikowy bit jako resztę.

Porównywanie liczb negabinarnych

Możliwe jest porównywanie liczb negabinarnych przez nieznaczne dostosowanie normalnego binarnego komparatora bez znaku . Porównując liczby i , odwróć każdy nieparzysty bit obu liczb. Następnie porównaj i użyj standardowego komparatora bez znaku. ${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$

Liczby ułamkowe

Reprezentacja podstawy -r może oczywiście być przenoszona poza punkt podstawy , umożliwiając reprezentację liczb niecałkowitych.

Podobnie jak w przypadku systemów o dodatniej podstawie, końcowe reprezentacje odpowiadają ułamkom, w których mianownik jest potęgą podstawy; powtarzające się reprezentacje odpowiadają innym racjonalnym i z tego samego powodu.

Nieunikalne reprezentacje

W przeciwieństwie do systemów o podstawie dodatniej, gdzie liczby całkowite i ułamki końcowe mają nieunikalne reprezentacje (na przykład w systemie dziesiętnym 0.999... = 1 ) w systemach o podstawie ujemnej liczby całkowite mają tylko jedną reprezentację. Istnieją jednak racjonalności o niejednoznacznych reprezentacjach. Dla cyfr {0, 1, ..., t } z największą cyfrą i ${\displaystyle \mathbf {t}:=r\!-\!\!1=-b\!-\!\!1}$

${\ Displaystyle T: = 0. {\ overline {01}} _ {b} = \ suma _ {i = 1} ^ {\ infty} b ^ {-2i} = {\ Frac {1} {b ^ { 2}-1}}={\frac {1}{r^{2}-1}}}$

mamy

${\ Displaystyle 0. {\ overline {0 \ mathbf {t}}} _ {b} = \ mathbf {t} T = {\ Frac {r \! - \! \! 1} {r ^ {2}- 1}}={\frac {1}{r+1}}}$     jak również

${\ Displaystyle 1. {\ overline {\ mathbf {t} 0}} _ {b} = 1 + \ mathbf {t} bT = {\ Frac {(r ^ {2}-1) + (r \! - \!\!1)b}{r^{2}-1}}={\frac {1}{r+1}}.}$

Tak więc każda liczba z dodanym ułamkiem końcowym ma dwie różne reprezentacje. ${\displaystyle {\frac {1}{r+1}}+z}$ ${\ Displaystyle Z \ w \ mathbb {Z} r ^ {\ mathbb {Z}}}$

Na przykład w negaternary, tj. i , jest ${\displaystyle b=-3}$${\ Displaystyle \ mathbf {t} = 2}$

${\ Displaystyle 1. {\ overline {02}} _ {(-3)} = {\ Frac {5} {4}} = 2. {\ overline {20}} _ {(-3)}}$.

Takie nieunikalne reprezentacje można znaleźć, biorąc pod uwagę największe i najmniejsze możliwe reprezentacje z częściami całkowitymi odpowiednio 0 i 1, a następnie zauważając, że są one równe. (Rzeczywiście, działa to z dowolnym systemem liczb całkowitych).

${\ Displaystyle {\ Frac {z (r + 1) + 1} {b ^ {i} (r + 1)}}}$

z ${\ Displaystyle Z, ja \ w \ mathbb {Z}.}$

Wyimaginowana baza

Tak jak użycie podstawy ujemnej umożliwia reprezentację liczb ujemnych bez wyraźnego znaku ujemnego, użycie podstawy urojonej umożliwia reprezentację liczb całkowitych Gaussa . Donald Knuth zaproponował poczwórną podstawę urojoną (podstawa 2i) w 1955 roku.

Zobacz też

• Podstawa poczwórna urojona
• Dwójkowy
• Zrównoważony trójskładnikowy
• Czwartorzędowy system liczbowy
• Systemy liczbowe
• 1 − 2 + 4 − 8 + ⋯ ( liczby p-adyczne )

Bibliografia

Dalsza lektura

• Warren Jr., Henry S. (2013) [2002]. Hacker's Delight (wyd. 2). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.

Zewnętrzne linki

• Weisstein, Eric W. „Negabinary” . MatematykaŚwiat .
• Weisstein, Eric W. „Negadecymalny” . MatematykaŚwiat .