Algoritm

From Geohashing
Revision as of 06:24, 3 October 2010 by imported>Llavids
Algoritmen

Den här gången var det vi som uppfann algoritmen!

Du behöver inte förstå detta för att kunna ge dig ut på geohashäventyr.

  • Dagens datum i formatet yyyy-mm-dd och det dagliga öppningspriset av Dow Jones Industrial Average (enligt finance.google.com) sätts ihop, med en apostrof emellan.
    • Väster om 30° västlig grad: Om det inte finns nåt öppningspris från Dow Jones den dagen används priset från föregående aktiva dag istället.
    • Öster om 30° västlig grad: Samma som väster, fast gårdagens pris används, oavsett om ett nytt blir tillgängligt senare på dagen i just den tidszonen. Det vill säga torsdag använder onsdagens öppning, fredag använder torsdagens och lördag till måndag använder fredagens öppningspris. (kolla 30W Time Zone Rule)
  • Resultatet körs sedan genom den väldokumenterade kryptografialgoritmen MD5 för att generera en pseudoslumpmässig (men ändå lätt verifierade) "hash" av storlek 32 hexadecimala siffror.
  • Hashen delas sedan upp i två delar med 16 siffror vardera.
  • Varje del får ett komma framför sig (så det blir ett decimaltal) och konverteras till basen 10.
  • Dessa decimaltal läggs till heltalsvärdena (latitud och longitud) för varje given kvadrant och bildar därmed dagens resmål.

Beräkningshjälp

Särdrag

Det finns ett antal resultat vid applicerande av algoritmen som kanske inte är uppenbara vid en första anblick, men som innebär intressant tankeexperiment och kanske ännu mer intressant bedrifter vid bizarra eller äventyrliga scenarier.

  • Koordinaterna vid den första meridianen är speglade istället för att följa rutmönstret. Det innebär att ett lågt longitudvärde (säg 0,001) kan göra så att två punkter hamnar väldigt nära varandra på varsin sida om 0°. Här borde det var 111:e dag bli två punkter inom en kilometer ifrån varandra. Ekvatorn har samma fenomen, och skärningen mellan dessa kan göra att fyra punkter hamnar väldigt nära varandra. Detta är tyvärr mitt ute i Atlanten.
  • Den 30W och den 180:e meridianen är inte lika speciella, de har helt enkelt helt oberoende punkter. De kan vara godtyckligt nära varandra eller upp till två kvadrantdiagonaler ifrån varandra. De interagerar med ekvatorn på samma sätt som ovan.
  • Däremot leder interaktionen mellan den 180:e meridianen och den internationella datumlinjen till en del intressanta observationer. Där de bryter varandra kan upp till tre hashpunkter vara väldigt nära varandra, till och med långt ifrån ekvatorn. Om man står precis väst om 180E, lite lite öster om datumlinjen så kan man vara på hashen till 179E från "idag" med hashen för 179E "imorgon" precis väster om dig och hashen för "idag" i 179W precis öster om dig. Chansen att få tre olika slumpmässiga koordinater att komma nära varandra på detta sätt är av en helt annan magnitud än det förra fallet.
  • Datumlinjen kan också göra så att en enda kvadrant kan innehålla två (eller inga) hashpunkter vid en given tidpunkt beroende på vilken sida av linjen punkterna för de två dagarna hamnar. Detta kan hända var som helst som linjen delar en kvadrant i två.
  • Kvadranter är som mest kvadratiska vid ekvatorn medan de vid polerna är ungefär 2 km * 111 km höga trianglar. Om du lyckas besöka någon av polerna, vilket i sig själv bevisar att "Mother Nature Is Your Bitch" så borde du kunna besöka väldigt många kvadranter inom ett väldigt kort tidsspann. På grund av 30W-regeln kommer hashpunkterna vara delade i två delar som utgör ojämna halvor av två olika stora 360-goner. Som sämst måste man då resa 700 km för att besöka alla 360 punkter, medan de rent teoretiskt kan hamna hur nära varandra som helst (28 juli 2008 var värdena 0,985 och 0,855, vilket satte 150 punkter bara 4,4 km ifrån varandra vid nordpolen och de resterande 210 längs en lite större 59 km båge bara 14,4 km bort. Det hade räckt att resa 78 km för att nå dem alla!).

Q: Jag försökte använda min md5sum från unit/linux kommandoprompt och hashen var inte samma som serien. Vad är korrekt?

A: Du glömde antagligen "-n" (echo utan ny rad). Testa detta för att matcha exemplet:
echo -n 2005-05-26-10458.68 | md5sum
Kommandot md5sum kan också kallas md5.

Implementationer

Om du inte vill göra beräkningarna själv så behövs det inte. An lista med referenser och praktiska implementationer finns på implementationssidan.

Kända problem

Flera kända problem listas här. Det finns en pågående diskussion om dessa och flera andra här: Talk:Main Page.

Slumpmässighet

slumpsimulering: klicka för att förstora

Några personer har ifrågasatt algoritmens slumpmässighet. För att analysera denna fråga skrevs ett litet python program som använder algoritmen för att skjuta på ett fönster genom att göra träffade pixlar röda. Här är resultatet: Bakgrunden är svart, en pixel blir ljusare ju fler gånger den träffas. Om du ser någon som helst system eller ett mönster kolla på A Beautiful Mind och anmäl dig till en passande institution.