Negative bases

Mat · December 18, 2011

Here's a fun little bit of theory for you I wouldn't usually ask this sort of stuff, I'd spend days trying to figure it out myself, but I think other people are going to like this one.

123.456 in base -10 should be: 284.664

Why? Well, if you apply the rules for normal numeric bases, it is possible:

2 * (-10)^2 = 200

8 * (-10)^1 = -80

4 * (-10)^0 = 4

6 * (-10)^-1 = -0.6

6 * (-10)^-2 = 0.06

4 * (-10)^-3 = -0.004

The sum of all of those is 123.456, so it works *in theory*.

Has anyone got any idea how that would look as a computer program? Obviously the traditional method is not going to work. I've been racking my brains to try and describe the method of doing it by hand as a program but it made me realise I was using trial and error a lot of the time.

I suppose a related problem is log_-b(a), as it should be complex, but ceiling(log) is also supposed to be the number of digits needed to display the number.

For those interested, here is my version for positive bases (greater than 2). Ideally I need a simple modification to support negatives. Not going to happen though.

#include <stdio.h>
#include <stdlib.h>

char* tobase( int, int );
unsigned int ilog2( unsigned int );

int main( int argc, char* argv[] )
{
    int ret;
    int n;
    int base;
    char* t;

    if ( argc != 3 )
    {
        puts( "Usage: tobase NUMBER BASE" );
        ret = 1;
    }
    else
    {
        n = atoi( argv[1] );
        base = atoi( argv[2] );

        t = tobase( n, base );

        if ( t == NULL )
        {
            ret = 2;
            puts( "Error." );
        }
        else
        {
            puts( t );
            free( t );
            ret = 0;
        }
    }

    return ret;
}

char* tobase( int i, int base )
{
    const char symbols[] =
        "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";

    char* ret;
    int lbn;
    int neg;
    int c;

    if ( ( base < 2 ) || ( base > 64 ) )
    {
        ret = NULL;
    }
    else
    {
        if ( i < 0 )
        {
            neg = 1;
            i = -i;
        }
        else
        {
            neg = 0;
        }

        lbn = ilog2( i ) / ilog2( base ) + 1;

        c = lbn + neg;
        ret = ( char* )malloc( ( c + 1 ) * sizeof( char ) );
        ret[c--] = '\0';

        if ( neg )
        {
            ret[0] = '-';
        }

        do
        {
            ret[c--] = symbols[i % base];
            i /= base;
        }
        while ( i );
    }

    return ret;
}

unsigned int ilog2( unsigned int i )
{
    unsigned int ret;

    ret = 0;

    if ( i > 0xFFFF )
    {
        ret = 16;
        i >>= 16;
    }

    if ( i > 0xFF )
    {
        i >>= 8;
        ret |= 8;
    }

    if ( i > 0xF )
    {
        i >>= 4;
        ret |= 4;
    }

    if ( i > 0x3 )
    {
        i >>= 2;
        ret |= 2;
    }

    ret |= ( i >> 1 );

    return ret;
}

jaberwacky · December 18, 2011

Please excuse my dear Aunt Sally.

2 * -10 ^ 2 = X

-10 ^ 2 = 100

2 * 100 = 200

x = 200

Nevermind, you knew that already. I thought you were wanting to multiply (2 * -10) and then raise.

Edited December 18, 2011 by LaCastiglione

jaberwacky · December 18, 2011

Is this the naive method?

Global Const $arr1[6] = [2, 8, 4, 6, 6, 4]

Global $total = 0
Global $j = 0

For $i = 2 To -3 Step -1
    $total += $arr1[$j] * (-10 ^ $i)
    $j += 1
Next

ConsoleWrite($total & @CRLF)

Mat · December 19, 2011

Yes... But that's going the other way and as you said is very naive.

czardas · December 19, 2011

Hahaha; and I thought the things I try out were crazy. You have created a non-contingeous numeric system.

Mat · December 19, 2011

It's very weird counting in negative bases.... Goes up in length by two digits rather than 1. There is definitely a pattern though, it's just difficult to describe.

10  |    -2    | -10  |
-----+----------+------+
 1   |  1       |  1   |
 2   |  110     |  2   |
 3   |  111     |  3   |
 4   |  100     |  4   |
 5   |  101     |  5   |
 6   |  11010   |  6   |
 7   |  11011   |  7   |
 8   |  11000   |  8   |
 9   |  11001   |  9   |
 10  |  11110   |  190 |
 11  |  11111   |  191 |
 12  |  11100   |  192 |
 13  |  11101   |  193 |
 14  |  10010   |  194 |
 15  |  10011   |  195 |
 16  |  10000   |  196 |
 17  |  10001   |  197 |
 18  |  10110   |  198 |
 19  |  10111   |  199 |
 20  |  10100   |  180 |
 21  |  10101   |  181 |
 22  |  1101010 |  182 |
 ... |    ...   |  ... |

I'd like to see addition using these Possibly an interesting way to encrypt data:

132 101 108 108 291 164 172 127 291 294 108 100 173

jaberwacky · December 19, 2011

Oh crap, I just noticed that the -2 column is backwards binary!

Oh wait, no it isn't. LOL!

Edited December 19, 2011 by LaCastiglione

MvGulik · December 19, 2011

??? ...

Yes, there are negative bases. They aren't used much, but they are
quite interesting. They allow you to represent both positive and
negative numbers with only positive digits. For example, if the base
is -2, then you have the following equalities:
Base 10 Base -2
-11 110101
-10 1010
-9 1011
-8 1000
-7 1001
-6 1110
-5 1111
-4 1100
-3 1101
-2 10
-1 11
0 0
1 1
2 110
3 111
4 100
5 101
6 11010
7 11011
8 11000
9 11001
10 11110
11 11111
12 11100
13 11101
14 10010
15 10011
16 10000

( http://mathforum.org/library/drmath/view/55710.html )

Aha, Making a little more sense.

Mat · December 19, 2011

Ah. So they do have a use thanks for that.

Richard Robertson · December 19, 2011

A use, yes, but how practical is that? Shouldn't negatives be clearly distinguishable from their positive counterpart?

Mat · December 19, 2011

Perhaps it's not practical. But it's possible. I'm not interested in this for a specific practical use.

Mat · December 19, 2011

Should've looked at Wikipedia

http://en.wikipedia.org/wiki/Negative_base#Calculation

Edit: Grrr... Why must python's modulo and division be so different from C?

Edit: This is hard. How do you find the number of digits for a number in a negative base?

Edited December 19, 2011 by Mat

Mat · December 19, 2011

It's late. That was the hardest thing I think I've ever tried to code. Was it worth it? Hell yeah.

Base converter up to base +-64 using only integer arithmetic, and it calculates the buffer size first. Bases greater than ip-like form should be a piece of cake. Negative bases less than -64? F***.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* tobase( int, int );
unsigned int ilog2( unsigned int );
int py_div( int, int );
int py_mod( int, int );

int main( int argc, char* argv[] )
{
    int ret;
    int n;
    int base;
    char* t;

    if ( argc != 3 )
    {
        puts( "Usage: tobase NUMBER BASE" );
        ret = 1;
    }
    else
    {
        n = atoi( argv[1] );
        base = atoi( argv[2] );

        t = tobase( n, base );

        if ( t == NULL )
        {
            ret = 2;
            puts( "Error." );
        }
        else
        {
            puts( t );
            free( t );
            ret = 0;
        }
    }

    return ret;
}

char* tobase( int i, int base )
{
    const char symbols[] =
        "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";

    char* ret;
    int lbn;
    int neg;
    int c;
    int rem;

    if ( ( ( base > -2 ) && ( base < 2 ) ) || ( base > 64 ) || ( base < -64 ) )
    {
    ret = NULL;
    }
    else if ( base < 0 )
    {
        if ( i < 0 )
        {
            neg = 1;
            lbn = ( ilog2( -i * -base + -i + base ) / ilog2( -base ) );
        }
        else
        {
            neg = 0;
            lbn = ( ilog2( i * -base + i + base ) / ilog2( -base ) );
        }
    
        if ( lbn % 2 == neg )
        {
            lbn++;
        }

        c = lbn;
        ret = ( char* )malloc( c + 1 );
        ret[c--] = '0';

        do
        {
            rem = py_mod(i, base);

            i = py_div(i, base);

            if ( rem < 0 )
            {
                i++;
                rem -= base;
            }

            ret[c--] = symbols[rem];
        } while ( i );
    }
    else
    {
        if ( i < 0 )
        {
            neg = 1;
            i = -i;
        }
        else
        {
            neg = 0;
        }

        lbn = ilog2( i ) / ilog2( base ) + 1;

        c = lbn + neg;
        ret = ( char* )malloc( ( c + 1 ) * sizeof( char ) );
        ret[c--] = '0';

        if ( neg )
        {
            ret[0] = '-';
        }

        do
        {
            ret[c--] = symbols[i % base];
            i /= base;
        }
        while ( i );
    }

    return ret;
}

unsigned int ilog2( unsigned int n )
{
    unsigned int ret;

    if (n == 0)
        return -1;

    ret = 0;

    if (n >= (1 <<16)) { n >>= 16; ret += 16; }
    if (n >= (1 << 8)) { n >>=  8; ret +=  8; }
    if (n >= (1 << 4)) { n >>=  4; ret +=  4; }
    if (n >= (1 << 2)) { n >>=  2; ret +=  2; }
    if (n >= (1 << 1)) {           ret +=  1; }

    return ret;
}

int py_div( int a, int b )
{
    int ret;

    ret = ( a - py_mod( a, b ) ) / b;

    return ret;
}

int py_mod( int a, int b )
{
    int ret;

    if ( a < 0 )
    {
        if ( b < 0 )
        {
            ret = -((-a) % (-b));
        }
        else
        {
            ret = a % b;
        }
    }
    else
    {
        if ( b < 0 )
        {
            ret = a % -b;
            if ( ret )
            {
                ret += b;
            }
        }
        else
        {
            ret = a % b;
        }
    }

    return ret;
}

Edit: Final version (apart from floats which will follow shortly):

Only bases it won't do are those that can't be expressed as integers, and 1, 0 and -1. Not sure if they are defined at all though. Base 1 is just a tally right? 11111₁ = 5₁₀ etc.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const char symbols[] =
        "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";

char* tobase( int, int );
char* tobase_neg( int, int );
char* tobase_pos( int, int );
char* tobase_neg64( int, int );
char* tobase_pos64( int, int );
unsigned int ilog2( unsigned int );
int py_div( int, int );
int py_mod( int, int );

int main( int argc, char* argv[] )
{
    int ret;
    int n;
    int base;
    char* t;

    if ( argc != 3 )
    {
        puts( "Usage: tobase NUMBER BASE" );
        ret = 1;
    }
    else
    {
        n = atoi( argv[1] );
        base = atoi( argv[2] );

        printf( "%i to base %in", n, base );

        t = tobase( n, base );

        if ( t == NULL )
        {
            ret = 2;
            puts( "Error." );
        }
        else
        {
            puts( t );
            free( t );
            ret = 0;
        }
    }

    return ret;
}

char* tobase_neg( int i, int base )
{
    char* ret;
    int lbn;
    char** parts;
    int n;
    int l;
    int rem;

    if ( i < 0 )
    {
        lbn = ( ilog2( -i * -base + -i + base ) / ilog2( -base ) );

        if ( lbn % 2 != 0 )
        {
            lbn++;
        }
    }
    else
    {
        lbn = ( ilog2( i * -base + i + base ) / ilog2( -base ) );

        if ( lbn % 2 == 0 )
        {
            lbn++;
        }
    }

    parts = ( char** )malloc( sizeof( char* ) * lbn );

    n = lbn - 1;

    do
    {
        rem = py_mod(i, base);

        i = py_div(i, base);

        if ( rem < 0 )
        {
            i++;
            rem -= base;
        }

        l += asprintf( &parts[n--], "%i", rem );
    } while ( i );

    l += lbn;
    ret = ( char* )malloc( l + 1 );
    ret[0] = '0';

    for ( n = 0; n < lbn; n++ )
    {
        strcat( ret, parts[n] );

        if ( n + 1 < lbn )
        {
            strcat( ret, "." );
        }

        free( parts[n] );
    }

    free( parts );

    return ret;
}

char* tobase_pos( int i, int base )
{
    char* ret;
    int lbn;
    int neg;
    char** parts;
    int n;
    int l;

    if ( i < 0 )
    {
        neg = 1;
        i = -i;
    }
    else
    {
        neg = 0;
    }

    lbn = ilog2( i ) / ilog2( base ) + 1;

    parts = ( char** )malloc( sizeof( char* ) * lbn );

    n = lbn - 1;

    do
    {
        l += asprintf( &parts[n--], "%i", i % base );
        i /= base;
    }
    while ( i );

    l += lbn + neg;
    ret = ( char* )malloc( l + 1 );

    if ( neg )
    {
        ret[0] = '-';
        ret[1] = '0';
    }
    else
    {
        ret[0] = '0';
    }

    for ( n = 0; n < lbn; n++ )
    {
        strcat( ret, parts[n] );

        if ( n + 1 < lbn )
        {
            strcat( ret, "." );
        }

        free( parts[n] );
    }

    free( parts );

    return ret;
}

char* tobase_neg64( int i, int base )
{
    char* ret;
    int lbn;
    int neg;
    int c;
    int rem;

    if ( i < 0 )
    {
        neg = 1;
        lbn = ( ilog2( -i * -base + -i + base ) / ilog2( -base ) );
    }
    else
    {
        neg = 0;
        lbn = ( ilog2( i * -base + i + base ) / ilog2( -base ) );
    }

    if ( lbn % 2 == neg )
    {
        lbn++;
    }

    c = lbn;
    ret = ( char* )malloc( c + 1 );
    ret[c--] = '0';

    do
    {
        rem = py_mod(i, base);

        i = py_div(i, base);

        if ( rem < 0 )
        {
            i++;
            rem -= base;
        }

        ret[c--] = symbols[rem];
    } while ( i );

    return ret;
}

char* tobase_pos64( int i, int base )
{
    char* ret;
    int lbn;
    int neg;
    int c;

    if ( i < 0 )
    {
        neg = 1;
        i = -i;
    }
    else
    {
        neg = 0;
    }

    lbn = ilog2( i ) / ilog2( base ) + 1;

    c = lbn + neg;
    ret = ( char* )malloc( ( c + 1 ) * sizeof( char ) );
    ret[c--] = '0';

    if ( neg )
    {
        ret[0] = '-';
    }

    do
    {
        ret[c--] = symbols[i % base];
        i /= base;
    }
    while ( i );

    return ret;
}

char* tobase( int i, int base )
{
    char* ret;

    if ( base < -64 )
    {
        ret = tobase_neg( i, base );
    }
    else if ( base <= -2 )
    {
        ret = tobase_neg64( i, base );
    }
    else if ( base > 64 )
    {
        ret = tobase_pos( i, base );
    }
    else if ( base >= 2 )
    {
        ret = tobase_pos64( i, base );
    }
    else
    {
        ret = NULL;
    }

    return ret;
}

unsigned int ilog2( unsigned int n )
{
    unsigned int ret;

    if (n == 0)
        return -1;

    ret = 0;

    if (n >= (1 <<16)) { n >>= 16; ret += 16; }
    if (n >= (1 << 8)) { n >>=  8; ret +=  8; }
    if (n >= (1 << 4)) { n >>=  4; ret +=  4; }
    if (n >= (1 << 2)) { n >>=  2; ret +=  2; }
    if (n >= (1 << 1)) {           ret +=  1; }

    return ret;
}

int py_div( int a, int b )
{
    int ret;

    ret = ( a - py_mod( a, b ) ) / b;

    return ret;
}

int py_mod( int a, int b )
{
    int ret;

    if ( a < 0 )
    {
        if ( b < 0 )
        {
            ret = -((-a) % (-b));
        }
        else
        {
            ret = a % b;
        }
    }
    else
    {
        if ( b < 0 )
        {
            ret = a % -b;
            if ( ret )
            {
                ret += b;
            }
        }
        else
        {
            ret = a % b;
        }
    }

    return ret;
}

Edited December 20, 2011 by Mat

czardas · December 20, 2011

Actually this is interesting from a theoretical perspective. The negative base idea is still a bit baffling and I still can't think of any uses outside encryption.

I just got to thinking about the standard nomenclature for larger numeric bases and figured that adding additional letters and symbols is overly confusing. Using double digits makes more sense. We do this with sexagesimal every time we look at a clock, and it doesn't cause any problems. If two hex digits were used to represent each number we can increase the number of practical bases to 254.

Mat · December 20, 2011

Thats plausible, but the common way to do it is put dots between the 'digits' like you get in an ip address. An ip address is just a base 256 number.

czardas · December 20, 2011

Of course.

I might experiment a bit with this, perhaps make a base 240 clock which rolls over every 4 hours (240 mins) or something.

JohnQSmith · December 20, 2011

Base 1 is just a tally right? 11111₁ = 5₁₀ etc.

That's correct and you can use any symbol to represent it, not just 1 (at least that's what a professor told me).

I've been lurking for 7 years. Finally decided to post.

Edited December 20, 2011 by JohnQSmith

Mat · December 20, 2011

Lurker or no lurker... Welcome to the forums You've been here longer than me. Twice as long as me actually

To keep consistent it should be a zero. What about decimals in base 1 Now that is a very interesting question. I don't think it's possible but ah well.

JohnQSmith · December 20, 2011

Here's what Wikipedia says about unary numbers. They don't mention decimals or would that be unimals?

MvGulik · December 20, 2011

11111₁ = 5₁₀

To keep consistent it should be a zero.

Your sure about that ... zero not really being a value, other than indication the lack of one. (Romans did there math(well, counting) whiteout it ... poor basters.

) Edited December 20, 2011 by MvGulik

Sign In

Negative bases

Recommended Posts

Mat

jaberwacky

jaberwacky

Mat

czardas

Mat

jaberwacky

MvGulik

Mat

Richard Robertson

Mat

Mat

Mat

czardas

Mat

czardas

JohnQSmith

Mat

JohnQSmith

MvGulik

Create an account or sign in to comment

Create an account

Sign in

Similar Content

Advanced Math UDF

Simulated Annealing - When brute-force takes too long

Program doesn't write to files

Can someone check my maths....

Stupid funny game

Browse

AutoIt Resources

Release

Beta