Negatif taban - Negative base

Bir negatif taban (veya negatif sayı tabanı ) bir inşa etmek için kullanılabilecek standart olmayan konumsal numarası sistemi . Diğer yer-değer sistemleri gibi, her konum, sistem tabanının uygun gücünün katlarını tutar; fakat bu taban negatiftir - yani, b bazı r ( r ≥ 2 ) doğal sayısı için -r'ye eşittir .

Negatif tabanlı sistemler, standart yer değeri sistemleriyle aynı sayıları barındırabilir, ancak hem pozitif hem de negatif sayılar, bir eksi işareti (veya bilgisayar gösteriminde bir işaret biti ) kullanılmadan temsil edilir ; bu avantaj, aritmetik işlemlerin artan karmaşıklığı ile karşılanmaktadır. Normalde negatif bir işaretin içerdiği bilgileri saklama ihtiyacı, genellikle negatif tabanlı bir sayının pozitif tabanlı eşdeğerinden bir basamak daha uzun olmasına neden olur.

Negatif tabanlı konumsal sayı sistemleri için ortak adlar , karşılık gelen pozitif tabanlı sistemin adının önüne negatif ön eki getirilerek oluşturulur ; örneğin, negadecimal (baz -10) karşılık için ondalık (10 tabanı), negabinary (baz-2) için ikili (taban 2), negaternary (baz-3) için üçlü (baz 3) ve negaquaternary (baz -4) için dörtlü (baz 4).

Örnek

Temsil ile ne kastedildiğini düşünün 12243 baz negadecimal sisteminde b -10:

10.000 + (−2.000) + 200 + (−40) + 3 = 8.163 , temsilNegadecimal gösterimde 12.243 ₋₁₀ eşdeğerdir8.163 ₁₀ ondalık gösterimde,-8,163 ₁₀ ondalık olarak yazılır9.977 _-10 negadecimal içinde.

Tarih

Negatif sayısal tabanlar ilk olarak Vittorio Grünwald tarafından Giornale di Matematiche di Battaglini'de yayınlanan 1885 tarihli bir monografide ele alındı . Grünwald, toplama, çıkarma, çarpma, bölme, kök çıkarma, bölünebilirlik testleri ve sayı tabanı dönüştürme işlemlerini gerçekleştirmek için algoritmalar verdi. Negatif bazlar daha sonra 1936'da AJ Kempner tarafından geçerken bahsedilmiş ve 1957'de Zdzisław Pawlak ve A. Wakulicz tarafından daha ayrıntılı olarak incelenmiştir .

Negabinary erken hayata geçirildi Polonyalı bilgisayara BINEG (ve UMC dan Z. Pawlak ve A. Lazarkiewicz tarafından fikirlere dayanan,) 1957-59 inşa Matematik Enstitüsü içinde Varşova . O zamandan beri uygulamalar nadir olmuştur.

Notasyon ve kullanım

Olarak tabanını gösteren -r , her tamsayı bir benzersiz olarak yazılabilir

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

her rakam burada d _k , 0 ila arasında bir tamsayıdır , r 1 - ve esas basamak d _n olup > 0 (sürece , n = 0 ). Baz r genişlemesi bir sonra dize verilir d _n d _{n -1} ... d ₁ d ₀ .

Negatif tabanlı sistemler bu nedenle, tabanın pozitif olduğu ancak rakamların kısmen negatif bir aralıktan alındığı dengeli üçlü gibi işaretli basamaklı temsillerle karşılaştırılabilir . (Aşağıdaki tabloda −1 değerinin basamağı tek karakter T olarak yazılmıştır.)

Bazı sayılann temel olarak aynı gösterimi -r temel olarak r . Örneğin, 100'den 109'a kadar olan sayılar, ondalık ve negadesimal olarak aynı temsillere sahiptir. Benzer şekilde,

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

ve ikili olarak 10001 ve negabinary olarak 10001 ile temsil edilir.

Bir dizi pozitif ve karşılık gelen negatif bazda açılımları olan bazı sayılar:

Nega dengeli üçlü hariç, negatif tam sayıların taban −r açılımlarının çift ​​sayıda basamağa sahipken, negatif olmayan tam sayıların taban −r açılımlarının tek sayıda basamağa sahip olduğuna dikkat edin.

Hesaplama

Taban -r bir dizi genişlemesi ile tekrar bölme bulunabilir -r negatif olmayan kalıntılar, kayıt ve son başlayarak bu kalanlar bitiştirme. a /  b , d kalanıyla c ise , o zaman bc + d = a ve dolayısıyla d = a - bc olduğuna dikkat edin . Doğru dönüştürmeye ulaşmak için, c değeri , d negatif olmayacak ve minimum olacak şekilde seçilmelidir . Bu, aşağıdaki örneğin dördüncü satırında örneklenmiştir, burada –5 ÷ –3, 1 kalan 2 yerine 2 kalan 1'e eşit olacak şekilde seçilmelidir. ${\displaystyle \{0,1,\ldots ,r-1\}}$

Örneğin, 146'yı ondalık sayıya dönüştürmek için:

${\displaystyle {\begin{array}{rr}146\div (-3)=&-48~\operatöradı {kalan} ~2\\-48\div (-3)=&16~\operatöradı {kalan} ~ 0\\16\div (-3)=&-5~\operatöradı {kalan} ~1\\-5\div (-3)=&2~\operatöradı {kalan} ~1\\2\div (-3 )=&0~\operatöradı {kalan} ~2\end{dizi}}}$

Kalanlar okuma geri 146, bir negaternary temsilini elde ₁₀ : 21102 _-3 .

Kanıt: ((( 2  · (–3) + 1 ) · (–3) + 1 ) · (–3) + 0 ) · (–3) + 2 = 146 ₁₀ .

Çoğu programlama dilinde , negatif bir sayıyı negatif bir sayıya bölmenin sonucunun (tamsayı aritmetiğinde) 0'a yuvarlandığını ve genellikle negatif bir kalan bıraktığını unutmayın. Böyle bir durumda elimizde a = (− r ) c + d = (− r ) c + d − r + r = (− r )( c + 1) + ( d + r ) olur . Çünkü | g | < r , ( d + r ) pozitif kalandır. Bu nedenle, böyle bir durumda doğru sonucu elde etmek için, yukarıdaki algoritmanın bilgisayar uygulamaları , bölüme ve kalanına sırasıyla 1 ve r eklemelidir .

Örnek uygulama kodu

Negabinary'ye

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

Negaternary için

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

piton

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'

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

Herhangi bir negatif tabana

Java

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

Otomatik Lisp

[-10 -2] aralığından:

(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

Tamsayıdan bazı negatif tabana dönüşüm:

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

Kısayol hesaplama

Aşağıdaki algoritmalar,

1. girdi, bit dizilerinde mevcuttur ve (taban +2; hanelerdeki rakamlar ) olarak kodlanmıştır ( günümüzün dijital bilgisayarlarının çoğunda olduğu gibi),${\görüntüleme stili \{0,1\}}$
2. bu tür bit dizileri üzerinde çalışan ekleme (+) ve xor (^) işlemleri vardır (günümüz dijital bilgisayarlarının çoğunda olduğu gibi),
3. çıktı basamakları seti standarttır, i. e. taban ile ,${\görüntüleme stili D}$${\displaystyle D=\{0,|b|-1\}}$${\displaystyle b\in \{-2,-4\}}$
4. çıktı aynı bit dizgisi biçiminde kodlanmıştır, ancak yerlerin anlamı başkadır.

Negabinary'ye

Negabinary'ye dönüştürme (taban -2; 'deki rakamlar ) dikkate değer bir kısayol sağlar (C uygulaması): ${\görüntüleme stili \{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)
}

D. Librik (Szudzik) yüzünden. Bitsel XOR kısmı orijinal olarak Schroeppel'e (1972) dayanmaktadır .

Aynı kısayol hesaplaması için JavaScript bağlantı noktası:

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

Negakuaterner için

Negakuaterner'e dönüştürme (taban -4; 'deki rakamlar ) benzer bir kısayola izin verir (C uygulaması): ${\görüntüleme stili \{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)
}

Aynı kısayol hesaplaması için JavaScript bağlantı noktası:

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

Aritmetik işlemler

Aşağıda negabinary için aritmetik işlemler açıklanmaktadır; daha büyük bazlardaki hesaplamalar benzerdir.

Ek

Negabinary sayıların eklenmesi, en az anlamlı bitlerden başlayarak bit düzeyinde ilerler ; her ekten gelen bitler, önceki bitten (LSB'de 0 olan) taşıma ( dengeli üçlü ) ile toplanır . Bu toplam daha sonra bir çıktı bitine ayrıştırılır ve tabloda gösterildiği gibi bir sonraki yineleme için taşınır:

Bu tablonun ikinci satırı, örneğin, -1 = 1 + 1 × -2; beşinci satır 2 = 0 + -1 × -2 diyor ; vesaire.

Örnek olarak 1010101 ₋₂ (1 + 4 + 16 + 64 = 85) ve 1110100 ₋₂ (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

yani sonuç 110011001 _-2 (1 − 8 + 16 − 128 + 256 = 137).

Diğer yöntem

İki negabinary sayı eklerken, her taşıma oluşturulduğunda, bir sonraki bite fazladan bir taşıma yayılmalıdır. Yukarıdakiyle aynı örneği düşünün

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 tam toplayıcı

Bir tam toplayıcı devresi negabinary numaralar eklemek için tasarlanmış olabilir. Toplamı hesaplamak için aşağıdaki mantık kullanılır ve şunları taşır:

${\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_{ ben}^{-}}$

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

Negabinary sayıların artması

Negabinary bir sayının arttırılması, aşağıdaki formül kullanılarak yapılabilir:

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

Çıkarma

Çıkarmak için, ikinci sayının her bitini -1 ile çarpın ve yukarıdaki tabloyu kullanarak sayıları ekleyin.

Örnek olarak, 1101001 ₋₂ (1 − 8 − 32 + 64 = 25) eksi 1110100 ₋₂ (4 + 16 − 32 + 64 = 52) hesaplamak için ,

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

yani sonuç 100101 _-2 (1 + 4 −32 = −27).

Tekli olumsuzlama, − x , sıfırdan ikili çıkarma olarak hesaplanabilir, 0 − x .

Çarpma ve bölme

Sola kaydırmak -2 ile çarpar, sağa kaydırmak -2 ile böler.

Çarpmak için, normal ondalık veya ikili sayılar gibi çarpın , ancak sayıları eklerken taşımayı eklemek için negabinary kurallarını kullanın.

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

Her bir sütun için, ekleme carry için sayı ve yeni elde etmek için, -2 tarafından toplam ikiye bölünür carry ve bakiye olarak elde edilen bit.

Negabinary sayıları karşılaştırma

Normal bir işaretsiz ikili karşılaştırıcıyı hafifçe ayarlayarak negabinary sayıları karşılaştırmak mümkündür . Sayıları karşılaştırırken ve her iki numara her tek konumlu bit ters çevirme. Bundan sonra, standart bir imzasız karşılaştırıcı kullanarak karşılaştırın ve kullanın. ${\görüntüleme stili A}$${\görüntüleme stili B}$${\görüntüleme stili A}$${\görüntüleme stili B}$

kesirli sayılar

Taban −r gösterimi, elbette , tamsayı olmayan sayıların temsiline izin vererek, sayı tabanı noktasının ötesine taşınabilir .

Pozitif tabanlı sistemlerde olduğu gibi, sonlandırıcı temsiller, paydanın tabanın gücü olduğu kesirlere karşılık gelir; yinelenen temsiller diğer rasyonellere karşılık gelir ve aynı nedenle.

Benzersiz olmayan temsiller

Tam sayıların ve sonlanan kesirlerin benzersiz olmayan temsillere sahip olduğu pozitif tabanlı sistemlerin aksine (örneğin, ondalık 0.999... = 1 ) negatif tabanlı sistemlerde tamsayılar yalnızca tek bir temsile sahiptir. Bununla birlikte, benzersiz olmayan temsilleri olan rasyoneller vardır. En büyük basamağa sahip {0, 1, ..., t } rakamları için ve ${\displaystyle \mathbf {t} :=r\!-\!\!1=-b\!-\!\!1}$

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

sahibiz

${\displaystyle 0.{\overline {0\mathbf {t} }}_{b}=\mathbf {t} T={\frac {r\!-\!\!1}{r^{2}- 1}}={\frac {1}{r+1}}}$     birlikte

${\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}}.}$

Bu nedenle , sonlanan kesri eklenmiş her sayının iki farklı temsili vardır. ${\displaystyle {\frac {1}{r+1}}+z}$ ${\displaystyle z\in \mathbb {Z} r^{\mathbb {Z} }}$

Örneğin, negaternary'de, yani ve , var ${\görüntüleme stili b=-3}$${\displaystyle \mathbf {t} =2}$

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

Bu tür benzersiz olmayan temsiller, sırasıyla 0 ve 1 tamsayı bölümleriyle mümkün olan en büyük ve en küçük temsiller dikkate alınarak ve sonra bunların eşit oldukları not edilerek bulunabilir. (Aslında, bu herhangi bir tamsayı tabanlı sistemle çalışır.) Bu nedenle benzersiz olmayan şekilde ifade edilemeyen rasyoneller, formunkilerdir.

${\displaystyle {\frac {z(r+1)+1}{b^{i}(r+1)}}}$

ile birlikte ${\displaystyle z,i\in \mathbb {Z} .}$

hayali taban

Negatif bir taban kullanmanın negatif sayıların açık bir negatif işaret olmadan temsiline izin vermesi gibi , sanal bir taban kullanmak da Gauss tamsayılarının temsiline izin verir . Donald Knuth , 1955'te dörtlü hayali tabanı (taban 2i) önerdi .

Ayrıca bakınız

• Kuater-hayali taban
• İkili
• Dengeli üçlü
• Kuaterner sayı sistemi
• Sayı sistemleri
• 1 − 2 + 4 − 8 + ⋯ ( p- adic sayılar )

Referanslar

daha fazla okuma

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

Dış bağlantılar

• Weisstein, Eric W. "Negabinary" . Matematik Dünyası .
• Weisstein, Eric W. "Negadesimal" . Matematik Dünyası .