Follow us on Twitter!
It is the path of least resistance that makes rivers and men crooked. - Bj Palmer
Friday, April 18, 2014
Navigation
Home
HellBoundHackers Main:
HellBoundHackers Find:
HellBoundHackers Information:
Learn
Communicate
Submit
Shop
Challenges
HellBoundHackers Exploit:
HellBoundHackers Programming:
HellBoundHackers Think:
HellBoundHackers Track:
HellBoundHackers Patch:
HellBoundHackers Other:
HellBoundHackers Need Help?
Other
Members Online
Total Online: 19
Guests Online: 16
Members Online: 3

Registered Members: 82822
Newest Member: TheBunter
Latest Articles

Positional Number Systems

Arrow Image A tutorial on decimal and non-decimal number systems, conversions between them, and a few potential uses.



Using non-standard positional number systems can be quite useful for programmers, as computers store information in binary, but there are other useful bases. In fact, the average person regularly uses 3 different bases. Decimal is probably the most commonly used base, so I don\'t imagine I need to explain it (though I will later, anyway). The other 2 are Unary and Sexagesimal. Unary is base-1. Whenever you use tally marks, count on your fingers, or even count physical objects, you are treating each element as 1 digit. This can have its uses but is highly inefficient, especially for computers: by the time you reach 11, youíve already surpassed the limit for an unsigned 32-bit integer. Sexagesimal is base-60. Hereís where itís used: 60 seconds in a minute, 60 minutes in an hour. Time is expressed as a 3 digit hexadecimal number representing seconds. If youíre using a base less than 10, generally numeric values starting at 0 are used. If your base is between 11 and 36 inclusive, after the number 9, letters are used, starting with a. If your base is greater than 36, digits are colon-delimited.

Decimal is base 10. What that means is that a given number is equal to the sum of each digit times a power of 10. For instance, 2503 =(2*10^3)+(5*10^2)+(0*10^1)+(3*10^0). Remember that anything to the 0 power is 1, so the farthest digit from the left is exactly equal to itís value. This is true in ALL bases, not just decimal. Now just like any good mathematician or programmer, we donít want an equation that will work on just one problem, we want a general, all-encompassing function. Here, we know that in base 10, we multiply the digits by powers of 10, so letís generalize and say that in base-n, we multiply by powers of n. next, look at the equation. Notice anything about the powers? Starting from the right, the powers of n increase by 1 each digit, starting at zero.

Now weíve got a simple, general conversion to decimal formula, but before we go any further, it helps to understand how counting works (bear with me here).
When you count in decimal, you go from 1-9, then 10-19, 20-29, ..., 90-99 then 100, etc. think of this like a sort of clock with 10 positions. when the ones hand gets all the way to 9, after 1 more change it arrives back at 0, and the tens hand increases by 1. When the tens hand gets to 9, the next time it moves, it arrives back at 0, and the 100ís hand increases by 1, etc. this works in all bases, except now you have to imagine there are n positions for every hand, where n is the base. so for instance, in base 3, when the smallest hand gets to 2 (I imagine most programmers will recognize 0 is 1 possible value, so digits may be 0, 1, or 2) the next location it moves to is 0, and the next hand up moves forward 1 position. Counting in base 3, then, would look like this: 0, 1, 2, 10, 11, 12, 20, 21, 22, now what? If you thought 30 was next, youíd be wrong. weíre counting in base-3, so the highest possible digit value is 2. the next number, then, is 100. Make sure to check each digit. If it will become equal to n in base-n, then you have to carry and reset the previous digits, just like in decimal. you can also this of it this way: powers of n in base-n will be written like powers of 10 in decimal, namely 1, 10, 100, 1000, etc. so essentially, all bases are base-10 because 4 in base-4 is 10, 9 in base-9 is 10, etc. (it almost seems like cheating. Whatís 342 squared? oh, itís 100 in base-342).

Okay, now that weíve covered counting in base-n, we can move on to conversion to base-n. there are 2 methods to use here, though one is only really practical for converting to binary. The first way is easier, but requires a lot more work the higher n becomes. In this method you simply take the highest power of n that goes into the decimal number you want to convert, then based on what power you used, find what digit that value would be in. letís use the number 8. in binary, we see that 8 is a power of 2. the 3rd power to be exact, so it would be a 1 in the fourth digit from the right (remembering that the farthest digit is to the 0 power), so 8 in binary is 1000. Now letís convert the same number to ternary (base-3). Well 3^1 is the highest power of 3 that fits in 8, but now how do we get 8 if we can only add 2 more to the value? Binary is easy because there are 2 possible values to the digit, 0 or 1, so either it adds value or it doesnít, but ternary has 3 possible values. remember the equation we had for decimal? itís the same thing. weíre not just adding powers of n, were adding products of powers of n and the digit value. so 3^1 fits in 8, but (2*3^1) fits better. now weíre only 2 away from the value, so that 0-power digit is 2. 8 in ternary is 22. Notice how much smaller 22 is that 1000? The higher the base, the less digits are needed to represent the value, assuming the number is higher than the base. trick question: whatís 8 in base-9? Well since 8 is less than or equal to 9-1, itís just 8. This is true for any number, x, in any base, n, where n>=x+1, with the stipulation that x in base-n will be a 1 digit number, or as an example, 22 in base 23 is 22. Here 22 is a 1 digit number with a value equal to 22*23^0.
Now for the other method. This method requires less work, but will only work for integers. simply take the number you want to convert, and repeatedly divide by the number of the base you want to convert to, recording the remainder of each operation, until you have nothing left. If you wrote them in exactly the order you got them in, write it backwards, and you have your number. Letís convert 38 to base 6 (using integer arithmetic. Any fractional portion is dropped). 38 / 6 = 6 R2, 6 / 6 = 1 R0, 1 / 6 = 0 R1 so 37 in base 6 is 102. This works because the first thing you want is the division remainder of the number by the base youíre converting to, so essentially x/n^0 then you divide by n^1 and take the remainder again. These operations are the inverse of converting to decimal.

Conversions between non-decimal bases is possible (I think) but is easiest between bases that are powers of each other. to make it simpler, say you want to convert a number in hexadecimal (base-16, if you didnít know) to binary. Well 16 is 2^4. we now know how many digits our binary number could have. yup, itís that simple. in fact, itís even simpler than that. each digit in hexadecimal translates directly to 4 bits (padded with 0ís, if necessary). If you want to convert easily to decimal from hex, just count from 0 to 15 in binary then next to it, write the numbers 0 to 9, then the letters a through f. Now as long as you pad 0ís you can just connect all these numbers together to get the binary representation. This is true for any base, as long as one is a power of another. So, say, 21 in base-3 to base-9, well 9=3^2, so 2 base-3 digits will be 1 base-9 digit. since we only have 2 base-3 digits, our number will be less than 9, and therefore less than 10, so we can just be lazy and convert to decimal (actually, thatís really all you ever have to do, because any group of digits will be less than the base youíre converting to if youíre going to a higher base. You could be converting from binary to quaternary (base-4) 2 binary digits will never be greater than 3, so go to decimal because itíll be the same in quaternary) and we get 7. so 21 in ternary=7 in base-9. also, 2121=77, 21212121=7777. Just pretend youíre converting each digit to or from decimal and pad zeroes where necessary.

Now hereís something Iíve been wondering about recently, and havenít been able to find any info on: rational bases. Iíve managed to work out all kinds of info on them myself.
let me explain in decimal: everything Iíve explained is true to the left of the decimal point. after that, the powers of 10 decrease, so 1.05 = (1*10^0)+(0*10^-1)+(0*10^-2). Generalizing that, after the base-n point, exponents continue to decrease, so why canít we convert 8 to base 1/2? the 0-power place would still equal itís value, so 1 in base 1/2 should be 1. after that it gets fun. remember negative exponents? n^-1=1/n, therefore 8 should be 0.001 (1/2^-3=8). now of course, the only practical use for this would be representing really small numbers as integers (think 0.001 in base 1/10=1000) or representing large numbers as minuscule numbers. Base-1/n would be the same number as base-n reflected across the 0-power place. (1000 base-2, 0.001 base-1/2)

Another interesting concept I recently stumbled upon is negative bases. Remember how an even exponent always makes a positive number? thatís the basic concept, but it makes counting really weird. for instance, negadecimal is 1-9 ans usual, but now the 10ís place has a negative value... what to do... oh, what about 100-90? yup, so after 9 you go to 190... then after 199 you go to 180 and the pattern continues like so with odd-powered digits being negative in value. the point? how do you represent -100? Why, with the positive number 1900, of course. Yay for all positive numbers, now good luck doing math with that...

Okay, now onto interesting notes and ideas: remember how I said I said generally those digits are used? These values are arbitrary. no oneís stopping you from representing binary using Aís and Sís, or 9ís and 5ís (in fact, the 5 could represent 1). Why is this useful? How about we use base 26? letís say a=0, b=1, c=2...z=25. Now type a message and convert to decimal. See? different bases ARE useful, and while this may not be the most complicated method of encryption, it could have uses, since most people donít even realize they arenít just using decimal... here\'s another example: remember that bit about converting between bases that are powers of each other? What if you want to compress a file quickly? why not convert to a higher base? then just convert back to decompress it. If the document is written in hex, why not change it to base-256? you\'ll cut the document size in half (theoretically) and still have all the same information in it. additionally, I mentioned Unary is inefficient. when you count on your fingers, they each have 2 possible positions that are easily distinguishable. take advantage of that. If you count in binary, even counting on 1 hand using only 4 fingers can get you to 31. Using 4 fingers on both hands, you can count to 255. if you use all 10 fingers, you can count to 1023 on just your fingers, and it only requires some simple multiplication to figure out values.
One final tidbit that might be useful is determining if a number is even or odd in a given base. If the base is even, the least significant digit determines whether or not the number is even. If the base is odd the number of odd digits determines whether or not the number is even. so in an even base, an even 0-power digit makes the number even. In an odd base, an even number of odd digits makes the number even.

Before I summarize, Iíd like to add one more piece of info that will be useful for determining how to store numbers in a given base if youíre writing a program: the number of digits x will have in base-n will be 1+logn(x) (with the given exception of conversions between non-decimal bases that are powers of each other). If you need an example, look at 8 in binary. log2(8)=3 and 8 in binary is 1000, 4 digits. This is because youíre reducing the number to 0 using integer arithmetic, which requires the denominator to be at least 1 higher than the numerator, but since weíre using powers, we need an exponent to put on n that will make n greater than x, so we use 1 more than the exponent that gives x. A number, x, in base-n will have 1+log10(x) digits, for essentially the same reason, but here, we treat the number as though itís a decimal number.

Okay, so if you got completely lost on this article, at least feel free to use these formulas: to convert a number, x, to a base, n, you would take the summation of 10^i*[(x/n^i)%n] as i goes from 0 to 1+logn(x).
to convert back to decimal, you would take the summation of n^i*[(x%10^[i+1])/10^i] as i goes from 0 to 1+log10(x).
Just remember that each iteration through this equation returns 1 digit and theyíll work to convert to any arbitrary base, so long as you use integers and integer arithmetic. If you want to convert rational numbers, do what I did and derive your own formulas.

Note: I came up with most of this information through experimentation. If anything in here is wrong, please let me know, so I can correct it.

Comments

rootDaemonon March 28 2011 - 01:19:35
Overall, nice article. However, I would suggest either pre- or post-fixing your numbers with the base. (ex. 8 in decimal = 8d) especially in the mid section of your article, your numbers need a lot of thought to determine their bases. Otherwise, I enjoyed it quite a lot.
richohealeyon September 13 2011 - 09:11:48
Please explain how 12 can't be represented in unary in a 32 bit int? You can store up to oh I dunno... 31?
Xunxenon February 08 2012 - 17:04:12
@Rich, it depends how you represent the number. I was treating it as though you were just adding a new power of 10 to the integer, in which case 11 would be 11,111,111,111. 2^32-1 (the max value in a 32 bit unsigned int) is 4,294,967,295. So representing unary in decimal is inefficient. You could, of course, represent it in binary, incrementing with a bitwise left shift and output the number as a string by using some simple logic in, which case you could represent up to 32 in unary with an unsigned 32 bit int.
Lintah_Cyberon July 13 2012 - 01:55:56
20
hc1984on July 18 2012 - 13:18:16
10-84 Cape 10-63 10-4 :ninja:
Post Comment

Sorry.

You must have completed the challenge Basic 1 and have 100 points or more, to be able to post.