{"id":1997,"date":"2018-03-29T12:44:02","date_gmt":"2018-03-29T09:44:02","guid":{"rendered":"http:\/\/spektrum.fi\/spektraklet\/?p=1997"},"modified":"2018-03-29T12:44:02","modified_gmt":"2018-03-29T09:44:02","slug":"allt-storre-flugsmallor-for-allt-mindre-flugor","status":"publish","type":"post","link":"http:\/\/spektrum.fi\/spektraklet\/allt-storre-flugsmallor-for-allt-mindre-flugor\/","title":{"rendered":"Allt st\u00f6rre flugsm\u00e4llor f\u00f6r allt mindre flugor"},"content":{"rendered":"<p style=\"text-align: center;\"><strong>Varning: Detta inl\u00e4gg inneh\u00e5ller extremt d\u00e5lig Java-kod.<br \/>\nL\u00e4s p\u00e5 egen risk.<\/strong><\/p>\n<p>Den som n\u00e5n g\u00e5ng har l\u00e4st Reddit-sidan ProgrammerHumor har kanske lagt m\u00e4rke till tendenserna att hitta p\u00e5 alldeles absurda l\u00f6sningar till mycket simpla problem eller koncept.<br \/>\nTill exempel, f\u00f6r cirka 9 m\u00e5nader sedan var volume sliders ett \u00e5terkommande sk\u00e4mt och d\u00e4rav skapades m\u00e5nga vackra implementationer, bl.a:<\/p>\n<ul>\n<li><a href=\"https:\/\/i.redd.it\/xwlb42y2nx2z.gif\">Veva upp ljudniv\u00e5n<\/a><\/li>\n<li><a href=\"https:\/\/i.redd.it\/yv6vv2vvt43z.gif\">Pumpa upp ljudniv\u00e5n<\/a><\/li>\n<li>L\u00e5t anv\u00e4ndaren demonstrera:<\/li>\n<\/ul>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter size-medium\" src=\"https:\/\/i.redd.it\/012cukejqs1z.png\" width=\"688\" height=\"472\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>Mer nyligen var temat om hur man &#8221;effektivast&#8221; kollar om ett givet heltal \u00e4r j\u00e4mnt eller udda. Funktioner som \u00e5stadkommer detta \u00e4r l\u00e4ttare att implementera \u00e4n volume sliders, s\u00e5 motiverad av mina nyfunna kunskaper i Tira (Tietorakenteet ja algoritmit) best\u00e4mde jag mig naturligtvis f\u00f6r att testa n\u00e5gra i Java. Metoderna nedan \u00e4r inspirerade av b\u00e5de ProgrammerHumor och egna id\u00e9er. N\u00e5gra av dem kan kr\u00e4va kunskap om Java eller talteori f\u00f6r att f\u00f6rst\u00e5, s\u00e5 en TL;DR i meme- format finns l\u00e4ngst ner f\u00f6r dem som inte bryr sig om tekniska detaljer.<\/p>\n<h5>Metod 1: Divisionsrest<\/h5>\n<p>Kolla talets divisionsrest med 2. Om resten \u00e4r 0, s\u00e5 \u00e4r talet j\u00e4mnt, annars udda.<\/p>\n<ul>\n<li>Tr\u00e5kig normie l\u00f6sning<\/li>\n<li>Anv\u00e4nder inte ens rekursion<\/li>\n<\/ul>\n<pre>public boolean isEven1(int n) {\r\n    return n % 2 == 0;\r\n}<\/pre>\n<h5>Metod 2: Sista siffran<\/h5>\n<p>Vi unders\u00f6ker talets sista siffra. Om den \u00e4r 1, 3, 5, 7 eller 9 \u00e4r talet udda, annars j\u00e4mnt. Javas indexOf()- metod f\u00f6r listor returnerar -1 ifall det s\u00f6kta objektet inte hittas i listan. D\u00e5 g\u00f6r vi ju s\u00e5 klart en lista av de udda siffrorna och kollar om metoden ger -1 f\u00f6r talets sista siffra.<\/p>\n<ul>\n<li>Beh\u00f6ver inte utf\u00f6ra n\u00e5n \u00e4cklig aritmetik<\/li>\n<li>Konstant tidskomplexitet, fortfarande helt f\u00f6r effektiv<\/li>\n<\/ul>\n<pre>public boolean isEven2(int n) {\r\n    List&lt;Character&gt; lastDigits\r\n        = Arrays.asList('1', '3', '5', '7', '9');\r\n    String number = Integer.toString(n);\r\n    char last = number.charAt(number.length() - 1);\r\n    \r\n    return lastDigits.indexOf(last) == -1;\r\n}<\/pre>\n<h5>Metod 3: Induktion<\/h5>\n<p>Vi anv\u00e4nder oss av matematisk induktion. Allm\u00e4nt g\u00e4ller att 0 \u00e4r ett j\u00e4mnt tal, efter varje j\u00e4mnt tal f\u00f6ljer ett udda, och efter varje udda f\u00f6ljer ett j\u00e4mnt. Vi bygger allts\u00e5 iterativt upp en array av booleans tills vi n\u00e5tt det n:te elementet, som vi returnerar. Dock f\u00f6r att undvika en OutOfMemoryError m\u00e5ste vi tyv\u00e4rr fuska lite och emellan\u00e5t skriva \u00f6ver gamla v\u00e4rden.<\/p>\n<ul>\n<li>O(n) tidskomplexitet. Fr\u00e5n Tira vet vi ju att O(n) \u00e4r bra.<\/li>\n<li>Induktionen kr\u00e4ver antagandet att 0 \u00e4r ett j\u00e4mnt tal.\u00a0 Detta kan verifieras med en av de andra metoderna.<\/li>\n<\/ul>\n<pre>public boolean isEven3(int n) {\r\n    n = n &lt; 0 ? -n : n;        \/\/g\u00f6r n positivt\r\n    int idx = 0;\r\n    boolean isCurrentEven = true;\r\n \r\n    boolean[] evenOdd = new boolean[10000];\r\n    while (idx &lt;= n) {\r\n        if (idx == 10000) {\r\n            idx -= 10000;\r\n            n -= 10000;\r\n        }\r\n \r\n        evenOdd[idx] = isCurrentEven;\r\n        isCurrentEven = !isCurrentEven;\r\n        idx++;\r\n    }\r\n    return evenOdd[idx - 1];\r\n}<\/pre>\n<h5>Metod 4: Overflow<\/h5>\n<p>Alla vet ju att rekursion \u00e4r bra, s\u00e5 h\u00e4r har vi en h\u00e4rlig blandning av rekursion och error handling.<\/p>\n<p>Vi antar som baskunskap att Javas Integer.MAX_VALUE,<br \/>\ndvs. 2^31 &#8211; 1, \u00e4r ett udda tal. Detta kan igen verifieras med n\u00e5gon annan metod.<br \/>\nOm\u00a0 n = 2^31 &#8211; 1 \u00e4r n udda. Annars kallar vi rekursivt p\u00e5 funktionen med parametern n + 2. S\u00e5 klart, om n \u00e4r ett j\u00e4mnt tal borde den eventuellt hoppa \u00f6ver 2^31 &#8211; 1 och orsaka en OverflowException. Men eftersom Java hanterar den h\u00e4r situationen utan att klaga, m\u00e5ste vi anv\u00e4nda Math.addExact()- metoden som explicit ger en Exception ifall vi g\u00e5r \u00f6ver 2^31 &#8211; 1.<\/p>\n<p>Rekursionen upprepas i v\u00e4rsta fall ca 2^30 g\u00e5nger, s\u00e5 en StackOverflowError orsakas l\u00e5ngt f\u00f6re det. Vid detta skede avbryter vi rekursionen och startar om med en hj\u00e4lpvariabel som s\u00e4ger hur l\u00e5ngt vi kommit f\u00f6rut.<\/p>\n<ul>\n<li>O(2^31 &#8211; n) tidskomplexitet. St\u00f6rre tal f\u00e5r snabbare svar.<\/li>\n<li>isEven4(1200000000) svarade\u00a0<em>true<\/em> p\u00e5 endast 23 sekunder.<\/li>\n<\/ul>\n<pre>int offset;\r\n \r\npublic boolean increment(int n) {\r\n    if (n == Integer.MAX_VALUE) {\r\n        return false;\r\n    }\r\n    try {\r\n        n = Math.addExact(n, 2);\r\n        offset += 2;\r\n        return increment(n);\r\n    } catch (ArithmeticException e) {\r\n        return true;\r\n    }\r\n}\r\n \r\npublic boolean isEven4(int n) {\r\n    offset = 0;\r\n    while (true) {\r\n        try {\r\n            return increment(n + offset);\r\n        } catch (StackOverflowError e) {\r\n            \/\/inget fel h\u00e4r, moving on...\r\n        }\r\n    }\r\n}<\/pre>\n<h5>Metod 5: Goldbach<\/h5>\n<p>En v\u00e4lk\u00e4nd hypotes inom talteorin \u00e4r den s.k. <a href=\"https:\/\/en.wikipedia.org\/wiki\/Goldbach%27s_conjecture\">Goldbach Conjecture<\/a>, som s\u00e4ger att varje j\u00e4mnt tal st\u00f6rre \u00e4n 2 kan uttryckas som summan av tv\u00e5 primtal. Resultatet har inte bevisats f\u00f6r godtyckligt stora j\u00e4mna tal, men det har verifierats med dator f\u00f6r tillr\u00e4ckligt stora tal f\u00f6r v\u00e5ra \u00e4ndam\u00e5l.<br \/>\nDet enda j\u00e4mna primtalet \u00e4r 2, dvs det st\u00f6rsta j\u00e4mna talet som kan uttryckas som summan av tv\u00e5 j\u00e4mna primtal \u00e4r 4. Allts\u00e5 om v\u00e5rt tal \u00e4r st\u00f6rre \u00e4n eller lika med 6 s\u00f6ker vi udda primtal vars summa \u00e4r v\u00e5rt givna tal. Annars unders\u00f6ker vi talet med Metod 4.<\/p>\n<p>Hur kan vi d\u00e5 visa att ett givet tal \u00e4r ett primtal? Vi anv\u00e4nder s\u00e5 klart <a href=\"https:\/\/en.wikipedia.org\/wiki\/Wilson%27s_theorem\">Wilson&#8217;s Theorem<\/a>. Enligt denna sats \u00e4r\u00a0n<strong>\u00a0<\/strong>ett primtal om och endast om talets (n-1)! divisionsrest med n \u00e4r n-1, dvs.<br \/>\n<img decoding=\"async\" class=\"mwe-math-fallback-image-inline\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/ff827e87d7b2ed57555f91066c10519c8c99954d\" alt=\"(n-1)!\\ \\equiv\\ -1 \\pmod n\" \/><br \/>\nTill detta \u00e4ndam\u00e5l har vi hj\u00e4lpfunktionerna modFactorial och isPrime.<\/p>\n<ul>\n<li>Antagligen O(n^3) tidskomplexitet. Funktionen modFactorial \u00e4r O(n) och isEven5 har en dubbel loop.<\/li>\n<li>K\u00f6rtiden varierar kraftigt mellan udda och j\u00e4mna tal av ungef\u00e4r samma storlek:<br \/>\nisEven5(4000) gav\u00a0<em>true\u00a0<\/em>p\u00e5 2 sekunder\u00a0och isEven5(4001) gav\u00a0<em>false<\/em> p\u00e5 cirka 15 sekunder.<br \/>\nisEven5(10000) gav\u00a0<em>true<\/em> efter 30 sekunder. Hur l\u00e4nge tog det f\u00f6r isEven5(10001)?<br \/>\n<img decoding=\"async\" loading=\"lazy\" class=\"alignnone size-medium\" src=\"https:\/\/i.gyazo.com\/bbc419f04ef9a718bb86d1212eded766.png\" width=\"409\" height=\"78\" \/><\/li>\n<li>Anv\u00e4nd allts\u00e5 den h\u00e4r metoden om du redan anar att ditt tal \u00e4r j\u00e4mnt!<\/li>\n<\/ul>\n<pre>public int modFactorial(int p, int mod) {\r\n    if (p &lt; 1) {\r\n        return -1;\r\n    }\r\n    long n = 1;\r\n    for (int i = 1; i &lt;= p; i++) {\r\n        n = n*i % mod;\r\n    }\r\n    return (int) n;\r\n}\r\n \r\npublic boolean isPrime(int n) {\r\n    if (n &lt; 2) {\r\n        return false;\r\n    } else {\r\n        return modFactorial(n - 1, n) == n - 1;\r\n    }\r\n}\r\n \r\npublic boolean isEven5(int n) {\r\n    n = n &lt; 0 ? -n : n; \/\/g\u00f6r n positivt\r\n    if (n &lt; 6) {\r\n        return isEven4(n);\r\n    }\r\n \r\n    for (int i = 3; i &lt; n; i++) {\r\n        if (!isPrime(i)) {\r\n            continue;\r\n        }\r\n        for (int j = 3; j &lt;= i; j++) {\r\n            if (!isPrime(j)) {\r\n                continue;\r\n            }\r\n            if (i + j == n) {\r\n                return true;\r\n            }\r\n        }\r\n    }\r\n    return false;\r\n}<\/pre>\n<p>H\u00e4r tog kreativiteten och\/eller t\u00e5lamodet slut, f\u00f6r om vi vill kan vi g\u00f6ra godtyckligt &#8221;effektiva&#8221; algoritmer, men de \u00e4r inte n\u00f6dv\u00e4ndigtvis s\u00e5 intressanta. Men nu har vi ju jobbat under premissen att v\u00e5r metod ska ge ett svar f\u00f6r just det talet vi stoppar in, och att svaret ska vara r\u00e4tt. Vad om vi \u00e4ndrar p\u00e5 spelreglerna lite? En bonusmetod, isEven6, hittas under l\u00e4nken l\u00e4ngst ner.<\/p>\n<p>Det h\u00e4r inl\u00e4gget kunde tolkas b\u00e5de som en uppmuntran och en varning. Avsiktligt d\u00e5lig kod kan vara v\u00e4ldigt underh\u00e5llande och l\u00e4ra en t\u00e4nka p\u00e5 problem p\u00e5 nya s\u00e4tt (om det h\u00e4r \u00e4r en bra eller d\u00e5lig sak \u00e4r upp till l\u00e4sarens tolkning). \u00c5 andra sidan \u00e4r dessa metoder det oundvikliga resultatet av att spendera helt f\u00f6r mycket tid p\u00e5 Tira.<\/p>\n<h3>TL;DR<\/h3>\n<p><a href=\"https:\/\/i.imgur.com\/TUYX6Tq.jpg\">https:\/\/i.imgur.com\/TUYX6Tq.jpg<\/a><\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Varning: Detta inl\u00e4gg inneh\u00e5ller extremt d\u00e5lig Java-kod. L\u00e4s p\u00e5 egen risk. Den som n\u00e5n g\u00e5ng har l\u00e4st Reddit-sidan ProgrammerHumor har kanske lagt m\u00e4rke till tendenserna att hitta p\u00e5 alldeles absurda l\u00f6sningar till mycket simpla problem eller koncept. Till exempel, f\u00f6r cirka 9 m\u00e5nader sedan var volume sliders ett \u00e5terkommande sk\u00e4mt och d\u00e4rav skapades m\u00e5nga vackra &hellip; <a href=\"http:\/\/spektrum.fi\/spektraklet\/allt-storre-flugsmallor-for-allt-mindre-flugor\/\" class=\"more-link\">Forts\u00e4tt l\u00e4sa <span class=\"screen-reader-text\">Allt st\u00f6rre flugsm\u00e4llor f\u00f6r allt mindre flugor<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":21,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[87,5],"tags":[122,53,76,123,57,124,125],"_links":{"self":[{"href":"http:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/posts\/1997"}],"collection":[{"href":"http:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"http:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/comments?post=1997"}],"version-history":[{"count":10,"href":"http:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/posts\/1997\/revisions"}],"predecessor-version":[{"id":2016,"href":"http:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/posts\/1997\/revisions\/2016"}],"wp:attachment":[{"href":"http:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/media?parent=1997"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/categories?post=1997"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/tags?post=1997"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}