Base-Negative Numbers?

Discussion in 'Computers and The Internet' started by AceK, Feb 19, 2015.

  1. AceK

    AceK Scientia Potentia Est

    Messages:
    7,824
    Likes Received:
    960
    Normally we deal with numbers in base 10, or decimal numbers, but numbers can also be commonly represented in other bases such as binary (base-2) or hexadecimal (base-16) which is a more human friendly way to work with binary data at a low level. The radix is the number that represents the base of a number and in the familiar decimal (base-10) numbers that we normally deal with the radix ris 10, and each place position (p to the left of the decimal point (aka radix point) represents the number in that place (beginning at zero) multiplied by an exponential power of the radix, ( therefore any number can be expressed as a polynomial. let n be the value at the positionp I.e. x= nr^p. (negative powers of r for places to the right of the decimal point)


    the number 1,234 can be represented as 1*10^3 + 2*10^2 + 3*10^1 + 4*10^0. thus converting between bases is somewhat trivial. the digits can be produced in an alternate number base by taking the modulus of the number and the desired radix, this produces the the least signitficant digit in the converted number. to get the rest of the digits integer division by the radix is performed and the process repeated on the dividend until the result of division reaches zero.

    what I'm having trouble wrapping my head around is how to do this when the radix is negative. in base negative ten (negadecimal) each place position is a power of negative 10 so -10 innegadecmal would be 10, since the "tens" place is -10^1, however 100 would still be 100, since -10^2 is positive 100. so far I have not been able to put anything together that works properly on non-trivial numbers. I can get it to work on such numbers as 10, 100, 1000 etc, but when I try 124 i get -124 which isn't correct. I don't seem to be handling the sign of the numbers properly, the sign seems to be reversed on odd numbers of digits but tits not quite as simple as that. the procedure I wrote extracts the values by doing the normal procedure of division and taking the remainder and doe 124 in base ten I actually get the values -1, 2, -4, which I'm not sure how to handle the signs of when converting to a string (which is why I get -124, but as a polynomial these actually add up to be 84)

    It seems that if I formed a polynomial expression that this would give the correct answer but my main troubles are
    A: that I'm not even sure that I'm right as far as 84 being the correct representation of -124 in base negative 10

    B: i'm not sure how this would work on bases other than 10 (or -10), for example base-16 (negahexadecimal?)

    what I have currently written gives 7F and in the digits buffer it has -7, 15 (as base-10 values) which does come out to be 7F by hand which is the same as 127 in normal hexadecimal.

    32767 gives 7FFF in base -16 which is again the same thing as normal hexadecimal but the digits buffer has -7, 15, -15, 15 which also is correct, somehow the negative base version is the same.

    -128 in base -16 gives -80, now the buffer has 8 and 0, which turns out 80 in base -16 is actually correct for -128 (8 * -16 = 0). -32768 gives 8000 which is also correct.

    these numbers are all nice ones, other ones do t work so nice.

    -2748 gives -ABC and -10, 11, and -12 which is -2396 in decimal so this isn't correct. negative and positive numbers are both supposed to have an unsigned representation in negative bases and you would never represent this as -ABC in hexadecimal because you don't normally write signed hexadecimal values (you use two's complement).

    I think that is the only practical application of negative bases that you can represent signed quantities as an unsigned representation. not sure if it's really ever used in real life as I've never heard of it before, two's complement is definitely far easier and more intuitive but this is mainly just a programming challenge to see if I can solve an unfamiliar problem.

    it seems to be much more difficult as a mathematical challenge, and I think a lot of what's giving me hell is that I still don't really grasp how base negative numbers are supposed to work. my method works on any regular positive number base and gives the correct answer but negative ones aren't so I think there's more to handling the sign of the result than I realize. I'm still not even sure exactly how to find out the negative base with paper and pen either, though i do get how to check if the result is correct or not (I think).

    TLDR:
    if someone who is very good at math could drop in and enlighten me. if I can ever figure this out the next step is to implement a way to handle imaginary bases (i.e. where the radix is a complex number with an imaginary component like base 2i). I have no idea what the implications of THAT would be but I imagine that it will be crazy as fuck and probably not resemble a normal number at all.
     
  2. skip

    skip Founder Administrator

    Messages:
    12,901
    Likes Received:
    1,822
    I gave up on math in 12th grade. I was at the top of my class, but it bored the shit out of me, as does this kinda thing... (no offense).

    I also cut classes a LOT in my senior year... Of course "base numbers" was taught long before that, and I enjoyed it then.

    "base negative 10". Somehow that doesn't sound like a "real" number to me, esp when squared.

    Perhaps when dealing with negatives, you must remove the - sign from the calculation, I'm guessing.

    Or perhaps it's like words, a double negative, is a positive statement. :)

    BTW, there's many pages on this subject if you look in google.
     
  3. IMjustfishin

    IMjustfishin Member

    Messages:
    1,255
    Likes Received:
    194
    i cant help, but i am curious why your doing this? is it for part of a program your creating?
     
  4. AceK

    AceK Scientia Potentia Est

    Messages:
    7,824
    Likes Received:
    960
    yeah, it's just something I was tinkering around yesterday with. it actually is a real thing, a number can actually have any base except for one and zero for obvious reasons the program will crash and burn if you try to convert to base zero or one (base 1 would be like and infinite number of digits maybe? and for zero it's impossible to because of division by zero.)

    I looked up an article about it that I'm gonna look at today further. like skip said they dontt seem like real numbers to me either but they do work, but it's hard to visualize their quantity. apparently when you add base negative numbers instead of adding to the left column when you carry, you have to subtract from the column to the right. subtraction I think is the except borrowing is actually addition, but only for the carry, and it's done in the opposite direction as well (add to the right). I think the rules are different for odd and even columns too when changing bases because the sign of the column flips (1, -10, 100, -1000 ...)

    seems so counterintuitive, still not sure I get it. it bothers me to leave a problem unsolved tho, and I want the same function that works properly on positive AND negative bases I may work on it again later when I get well caffeinated.

    I do t know if I have it in me to fuck with the imaginary number bases tho.
     
  5. Moonglow181

    Moonglow181 Lifetime Supporter Lifetime Supporter

    Messages:
    16,175
    Likes Received:
    4,919
    I have not the foggiest notion of what you are talking about...but I wish you luck with it!
     
    1 person likes this.
  6. Gyro Gearloose

    Gyro Gearloose Senior Member

    Messages:
    3,980
    Likes Received:
    244
    Hello,


    I don't think so. -12410 is 1936 in the negative base system: -12410 = 1*-10^3 + 9*-10^2 + 3*-10^1 + 6*-10^0



    I'm not very good at math ;). But I guess the way is to look how it works in decimal and then exactly follow that scheme. At first don't think if it makes sense, just do it. Then the right answer should pop out.

    Regards
    Gyro
     
    1 person likes this.
  7. AceK

    AceK Scientia Potentia Est

    Messages:
    7,824
    Likes Received:
    960
    ^just do it and then try to understand it later, lol sometimes that actually works

    ur answer 1936 is correct and I see how it works now, somehow I gotta figure out a way to get that -1000 in there which doesn't naturally come out of -124.

    the 84 was a bug I guess because that's the value you get from the normal procedure if you do it without ha doing the sig of the number first. in positive bases it doesn't seem to really matter what you do with the sign, whether you handle the sign first, and use the absolute value, or whether you you just go on and then use the absolute value of all the resulting digits and then apply the appropriate sign to it. with negative base tho, I'm thinking something completely different has to be done.

    I'm gonna study negative bases until I can do it on paper, then when I can do that I'll be able to code it. I easily tell that your answer is correct, but starting with -124 im not sure how to get there.

    the fact that negative numbers are positive in negative bases leads me to wonder about what a negative number in a negative base would be in a positive base? it would either be an imaginary number, or just like an alternate version.
     
  8. Gyro Gearloose

    Gyro Gearloose Senior Member

    Messages:
    3,980
    Likes Received:
    244
    Hello,

    I confess, I had a sharp eye on it and then the solution came out ;). To do it algorithmically I think one way to do it is with the following rule: subtract the smallest multiple of a power of the target base, whose absolute value is just bigger than the absolute value of your number, then repeat until 0.

    Your number is -12410, the absolute value is |-124| = 124.

    Step 1: -124 = 1 * -10^3, remainder 876

    |1 * -10^3| is just bigger than |-124|, so the higgest exponent of -10 you need is 3, and the multiplicator 1 of the power -10^3 is your first digit.

    Step 2: 876 = 9 * -10^2, remainder -24

    |9 * -10^2| is just bigger than |876|, so the higgest exponent of -10 you need is 2, and the multiplicator 9 of the power -10^2 is your next digit.

    And so on. See the pattern? Now assume your number is 12410:

    Step 1: 124 = 2 * -10^2, remainder -76

    |2 * -10^2| is just bigger than |124|, so the higgest exponent of -10 you need is 2, and the multiplicator 2 of the power -10^2 is your first digit.

    Step 2: -76 = 8 * -10^1, remainder 4

    |8 * -10^1| is just bigger than |-76|, so the higgest exponent of -10 you need is 1, and the multiplicator 8 of the power -10^1 is your next digit.

    And so on. So if you implement this, there might be other or easier ways to do that. Maybe Horner Scheme might help here, I don't know. And it's up to the reader to generalize the algorithm, so that it works with positive and negative bases equaly ;).

    Regards
    Gyro
     
    2 people like this.
  9. AceK

    AceK Scientia Potentia Est

    Messages:
    7,824
    Likes Received:
    960
    ah, I think I can get that. it makes sense when u look at it that way, i kinda got tunnel vision. I was trying to figure out a method that involved taking the base-compliment for digits that have even expansion power and then carrying a one to the left ... and just realized what I (think) was doing wrong with that. I was taking 10s' compliments for base -10, and couldn't figure out why it only worked on the absolute value of the number but ended up being the correct representation of the negative number.

    I think I'll try coding both methods, urs seems like it might be easier. mine seems to need an intermediate step, and has some weird quirk I can't find out. Id like to have a nice small function that handles positive and negative bases without being a big mess. Theres already some weird questionable parts in there leftover from other shit I tried that probably aren't really necessary, so I think I'll try making a function that does negative bases, then try to merge the other one into it, the goal being a generalized routine thats as short and simple as I can get.
     
  10. Gyro Gearloose

    Gyro Gearloose Senior Member

    Messages:
    3,980
    Likes Received:
    244
    Hello,

    I think you can get rid of the |x| and generalize both cases, if you think about how the numbers are ordered on the number line, i.e. -100010 < 10010, but -1000-10 > 100-10. I wonder what happens if you use complex bases. I have the feeling nothing changes, but who knows ;).

    Regards
    Gyro
     
  11. Gyro Gearloose

    Gyro Gearloose Senior Member

    Messages:
    3,980
    Likes Received:
    244
    Hello,

    shush, it's about world domination. Muaahhahahahahahahaaaaa.

    Regards
    Gyro
     
  12. AceK

    AceK Scientia Potentia Est

    Messages:
    7,824
    Likes Received:
    960
    it compiled, but ultimately results in a segmentation fault because it goes off the end the buffer it puts the digits in.

    obviously i made a mistake. if i have it right, once you find the biggest exponent its supposed to get decremented each iteration? for some reason it's decrementing and then getting incremented again which makes it never terminate even tho i can't find an e++ anywhere. some of the digits are right tho. i commented out a tiny peice of the code and it made it worse, so i uncommented it but it still acts like i didnt' uncomment it. how the fuck can i put it back exactly how it was but it still acts like i never put it back?! lol

    maybe tomorrow after i go to sleep and am not drunk this will make more sense ;p
     
  13. Gyro Gearloose

    Gyro Gearloose Senior Member

    Messages:
    3,980
    Likes Received:
    244
    Hello,

    C code? If it's not too long and you want to copy it to a paste bin, I might be motivated enough to look at it later this day ;).

    Regards
    Gyro
     
  14. AceK

    AceK Scientia Potentia Est

    Messages:
    7,824
    Likes Received:
    960
    the whole thing is like 200 lines, but the actual function for doing the negative base conversion is only like 25 lines including comments.

    i'm only gonna paste the relevant function, since the rest just adds noise. i fixed the segfault but now it doesn't give the correct digits cuz i lost track of what it is supposed to do lol.

    I'd appreciate it

    http://pastebin.com/vee8BVYf
     
  15. Asmodean

    Asmodean Slo motion rider

    Messages:
    50,551
    Likes Received:
    10,133
    I find it interesting but am clueless in this regard.
     
  16. Gyro Gearloose

    Gyro Gearloose Senior Member

    Messages:
    3,980
    Likes Received:
    244
    Hello,

    there are at least two problems. In line 23 you start finding the e for the next calculation, but your e is 1 too big. For instance, you need -10^3, so e should be 3. But you calculated it to be 4. As a quick work around, not a solution, I wrote e--; into line 28 ;). Maybe you tried to fix it later in the code where you call --e, I don't know.

    Second is line 36. You must not use the absolute values there, so something like 'connegbase(n - (m * ipow(r, e)), r);' should do the trick. Calling connegBase(-124, -10) then fills the buffer with the numbers 1, 9, 3 and 6.



    Regards
    Gyro
     
    1 person likes this.
  17. Asmodean

    Asmodean Slo motion rider

    Messages:
    50,551
    Likes Received:
    10,133
    Impressive Gyro :) Well, not sure about that, but it is to me.
     
  18. Gyro Gearloose

    Gyro Gearloose Senior Member

    Messages:
    3,980
    Likes Received:
    244
    Hello,

    thanks, Asmo ;). There are some other quirks with the code, but AFAIK ace_k is new to C. So yeah, it's fun stuff to do ;).

    Regards
    Gyro
     
  19. Gyro Gearloose

    Gyro Gearloose Senior Member

    Messages:
    3,980
    Likes Received:
    244
    Hello,

    well, the two fixes from above aren't enough, as one finds out with other inputs ;). Let's have a deeper look.

    Regards
    Gyro
     
  20. AceK

    AceK Scientia Potentia Est

    Messages:
    7,824
    Likes Received:
    960
    thanks a lot, that seemed to make it work for negaoctal when i tried converting 9 into base -8 and got 171 which is correct.

    for some reason 16 in base -16 gave 1, which isn't right.

    i always suspected that while loop. i changed the < in the expression to an <= which makes it give the correct answer for 16 = 0x1F0 (because 16 isn't greater than, it's equal to)

    this is what works:

    while ( !e_flg &&
    abs(ipow(r, e++)) <= abs(n)) {
    ;
    }
    e_flg = true;
    e--;
    still needs that e-- on its own line, i tried putting the e++ inside the braces and not in the conditional expression, but having it after the loop is the only way that does everything that has to be done. it seems like it needs to be there, but it doesn't really look like it should have to be. i'm glad to have gotten this far tho because that works correctly for every number i've tried. (as long as r is negative)

    also, in the if conditional expression, testing for only e instead of e && n. i put the n in there to see what it would do and it didn't seem to have any effect so i left it like that, but on number like -100 that fucks it up, because i guess the remainder can be 0 in those such numbers even though the process isn't actually finished. so it seems testing for e is all that has to be done to tell if you're finished and once e reaches zero then the remainder "has" to be zero also. however, doing this breaks it for -10 causing it to give 1 11 0 which "11" isn't a valid digit even though addint them up results in -10 ????

    numbers that are exactly the same value as the base eg. -10 will give a result where the second digit 1 more than the absolute value of the base which add up to be the right number but aren't valid digits in that base :confused: it's like it "overshoots" in that one case.

    if u take subtract the absolute value of the base from the too big digit (or just add the negative base to the digit) you get the correct digit, then you have to subtract one from the next place to the left and that give the correct result for negative ten without screwing up other numbers but that seems like a hack that would probably not hold up well.

    weird.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice