wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> BASE N
        
(Message started by: eviljed on Aug 9^th, 2002, 11:12am)

Title: BASE N
Post by eviljed on Aug 9^th, 2002, 11:12am

I'll just describe base n:

an addition tabe can be described as such:

xxxx | n-n | n-(n+1) | n-(n+2) | ... | n
____________________________________
n-n | 0 | 1 | 2 | ... | n
n-(n+1) | 1 | 2 | 3 | ... | n+1
n-(n+2) | 2 | 3 | 4 | ... | n+2
... | | | | |
n | n | n+1 | n+2 | ... | 2n

Now to translate (all you 744t people feel free to either skip or correct me):

Given that my little table would not work in base 4, 3, 2, or 1. Base 0 could not exist by default (no numbers to work with beyond the given limit). Base 1 would be doable, albeit strange (4 would be expressed as 0000). Each number placement represents a set of a given number to a power determined by it's significance. Since we tend to read numbers from the right to the left, it stands to reason that the least significant place be the far left. Each place is calculated as (given base n): number in place * n^(number = significance of place). This calculation is done for each place, and the results are added together to represent the total value of the number.

As for base -2, I don't know. My hunch would be that it is a base system that would be the equivilant of a binary system where every number has been given it's one's compliment (or maybe two's compliment).

Title: base -2????
Post by Aaron on Aug 9^th, 2002, 12:26pm

I think my head just exploded from reading that...

for me a base n addition works like this:

concider a number with each of it's digit an element in an array like so... a[5]a[4]a[3]a[2]a[1]a[0]
eg.
1024 => a[3] = 1, a[2] = 0, a[1] = 2, a[0] = 4

so for a + b = c:

for(int i = 0; i < max(a.length, b.length); i++) {
c[i] = a[i] + b[i] + c[i]; // carry over
while(c[i] >= n) {
c[i] -= n'
c[i + 1] ++;
}
}

This gets screwed bad when n is zero or a negative number.

I don't think base 1 would work out in reality though... because even "0000" is just 0x1^3 + 0x1^2 + 0x1^1 + 0x1^0, which is still 0. in fact, as soon as you have a number larger then 0, let's say 1, you would coutinuously carry over that 1 and have infinite 0's.

Title: Re: BASE N
Post by AlexH on Aug 9^th, 2002, 9:32pm

Here is the method for base -2 arithmetic. We're adding numbers a,b to get a sum s. Instead of using one carry bit from each digit to the next, we will use 2 carry digits. c1 is carried one left as usual, and c2 is carried to the digit 2 left of current. This means to compute the ith digit of s (i increasing as we go leftward) we have inputs a[i],b[i],c1[i-1],c2[i-2]. Intuitively we need 2 carry bits because the sum of 2d-digit numbers in a negative base can overflow a (2d+1) digit number.

s[i] = XOR (a[i],b[i],c1[i-1],c2[i-2])
Define x by
x = a[i]+b[i]+c2[i-2]-c1[i-1]
In order to properly be performing addition, we need:
x = s[i] -2c1[i] + 4c2[i]
So:
c2[i] is 1 when x=2 or 3, and is 0 otherwise.
c1[i] is 1 when x=-1, 2, or 3, and is 0 otherwise.