Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Converting a number back to its positional values

  1. Apr 29, 2015 #1
    In positional notation, say I have a number like this in base- 10

    73901=7×104 +3×103 +9×102 +0×101 +1×100
    it's pretty obvious how to go back and forth from the number to positional notation.

    So if someone gave me a new number like 234 I can easily know

    23410 = 2×102 + 3×101 + 4×100

    However say you have a number in a different base like base-42

    2×422 + 5×421 + 13×420 = 375142

    Is there a general procedure for determining the positional values from the number? Say someone gave me 375142, how can I go backwards to find the exact values that the number is made of in that base?
     
    Last edited: Apr 29, 2015
  2. jcsd
  3. Apr 29, 2015 #2

    phinds

    User Avatar
    Gold Member
    2016 Award

    If you are saying that someone gives you 3751 DECIMAL and you are supposed to convert it to base 42, then you just have to do the calculations. If someone gives you 3751 in base 42, then it is 3751.
     
  4. Apr 29, 2015 #3

    Mentallic

    User Avatar
    Homework Helper

    [tex]3751_{10} = 25(13)_{42}[/tex]

    where the subscript is the base number, and 13 is enclosed in brackets to denote it should be a single digit. In hexadecimal (base 16) the numbers 10-15 are given the letters A-F respectively, so you could represent it as

    [tex]3751_{10}=25D_{42}[/tex]

    granted that the reader understands D represent 13 in hexadecimal, but then you still have the problem of not being able to represent the numbers 16-41. You could of course concoct a method to do so, such as extending it to use the entire alphabet, and then letters from other alphabets etc.

    As phinds said, converting from one base to another requires calculations though. It's not as clear-cut.
     
  5. Apr 29, 2015 #4
    Sorry guys I forgot the subscripts on my numbers to indicate what base they are in.

    I'm not interested to convert form one base to another. I'm staying in the same base (say base 42) and I want to reconstruct the positional notation that was used to get the number. Is that possible?

    So without knowing the positional notation for 375142 is there a way to reconstruct it like we can for base 10 numbers?
     
  6. Apr 29, 2015 #5

    Mentallic

    User Avatar
    Homework Helper

    Well now that you've gone back and changed it

    This is not a valid equality. The expression on the left side is equal to [itex]3751_{10}[/itex] but [itex]3751_{10}\neq 3751_{42}[/itex] or 3751 in any other base.

    For any base b,

    [tex](a_na_{n-1}a_{n-2}...a_1a_0)_b = a_nb^n+a_{n-1}b^{n-1}+...+a_1b+a_0[/tex]

    Which is exactly what you did in decimal, so you have to follow the same rules for any other base, such as

    [tex]3751_{42}=3\times 42^3 + 7\times 42^2 + 5 \times 42 + 1[/tex]

    and

    [tex]2\times 42^2 + 5\times 42 + 13 = 25D_{42}[/tex]

    which I explained in my previous comment.
     
  7. Apr 30, 2015 #6
    I think I understand now, I'll explain further what I'm trying to do, can you tell me if I'm on the right track?
    I'm trying to encrypt strings of alphabetic characters using format preserving encryption.

    So say my vocabulary of strings consist of only these 7 characters A,B,C,D,E,F,G, where A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7

    To encrypt the word CDG I know in base 7 it is 2367.
    This equals 2x72 + 3x71 + 6x70 = 12510 (is this right so far?)

    For a 3 letter word, to encrypt with a result also as a 3 letter word my total possible values for the result range from 0 to 7N - 1 = 0 to 342 (where N is the number of characters)

    Passing the base 10 representation through the Encryption function (with the range of allowed values)
    I get E(125) => 22110

    221 is also in base 10 so in order to go back to represent that number in the original scheme (base 7) I need to convert it to base 7
    so 22110 = 4347
    This would equal EDE.

    Does this make sense?
     
  8. Apr 30, 2015 #7

    Mark44

    Staff: Mentor

    No. In base-7, there are 7 digits: 0, 1, 2, 3, 4, 5, and 6.

    710 would be 107.

    Since you have 8 symbols (0, 1, 2, ..., 6, 7) base-8 would be appropriate.
     
  9. Apr 30, 2015 #8
    Yes that's correct, sorry. I'll edit my post to remove the extra character H from the sequence. (Or if someone can do it for me since it seems the edit option is no longer present)

    So did I do the calculation correctly?
     
  10. Apr 30, 2015 #9

    Mentallic

    User Avatar
    Homework Helper

    Well considering you're the student here, making mistakes and leaving them as they are is fine. It also helps with the flow of conversation to leave it. If someone in the future decided to read through the entire thread because they're having the same problem, then answers that are quoting something that isn't there any more would get confusing.

    Remove the letter H=7 and you're all good.

    I lost you here. Where did 221 come from?
     
  11. Apr 30, 2015 #10
    Since I don't have my encryption function developed yet, I just made that number up, so 221 is just a hypothetical result of the encryption in the range between 0 and 7N - 1
     
  12. Apr 30, 2015 #11

    jbriggs444

    User Avatar
    Science Advisor

    Will the encryption function operate on numbers or on strings of decimal digits?

    Edit: Removed commentary.

    The usual algorithm for converting a number to a string of digits in a particular radix is a loop. Divide by the radix and take the remainder. That is the low order digit of the result. Retain the quotient and repeat.

    So if you have the number 221 and you wish to convert it to base 7, you would take 221/7 which is 31 with a remainder of 4. The low digit is 4.

    Now take 31/7 which is 4 with a remainder of 3. The next lowest digit is 3.

    Now take 4/7 which is 0 with a remainder of 4. The high order digit is 4.

    22110 = 4347

    Check to verify: 4x72 + 3x71 + 4 = 196 + 21 + 4 = 221
     
    Last edited: Apr 30, 2015
  13. Apr 30, 2015 #12
    It will operate on numbers only not alphabetics, where the number represents the entire string (not individual characters within it - I'm not sure if that answers your question.

    Thank you for describing how to get the number as it is represented in positional notation. That was the final step.
     
    Last edited: Apr 30, 2015
  14. Apr 30, 2015 #13

    Mark44

    Staff: Mentor

    This seems pretty straightforward to me. You have an alphabet of, say 7 letters, A, B, C, D, E, F, G.
    1. For a given message of these 7 letters, there's a one-to-one map between a string of letters and a number in base-7. For example, the string CAB would be 2017
    2. Encrypt the number string. Presumably each digit 0...7 will be transformed to another digit in this same set. For example, 2017 might go to 3127, with the encoding being n -> (n + 1) mod 7. Here 0 -> 1, 1 -> 2, ... and 6 -> 0 (i.e., wraps around). The encrypted word would be DBC. As long as the encryption scheme works on a single digit at a time, it is a one-to-one operation, hence it is invertible, which is what you want so that you can decrypt an encrypted message.
    3. To decrypt a word perform the reverse operation as was done to encrypt the word. In my example, we subtract 1 (modulo 7) from the digit. So 0 -> 6, 1 -> 0, 2 -> 1, 3 -> 2, and so on. In my example, 3127 -> 201.
    4. From the number string, write the letters, which in this case would be CAB.

    This system will work as long as you are working in a base the same size as the number of letters in your alphabet.
     
  15. Apr 30, 2015 #14

    jbriggs444

    User Avatar
    Science Advisor

    Why go through all that rigamarole? The base 7 is not contributing anything to that scheme. It is still a [very] simple substitution cipher.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Converting a number back to its positional values
Loading...