Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (753) Games in Android Showcase (228) games submitted by our members Games in WIP (842) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 The Wrath of Ackermann  (Read 10773 times) 0 Members and 1 Guest are viewing this topic.
ctomni231

JGO Wizard

Medals: 99
Projects: 1
Exp: 7 years

Not a glitch. Just have a lil' pixelexia...

 « Posted 2014-07-07 06:47:48 »

Ackermann's Function

For those too lazy to go through that video, this topic is about Ackermann's function. Literally a function to prove that even computing has its limits. The recursive case in Ackermann's function is pretty simple and can be written in a few lines of code.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22 `public class ackermann {   public static void main(String[] args){      for(int i = 0; i < 6; i++){         for(int j = 0; j < 6; j++){            System.out.printf("ackerman (%d, %d) is: %d\n", i, j, ack(i, j));         }      }   }        private static int ack(int m, int n){      int ans;      if (m == 0)         ans = n+1;      else if (n == 0)         ans = ack(m-1, 1);      else         ans = ack(m-1, ack(m, n-1));            return ans;   }}`

However, this does a number on processing machines, with A(4,2) taking ages to compute on even the most powerful machines. (With Java, I had to do a bit more to avoid stack overflow errors...) I think before we even think about tackling the universe, I'm actually curious about how deep into Ackmermann's function we can calculate today before our computer's die from the processing strain. No matter how much I optimized, we just couldn't think of a good way to calculate past A(4,2)...

Any thoughts or takers?

Roquen

JGO Kernel

Medals: 517

 « Reply #1 - Posted 2014-07-07 08:14:29 »

Well uncomputable functions and undecidable/unsolvable problems are called that for a good reason.  Busy beaver is a fun example.
Roquen

JGO Kernel

Medals: 517

 « Reply #2 - Posted 2014-07-07 08:31:20 »

Wait.  Past A(4,2)?  A(4,2) requires 2^16 bits (assuming unsigned).
ags1

JGO Kernel

Medals: 363
Projects: 7

Make code not war!

 « Reply #3 - Posted 2014-07-07 08:35:25 »

I guess a 99.9% approximation of this function would be blindingly fast. After, even common functions like sin() or cos() are only calculated to a certain degree of precision.

pjt33

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

 « Reply #4 - Posted 2014-07-07 09:14:28 »

No matter how much I optimized, we just couldn't think of a good way to calculate past A(4,2)...

Any thoughts or takers?
Depends what you mean by calculate. For m > 2, A(m, n) + 3 = 2 → (n+3) → (m − 2) = 2 → (2 → (n+2) → (m − 2)) → (m − 3) = 2 → (A(m, n − 1) + 3) → (m − 3), so in particular A(4, n) + 3 = 2A(4, n − 1) + 3. If you want to calculate that naïvely as a list of bits, you'll run into trouble. But selecting the correct representation of your data is the first thing to learn in computing.
Riven

« JGO Overlord »

Medals: 1336
Projects: 4
Exp: 16 years

 « Reply #5 - Posted 2014-07-07 12:51:06 »

Super-duper fast: (until 64 bit overflow)
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56 `public class Ackermann {   private static final int MAX = 5;   public static void main(String[] args) {      for(int i = 0; i < MAX; i++) {         for(int j = 0; j < MAX; j++) {            long t0 = System.nanoTime();            long got = ack(i, j);            long t1 = System.nanoTime();            System.out.printf("ackerman (%d, %d) is: %d (took: %d micros)\n", i, j, got, (t1 - t0) / 1000);         }      }   }   private static long ack(long m, long n) {      if(m == 0)         return m0(n);      if(m == 1)         return m1(n);      if(m == 2)         return m2(n);      if(m == 3)         return m3(n);      long ans;      if(m == 0)         ans = n + 1;      else if(n == 0)         ans = ack(m - 1, 1);      else         ans = ack(m - 1, ack(m, n - 1));      return ans;   }   private static long m0(long n) {      return n + 1;   }   private static long m1(long n) {      return n + 2;   }   private static long m2(long n) {      return n * 2 + 3;   }   private static long m3(long n) {      long sum = 1;      for(int i = 0; i <= n; i++)         if((sum = (sum << 1) + 3) < 0L)            throw new IllegalStateException("64 bit overflow");      return sum;   }}`

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 `ackerman (0, 0) is: 1 (took: 2 micros)ackerman (0, 1) is: 2 (took: 0 micros)ackerman (0, 2) is: 3 (took: 0 micros)ackerman (0, 3) is: 4 (took: 0 micros)ackerman (0, 4) is: 5 (took: 0 micros)ackerman (1, 0) is: 2 (took: 2 micros)ackerman (1, 1) is: 3 (took: 0 micros)ackerman (1, 2) is: 4 (took: 0 micros)ackerman (1, 3) is: 5 (took: 0 micros)ackerman (1, 4) is: 6 (took: 0 micros)ackerman (2, 0) is: 3 (took: 2 micros)ackerman (2, 1) is: 5 (took: 0 micros)ackerman (2, 2) is: 7 (took: 0 micros)ackerman (2, 3) is: 9 (took: 0 micros)ackerman (2, 4) is: 11 (took: 0 micros)ackerman (3, 0) is: 5 (took: 2 micros)ackerman (3, 1) is: 13 (took: 0 micros)ackerman (3, 2) is: 29 (took: 0 micros)ackerman (3, 3) is: 61 (took: 0 micros)ackerman (3, 4) is: 125 (took: 0 micros)ackerman (4, 0) is: 13 (took: 0 micros)ackerman (4, 1) is: 65533 (took: 1 micros)Exception in thread "main" java.lang.IllegalStateException: 64 bit overflow   at softlylit.main.Ackermann.m3(Ackermann.java:57)   at softlylit.main.Ackermann.ack(Ackermann.java:26)   at softlylit.main.Ackermann.ack(Ackermann.java:34)   at softlylit.main.Ackermann.main(Ackermann.java:11)`

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Riven

« JGO Overlord »

Medals: 1336
Projects: 4
Exp: 16 years

 « Reply #6 - Posted 2014-07-07 13:10:57 »

A(4,2) in 362 milliseconds
A(4,2) in 107 microseconds (~1.1ms)

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89 `import java.math.BigInteger;public class BigAckermann {   private static final int MAX = 5;   public static void main(String[] args) {      for(int i = 0; i < MAX; i++) {         for(int j = 0; j < MAX; j++) {            long t0 = System.nanoTime();            BigInteger got = ack(BigInteger.valueOf(i), BigInteger.valueOf(j));            long t1 = System.nanoTime();            if(i < 4) {               System.out.printf("big.ackerman (%d, %d) is: %d (took: %d micros)\n", i, j, got, (t1 - t0) / 1000);            }            else {               System.out.printf("big.ackerman (%d, %d) is: ... (took: %d micros)\n", i, j, (t1 - t0) / 1000);               String str = got.toString();               for(int k = 0; k < str.length(); k += 80) {                  System.out.println(str.substring(k, Math.min(k + 80, str.length())));               }            }         }      }   }   private static BigInteger ack(BigInteger m, BigInteger n) {      if(m.equals(valueOf(0)))         return m0(n);      if(m.equals(valueOf(1)))         return m1(n);      if(m.equals(valueOf(2)))         return m2(n);      if(m.equals(valueOf(3)))         return m3(n);      if(m.equals(valueOf(4)))         return m4(n);      BigInteger ans;      if(n.equals(valueOf(0)))         ans = ack(m.subtract(valueOf(1)), valueOf(1));      else         ans = ack(m.subtract(valueOf(1)), ack(m, n.subtract(valueOf(1))));      return ans;   }   private static BigInteger m0(BigInteger n) {      return n.add(valueOf(1));   }   private static BigInteger m1(BigInteger n) {      return n.add(valueOf(2));   }   private static BigInteger m2(BigInteger n) {      return n.shiftLeft(1).add(valueOf(3));   }   private static BigInteger m3(BigInteger n) {      BigInteger sum = valueOf(1);      for(int i = 0; n.subtract(valueOf(i)).signum() >= 0; i++) {         sum = sum.shiftLeft(1);         sum = sum.add(valueOf(3));      }      return sum;   }   private static BigInteger m4(BigInteger n) {      BigInteger pow = valueOf(1);      for(int k = 0, len = n.intValue() + 3; k < len; k++)         if(pow.intValue() <= 0)            throw new IllegalStateException("2^MAX");         else            pow = valueOf(1).shiftLeft(pow.intValue());      return pow.subtract(valueOf(3));   }   private static final BigInteger[] table = new BigInteger[1024];   static {      for(int i = 0; i < table.length; i++)         table[i] = BigInteger.valueOf(i);   }   private static BigInteger valueOf(int i) {      if(i < table.length)         return table[i];      return BigInteger.valueOf(i);   }`

A(4,0) = (222)-3
A(4,1) = (2222)-3
A(4,2) = (22222)-3

No wonder this scales poorly

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  141  142  143  144  145  146  147  148  149  150  151  152  153  154  155  156  157  158  159  160  161  162  163  164  165  166  167  168  169  170  171  172  173  174  175  176  177  178  179  180  181  182  183  184  185  186  187  188  189  190  191  192  193  194  195  196  197  198  199  200  201  202  203  204  205  206  207  208  209  210  211  212  213  214  215  216  217  218  219  220  221  222  223  224  225  226  227  228  229  230  231  232  233  234  235  236  237  238  239  240  241  242  243  244  245  246  247  248  249  250  251  252  253  254  255  256  257  258  259  260  261  262  263  264  265  266  267  268  269  270  271  272  273  274  275  276  277 `big.ackerman (0, 0) is: 1 (took: 9 micros)big.ackerman (0, 1) is: 2 (took: 5 micros)big.ackerman (0, 2) is: 3 (took: 2 micros)big.ackerman (0, 3) is: 4 (took: 1 micros)big.ackerman (0, 4) is: 5 (took: 1 micros)big.ackerman (1, 0) is: 2 (took: 3 micros)big.ackerman (1, 1) is: 3 (took: 2 micros)big.ackerman (1, 2) is: 4 (took: 2 micros)big.ackerman (1, 3) is: 5 (took: 2 micros)big.ackerman (1, 4) is: 6 (took: 2 micros)big.ackerman (2, 0) is: 3 (took: 7 micros)big.ackerman (2, 1) is: 5 (took: 3 micros)big.ackerman (2, 2) is: 7 (took: 3 micros)big.ackerman (2, 3) is: 9 (took: 3 micros)big.ackerman (2, 4) is: 11 (took: 3 micros)big.ackerman (3, 0) is: 5 (took: 11 micros)big.ackerman (3, 1) is: 13 (took: 11 micros)big.ackerman (3, 2) is: 29 (took: 9 micros)big.ackerman (3, 3) is: 61 (took: 11 micros)big.ackerman (3, 4) is: 125 (took: 13 micros)big.ackerman (4, 0) is: ... (took: 9 micros)13big.ackerman (4, 1) is: ... (took: 8 micros)65533big.ackerman (4, 2) is: ... (took: 107 micros)2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203002916969592156108764948889254090805911457037675208500206671563702366126359747144807111774815880914135742720967190151836282560618091458852699826141425030123391108273603843767876449043205960379124490905707560314035076162562476031863793126484703743782954975613770981604614413308692118102485959152380195331030292162800160568670105651646750568038741529463842244845292537361442533614373729088303794601274724958414864915930647252015155693922628180691650796381064132275307267143998158508811292628901134237782705567421080070065283963322155077831214288551675554073345107213112427399562982719769150054883905223804357045848197956393157853510018992000024141963706813559840464039472194016069517690156119726982337890017641517190051133466306898140219383481435426387306539552969691388024158161859561100640362119796101859534802787167200122604642492385111393400464351623867567078745259464670903886547743483217897012764455529409092021959585751622973333576159552394885297579954028471943529913543763705986928913757153740001986394332464890052543106629669165243419174691389632476560289415199775477703138064781342309596190960654591300890188887588084733625956065444888501447335706058817090162108499714529568344061979690565469813631162053579369791403236328496233046421066136200220175787851857409162050489711781820400187282939943446186224328009837323764931814789848119452713007440220765680910376203999203492023906626264491909167985461515778839060397720759279378852241294301017458086862263369284725851403039615558564330385450688652213114813638408384778263790459607186876728509763471271988890680478243230394718650525660978150729861141430305816927924971409161059417185352275887504477592218301158780701975535722241400019548102005661773589781499532325208589753463547007786690406429016763808161740550405117670093673202804549339027992491867306539931640720492238474815280619166900933805732120816350707634351669869625020969023162859350071874190579161241536897514808261904847946571736601005892476655445840838334790544144817684255327207315586349347605137419779525190365032198020108764738368682531025183377533908861426184800374008082238104076468878471647552945326947661700424461063311238021134588694532200116564076327023074292426051582811070387018345324567635625951430032037432740780879056283663406965030844225855967039271869461158513793386475699748568670079823960604393478850861649260304945061743412365828352144806726676841807083754862211408236579802961200027441324438432402331257403545019352428776430880232850855886089962774458164680857875115807014743763867976955049991643998284357290415378143438847303484261903388841494031366139854257635577105335580206622185577060082551288893332226436281984838613239570676191409638533832374343758830859233722284644287996245605476932428998432652677378373173288063210753211238680604674708428051166488709084770291208161104912555598322366244868556651402684641209694982590565519216188104341226838996283071654868525536914850299539675503954938371853405900096187489473992880432496373165753803673586710175783994818471798498246948060532081996066183434012476096639519778021441199752546704080608499344178256285092726523709898651539462193004607364507926212975917698293892367015170992091531567814439791248475706237804600009918293321306880570046591458387208088016887445835557926258465124763087148566313528934166117490617526671492672176128330845273936469244582892571388877839056300482483799839692029222215486145902373478222682521639957440801727144146179559226175083889020074169926238300282286249284182671243405751424188569994272331606998712986882771820617214453142574944015066139463169197629181506579745526236191224848063890033669074365989226349564114665503062965960199720636202603521917776740668777463549375318899587866282125469797102065747232721372918144666659421872003474508942830911535189271114287108376159222380276605327823351661555149369375778466670145717971901227117812780450240026384758788339396817962950690798817121690686929538248529830023476068454114178139110648560236549754227497231007615131870024053910510913817843721791422528587432098524957878034683703337818421444017138688124249984418618129271198533315382567321870421530631197748535214670955334626336610864667332292409879849256691109516143618601548909740241913509623043612196128165950518666022030715613684732364660868905014263913906515063908199378852318365059897299125404479443425166774299659811849233151555272883274028352688442408752811283289980625912673699546247341543333500147231430612750390307397135252069338173843322950701049061867539433130784798015655130384758155685236218010419650255596181934986315913233036096461905990236112681196023441843363334594927631946101716652913823717182394299216272538461776065694542297877071383198817036964588689811863210976900355735884624464835706291453052757101278872027965364479724025405448132748391794128826423835171949197209797145936887537198729130831738033911016128547415377377715951728084111627597186384924222802373441925469991983672192131287035585307966942713416391033882754318613643490100943197409047331014476299861725424423355612237435715825933382804986243892498222780715951762757847109475119033482241412025182688713728193104253478196128440176479531505057110722974314569915223451643121848657575786528197564843508958384722923534559464521215831657751471298708225909292655638836651120681943836904116252668710044560243704200663709001941185557160472044643696932850060046928140507119069261393993902735534545567470314903886022024639948260501762431969305640666366626090207048887438898907498152865444381862917382901051820869936382661868303915273264581286782806601337500096593364625146091723180312930347877421234679118454791311109897794648216922505629399956793483801699157439700537542134485874586856047286751065423341893839099110586465595113646061055156838541217459801807133163612573079611168343863767667307354583494789788316330129240800836356825939157113130978030516441716682518346573675934198084958947940983292500086389778563494693212473426103062713745077286156922596628573857905533240641849018451328284632709269753830867308409142247659474439973348130810986399417379789657010687026734161967196591599588537834822988270125605842365589539690306474965584147981310997157542043256395776070485100881578291408250777738559790129129407309462785944505859412273194812753225152324801503466519048228961406646890305102510916237770448486230229488966711380555607956620732449373374027836767300203011615227008921843515652121379215748206859356920790214502277133099987729459596952817044582181956080965811702798062669891205061560742325686842271306295009864421853470810407128917646906550836129916694778023822502789667843489199409657361704586786242554006942516693979292624714524945408858422726153755260071904336329196375777502176005195800693847635789586878489536872122898557806826518192703632099480155874455575175312736471421295536494084385586615208012115079075068553344489258693283859653013272046970694571546959353658571788894862333292465202735853188533370948455403336565356988172582528918056635488363743793348411845580168331827676834646291995605513470039147876808640322629616641560667508153710646723108461964247537490553744805318226002710216400980584497526023035640038083472053149941172965736785066421400842696497103241919182121213206939769143923368374709228267738708132236680086924703491586840991153098315412063566123187504305467536983230827966457417620806593177265685841681837966106144963432544111706941700222657817358351259821080769101961052229263879745049019254311900620561906577452416191913187533984049343976823310298465893318373015809592522829206820862230332585280119266496314441316442773003237792274712330696417149945532261035475145631290668854345426869788447742981777493710117614651624183616680254815296335308490849943006763654806102940094693750609845588558043970485914449584445079978497045583550685408745163316464118083123079704389849190506587586425810738422420591191941674182490452700288263983057950057341711487031187142834184499153456702915280104485145176055306971441761368582384102787659324662689978418319620312262421177391477208004883578333569204533935953254564897028558589735505751235129536540502842081022785248776603574246366673148680279486052445782673626230852978265057114624846595914210278122788941448163994973881884622768244851622051817076722169863265701654316919742651230041757329904473537672536845792754365412826553581858046840069367718605020070547247548400805530424951854495267247261347318174742180078574693465447136036975884118029408039616746946288540679172138601225419503819704538417268006398820656328792839582708510919958839448297775647152026132871089526163417707151642899487953564854553553148754978134009964854498635824847690590033116961303766127923464323129706628411307427046202032013368350385425360313636763575212604707425311209233402837482949453104727418969287275572027615272268283376741393425652653283068469997597097750005560889932685025049212884068274139881631540456490350775871680074055685724021758685439053228133770707415830756269628316955687424060527726485853050611356384851965918968649596335568216975437621430778665934730450164822432964891270709898076676625671517269062058815549666382573829274182082278960684488222983394816670984039024283514306813767253460126007269262969468672750794346190439996618979611928750519442356402644303271737341591281496056168353988188569484045342311424613559925272330064881627466723523751234311893442118885085079358163848994487544756331689213869675574302737953785262542329024881047181939037220666894702204258836895840939998453560948869946833852579675161882159410981624918741813364726965123980677561947912557957446471427868624053750576104204267149366084980238274680575982591331006919941904651906531171908926077949119217946407355129633864523035673345588033313197080365457184791550432654899559705862888286866606618021882248602144999973122164138170653480175510438406624412822803616648904257377640956326482825258407669045608439490325290526337532316509087681336614242398309530806549661879381949120033919489494065132398816642080088395554942237096734840072642705701165089075196155370186264797456381187856175457113400473810762763014953309735174180655479112660938034311378532532883533352024934365979129341284854970946826329075830193072665337782559314331110963848053940859283988907796210479847919686876539987477095912788727475874439806779824968278272200926449944559380414608770641941810440758269805688038949654616587983904660587645341810289907194293021774519976104495043196841503455514044820928933378657363052830619990077748726922998608279053171691876578860908941817057993404890218441559791092676862796597583952483926734883634745651687016166240642424241228961118010615682342539392180052483454723779219911228595914191877491793823340010078128326506710281781396029120914720100947878752551263372884222353869490067927664511634758101193875319657242121476038284774774571704578610417385747911301908583877890152334343013005282797038580359815182929600305682612091950943737325454171056383887047528950563961029843641360935641632589408137981511693338619797339821670761004607980096016024823096943043806956620123213650140549586250615282588033022908385812478469315720323233601899469437647726721879376826431828382603564520699468630216048874528424363593558622333506235945002890558581611275341783750455936126130852640828051213873177490200249552738734585956405160830583053770732533971552620444705429573538361113677523169972740292941674204423248113875075631319078272188864053374694213842169928862940479635305150560788126366206497231257579019598873041195626227343728900516561111094111745277965482790471250581999077498063821559376885546498822938985408291325129076478386322494781016753491693489288104203015610283386143827378160946341335383578340765314321417150655877547820252454780657301342277470616744241968952613164274104695474621483756288299771804186785084546965619150908695874251184435837306590951460980451247409411373899927822492983367796011015387096129749705566301637307202750734759922943792393824427421186158236161317886392553095117188421298508307238259729144142251579403883011359083331651858234967221259621812507058113759495525022747274674369887131926670769299199084467161228738858457584622726573330753735572823951616964175198675012681745429323738294143824814377139861906716657572945807804820559511881687188075212971832636442155336787751274766940790117057509819575084563565217389544179875074523854455200133572033332379895074393905312918212255259833790909463630202185353848854825062897715616963860712382771725621313460549401770413581731931763370136332252819127547191443450920711848838366818174263342949611870091503049165339464763717766439120798347494627397822171502090670190302469762151278521956142070806461631373236517853976292092025500288962012970141379640038055734949269073535145961208674796547733692958773628635660143767964038430796864138563447801328261284589184898528048048844180821639423974014362903481665458114454366460032490618763039502356402044530748210241366895196644221339200757479128683805175150634662569391937740283512075666260829890491877287833852178522792045771846965855278790447562192663992008409302075673925363735628390829817577902153202106409617373283598494066652141198183810884515459772895164572131897797907491941013148368544639616904607030107596818933741217575988165127000761262789169510406315857637534787420070222051070891257612361658026806815858499852631465878086616800733264676830206391697203064894405628195406190685242003053463156621891327309069687353181641094514288036605995220248248886711554429104721929134248346438705368508648749099178812670565665387191049721820042371492740164460943459845392536706132210616533085662021188968234005752675486101476993688738209584552211571923479686888160853631615862880150395949418529489227074410828207169303387818084936204018255222271010985653444817207470756019245915599431072949578197878590578940052540122867517142511184356437184053563024181225473266093302710397968091064939272722683035410467632591355279683837705019855234621222858410557119921731717969804339317707750755627056047831779844447637560254637033369247114220815519973691371975163241302748712199863404548248524570118553342675264715978310731245663429805221455494156252724028915333354349341217862037007260315279870771872491234494477147909520734761385425485311552773301030342476835865496093722324007154518129732692081058424090557725645803681462234493189708138897143299831347617799679712453782310703739151473878692119187566700319321281896803322696594459286210607438827416919465162267632540665070881071030394178860564893769816734159025925194611823642945652669372203155504700213598846292758012527715422016629954863130324912311029627923723899766416803497141226527931907636326136814145516376656559839788489381733082668779901962886932296597379951931621187215455287394170243669885593888793316744533363119541518404088283815193421234122820030950313341050704760159987985472529190665222479319715440331794836837373220821885773341623856441380700541913530245943913502554531886454796252260251762928374330465102361057583514550739443339610216229675461415781127197001738611494279501411253280621254775810512972088465263158094806633687670147310733540717710876615935856814098212967730759197382973441445256688770855324570888958320993823432102718224114763732791357568615421252849657903335093152776925505845644010552192644505312073756287744998163646332835816140330175813967359427327690448920361880386754955751806890058532927201493923500525845146706982628548257883267398735220457228239290207144822219885587102896991935873074277815159757620764023951243860202032596596250212578349957710085626386118233813318509014686577064010676278617583772772895892746039403930337271873850536912957126715066896688493880885142943609962012966759079225082275313812849851526902931700263136328942095797577959327635531162066753488651317323872438748063513314512644889967589828812925480076425186586490241111127301357197181381602583178506932244007998656635371544088454866393181708395735780799059730839094881804060935959190907473960904410150516321749681412100765719177483767355751000733616922386537429079457803200042337452807566153042929014495780629634138383551783599764708851349004856973697965238695845994595592090709058956891451141412684505462117945026611750166928260250950770778211950432617383223562437601776799362796099368975191394965033358507155418436456852616674243688920371037495328425927131610537834980740739158633817967658425258036737206469351248652238481341663808061505704829059890696451936440018597120425723007316410009916987524260377362177763430621616744884930810929901009517974541564251204822086714586849255132444266777127863728211331536224301091824391243380214046242223349153559516890816288487989988273630445372432174280215755777967021666317047969728172483392841015642274507271779269399929740308072770395013581545142494049026536105825409373114653104943382484379718606937214444600826798002471229489405761853892203425608302697052876621377373594394224114707074072902725461307358541745691419446487624357682397065703184168467540733466346293673983620004041400714054277632480132742202685393698869787607009590048684650626771363070979821006557285101306601010780633743344773073478653881742681230743766066643312775356466578603715192922768440458273283243808212841218776132042460464900801054731426749260826922155637405486241717031027919996942645620955619816454547662045022411449404749349832206807191352767986747813458203859570413466177937228534940031631599544093684089572533438702986717829770373332806801764639502090023941931499115009105276821119510999063166150311585582835582607179410052528583611369961303442790173811787412061288182062023263849861515656451230047792967563618345768105043341769543067538041113928553792529241347339481050532025708728186307291158911335942014761872664291564036371927602306283840650425441742335464549987055318726887926424102147363698625463747159744354943443899730051742525110877357886390946812096673428152585919924857640488055071329814299359911463239919113959926752576359007446572810191805841807342227734721397723218231771716916400108826112549093361186780575722391018186168549108500885272274374212086524852372456248697662245384819298671129452945515497030585919307198497105414181636968976131126744027009648667545934567059936995464500558921628047976365686133316563907395703272034389175415267500915011198856872708848195531676931681272892143031376818016445477367518353497857924276463354162433601125960252109501612264110346083465648235597934274056868849224458745493776752120324703803035491157544831295275891939893680876327685438769557694881422844311998595700727521393176837831770339130423060958999137314684569010422095161967070506420256733873446115655276175992727151877660010238944760539789516945708802728736225121076224091810066700883474737605156285533943565843756271241244457651663064085939507947550920463932245202535463634444791755661725962187199279186575490857852950012840229035061514937310107009446151011613712423761426722541732055959202782129325725947146417224977321316381845326555279604270541871496236585252458648933254145062642337885651464670604298564781968461593663288954299780722542264790400616019751975007460545150060291806638271497016110987951336633771378434416194053121445291855180136575558667615019373029691932076120009255065081583275508499340768797252369987023567931026804136745718956641431852679054717169962990363015545645090044802789055701968328313630718997699153166679208958768572290600915472919636381673596673959975710326015571920237348580521128117458610065152598883843114511894880552129145775699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156733Exception in thread "main" java.lang.IllegalStateException: 2^MAX   at softlylit.main.BigAckermann.m4(BigAckermann.java:75)   at softlylit.main.BigAckermann.ack(BigAckermann.java:39)   at softlylit.main.BigAckermann.main(BigAckermann.java:13)`

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Riven

« JGO Overlord »

Medals: 1336
Projects: 4
Exp: 16 years

 « Reply #7 - Posted 2014-07-07 14:24:44 »

A(4,2) is pretty much a hard limit - it's even trivial to compute (about 1ms).

I guess a 99.9% approximation of this function would be blindingly fast. After, even common functions like sin() or cos() are only calculated to a certain degree of precision.
A(4,3) is impossible, due to memory requirements, as we raise 2 to the power of the big number printed in the previous post, which dwarfs the number of atoms in the universe - so there would be no way to represent it, in this universe.

Errrr, I just saw all the 'optimisations' were also to be found in the Wikipedia article... all that hard work for nothing

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
ags1

JGO Kernel

Medals: 363
Projects: 7

Make code not war!

 « Reply #8 - Posted 2014-07-07 19:02:57 »

You can always write down a number no matter how big it is. All you need is the right syntax.

Roquen

JGO Kernel

Medals: 517

 « Reply #9 - Posted 2014-07-07 19:04:14 »

No you can't.  That's the point.
ags1

JGO Kernel

Medals: 363
Projects: 7

Make code not war!

 « Reply #10 - Posted 2014-07-07 19:12:49 »

Write down the number of atoms in the universe. Put a squared next to it.

Longarmx
 « Reply #11 - Posted 2014-07-07 19:23:35 »

Write down the number of atoms in the universe. Put a squared next to it.

Or, just 2^ack(4,3)

ags1

JGO Kernel

Medals: 363
Projects: 7

Make code not war!

 « Reply #12 - Posted 2014-07-07 19:24:46 »

(ack(4,3))^ack(4,3)

Longarmx
 « Reply #13 - Posted 2014-07-07 19:36:03 »

The mother of all computations:

ack(g64, g64);

Roquen

JGO Kernel

Medals: 517

 « Reply #14 - Posted 2014-07-07 19:45:34 »

ack(g64, g64);
That would be an insanely big number.  But all of this is beside the point.  There are things which can't be computed or even manipulated symbolically in finite time and/or space.
Roquen

JGO Kernel

Medals: 517

 « Reply #15 - Posted 2014-07-07 19:49:03 »

Oh yeah, since it came up: https://plus.google.com/117663015413546257905/posts/KJTgfjkTZCQ
ctomni231

JGO Wizard

Medals: 99
Projects: 1
Exp: 7 years

Not a glitch. Just have a lil' pixelexia...

 « Reply #16 - Posted 2014-07-08 03:20:40 »

Whew, well at least I can lay this to rest. Thanks for tackling this problem. It was really cool trying to out optimize this for a weekend. I feel a bit of reserve that our technology is the limiter in the ability to calculate A(4,3), and it isn't just me.

Though I can't shake the feeling that future beings will call us idiots once they dig this up...

Roquen

JGO Kernel

Medals: 517

 « Reply #17 - Posted 2014-07-08 07:10:55 »

The thing about proofs is: there are no counter examples unless they're flawed.
Pages: [1]
 ignore  |  Print

 ivj94 (581 views) 2018-03-24 14:47:39 ivj94 (45 views) 2018-03-24 14:46:31 ivj94 (372 views) 2018-03-24 14:43:53 Solater (60 views) 2018-03-17 05:04:08 nelsongames (107 views) 2018-03-05 17:56:34 Gornova (147 views) 2018-03-02 22:15:33 buddyBro (690 views) 2018-02-28 16:59:18 buddyBro (90 views) 2018-02-28 16:45:17 xxMrPHDxx (492 views) 2017-12-31 17:17:51 xxMrPHDxx (728 views) 2017-12-31 17:15:51
 SHC 10x NuclearPixels 10x Zemlaynin 10x KaiHH 10x ByerN 7x Spasi 6x Guerra2442 6x philfrei 5x VaTTeRGeR 5x orangepascal 4x ags1 4x princec 3x ndnwarrior15 3x Trilarion 3x mesterh 3x Phased 2x
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org