CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content |Store| Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Base 8"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange This and that Topic #656
Reading Topic #656
DMays
guest
Nov-22-05, 10:37 PM (EST)
 
"Base 8"
 
   I need your help. I was told that this number is in code, possibly Base 8. I need to convert this number string to another number that might possibly be GPS coordinates. If any of this makes sense to you, and you can help, it would be appreciated. Thanks in advance.

124157040146151156144040164150145040143141143150145054040147157040163164141156144040165156144145162040164150145040104157165147150142157171047163040142141171157156145164054040164150145156040147157040056065066040155151154145163040157156040141040142145141162151156147040157146040061060062040144145147162145145163040164162165145


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

  Subject     Author     Message Date     ID  
Base 8 DMays Nov-22-05 TOP
  RE: Base 8 alexb Nov-22-05 2
     RE: Base 8 Deep G Nov-24-05 3
         RE: Base 8 alexb Nov-24-05 4
             RE: Base 8 DMays Nov-30-05 5
                 RE: Base 8 mr_homm Dec-01-05 6
  RE: Base 8 DMays Dec-13-05 7

Conferences | Forums | Topics | Previous Topic | Next Topic
alexb
Charter Member
1714 posts
Nov-22-05, 11:43 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
2. "RE: Base 8"
In response to message #0
 
   Well, in base 10 the number is

6565762620925232540521055199468436989024632287847668387873628141152272309360607800382356977712689504762801665729217809392912979638727439174630392146755470053371292813963895738462584388710428343667676105320793654367313480024211155400232208744203953156464124855205963463938591363635589379844709


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Deep G
Member since Nov-6-05
Nov-24-05, 10:41 AM (EST)
Click to EMail Deep%20G Click to send private message to Deep%20G Click to view user profileClick to add this user to your buddy list  
3. "RE: Base 8"
In response to message #2
 
   Hi,

Could you please explain how did you convert such a huge number from base 8 to base 10? I can see that conversion from one base to the other when both of them are some integral powers of 2 is easy. But what about a base which is not anintegral power of 2. Is there a general approach that could be followed while converting between arbitrary bases?

:o)
Regards,
Deep G


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1714 posts
Nov-24-05, 10:55 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
4. "RE: Base 8"
In response to message #3
 
   The algorithm for base conversion does not depend on the size of the numbers. Its implementation may. For the algorithm itself, please search this site.

As to the implementation, Java has a class BigInteger that accepts strings of arbitrary length. So in Java, it was pretty simple:

BigInteger bi = new BigInteger(yourNumberString, 8); // octal system
print(bi.toString(10)); // decimal system

Now, this probably won't satisfy your curiosity. For, the explanation begs a question, "And how the class BigInteger has been implemented?"

Well, I do not know the details, but can imagine a possibility of having a sequence of integers where each member is considered as a "big digit". For example, you can store numbers in triples of digits. Say, 1234567770 could be stored as

770 + 567·103 + 234·106 + 1·109, or as, say,

(1, 9), (234, 6), (567, 3), (770, 0)

Multiplication and division over such explicit'sequences can certainly can be devised, although, again, the implementation may be tedious.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
DMays
guest
Nov-30-05, 11:53 AM (EST)
 
5. "RE: Base 8"
In response to message #4
 
   I still need to know if there is a way to convert the above number string into coordinates that will be similar to these:

N 35 08.837 W 089 59.569


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Dec-01-05, 07:52 AM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
6. "RE: Base 8"
In response to message #5
 
   The number you have posted is long enough that it is probably possible to extract clues about how to decode it by checking for internal patterns. The most obvious way is to compute its autocorrelation function. Look for peak values in the autocorrelation to find periodic patterns of digits. This gives a clue as to how to break up the long number into shorter messages, each of which should be some kind of geographic coordinates. To calculate the autocorrelation, make two copies of your number, and in the second copy, shift all the digits n steps to the right and wrap the last n digits back to the beginning of the number (basically, roll the number to the right by n digits). Then place the new number directly below the original number, and multiply each digit in the shifted number with the digit directly above it, and add up all the individual products you get this way. What you get is A(n), the autocorrelation with a shift of n. Do this for all n's starting from n=0 up to n = length of your number. Graph what you get and look for peaks in the graph. The position of the first sharp peak shows that the number contains some kind of repeating pattern, and the length of the pattern is equal to the value of n where the peak occurs.

The latitude, in the degrees and decimal arcminutes format you have mentioned, will need to represent numbers up to 180 degrees, which will require 8 binary digits (since 2^8 is the first power of 2 which is larger than 180), and upto 59.999 minutes, which will require 16 binary digits (since 2^16 = 65536 is the first power of 2 which is larger than 59,999). Altogether the numbers will require 24 digits, and at least one extra digit to represent N or S. The longitude coordinate is similar. Therefore, each coordinate pair will require a minimum of 50 binary digits, and perhaps more if there are some start and stop code numbers. Since 3 binary digits is one base 8 digit, this means that each coordinate pair must be at least 13 digits long. Its actual length may be longer if there are any "filler numbers."

Then, within each shorter message, look for key number combinations that probably represent N S E and W. These would be expected to be in similar positions within each message, and in each position, there should only be two values, representing N or S in the first postion, and E or W in the second. Also, it is possible that the number values will be signed, with plus representing N and E, and minus representing S and W. The representation of signed numbers can be done with either sign/magnitude or with 2's complement format, which requires converting the base 8 digits into binary. Either of these formats will start with a binary digit 1 if negative and 0 if positive. A base 8 digit "7" represents three 1's in a row, and so is likely (but not certain) to be the start of a negative number.

This is basically a lesson in codebreaking, since you don't have direct knowledge of how the geographical coordinates are encoded in the number string. The best thing to do, of course, is to simply ask the person responsible for the number string what the encoding is, but I assume you can't do that, or you wouldn't be asking here. There is much more to codebreaking than what I have said here, and much more in fact that I do not know (I'm only an amateur). One thing I do know is that codebreaking can be a LOT of work! And you're never really sure you've got it right until you can try your decoding method on a fresh number string from the same source.

Hope this helps,

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
DMays
guest
Dec-13-05, 03:11 PM (EST)
 
7. "RE: Base 8"
In response to message #0
 
   Thanks everyone for your help, we have solved the puzzle. The number string was a list of three digit ASCII code that needed to be converted from Octal to Character format.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK