Negative bases

[Mat]

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.

expandcollapse popup

#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]

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]

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]

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

[czardas]

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

[Mat]

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]

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]

??? ...

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]

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

[Richard Robertson]

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

[Mat]

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

[Mat]

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]

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***.

expandcollapse popup

#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.

expandcollapse popup

#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]

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]

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]

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]

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]

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]

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

[MvGulik]

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