# Negative bases

maths more maths

29 replies to this topic

### #1 Mat

Mat

43 38 48 31 30 4E 34 4F 32

• MVPs
• 4,042 posts

Posted 18 December 2011 - 09:02 PM

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.

Plain Text
```#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;
}```

I don't know where I'm going, but I'm on my way.

### #2 jaberwocky6669

jaberwocky6669

Dull light.

• Active Members
• 2,082 posts

Posted 18 December 2011 - 11:36 PM

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 by LaCastiglione, 18 December 2011 - 11:45 PM.

### #3 jaberwocky6669

jaberwocky6669

Dull light.

• Active Members
• 2,082 posts

Posted 18 December 2011 - 11:52 PM

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

### #4 Mat

Mat

43 38 48 31 30 4E 34 4F 32

• MVPs
• 4,042 posts

Posted 19 December 2011 - 08:09 AM

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

I don't know where I'm going, but I'm on my way.

### #5 czardas

czardas

• Active Members
• 5,079 posts

Posted 19 December 2011 - 08:52 AM

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

### #6 Mat

Mat

43 38 48 31 30 4E 34 4F 32

• MVPs
• 4,042 posts

Posted 19 December 2011 - 09:35 AM

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.

Plain Text
``` 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`

I don't know where I'm going, but I'm on my way.

### #7 jaberwocky6669

jaberwocky6669

Dull light.

• Active Members
• 2,082 posts

Posted 19 December 2011 - 11:20 AM

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

Oh wait, no it isn't. LOL!

Edited by LaCastiglione, 19 December 2011 - 11:21 AM.

### #8 MvGulik

MvGulik

Universalist

• Active Members
• 2,795 posts

Posted 19 December 2011 - 12:58 PM

??? ...

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

(
Aha, Making a little more sense.
Don't Fall in Love With Ideas"If you fall in love with an idea, you won't see the merits of alternative approaches -- and will probably miss an opportunity or two. One of life's great pleasures is letting go of a previously cherished idea. Then you're free to look for new ones. What part of your idea are you in love with? What would happen if you kissed it goodbye?"

### #9 Mat

Mat

43 38 48 31 30 4E 34 4F 32

• MVPs
• 4,042 posts

Posted 19 December 2011 - 01:41 PM

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

I don't know where I'm going, but I'm on my way.

### #10 Richard Robertson

Richard Robertson

Universalist

• Active Members
• 9,695 posts

Posted 19 December 2011 - 01:50 PM

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

### #11 Mat

Mat

43 38 48 31 30 4E 34 4F 32

• MVPs
• 4,042 posts

Posted 19 December 2011 - 01:59 PM

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

I don't know where I'm going, but I'm on my way.

### #12 Mat

Mat

43 38 48 31 30 4E 34 4F 32

• MVPs
• 4,042 posts

Posted 19 December 2011 - 04:18 PM

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 by Mat, 19 December 2011 - 08:40 PM.

I don't know where I'm going, but I'm on my way.

### #13 Mat

Mat

43 38 48 31 30 4E 34 4F 32

• MVPs
• 4,042 posts

Posted 19 December 2011 - 11:34 PM

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

Plain Text
```#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? 111111 = 510 etc.

Plain Text
```#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 by Mat, 20 December 2011 - 02:02 PM.

I don't know where I'm going, but I'm on my way.

### #14 czardas

czardas

• Active Members
• 5,079 posts

Posted 20 December 2011 - 08:15 AM

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.

### #15 Mat

Mat

43 38 48 31 30 4E 34 4F 32

• MVPs
• 4,042 posts

Posted 20 December 2011 - 08:36 AM

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.

I don't know where I'm going, but I'm on my way.

### #16 czardas

czardas

• Active Members
• 5,079 posts

Posted 20 December 2011 - 08:42 AM

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.

### #17 JohnQSmith

JohnQSmith

Polymath

• Active Members
• 226 posts

Posted 20 December 2011 - 02:54 PM

Base 1 is just a tally right? 111111 = 510 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 by JohnQSmith, 20 December 2011 - 02:57 PM.

### #18 Mat

Mat

43 38 48 31 30 4E 34 4F 32

• MVPs
• 4,042 posts

Posted 20 December 2011 - 03:47 PM

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.

I don't know where I'm going, but I'm on my way.

### #19 JohnQSmith

JohnQSmith

Polymath

• Active Members
• 226 posts

Posted 20 December 2011 - 04:32 PM

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

### #20 MvGulik

MvGulik

Universalist

• Active Members
• 2,795 posts

Posted 20 December 2011 - 07:14 PM

111111 = 510

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 by MvGulik, 20 December 2011 - 07:16 PM.

Don't Fall in Love With Ideas"If you fall in love with an idea, you won't see the merits of alternative approaches -- and will probably miss an opportunity or two. One of life's great pleasures is letting go of a previously cherished idea. Then you're free to look for new ones. What part of your idea are you in love with? What would happen if you kissed it goodbye?"

### Also tagged with one or more of these keywords: maths, more maths

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users