Negative base

History

Negative numerical bases were first considered by Vittorio Grünwald in an 1885 monograph published in Giornale di Matematiche di Battaglini. Grünwald gave algorithms for performing addition, subtraction, multiplication, division, root extraction, divisibility tests, and radix conversion. Negative bases were later mentioned in passing by A. J. Kempner in 1936 and studied in more detail by Zdzisław Pawlak and A. Wakulicz in 1957.

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. Implementations since then have been rare.

zfp, a floating-point compression algorithm from the Lawrence Livermore National Laboratory, uses negabinary to store numbers. According to zfp's documentation:

Unlike sign-magnitude representations, the leftmost one-bit in negabinary simultaneously encodes the sign and approximate magnitude of a number. Moreover, unlike two’s complement, numbers small in magnitude have many leading zeros in negabinary regardless of sign, which facilitates encoding.

Notation and use

Denoting the base as −r, every integer a can be written uniquely as

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

where each digit d_k is an integer from 0 to r − 1 and the leading digit d_n > 0 (unless n = 0). The base −r expansion of a is then given by the string d_nd_n−1...d₁d₀.

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 −r as in base r. For example, the numbers from 100 to 109 have the same representations in decimal and negadecimal. Similarly,

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

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:

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

Calculation

The base −r expansion of a number can be found by repeated division by −r, recording the non-negative remainders in ${\displaystyle \{0,1,\dots ,r-1\}}$, and concatenating those remainders, starting with the last. Note that if a / b is c with remainder d, then bc + d = a and therefore d = a − bc. To arrive at the correct conversion, the value for c must be chosen such that d is non-negative and minimal. For the fourth line of the following example this means that

${\displaystyle -5÷(-3)=2\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{r}1}$

has to be chosen — and not ${\displaystyle =3\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{r}4}$ nor ${\displaystyle =1\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{r}-2.}$

For example, to convert 146 in decimal to negaternary:

${\displaystyle \begin{array}{rr}146÷(-3)=& -48\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{r}2\\ -48÷(-3)=& 16\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{r}0\\ 16÷(-3)=& -5\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{r}1\\ -5÷(-3)=& 2\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{r}1\\ 2÷(-3)=& 0\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{r}2\end{array}}$

Reading the remainders backward we obtain the negaternary representation of 146₁₀: 21102_–3.

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

= 146₁₀.

Reading the remainders forward we can obtain the negaternary least-significant-digit-first representation.

Proof: 2 + ( 0 + ( 1 + ( 1 + ( 2 ) · -3 ) · -3) · -3 ) · -3 = 146₁₀.

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 a = (−r)c + d = (−r)c + d − r + r = (−r)(c + 1) + (d + r). Because |d| < r, (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 r to the quotient and remainder respectively.

Example implementation code

To negabinary

C#

<span id="mwAfc"></span><span class="k" id="mwAfg">static</span><span class="w" id="mwAfk"> </span><span class="kt" id="mwAfo">string</span><span class="w" id="mwAfs"> </span><span class="nf" id="mwAfw">ToNegabinary</span><span class="p" id="mwAf0">(</span><span class="kt" id="mwAf4">int</span><span class="w" id="mwAf8"> </span><span class="n" id="mwAgA">val</span><span class="p" id="mwAgE">)</span> <span class="p" id="mwAgI">{</span> <span class="w" id="mwAgM"> </span><span class="kt" id="mwAgQ">string</span><span class="w" id="mwAgU"> </span><span class="n" id="mwAgY">result</span><span class="w" id="mwAgc"> </span><span class="o" id="mwAgg">=</span><span class="w" id="mwAgk"> </span><span class="kt" id="mwAgo">string</span><span class="p" id="mwAgs">.</span><span class="n" id="mwAgw">Empty</span><span class="p" id="mwAg0">;</span> <span class="w" id="mwAg4"> </span><span class="k" id="mwAg8">while</span><span class="w" id="mwAhA"> </span><span class="p" id="mwAhE">(</span><span class="n" id="mwAhI">val</span><span class="w" id="mwAhM"> </span><span class="o" id="mwAhQ">!=</span><span class="w" id="mwAhU"> </span><span class="m" id="mwAhY">0</span><span class="p" id="mwAhc">)</span> <span class="w" id="mwAhg"> </span><span class="p" id="mwAhk">{</span> <span class="w" id="mwAho"> </span><span class="kt" id="mwAhs">int</span><span class="w" id="mwAhw"> </span><span class="n" id="mwAh0">remainder</span><span class="w" id="mwAh4"> </span><span class="o" id="mwAh8">=</span><span class="w" id="mwAiA"> </span><span class="n" id="mwAiE">val</span><span class="w" id="mwAiI"> </span><span class="o" id="mwAiM">%</span><span class="w" id="mwAiQ"> </span><span class="o" id="mwAiU">-</span><span class="m" id="mwAiY">2</span><span class="p" id="mwAic">;</span> <span class="w" id="mwAig"> </span><span class="n" id="mwAik">val</span><span class="w" id="mwAio"> </span><span class="o" id="mwAis">=</span><span class="w" id="mwAiw"> </span><span class="n" id="mwAi0">val</span><span class="w" id="mwAi4"> </span><span class="o" id="mwAi8">/</span><span class="w" id="mwAjA"> </span><span class="o" id="mwAjE">-</span><span class="m" id="mwAjI">2</span><span class="p" id="mwAjM">;</span> <span class="w" id="mwAjQ"> </span><span class="k" id="mwAjU">if</span><span class="w" id="mwAjY"> </span><span class="p" id="mwAjc">(</span><span class="n" id="mwAjg">remainder</span><span class="w" id="mwAjk"> </span><span class="o" id="mwAjo"><</span><span class="w" id="mwAjs"> </span><span class="m" id="mwAjw">0</span><span class="p" id="mwAj0">)</span> <span class="w" id="mwAj4"> </span><span class="p" id="mwAj8">{</span> <span class="w" id="mwAkA"> </span><span class="n" id="mwAkE">remainder</span><span class="w" id="mwAkI"> </span><span class="o" id="mwAkM">+=</span><span class="w" id="mwAkQ"> </span><span class="m" id="mwAkU">2</span><span class="p" id="mwAkY">;</span> <span class="w" id="mwAkc"> </span><span class="n" id="mwAkg">val</span><span class="w" id="mwAkk"> </span><span class="o" id="mwAko">+=</span><span class="w" id="mwAks"> </span><span class="m" id="mwAkw">1</span><span class="p" id="mwAk0">;</span> <span class="w" id="mwAk4"> </span><span class="p" id="mwAk8">}</span> <span class="w" id="mwAlA"> </span><span class="n" id="mwAlE">result</span><span class="w" id="mwAlI"> </span><span class="o" id="mwAlM">=</span><span class="w" id="mwAlQ"> </span><span class="n" id="mwAlU">remainder</span><span class="p" id="mwAlY">.</span><span class="n" id="mwAlc">ToString</span><span class="p" id="mwAlg">()</span><span class="w" id="mwAlk"> </span><span class="o" id="mwAlo">+</span><span class="w" id="mwAls"> </span><span class="n" id="mwAlw">result</span><span class="p" id="mwAl0">;</span> <span class="w" id="mwAl4"> </span><span class="p" id="mwAl8">}</span> <span class="w" id="mwAmA"> </span><span class="k" id="mwAmE">return</span><span class="w" id="mwAmI"> </span><span class="n" id="mwAmM">result</span><span class="p" id="mwAmQ">;</span> <span class="p" id="mwAmU">}</span>

C++

<span id="mwAmk"></span><span class="k" id="mwAmo">auto</span><span class="w" id="mwAms"> </span><span class="n" id="mwAmw">to_negabinary</span><span class="p" id="mwAm0">(</span><span class="kt" id="mwAm4">int</span><span class="w" id="mwAm8"> </span><span class="n" id="mwAnA">value</span><span class="p" id="mwAnE">)</span> <span class="p" id="mwAnI">{</span> <span class="w" id="mwAnM"> </span><span class="n" id="mwAnQ">std</span><span class="o" id="mwAnU">::</span><span class="n" id="mwAnY">bitset</span><span class="o" id="mwAnc"><</span><span class="k" id="mwAng">sizeof</span><span class="p" id="mwAnk">(</span><span class="kt" id="mwAno">int</span><span class="p" id="mwAns">)</span><span class="w" id="mwAnw"> </span><span class="o" id="mwAn0">*</span><span class="w" id="mwAn4"> </span><span class="n" id="mwAn8">CHAR_BIT</span><span class="w" id="mwAoA"> </span><span class="o" id="mwAoE">></span><span class="w" id="mwAoI"> </span><span class="n" id="mwAoM">result</span><span class="p" id="mwAoQ">;</span> <span class="w" id="mwAoU"> </span><span class="n" id="mwAoY">std</span><span class="o" id="mwAoc">::</span><span class="kt" id="mwAog">size_t</span><span class="w" id="mwAok"> </span><span class="n" id="mwAoo">bit_position</span><span class="w" id="mwAos"> </span><span class="o" id="mwAow">=</span><span class="w" id="mwAo0"> </span><span class="mi" id="mwAo4">0</span><span class="p" id="mwAo8">;</span> <span class="w" id="mwApA"> </span><span class="k" id="mwApE">while</span><span class="w" id="mwApI"> </span><span class="p" id="mwApM">(</span><span class="n" id="mwApQ">value</span><span class="w" id="mwApU"> </span><span class="o" id="mwApY">!=</span><span class="w" id="mwApc"> </span><span class="mi" id="mwApg">0</span><span class="p" id="mwApk">)</span> <span class="w" id="mwApo"> </span><span class="p" id="mwAps">{</span> <span class="w" id="mwApw"> </span><span class="k" id="mwAp0">const</span><span class="w" id="mwAp4"> </span><span class="k" id="mwAp8">auto</span><span class="w" id="mwAqA"> </span><span class="n" id="mwAqE">div_result</span><span class="w" id="mwAqI"> </span><span class="o" id="mwAqM">=</span><span class="w" id="mwAqQ"> </span><span class="n" id="mwAqU">std</span><span class="o" id="mwAqY">::</span><span class="n" id="mwAqc">div</span><span class="p" id="mwAqg">(</span><span class="n" id="mwAqk">value</span><span class="p" id="mwAqo">,</span><span class="w" id="mwAqs"> </span><span class="mi" id="mwAqw">-2</span><span class="p" id="mwAq0">);</span> <span class="w" id="mwAq4"> </span><span class="k" id="mwAq8">if</span><span class="w" id="mwArA"> </span><span class="p" id="mwArE">(</span><span class="n" id="mwArI">div_result</span><span class="p" id="mwArM">.</span><span class="n" id="mwArQ">rem</span><span class="w" id="mwArU"> </span><span class="o" id="mwArY"><</span><span class="w" id="mwArc"> </span><span class="mi" id="mwArg">0</span><span class="p" id="mwArk">)</span> <span class="w" id="mwAro"> </span><span class="n" id="mwArs">value</span><span class="w" id="mwArw"> </span><span class="o" id="mwAr0">=</span><span class="w" id="mwAr4"> </span><span class="n" id="mwAr8">div_result</span><span class="p" id="mwAsA">.</span><span class="n" id="mwAsE">quot</span><span class="w" id="mwAsI"> </span><span class="o" id="mwAsM">+</span><span class="w" id="mwAsQ"> </span><span class="mi" id="mwAsU">1</span><span class="p" id="mwAsY">;</span> <span class="w" id="mwAsc"> </span><span class="k" id="mwAsg">else</span> <span class="w" id="mwAsk"> </span><span class="n" id="mwAso">value</span><span class="w" id="mwAss"> </span><span class="o" id="mwAsw">=</span><span class="w" id="mwAs0"> </span><span class="n" id="mwAs4">div_result</span><span class="p" id="mwAs8">.</span><span class="n" id="mwAtA">quot</span><span class="p" id="mwAtE">;</span> <span class="w" id="mwAtI"> </span><span class="n" id="mwAtM">result</span><span class="p" id="mwAtQ">.</span><span class="n" id="mwAtU">set</span><span class="p" id="mwAtY">(</span><span class="n" id="mwAtc">bit_position</span><span class="p" id="mwAtg">,</span><span class="w" id="mwAtk"> </span><span class="n" id="mwAto">div_result</span><span class="p" id="mwAts">.</span><span class="n" id="mwAtw">rem</span><span class="w" id="mwAt0"> </span><span class="o" id="mwAt4">!=</span><span class="w" id="mwAt8"> </span><span class="mi" id="mwAuA">0</span><span class="p" id="mwAuE">);</span> <span class="w" id="mwAuI"> </span><span class="o" id="mwAuM">++</span><span class="n" id="mwAuQ">bit_position</span><span class="p" id="mwAuU">;</span> <span class="w" id="mwAuY"> </span><span class="p" id="mwAuc">}</span> <span class="w" id="mwAug"> </span><span class="k" id="mwAuk">return</span><span class="w" id="mwAuo"> </span><span class="n" id="mwAus">result</span><span class="p" id="mwAuw">;</span> <span class="p" id="mwAu0">}</span>

To negaternary

C#

<span id="mwAvI"></span><span class="k" id="mwAvM">static</span><span class="w" id="mwAvQ"> </span><span class="kt" id="mwAvU">string</span><span class="w" id="mwAvY"> </span><span class="nf" id="mwAvc">Negaternary</span><span class="p" id="mwAvg">(</span><span class="kt" id="mwAvk">int</span><span class="w" id="mwAvo"> </span><span class="n" id="mwAvs">val</span><span class="p" id="mwAvw">)</span> <span class="p" id="mwAv0">{</span> <span class="w" id="mwAv4"> </span><span class="kt" id="mwAv8">string</span><span class="w" id="mwAwA"> </span><span class="n" id="mwAwE">result</span><span class="w" id="mwAwI"> </span><span class="o" id="mwAwM">=</span><span class="w" id="mwAwQ"> </span><span class="kt" id="mwAwU">string</span><span class="p" id="mwAwY">.</span><span class="n" id="mwAwc">Empty</span><span class="p" id="mwAwg">;</span> <span class="w" id="mwAwk"> </span><span class="k" id="mwAwo">while</span><span class="w" id="mwAws"> </span><span class="p" id="mwAww">(</span><span class="n" id="mwAw0">val</span><span class="w" id="mwAw4"> </span><span class="o" id="mwAw8">!=</span><span class="w" id="mwAxA"> </span><span class="m" id="mwAxE">0</span><span class="p" id="mwAxI">)</span> <span class="w" id="mwAxM"> </span><span class="p" id="mwAxQ">{</span> <span class="w" id="mwAxU"> </span><span class="kt" id="mwAxY">int</span><span class="w" id="mwAxc"> </span><span class="n" id="mwAxg">remainder</span><span class="w" id="mwAxk"> </span><span class="o" id="mwAxo">=</span><span class="w" id="mwAxs"> </span><span class="n" id="mwAxw">val</span><span class="w" id="mwAx0"> </span><span class="o" id="mwAx4">%</span><span class="w" id="mwAx8"> </span><span class="o" id="mwAyA">-</span><span class="m" id="mwAyE">3</span><span class="p" id="mwAyI">;</span> <span class="w" id="mwAyM"> </span><span class="n" id="mwAyQ">val</span><span class="w" id="mwAyU"> </span><span class="o" id="mwAyY">=</span><span class="w" id="mwAyc"> </span><span class="n" id="mwAyg">val</span><span class="w" id="mwAyk"> </span><span class="o" id="mwAyo">/</span><span class="w" id="mwAys"> </span><span class="o" id="mwAyw">-</span><span class="m" id="mwAy0">3</span><span class="p" id="mwAy4">;</span> <span class="w" id="mwAy8"> </span><span class="k" id="mwAzA">if</span><span class="w" id="mwAzE"> </span><span class="p" id="mwAzI">(</span><span class="n" id="mwAzM">remainder</span><span class="w" id="mwAzQ"> </span><span class="o" id="mwAzU"><</span><span class="w" id="mwAzY"> </span><span class="m" id="mwAzc">0</span><span class="p" id="mwAzg">)</span> <span class="w" id="mwAzk"> </span><span class="p" id="mwAzo">{</span> <span class="w" id="mwAzs"> </span><span class="n" id="mwAzw">remainder</span><span class="w" id="mwAz0"> </span><span class="o" id="mwAz4">+=</span><span class="w" id="mwAz8"> </span><span class="m" id="mwA0A">3</span><span class="p" id="mwA0E">;</span> <span class="w" id="mwA0I"> </span><span class="n" id="mwA0M">val</span><span class="w" id="mwA0Q"> </span><span class="o" id="mwA0U">+=</span><span class="w" id="mwA0Y"> </span><span class="m" id="mwA0c">1</span><span class="p" id="mwA0g">;</span> <span class="w" id="mwA0k"> </span><span class="p" id="mwA0o">}</span> <span class="w" id="mwA0s"> </span><span class="n" id="mwA0w">result</span><span class="w" id="mwA00"> </span><span class="o" id="mwA04">=</span><span class="w" id="mwA08"> </span><span class="n" id="mwA1A">remainder</span><span class="p" id="mwA1E">.</span><span class="n" id="mwA1I">ToString</span><span class="p" id="mwA1M">()</span><span class="w" id="mwA1Q"> </span><span class="o" id="mwA1U">+</span><span class="w" id="mwA1Y"> </span><span class="n" id="mwA1c">result</span><span class="p" id="mwA1g">;</span> <span class="w" id="mwA1k"> </span><span class="p" id="mwA1o">}</span> <span class="w" id="mwA1s"> </span><span class="k" id="mwA1w">return</span><span class="w" id="mwA10"> </span><span class="n" id="mwA14">result</span><span class="p" id="mwA18">;</span> <span class="p" id="mwA2A">}</span>

Python

<span id="mwA2U"></span><span class="k" id="mwA2Y">def</span> <span class="nf" id="mwA2c">negaternary</span><span class="p" id="mwA2g">(</span><span class="n" id="mwA2k">i</span><span class="p" id="mwA2o">:</span> <span class="nb" id="mwA2s">int</span><span class="p" id="mwA2w">)</span> <span class="o" id="mwA20">-></span> <span class="nb" id="mwA24">str</span><span class="p" id="mwA28">:</span> <span class="w" id="mwA3A"> </span><span class="sd" id="mwA3E">"""Decimal to negaternary."""</span> <span class="k" id="mwA3I">if</span> <span class="n" id="mwA3M">i</span> <span class="o" id="mwA3Q">==</span> <span class="mi" id="mwA3U">0</span><span class="p" id="mwA3Y">:</span> <span class="n" id="mwA3c">digits</span> <span class="o" id="mwA3g">=</span> <span class="p" id="mwA3k">[</span><span class="s2" id="mwA3o">"0"</span><span class="p" id="mwA3s">]</span> <span class="k" id="mwA3w">else</span><span class="p" id="mwA30">:</span> <span class="n" id="mwA34">digits</span> <span class="o" id="mwA38">=</span> <span class="p" id="mwA4A">[]</span> <span class="k" id="mwA4E">while</span> <span class="n" id="mwA4I">i</span> <span class="o" id="mwA4M">!=</span> <span class="mi" id="mwA4Q">0</span><span class="p" id="mwA4U">:</span> <span class="n" id="mwA4Y">i</span><span class="p" id="mwA4c">,</span> <span class="n" id="mwA4g">remainder</span> <span class="o" id="mwA4k">=</span> <span class="nb" id="mwA4o">divmod</span><span class="p" id="mwA4s">(</span><span class="n" id="mwA4w">i</span><span class="p" id="mwA40">,</span> <span class="o" id="mwA44">-</span><span class="mi" id="mwA48">3</span><span class="p" id="mwA5A">)</span> <span class="k" id="mwA5E">if</span> <span class="n" id="mwA5I">remainder</span> <span class="o" id="mwA5M"><</span> <span class="mi" id="mwA5Q">0</span><span class="p" id="mwA5U">:</span> <span class="n" id="mwA5Y">i</span><span class="p" id="mwA5c">,</span> <span class="n" id="mwA5g">remainder</span> <span class="o" id="mwA5k">=</span> <span class="n" id="mwA5o">i</span> <span class="o" id="mwA5s">+</span> <span class="mi" id="mwA5w">1</span><span class="p" id="mwA50">,</span> <span class="n" id="mwA54">remainder</span> <span class="o" id="mwA58">+</span> <span class="mi" id="mwA6A">3</span> <span class="n" id="mwA6E">digits</span><span class="o" id="mwA6I">.</span><span class="n" id="mwA6M">append</span><span class="p" id="mwA6Q">(</span><span class="nb" id="mwA6U">str</span><span class="p" id="mwA6Y">(</span><span class="n" id="mwA6c">remainder</span><span class="p" id="mwA6g">))</span> <span class="k" id="mwA6k">return</span> <span class="s2" id="mwA6o">""</span><span class="o" id="mwA6s">.</span><span class="n" id="mwA6w">join</span><span class="p" id="mwA60">(</span><span class="n" id="mwA64">digits</span><span class="p" id="mwA68">[::</span><span class="o" id="mwA7A">-</span><span class="mi" id="mwA7E">1</span><span class="p" id="mwA7I">])</span>

<span id="mwA7U"></span><span class="gp" id="mwA7Y">>>> </span><span class="n" id="mwA7c">negaternary</span><span class="p" id="mwA7g">(</span><span class="mi" id="mwA7k">1000</span><span class="p" id="mwA7o">)</span> <span class="go" id="mwA7s">'2212001'</span>

Common Lisp

<span id="mwA78"></span><span class="p" id="mwA8A">(</span><span class="nb" id="mwA8E">defun</span><span class="w" id="mwA8I"> </span><span class="nv" id="mwA8M">negaternary</span><span class="w" id="mwA8Q"> </span><span class="p" id="mwA8U">(</span><span class="nv" id="mwA8Y">i</span><span class="p" id="mwA8c">)</span> <span class="w" id="mwA8g"> </span><span class="p" id="mwA8k">(</span><span class="k" id="mwA8o">if</span><span class="w" id="mwA8s"> </span><span class="p" id="mwA8w">(</span><span class="nb" id="mwA80">zerop</span><span class="w" id="mwA84"> </span><span class="nv" id="mwA88">i</span><span class="p" id="mwA9A">)</span> <span class="w" id="mwA9E"> </span><span class="s" id="mwA9I">"0"</span> <span class="w" id="mwA9M"> </span><span class="p" id="mwA9Q">(</span><span class="k" id="mwA9U">let</span><span class="w" id="mwA9Y"> </span><span class="p" id="mwA9c">((</span><span class="nv" id="mwA9g">digits</span><span class="w" id="mwA9k"> </span><span class="s" id="mwA9o">""</span><span class="p" id="mwA9s">)</span> <span class="w" id="mwA9w"> </span><span class="p" id="mwA90">(</span><span class="nb" id="mwA94">rem</span><span class="w" id="mwA98"> </span><span class="mi" id="mwA-A">0</span><span class="p" id="mwA-E">))</span> <span class="w" id="mwA-I"> </span><span class="p" id="mwA-M">(</span><span class="nb" id="mwA-Q">loop</span><span class="w" id="mwA-U"> </span><span class="nv" id="mwA-Y">while</span><span class="w" id="mwA-c"> </span><span class="p" id="mwA-g">(</span><span class="nb" id="mwA-k">not</span><span class="w" id="mwA-o"> </span><span class="p" id="mwA-s">(</span><span class="nb" id="mwA-w">zerop</span><span class="w" id="mwA-0"> </span><span class="nv" id="mwA-4">i</span><span class="p" id="mwA-8">))</span><span class="w" id="mwA_A"> </span><span class="nb" id="mwA_E">do</span> <span class="w" id="mwA_I"> </span><span class="p" id="mwA_M">(</span><span class="k" id="mwA_Q">progn</span> <span class="w" id="mwA_U"> </span><span class="p" id="mwA_Y">(</span><span class="nb" id="mwA_c">multiple-value-setq</span><span class="w" id="mwA_g"> </span><span class="p" id="mwA_k">(</span><span class="nv" id="mwA_o">i</span><span class="w" id="mwA_s"> </span><span class="nb" id="mwA_w">rem</span><span class="p" id="mwA_0">)</span><span class="w" id="mwA_4"> </span><span class="p" id="mwA_8">(</span><span class="nb" id="mwBAA">truncate</span><span class="w" id="mwBAE"> </span><span class="nv" id="mwBAI">i</span><span class="w" id="mwBAM"> </span><span class="mi" id="mwBAQ">-3</span><span class="p" id="mwBAU">))</span> <span class="w" id="mwBAY"> </span><span class="p" id="mwBAc">(</span><span class="nb" id="mwBAg">when</span><span class="w" id="mwBAk"> </span><span class="p" id="mwBAo">(</span><span class="nb" id="mwBAs">minusp</span><span class="w" id="mwBAw"> </span><span class="nb" id="mwBA0">rem</span><span class="p" id="mwBA4">)</span> <span class="w" id="mwBA8"> </span><span class="p" id="mwBBA">(</span><span class="nb" id="mwBBE">incf</span><span class="w" id="mwBBI"> </span><span class="nv" id="mwBBM">i</span><span class="p" id="mwBBQ">)</span> <span class="w" id="mwBBU"> </span><span class="p" id="mwBBY">(</span><span class="nb" id="mwBBc">incf</span><span class="w" id="mwBBg"> </span><span class="nb" id="mwBBk">rem</span><span class="w" id="mwBBo"> </span><span class="mi" id="mwBBs">3</span><span class="p" id="mwBBw">))</span> <span class="w" id="mwBB0"> </span><span class="p" id="mwBB4">(</span><span class="nb" id="mwBB8">setf</span><span class="w" id="mwBCA"> </span><span class="nv" id="mwBCE">digits</span><span class="w" id="mwBCI"> </span><span class="p" id="mwBCM">(</span><span class="nb" id="mwBCQ">concatenate</span><span class="w" id="mwBCU"> </span><span class="ss" id="mwBCY">'string</span><span class="w" id="mwBCc"> </span><span class="p" id="mwBCg">(</span><span class="nb" id="mwBCk">write-to-string</span><span class="w" id="mwBCo"> </span><span class="nb" id="mwBCs">rem</span><span class="p" id="mwBCw">)</span><span class="w" id="mwBC0"> </span><span class="nv" id="mwBC4">digits</span><span class="p" id="mwBC8">))))</span> <span class="w" id="mwBDA"> </span><span class="nv" id="mwBDE">digits</span><span class="p" id="mwBDI">)))</span>

To any negative base

Java

<span id="mwBDc"></span><span class="kn" id="mwBDg">import</span><span class="w" id="mwBDk"> </span><span class="nn" id="mwBDo">java.util.ArrayList</span><span class="p" id="mwBDs">;</span> <span class="kn" id="mwBDw">import</span><span class="w" id="mwBD0"> </span><span class="nn" id="mwBD4">java.util.Collections</span><span class="p" id="mwBD8">;</span> <span class="kd" id="mwBEA">public</span><span class="w" id="mwBEE"> </span><span class="n" id="mwBEI">ArrayList</span><span class="o" id="mwBEM"><</span><span class="n" id="mwBEQ">Integer</span><span class="o" id="mwBEU">></span><span class="w" id="mwBEY"> </span><span class="nf" id="mwBEc">negativeBase</span><span class="p" id="mwBEg">(</span><span class="kt" id="mwBEk">int</span><span class="w" id="mwBEo"> </span><span class="n" id="mwBEs">input</span><span class="p" id="mwBEw">,</span><span class="w" id="mwBE0"> </span><span class="kt" id="mwBE4">int</span><span class="w" id="mwBE8"> </span><span class="n" id="mwBFA">base</span><span class="p" id="mwBFE">)</span><span class="w" id="mwBFI"> </span><span class="p" id="mwBFM">{</span> <span class="w" id="mwBFQ"> </span><span class="n" id="mwBFU">ArrayList</span><span class="o" id="mwBFY"><</span><span class="n" id="mwBFc">Integer</span><span class="o" id="mwBFg">></span><span class="w" id="mwBFk"> </span><span class="n" id="mwBFo">result_rev</span><span class="w" id="mwBFs"> </span><span class="o" id="mwBFw">=</span><span class="w" id="mwBF0"> </span><span class="k" id="mwBF4">new</span><span class="w" id="mwBF8"> </span><span class="n" id="mwBGA">ArrayList</span><span class="o" id="mwBGE"><></span><span class="p" id="mwBGI">();</span> <span class="w" id="mwBGM"> </span><span class="kt" id="mwBGQ">int</span><span class="w" id="mwBGU"> </span><span class="n" id="mwBGY">number</span><span class="w" id="mwBGc"> </span><span class="o" id="mwBGg">=</span><span class="w" id="mwBGk"> </span><span class="n" id="mwBGo">input</span><span class="p" id="mwBGs">;</span> <span class="w" id="mwBGw"> </span><span class="k" id="mwBG0">while</span><span class="w" id="mwBG4"> </span><span class="p" id="mwBG8">(</span><span class="n" id="mwBHA">number</span><span class="w" id="mwBHE"> </span><span class="o" id="mwBHI">!=</span><span class="w" id="mwBHM"> </span><span class="mi" id="mwBHQ">0</span><span class="p" id="mwBHU">)</span><span class="w" id="mwBHY"> </span><span class="p" id="mwBHc">{</span> <span class="w" id="mwBHg"> </span><span class="kt" id="mwBHk">int</span><span class="w" id="mwBHo"> </span><span class="n" id="mwBHs">i</span><span class="w" id="mwBHw"> </span><span class="o" id="mwBH0">=</span><span class="w" id="mwBH4"> </span><span class="n" id="mwBH8">number</span><span class="w" id="mwBIA"> </span><span class="o" id="mwBIE">%</span><span class="w" id="mwBII"> </span><span class="n" id="mwBIM">base</span><span class="p" id="mwBIQ">;</span> <span class="w" id="mwBIU"> </span><span class="n" id="mwBIY">number</span><span class="w" id="mwBIc"> </span><span class="o" id="mwBIg">/=</span><span class="w" id="mwBIk"> </span><span class="n" id="mwBIo">base</span><span class="p" id="mwBIs">;</span> <span class="w" id="mwBIw"> </span><span class="k" id="mwBI0">if</span><span class="w" id="mwBI4"> </span><span class="p" id="mwBI8">(</span><span class="n" id="mwBJA">i</span><span class="w" id="mwBJE"> </span><span class="o" id="mwBJI"><</span><span class="w" id="mwBJM"> </span><span class="mi" id="mwBJQ">0</span><span class="p" id="mwBJU">)</span><span class="w" id="mwBJY"> </span><span class="p" id="mwBJc">{</span> <span class="w" id="mwBJg"> </span><span class="n" id="mwBJk">i</span><span class="w" id="mwBJo"> </span><span class="o" id="mwBJs">+=</span><span class="w" id="mwBJw"> </span><span class="n" id="mwBJ0">Math</span><span class="p" id="mwBJ4">.</span><span class="na" id="mwBJ8">abs</span><span class="p" id="mwBKA">(</span><span class="n" id="mwBKE">base</span><span class="p" id="mwBKI">);</span> <span class="w" id="mwBKM"> </span><span class="n" id="mwBKQ">number</span><span class="o" id="mwBKU">++</span><span class="p" id="mwBKY">;</span> <span class="w" id="mwBKc"> </span><span class="p" id="mwBKg">}</span> <span class="w" id="mwBKk"> </span><span class="n" id="mwBKo">result_rev</span><span class="p" id="mwBKs">.</span><span class="na" id="mwBKw">add</span><span class="p" id="mwBK0">(</span><span class="n" id="mwBK4">i</span><span class="p" id="mwBK8">);</span> <span class="w" id="mwBLA"> </span><span class="p" id="mwBLE">}</span> <span class="w" id="mwBLI"> </span><span class="k" id="mwBLM">return</span><span class="w" id="mwBLQ"> </span><span class="n" id="mwBLU">Collections</span><span class="p" id="mwBLY">.</span><span class="na" id="mwBLc">reverse</span><span class="p" id="mwBLg">(</span><span class="n" id="mwBLk">results_rev</span><span class="p" id="mwBLo">.</span><span class="na" id="mwBLs">clone</span><span class="p" id="mwBLw">());</span> <span class="p" id="mwBL0">}</span>

The above gives the result in an ArrayList of integers, so that the code does not have to handle how to represent a base smaller than -10. To display the result as a string, one can decide on a mapping of base to characrters. For example:

<span id="mwBME"></span><span class="kn" id="mwBMI">import</span><span class="w" id="mwBMM"> </span><span class="nn" id="mwBMQ">java.util.stream.Collectors</span><span class="p" id="mwBMU">;</span> <span class="kd" id="mwBMY">final</span><span class="w" id="mwBMc"> </span><span class="n" id="mwBMg">String</span><span class="w" id="mwBMk"> </span><span class="n" id="mwBMo">alphabet</span><span class="w" id="mwBMs"> </span><span class="o" id="mwBMw">=</span><span class="w" id="mwBM0"> </span><span class="s" id="mwBM4">"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ@_"</span><span class="p" id="mwBM8">;</span> <span class="kd" id="mwBNA">public</span><span class="w" id="mwBNE"> </span><span class="n" id="mwBNI">String</span><span class="w" id="mwBNM"> </span><span class="nf" id="mwBNQ">toBaseString</span><span class="p" id="mwBNU">(</span><span class="n" id="mwBNY">ArrayList</span><span class="o" id="mwBNc"><</span><span class="n" id="mwBNg">Integer</span><span class="o" id="mwBNk">></span><span class="w" id="mwBNo"> </span><span class="n" id="mwBNs">lst</span><span class="p" id="mwBNw">)</span><span class="w" id="mwBN0"> </span><span class="p" id="mwBN4">{</span> <span class="w" id="mwBN8"> </span><span class="c1" id="mwBOA">// Would throw exception if base is beyond the 64 possible characters</span> <span class="w" id="mwBOE"> </span><span class="k" id="mwBOI">return</span><span class="w" id="mwBOM"> </span><span class="n" id="mwBOQ">lst</span><span class="p" id="mwBOU">.</span><span class="na" id="mwBOY">stream</span><span class="p" id="mwBOc">().</span><span class="na" id="mwBOg">map</span><span class="p" id="mwBOk">(</span><span class="n" id="mwBOo">n</span><span class="w" id="mwBOs"> </span><span class="o" id="mwBOw">-></span><span class="w" id="mwBO0"> </span><span class="n" id="mwBO4">alphabet</span><span class="o" id="mwBO8">[</span><span class="n" id="mwBPA">n</span><span class="o" id="mwBPE">]</span><span class="p" id="mwBPI">).</span><span class="na" id="mwBPM">collect</span><span class="p" id="mwBPQ">(</span><span class="n" id="mwBPU">Collectors</span><span class="p" id="mwBPY">.</span><span class="na" id="mwBPc">joining</span><span class="p" id="mwBPg">(</span><span class="s" id="mwBPk">""</span><span class="p" id="mwBPo">));</span> <span class="p" id="mwBPs">}</span>

AutoLisp

<span id="mwBP8"></span><span class="p" id="mwBQA">(</span><span class="nb" id="mwBQE">defun</span><span class="w" id="mwBQI"> </span><span class="nv" id="mwBQM">negabase</span><span class="w" id="mwBQQ"> </span><span class="p" id="mwBQU">(</span><span class="nv" id="mwBQY">num</span><span class="w" id="mwBQc"> </span><span class="nv" id="mwBQg">baz</span><span class="w" id="mwBQk"> </span><span class="nb" id="mwBQo">/</span><span class="w" id="mwBQs"> </span><span class="nv" id="mwBQw">dig</span><span class="w" id="mwBQ0"> </span><span class="nv" id="mwBQ4">rst</span><span class="p" id="mwBQ8">)</span> <span class="w" id="mwBRA"> </span><span class="c1" id="mwBRE">;; NUM is any number.</span> <span class="w" id="mwBRI"> </span><span class="c1" id="mwBRM">;; BAZ is any number in the interval [-10, -2]. (This is forced by how we do string notation.)</span> <span class="w" id="mwBRQ"> </span><span class="c1" id="mwBRU">;;</span> <span class="w" id="mwBRY"> </span><span class="c1" id="mwBRc">;; NUM and BAZ will be truncated to an integer if they're floats (e.g. 14.25</span> <span class="w" id="mwBRg"> </span><span class="c1" id="mwBRk">;; will be truncated to 14, -123456789.87 to -123456789, etc.).</span> <span class="w" id="mwBRo"> </span><span class="p" id="mwBRs">(</span><span class="k" id="mwBRw">if</span><span class="w" id="mwBR0"> </span><span class="p" id="mwBR4">(</span><span class="nb" id="mwBR8">and</span><span class="w" id="mwBSA"> </span><span class="p" id="mwBSE">(</span><span class="nb" id="mwBSI">numberp</span><span class="w" id="mwBSM"> </span><span class="nv" id="mwBSQ">num</span><span class="p" id="mwBSU">)</span> <span class="w" id="mwBSY"> </span><span class="p" id="mwBSc">(</span><span class="nb" id="mwBSg">numberp</span><span class="w" id="mwBSk"> </span><span class="nv" id="mwBSo">baz</span><span class="p" id="mwBSs">)</span> <span class="w" id="mwBSw"> </span><span class="p" id="mwBS0">(</span><span class="nb" id="mwBS4"><=</span><span class="w" id="mwBS8"> </span><span class="p" id="mwBTA">(</span><span class="nv" id="mwBTE">fix</span><span class="w" id="mwBTI"> </span><span class="nv" id="mwBTM">baz</span><span class="p" id="mwBTQ">)</span><span class="w" id="mwBTU"> </span><span class="mi" id="mwBTY">-2</span><span class="p" id="mwBTc">)</span> <span class="w" id="mwBTg"> </span><span class="p" id="mwBTk">(</span><span class="nb" id="mwBTo">></span><span class="w" id="mwBTs"> </span><span class="p" id="mwBTw">(</span><span class="nv" id="mwBT0">fix</span><span class="w" id="mwBT4"> </span><span class="nv" id="mwBT8">baz</span><span class="p" id="mwBUA">)</span><span class="w" id="mwBUE"> </span><span class="mi" id="mwBUI">-11</span><span class="p" id="mwBUM">))</span> <span class="w" id="mwBUQ"> </span><span class="p" id="mwBUU">(</span><span class="k" id="mwBUY">progn</span> <span class="w" id="mwBUc"> </span><span class="p" id="mwBUg">(</span><span class="k" id="mwBUk">setq</span><span class="w" id="mwBUo"> </span><span class="nv" id="mwBUs">baz</span><span class="w" id="mwBUw"> </span><span class="p" id="mwBU0">(</span><span class="nb" id="mwBU4">float</span><span class="w" id="mwBU8"> </span><span class="p" id="mwBVA">(</span><span class="nv" id="mwBVE">fix</span><span class="w" id="mwBVI"> </span><span class="nv" id="mwBVM">baz</span><span class="p" id="mwBVQ">))</span> <span class="w" id="mwBVU"> </span><span class="nv" id="mwBVY">num</span><span class="w" id="mwBVc"> </span><span class="p" id="mwBVg">(</span><span class="nb" id="mwBVk">float</span><span class="w" id="mwBVo"> </span><span class="p" id="mwBVs">(</span><span class="nv" id="mwBVw">fix</span><span class="w" id="mwBV0"> </span><span class="nv" id="mwBV4">num</span><span class="p" id="mwBV8">))</span> <span class="w" id="mwBWA"> </span><span class="nv" id="mwBWE">dig</span><span class="w" id="mwBWI"> </span><span class="p" id="mwBWM">(</span><span class="k" id="mwBWQ">if</span><span class="w" id="mwBWU"> </span><span class="p" id="mwBWY">(</span><span class="nb" id="mwBWc">=</span><span class="w" id="mwBWg"> </span><span class="nv" id="mwBWk">num</span><span class="w" id="mwBWo"> </span><span class="mi" id="mwBWs">0</span><span class="p" id="mwBWw">)</span><span class="w" id="mwBW0"> </span><span class="s" id="mwBW4">"0"</span><span class="w" id="mwBW8"> </span><span class="s" id="mwBXA">""</span><span class="p" id="mwBXE">))</span> <span class="w" id="mwBXI"> </span><span class="p" id="mwBXM">(</span><span class="nv" id="mwBXQ">while</span><span class="w" id="mwBXU"> </span><span class="p" id="mwBXY">(</span><span class="nb" id="mwBXc">/=</span><span class="w" id="mwBXg"> </span><span class="nv" id="mwBXk">num</span><span class="w" id="mwBXo"> </span><span class="mi" id="mwBXs">0</span><span class="p" id="mwBXw">)</span> <span class="w" id="mwBX0"> </span><span class="p" id="mwBX4">(</span><span class="k" id="mwBX8">setq</span><span class="w" id="mwBYA"> </span><span class="nv" id="mwBYE">rst</span><span class="w" id="mwBYI"> </span><span class="p" id="mwBYM">(</span><span class="nb" id="mwBYQ">-</span><span class="w" id="mwBYU"> </span><span class="nv" id="mwBYY">num</span><span class="w" id="mwBYc"> </span><span class="p" id="mwBYg">(</span><span class="nb" id="mwBYk">*</span><span class="w" id="mwBYo"> </span><span class="nv" id="mwBYs">baz</span><span class="w" id="mwBYw"> </span><span class="p" id="mwBY0">(</span><span class="k" id="mwBY4">setq</span><span class="w" id="mwBY8"> </span><span class="nv" id="mwBZA">num</span><span class="w" id="mwBZE"> </span><span class="p" id="mwBZI">(</span><span class="nv" id="mwBZM">fix</span><span class="w" id="mwBZQ"> </span><span class="p" id="mwBZU">(</span><span class="nb" id="mwBZY">/</span><span class="w" id="mwBZc"> </span><span class="nv" id="mwBZg">num</span><span class="w" id="mwBZk"> </span><span class="nv" id="mwBZo">baz</span><span class="p" id="mwBZs">))))))</span> <span class="w" id="mwBZw"> </span><span class="p" id="mwBZ0">(</span><span class="k" id="mwBZ4">if</span><span class="w" id="mwBZ8"> </span><span class="p" id="mwBaA">(</span><span class="nb" id="mwBaE">minusp</span><span class="w" id="mwBaI"> </span><span class="nv" id="mwBaM">rst</span><span class="p" id="mwBaQ">)</span> <span class="w" id="mwBaU"> </span><span class="p" id="mwBaY">(</span><span class="k" id="mwBac">setq</span><span class="w" id="mwBag"> </span><span class="nv" id="mwBak">num</span><span class="w" id="mwBao"> </span><span class="p" id="mwBas">(</span><span class="nb" id="mwBaw">1+</span><span class="w" id="mwBa0"> </span><span class="nv" id="mwBa4">num</span><span class="p" id="mwBa8">)</span> <span class="w" id="mwBbA"> </span><span class="nv" id="mwBbE">rst</span><span class="w" id="mwBbI"> </span><span class="p" id="mwBbM">(</span><span class="nb" id="mwBbQ">-</span><span class="w" id="mwBbU"> </span><span class="nv" id="mwBbY">rst</span><span class="w" id="mwBbc"> </span><span class="nv" id="mwBbg">baz</span><span class="p" id="mwBbk">)))</span> <span class="w" id="mwBbo"> </span><span class="p" id="mwBbs">(</span><span class="k" id="mwBbw">setq</span><span class="w" id="mwBb0"> </span><span class="nv" id="mwBb4">dig</span><span class="w" id="mwBb8"> </span><span class="p" id="mwBcA">(</span><span class="nv" id="mwBcE">strcat</span><span class="w" id="mwBcI"> </span><span class="p" id="mwBcM">(</span><span class="nv" id="mwBcQ">itoa</span><span class="w" id="mwBcU"> </span><span class="p" id="mwBcY">(</span><span class="nv" id="mwBcc">fix</span><span class="w" id="mwBcg"> </span><span class="nv" id="mwBck">rst</span><span class="p" id="mwBco">))</span><span class="w" id="mwBcs"> </span><span class="nv" id="mwBcw">dig</span><span class="p" id="mwBc0">)))</span> <span class="w" id="mwBc4"> </span><span class="nv" id="mwBc8">dig</span><span class="p" id="mwBdA">)</span> <span class="w" id="mwBdE"> </span><span class="p" id="mwBdI">(</span><span class="k" id="mwBdM">progn</span> <span class="w" id="mwBdQ"> </span><span class="p" id="mwBdU">(</span><span class="nv" id="mwBdY">prompt</span> <span class="w" id="mwBdc"> </span><span class="p" id="mwBdg">(</span><span class="nb" id="mwBdk">cond</span> <span class="w" id="mwBdo"> </span><span class="p" id="mwBds">((</span><span class="nb" id="mwBdw">and</span><span class="w" id="mwBd0"> </span><span class="p" id="mwBd4">(</span><span class="nb" id="mwBd8">not</span><span class="w" id="mwBeA"> </span><span class="p" id="mwBeE">(</span><span class="nb" id="mwBeI">numberp</span><span class="w" id="mwBeM"> </span><span class="nv" id="mwBeQ">num</span><span class="p" id="mwBeU">))</span> <span class="w" id="mwBeY"> </span><span class="p" id="mwBec">(</span><span class="nb" id="mwBeg">not</span><span class="w" id="mwBek"> </span><span class="p" id="mwBeo">(</span><span class="nb" id="mwBes">numberp</span><span class="w" id="mwBew"> </span><span class="nv" id="mwBe0">baz</span><span class="p" id="mwBe4">)))</span> <span class="w" id="mwBe8"> </span><span class="s" id="mwBfA">"\nWrong number and negabase."</span><span class="p" id="mwBfE">)</span> <span class="w" id="mwBfI"> </span><span class="p" id="mwBfM">((</span><span class="nb" id="mwBfQ">not</span><span class="w" id="mwBfU"> </span><span class="p" id="mwBfY">(</span><span class="nb" id="mwBfc">numberp</span><span class="w" id="mwBfg"> </span><span class="nv" id="mwBfk">num</span><span class="p" id="mwBfo">))</span> <span class="w" id="mwBfs"> </span><span class="s" id="mwBfw">"\nWrong number."</span><span class="p" id="mwBf0">)</span> <span class="w" id="mwBf4"> </span><span class="p" id="mwBf8">((</span><span class="nb" id="mwBgA">not</span><span class="w" id="mwBgE"> </span><span class="p" id="mwBgI">(</span><span class="nb" id="mwBgM">numberp</span><span class="w" id="mwBgQ"> </span><span class="nv" id="mwBgU">baz</span><span class="p" id="mwBgY">))</span> <span class="w" id="mwBgc"> </span><span class="s" id="mwBgg">"\nWrong negabase."</span><span class="p" id="mwBgk">)</span> <span class="w" id="mwBgo"> </span><span class="p" id="mwBgs">(</span><span class="no" id="mwBgw">t</span> <span class="w" id="mwBg0"> </span><span class="s" id="mwBg4">"\nNegabase must be inside [-10 -2] interval."</span><span class="p" id="mwBg8">)))</span> <span class="w" id="mwBhA"> </span><span class="p" id="mwBhE">(</span><span class="nb" id="mwBhI">princ</span><span class="p" id="mwBhM">))))</span>

Shortcut calculation

The following algorithms assume that

1. the input is available in bitstrings and coded in (base +2; digits in ${\displaystyle \{0,1\}}$) (as in most of today's digital computers),
2. there are add (+) and xor (^) operations which operate on such bitstrings (as in most of today's digital computers),
3. the set ${\displaystyle D}$ of output digits is standard, i. e. ${\displaystyle D=\{0,|b|-1\}}$ with base ${\displaystyle b\in \{-2,-4\}}$,
4. the output is coded in the same bitstring format, but the meaning of the places is another one.

To negabinary

The conversion to negabinary (base −2; digits in ${\displaystyle \{0,1\}}$) allows a remarkable shortcut (C implementation):

<span id="mwBic"></span><span class="kt" id="mwBig">uint32_t</span><span class="w" id="mwBik"> </span><span class="nf" id="mwBio">toNegaBinary</span><span class="p" id="mwBis">(</span><span class="kt" id="mwBiw">uint32_t</span><span class="w" id="mwBi0"> </span><span class="n" id="mwBi4">value</span><span class="p" id="mwBi8">)</span><span class="w" id="mwBjA"> </span><span class="c1" id="mwBjE">// input in standard binary</span> <span class="p" id="mwBjI">{</span> <span class="w" id="mwBjM"> </span><span class="kt" id="mwBjQ">uint32_t</span><span class="w" id="mwBjU"> </span><span class="n" id="mwBjY">Schroeppel2</span><span class="w" id="mwBjc"> </span><span class="o" id="mwBjg">=</span><span class="w" id="mwBjk"> </span><span class="mh" id="mwBjo">0xAAAAAAAA</span><span class="p" id="mwBjs">;</span><span class="w" id="mwBjw"> </span><span class="c1" id="mwBj0">// = 2/3*((2*2)^16-1) = ...1010</span> <span class="w" id="mwBj4"> </span><span class="k" id="mwBj8">return</span><span class="w" id="mwBkA"> </span><span class="p" id="mwBkE">(</span><span class="n" id="mwBkI">value</span><span class="w" id="mwBkM"> </span><span class="o" id="mwBkQ">+</span><span class="w" id="mwBkU"> </span><span class="n" id="mwBkY">Schroeppel2</span><span class="p" id="mwBkc">)</span><span class="w" id="mwBkg"> </span><span class="o" id="mwBkk">^</span><span class="w" id="mwBko"> </span><span class="n" id="mwBks">Schroeppel2</span><span class="p" id="mwBkw">;</span><span class="w" id="mwBk0"> </span><span class="c1" id="mwBk4">// eXclusive OR</span> <span class="w" id="mwBk8"> </span><span class="c1" id="mwBlA">// resulting unsigned int to be interpreted as string of elements ε {0,1} (bits)</span> <span class="p" id="mwBlE">}</span>

JavaScript port for the same shortcut calculation:

<span id="mwBlU"></span><span class="kd" id="mwBlY">function</span><span class="w" id="mwBlc"> </span><span class="nx" id="mwBlg">toNegaBinary</span><span class="p" id="mwBlk">(</span><span class="nx" id="mwBlo">value</span><span class="p" id="mwBls">)</span><span class="w" id="mwBlw"> </span><span class="p" id="mwBl0">{</span> <span class="w" id="mwBl4"> </span><span class="kd" id="mwBl8">const</span><span class="w" id="mwBmA"> </span><span class="nx" id="mwBmE">Schroeppel2</span><span class="w" id="mwBmI"> </span><span class="o" id="mwBmM">=</span><span class="w" id="mwBmQ"> </span><span class="mh" id="mwBmU">0xAAAAAAAA</span><span class="p" id="mwBmY">;</span> <span class="w" id="mwBmc"> </span><span class="c1" id="mwBmg">// Convert as in C, then convert to a NegaBinary String</span> <span class="w" id="mwBmk"> </span><span class="k" id="mwBmo">return</span><span class="w" id="mwBms"> </span><span class="p" id="mwBmw">(</span><span class="w" id="mwBm0"> </span><span class="p" id="mwBm4">(</span><span class="w" id="mwBm8"> </span><span class="nx" id="mwBnA">value</span><span class="w" id="mwBnE"> </span><span class="o" id="mwBnI">+</span><span class="w" id="mwBnM"> </span><span class="nx" id="mwBnQ">Schroeppel2</span><span class="w" id="mwBnU"> </span><span class="p" id="mwBnY">)</span><span class="w" id="mwBnc"> </span><span class="o" id="mwBng">^</span><span class="w" id="mwBnk"> </span><span class="nx" id="mwBno">Schroeppel2</span><span class="w" id="mwBns"> </span><span class="p" id="mwBnw">).</span><span class="nx" id="mwBn0">toString</span><span class="p" id="mwBn4">(</span><span class="mf" id="mwBn8">2</span><span class="p" id="mwBoA">);</span> <span class="p" id="mwBoE">}</span>

The algorithm is first described by Schroeppel in the HAKMEM (1972) as item 128. The Wolfram MathWorld documents a version in the Wolfram Language by D. Librik (Szudzik).

To negaquaternary

The conversion to negaquaternary (base −4; digits in ${\displaystyle \{0,1,2,3\}}$) allows a similar shortcut (C implementation):

<span id="mwBo4"></span><span class="kt" id="mwBo8">uint32_t</span><span class="w" id="mwBpA"> </span><span class="nf" id="mwBpE">toNegaQuaternary</span><span class="p" id="mwBpI">(</span><span class="kt" id="mwBpM">uint32_t</span><span class="w" id="mwBpQ"> </span><span class="n" id="mwBpU">value</span><span class="p" id="mwBpY">)</span><span class="w" id="mwBpc"> </span><span class="c1" id="mwBpg">// input in standard binary</span> <span class="p" id="mwBpk">{</span> <span class="w" id="mwBpo"> </span><span class="kt" id="mwBps">uint32_t</span><span class="w" id="mwBpw"> </span><span class="n" id="mwBp0">Schroeppel4</span><span class="w" id="mwBp4"> </span><span class="o" id="mwBp8">=</span><span class="w" id="mwBqA"> </span><span class="mh" id="mwBqE">0xCCCCCCCC</span><span class="p" id="mwBqI">;</span><span class="w" id="mwBqM"> </span><span class="c1" id="mwBqQ">// = 4/5*((2*4)^8-1) = ...11001100 = ...3030</span> <span class="w" id="mwBqU"> </span><span class="k" id="mwBqY">return</span><span class="w" id="mwBqc"> </span><span class="p" id="mwBqg">(</span><span class="n" id="mwBqk">value</span><span class="w" id="mwBqo"> </span><span class="o" id="mwBqs">+</span><span class="w" id="mwBqw"> </span><span class="n" id="mwBq0">Schroeppel4</span><span class="p" id="mwBq4">)</span><span class="w" id="mwBq8"> </span><span class="o" id="mwBrA">^</span><span class="w" id="mwBrE"> </span><span class="n" id="mwBrI">Schroeppel4</span><span class="p" id="mwBrM">;</span><span class="w" id="mwBrQ"> </span><span class="c1" id="mwBrU">// eXclusive OR</span> <span class="w" id="mwBrY"> </span><span class="c1" id="mwBrc">// resulting unsigned int to be interpreted as string of elements ε {0,1,2,3} (pairs of bits)</span> <span class="p" id="mwBrg">}</span>

JavaScript port for the same shortcut calculation:

<span id="mwBrw"></span><span class="kd" id="mwBr0">function</span><span class="w" id="mwBr4"> </span><span class="nx" id="mwBr8">toNegaQuaternary</span><span class="p" id="mwBsA">(</span><span class="nx" id="mwBsE">value</span><span class="p" id="mwBsI">)</span><span class="w" id="mwBsM"> </span><span class="p" id="mwBsQ">{</span> <span class="w" id="mwBsU"> </span><span class="kd" id="mwBsY">const</span><span class="w" id="mwBsc"> </span><span class="nx" id="mwBsg">Schroeppel4</span><span class="w" id="mwBsk"> </span><span class="o" id="mwBso">=</span><span class="w" id="mwBss"> </span><span class="mh" id="mwBsw">0xCCCCCCCC</span><span class="p" id="mwBs0">;</span> <span class="w" id="mwBs4"> </span><span class="c1" id="mwBs8">// Convert as in C, then convert to NegaQuaternary String</span> <span class="w" id="mwBtA"> </span><span class="k" id="mwBtE">return</span><span class="w" id="mwBtI"> </span><span class="p" id="mwBtM">(</span><span class="w" id="mwBtQ"> </span><span class="p" id="mwBtU">(</span><span class="w" id="mwBtY"> </span><span class="nx" id="mwBtc">value</span><span class="w" id="mwBtg"> </span><span class="o" id="mwBtk">+</span><span class="w" id="mwBto"> </span><span class="nx" id="mwBts">Schroeppel4</span><span class="w" id="mwBtw"> </span><span class="p" id="mwBt0">)</span><span class="w" id="mwBt4"> </span><span class="o" id="mwBt8">^</span><span class="w" id="mwBuA"> </span><span class="nx" id="mwBuE">Schroeppel4</span><span class="w" id="mwBuI"> </span><span class="p" id="mwBuM">).</span><span class="nx" id="mwBuQ">toString</span><span class="p" id="mwBuU">(</span><span class="mf" id="mwBuY">4</span><span class="p" id="mwBuc">);</span> <span class="p" id="mwBug">}</span>

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:

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₋₂ (1 + 4 + 16 + 64 = 85) and 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

so the result is 110011001₋₂ (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 1 0 1 0 0 0 Carry: 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:

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

${\displaystyle c_{i+1}^{-}=a_i{b}_i\overline{c_i^{-}}+(a_i\oplus b_i)c_i^{+}\overline{c_i^{-}}}$

Incrementing negabinary numbers

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

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

(The operations in this formula are to be interpreted as operations on regular binary numbers. For example, ${\displaystyle 2x}$ is a binary left shift by one bit.)

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₋₂ (1 − 8 − 32 + 64 = 25) minus 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

so the result is 100101₋₂ (1 + 4 −32 = −27).

Unary negation, −x, can be computed as binary subtraction from zero, 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 ${\displaystyle A}$ and ${\displaystyle B}$, invert each odd positioned bit of both numbers. After this, compare ${\displaystyle A}$ and ${\displaystyle B}$ using a standard unsigned comparator.

Fractional numbers

Base −r representation may of course be carried beyond the radix point, allowing the representation of non-integer 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 ${\displaystyle \mathbf{t}:=r-1=-b-1}$ the biggest digit and

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

we have

${\displaystyle 0.{\overline{0\mathbf{t}}}_b=\mathbf{t}T=\frac{r-1}{r^2-1}=\frac{1}{r+1}}$ as well as

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

So every number ${\displaystyle \frac{1}{r+1}+z}$ with a terminating fraction ${\displaystyle z\in \mathbb{Z}{r}^{\mathbb{Z}}}$ added has two distinct representations.

For example, in negaternary, i.e. ${\displaystyle b=-3}$ and ${\displaystyle \mathbf{t}=2}$, there is

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

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

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

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

Imaginary base

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.