Well, one might doubt the validity of that list. Given that Java, the language with no reason to exist is number 2. And C#, with even less reason to exist (we already had Java thanks) is number 5. Then they have CSS as number 8, WTF?
That's the argumentum ad populum fallacy, just because JavaScript is a popular language with a bright future, don't mean it's not a terrible language.
I do know and appreciate that point of view.
But let's take a different idea. From evolution.
Since the beginning, with FORTRAN, programming languages have mutated, cross bred, and generally progressed in a way that could be seen as evolutionary.
So what then is the driving force behind this evolution? Normally in the biological world we think of "survival of the fittest." That is to say the creatures that can survive in their environment go on to create more similar creatures. Whilst the variants that do not fit their environment wither and die.
How does this relate to programming languages?
Well let's imagine the languages as like creatures. Mutating and cross breeding with the help of humans that like to do such things.
Let's imagine the "environment" is the huge user base of programmers who use the languages.
So, survival of a programming language is nothing to do with how "good" or "terrible" you may think it is. It's all to do with how well it fits its environment, the mass of programmers and whatever it is they want to do with it.
What is wrong with a non recursive solution? Why it needs to be recursive?
From an aesthetic point of view many programmers would say that the normal iterative version is ugly:
for ( c = 0 ; c < n ; c++ )
{
if ( c <= 1 )
next = c;
else
{
next = first + second;
first = second;
second = next;
}
printf("%d\n",next);
}
Where as the recursive version is a thing of beauty:
intFibonacci(int n){
if ( n < 2 )
return n;
elsereturn ( Fibonacci(n-1) + Fibonacci(n-2) );
}
Which I'm sure you will agree is true. The recursive version very clearly expresses the definition of fibonacci numbers.
More practically there have been many recursive fibos posted on this forum in various languages and language implementations along with their benchmark timings. It's a good test of function call overhead. So a COBOL recursive fibo result is in order.
Some offer dire warnings that the recursive fibo will blow up your stack for large n. This is true but overlooks the points that:
1) The execution time is O(fibo(n)) so you won't live long enough to blow up even a small stack.
2) The numbers get huge so even when using 64 bit ints you can only get up to fibo(92) before overflowing the number range (if your computer could live that long) like so:
I see the beauty and understand that it shows the function overhead. A completely not needed function overhead. Bloat. Pretty sure the iterative version is faster.
The presented code does in fact run all 93 iterations. Just without recursion. You are the Linux and command line guy. Just run it thru GnuCOBOL/OpenCobol and time it!
You even can look at the generated C code. Sadly GnuCobol uses curses/ncurses for SCREEN SECTIONS and BerkleyDB for Database (mostly ISAM) stuff. So no COBOL on the Prop. PropGCC can't handle this.
Emscripten might. Not even sure there.
But your local Linux thing can. Even the RasPi. Self hosted.
I think the recursive version of Fibonacci in COBOL would loose some of it beauty as you call it. Sure doable. But why?
COBOL sources are almost readable English language. Verbose but thru this well self-commented also. Honestly you could take the guy doing this on paper, show him the part of the listing and he was able to understand it. And tell you what's wrong. Putting recursion into something just because it looks cool thereby f...ing up all people working with that code later is uncool, I think.
And later can mean 50 years later or so. Think of the movie Idiocracy. COBOL will survive. JavaScript? Hmm....
As for the restriction of 32 or 64 bits. COBOL has some standard named data types for the ease of use. But you can declare without a problem a variable able to display the money America already spend in say cents and use it in calculations.
I've actually come to like Javascript. It's ubiquity has created a competitive marketplace for fast, efficient interpreters. And the JS debugging tools that come with Firefox are really helpful. I've used it extensively on the client side of both of these projects, with Perl as my chosen language for the server side:
Yes there is a lot of function call overhead in the recursive fibo. And yes the iterative version is far faster. The execution time of the recursive is proportional to fib(n) which obviously gets very big very quickly.
For sure I will be trying your code in open-cobol when I have a moment.
Having to have ncurses and BerklyDB in order to run the compiled code may be a show stopper for getting this running in JS in the browser. I'm not about to try compiling those to JS. Perhaps we can make tiny versions of any required ncurses/berkley functions in JS though.
I think the recursive version of Fibonacci in COBOL would loose some of it beauty as you call it. Sure doable. But why?
Perhaps recursive cobol is not so pretty. That recursive factorial thing looked OK though. Why do it? because that is the standard benchmark around here.
Putting recursion into something just because it looks cool thereby f...ing up all people working with that code later is uncool, I think.
That is true, especially in languages like C, but consider this version in Haskell:
fib0 = 0fib1 = 1fib n = fib (n-1) + fib (n-2)
That so beautifully and concisely expresses what it is. Much easier to read than any other language. Sadly it's also exponentially slow.
Some languages can optimize away the overhead of recursion so that a recursive algorithm executes in the same time as an iterative loop. (See "tail call optimization"). This allows some code to be very much more readable when written recursively whilst also being speedy. Sadly rearranging that Haskell code to allow tail call recursion make it less readable again and is still fibo(n) run time.
It's cool to know that COBOL handles really big numbers. Sadly that could be an other issue in getting it to run in the browser in general. We would have to include a big number library.
>>SOURCE FREE
IDENTIFICATION DIVISION.
PROGRAM-ID. fibonacci-main.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 num PIC 9(6) COMP.
01 fib-num PIC 9(6) COMP.
PROCEDURE DIVISION.
ACCEPT num
CALL"fibonacci" USING CONTENT num RETURNING fib-num
DISPLAY fib-num
.
END PROGRAM fibonacci-main.
IDENTIFICATION DIVISION.
PROGRAM-ID. fibonacci RECURSIVE.
DATA DIVISION.
LOCAL-STORAGE SECTION.
011-before PIC 9(6) COMP.
012-before PIC 9(6) COMP.
LINKAGE SECTION.
01 num PIC 9(6) COMP.
01 fib-num PIC 9(6) COMP BASED.
PROCEDURE DIVISION USING num RETURNING fib-num.
ALLOCATE fib-num
EVALUATE num
WHEN 0
MOVE 0TO fib-num
WHEN 1
MOVE 1TO fib-num
WHEN OTHER
SUBTRACT 1FROM num
CALL"fibonacci" USING CONTENT num RETURNING 1-before
SUBTRACT 1FROM num
CALL"fibonacci" USING CONTENT num RETURNING 2-before
ADD1-before TO2-before GIVING fib-num
END-EVALUATE
.
END PROGRAM fibonacci.
Oh my frikken God. how could that be so huge and complicated ?!
Compare to the Haskell version above.
It compiles and runs but I have no idea how to get a result out of it. If I type a small number on the command line after running it it immediately prints 000000 and exits like so:
$ ./fibo-exe
10000000
If I type a big number in in hangs up my whole machine for ages and then dies !
I have no idea what to do with this. Any suggestions msrobots?
Ah, forgot about that. I have not used or seen a card punch since 1975 when I was learning ALGOL on an ICL 2960 at Uni.
Mind you even then we were quite advanced. The output was line printed on line printers. Reams of that wide paper with green stripes would be in my pigeon hole in the morning after the card deck was run over night. Normally full of syntax errors or core dumps. It was nice to have the computer operator slaves to operate the machine for us but boy were they slow.
Does that mean to get this running under JS in the browser we have make a graphical simulation of the card punch and line printer?
Unix is already piping the "files" stdout and stdin to and fro the console input and console output, basically my terminal.
In the code I see.
ACCEPT num
CALL "fibonacci" USING CONTENT num RETURNING fib-num
DISPLAY fib-num
Which, googling around I can assume to be:
get num from user input
calculate fib-num as fibonacci of num
print fib-num
Which is what it does. As my session with it, posted above shows.
Problem is the results are all zero and it blows up for inputs like 40. Which by the way a recursive fibo should not do, even if the calculation takes for ever. This should not use a lot of memory.
Great that you are able to run COBOL, finally. You are old and grown up enough to cherish this language, I hope.
First example:
Iterative code, but up to 36 characters in the result. So we display Fibonacci(0) to Fibonacci(173)
just copy into some-file and use cobc -x -free some-file
and run it.
IDENTIFICATION DIVISION.
PROGRAM-ID. "Fibonacci".
DATA DIVISION.
WORKING-STORAGE SECTION.
01 ix BINARY-C-LONG VALUE 0.
01 first-number PIC 9(36) VALUE 0.
01 second-number PIC 9(36) VALUE 1.
01 temp-number PIC 9(36) VALUE 1.
01 display-line.
05 display-num PIC Z(3)9.
05 display-number PIC Z(36)9.
PROCEDURE DIVISION.
START-PROGRAM.
MOVE 0to display-num
MOVE first-number TO display-number
DISPLAY display-line.
MOVE 1to display-num
MOVE second-number TO display-number
PERFORM VARYING ix FROM2 BY 1UNTIL ix = 174
DISPLAY display-line
ADD first-number TO second-number GIVING temp-number
MOVE second-number TO first-number
MOVE temp-number TO second-number
MOVE ix to display-num
MOVE temp-number TO display-number
END-PERFORM
DISPLAY display-line
.
STOP RUN.
You did mention a numeric overflow after Fibonacci(93) using C longs. Does not apply for COBOL. See above.
I also did get your recursive version running.
You are right. GnuCOBOL runs into some major stack issue there. Works fine below Fibonacci(30). But then it barfs somehow. Not coming back. No errors. Just hangs.
I guess GnuCobol 1,1 does not really support recursion. Not sure there. Never used recursion in COBOL before.
anyways runnable version for you:
>>SOURCE FREE
IDENTIFICATION DIVISION.
PROGRAM-ID. fibonacci-main.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 num BINARY-C-LONG.
01 fib-num BINARY-C-LONG.
PROCEDURE DIVISION.
ACCEPT num
CALL"fibonacci" USING num fib-num
DISPLAY fib-num
STOP RUN.
END PROGRAM fibonacci-main.
IDENTIFICATION DIVISION.
PROGRAM-ID. fibonacci RECURSIVE.
DATA DIVISION.
LOCAL-STORAGE SECTION.
011-before BINARY-C-LONG.
012-before BINARY-C-LONG.
LINKAGE SECTION.
01 num BINARY-C-LONG.
01 fib-num BINARY-C-LONG.
PROCEDURE DIVISION USING num fib-num.
EVALUATE num
WHEN 0
MOVE 0TO fib-num
WHEN 1
MOVE 1TO fib-num
WHEN OTHER
SUBTRACT 1FROM num
CALL"fibonacci" USING num 1-before
SUBTRACT 1FROM num
CALL"fibonacci" USING num 2-before
ADD1-before TO2-before GIVING fib-num
ADD2to num
END-EVALUATE
.
END PROGRAM fibonacci.
Ugly, isn't it?
The iterative version is way faster then the recursive one, Way faster. Beauty or not. And does not hang.
But now that I have not only seen, but tried to understand some Cobol code, I don't find it particularly easy to read. I'm not more sure about exactly what's going to happen than with any other computer language, in fact it's worse sometimes. So I'm not so sure about that part of the language. It was supposed to be one of its major points (the other being decimal calculations I guess).
"Old and grown up"!? I never did pull off the "grown up" part very well and now I seem to be retrograding
I'll start cherishing immediately. Squinting a bit at COBOL I see it looks a lot like PASM. Seriously:
COBOL:
ADD first-number TO second-number GIVING temp-number
MOVE second-number TO first-number
MOVE temp-number TO second-number
MOVE ix to display-num
MOVE temp-number TO display-number
It's impressive to see the big number results for fibo
fibo(173) = 638817435613190341905763972389505493
I wonder how the performance of that compares to using big integers in Python?
Surprisingly the recursive version does actually run properly on my machine at home. Gives the correct results instead of just zero. I don't know if that's because I have a 64 bit machine as opposed to my old 32 bit office machine. Or because I'm using Debian Jessie here instead of Wheezy. I seem to have the same OpenCOBOL 1.1.0 but perhaps some libraries it uses are newer.
fib(40) takes almost a minute!
$ time ./fibo-recursive40+00000000000102334155real0m53.979s
user0m51.164s
sys 0m0.024s
Yep, it's damn ugly code. COBOL syntax just does not encourage such elegant coding style.
Never used recursion in COBOL before.
How do you guys search a binary tree or any interesting data structure in COBOL without recursion?
Recursive fibo is well known to be very slow. Such code is not expected to be used in reality. It's an example of recursion, it's a benchmark.
Strangely, I wrote a recursive FFT in C. It was very much nicer to read than the normal approach of three nested loops. It reflected the algorithm nicely. It was of course slower than the more standard approach. But then surprisingly I found that for really big input arrays, tens or millions of elements, the recursive version started to beat the iterative. I still have not figured out why but I think it was down to how the CPU caches are used.
COBOL looks like assembly language becuase it was meant to compile, with a really minimal compiler, to CISC assembly languages for mainframe computers which were in turn meant to be programmed directly by humans. The compiler was more about automating resource allocation for variables and moving data around between storage devices than it was about converting high level logic like algebraic expressions to low level instructions.
It looks like we are having to explain to the compiler where it will find it's local variables and where it will find it's parameters on the stack. Rather than have it work that out for itself. Now a days we see things like "section" in the output of a compilation.
On the other hand I imagine even mainframes did not support arbitrary length integers so some real compilation work is going on somewhere. Did early COBOL compilers do that? I have no idea.
Whilst we are here. How come the iterative fibo code uses 36 digit numbers but the recursive uses BINARY-C-LONG?
Not that anyone would ever live long enough to see a result out of the recursive algorithm that required a C long to hold the result.
On the other hand....my PC can calculate the 5759 digits of fibo (27557) in python using the recursive algorithm in 90ms ! See code at the end of the post.
$ time python fibo.py
52834471370566714419560525535867384494153583057216213517953718526993805659933058191304885829014630011353164491727721069618536593815336350122958985919250785121289763741656938144350170600403199279361530695853890291198289017455833865818210989420410476347140723073223911794196338272466510731323265786732079621221369837919954008619682868886101033314532121272138676397992918082162146409908637977857721753650302407929032694400637723586843481980842347966532612936842217535783309169189816200804348361919627098255786871929536398103075716280234245790579979961449211309755486684479370669246731566408835413095760604342144607499745894836518967508411264314371629226306604967363250168782897734122120161803626072248535150976385694269901644918847176026199567915149537564004022463929385748265911642339173894989579928212410229034875172515841706765141077041878494415911682373342335561093041786001283299154026583195095951474560011419360254647360087766208216098115941451731092353719612194215716279380102404492919860247796821615406398433706069322922946663672533143653826050175536548430202403237167198873788778886254004268266452881532010318717417708053954581600513240155576908688705009072344618899431258552517427769194743206558224849519009068976179359856314332238571445899029997164163244764942821788121683146704401653686986902785659330961922927322402155573306311396075412704564486593273122073057056590033512679747210123844198897886597170870208094465991130518136631414091642152558129040007845629920449250558121526730818551290736642712507684054419753505658395877200172306095765407760914658942385978606963000078001087745002368491184131008008587297468324499633540560498835494683101807676862961343894656837837420241431622269179936039267319045213906634818258765553978055745816412660304236713139477421521942647016390209215943553218471445393147804288771195332937027998752950765315380395488310192764031582033351412173100453354089662858730160309577185114166817545947672810214658899771291513090297002033227086843548706364851128376125000290801028761147817608750188768310503158881037510428510286873155731721225349730786310920905542400754425782363946836556312019884487184842756250040086540029801470245547505549136724589831393689479194455125342895705177207179416877054384576199181791685778471325780480431674763816932708678225723131941557017926910461341595124811188824236320497823905588172217941893345740806421200554027808922893677095772095223590497128088885439069235564000510521505653138658240356052962658914676895226546996775868726568568728869184156516959754866366460735961060264084529126695258464652804613766381756790139281301915503729229897376264337897565519745632759685038399332760336534015928618810660577305285384410547412865237107859836368825382256037181712718013988076030987505993772820145831824436856536562371167377448112444628211332991560390561938032958700156570371663291423888455663064520151060780324942778225699930065109894166860808447619999888751784124172355087740476457805832547453838597497648493112422786795146436012263760312079529386386686626499224475740422048900488742744109011861792441231245837871762705156980362159674324678010989604992774855486543322638023737052180858533577639135523783349060634159210946069315096971035007416319418351298044847718397938758735203701850121238114996238088239547696157592490322381467588257889364239552015764653122247679900621617933985959434951861793994119699810482028269499670007960707659283256854534723706489114559213062619986070999131899051361959215818381990736770676391694495878460832866192674353296830764710063136866426263843079483455155116468324154462243314397682613511542337655894868461477429164562986770439119756544300724060368696206786449236368425031479225097370660474700685277109603327445229463940309237338356255181876031252758540257525549752846828483510973818777147672271993654547228582200979984073034799072224052785361278995694707618852973673660051685042627077372934225398123526342032025075369219265771064587346908674546808495403240271736998526135460116405419732789261767375889618043313052790665471606949591788375570083903339252944973809801783338814806684275476989729637561905670208480765729743233004814195493485032094756741768613237880436237457093950568707533577588856430677807794773042517466539058877222063846322376873912851778950707721102652762149608095815676193831802157779192545348506330221093423864930749428632038523227930286182338506529854154150856476840248603246272292714927806065879530519479580902885594739569352432838053812849798829967227477510884887616663426834938881700600815558943440721229786098383651193120550232121931134378827480122892926295869540562559026263544357886020090510627989411288117462321728869076471023430981090690280140566317018628010773625031354428325229126557605629948465853603123163401669673420647110278020251953758640551964085316406565793469583068937217627031294215928395811185251377549467170203463701132202465337856428910516592380905779398442858910512802316253862132873665233824450997491063616822931650221355116786620818274219294740297440319140808708278422251572376334476970273632357836255545181115790774035383598717452081360853023977077728492574255016452661589476088551822613485009871682543669928524154614603688426837591560632370619694022044785200653921136666952657316801888528381276767634784262055899066657646460485294667427839204576784855541946872289050828639656662530671323848146241811542568302443550138980525550236554952424624949255209449051940372088657647146131198530195780869015512601012646002879862290544920721020223063988093553450040564750495081903047222801612767958289288097703261949648171811716615472576203874624094107777617040263650967596882127537533584632387445812058491312353601383790859667309359265121483324958595272211534095511107599884613222512782951193344645332974491268998945772956886708037
real 0m0.093s
user 0m0.056s
sys 0m0.036s
[code]
memo = {0:0, 1:1}
def fibo(n):
ifnot n in memo:
memo[n] = fibo(n-1) + fibo(n-2)
return memo[n]
print fibo(27557)
As for the readability - it depends. Function are available with GnuCOBOL 2.0 not yet available in OC 1xx. But the syntax of functions is not much different from the call of Sub Programs shown in the recursive example. But without knowing COBOL at all, @Heater was able to translate to PASM by just squinting at it.
COBOL was the second language created by Grace Hopper. The first one was Flow-Matic. the first attempt to write a HLL and a compiler. Before that there where no compiler at all.
Grace Hopper invented the idea of a compiler and HLLs. So COBOL is a first gen. language. But most of it is there, branches and loops, even structures.
@Heater.
I used 36 digits in the first example to show larger numbers. Thus fibo(173) was doable. Your c version peters out at fibo(93) because of numeric overflow.
As this is an anti-JavaScript thread my problem now is how to demonstrate that JS can also achieve such big fibo results? And how long will they take to run?
Function are available with GnuCOBOL 2.0 ... But the syntax of functions is not much different from the call of Sub Programs shown in the recursive example.
I really don't want to see how COBOL with classes and objects will look:)
Grace Hopper was amazing but as usual Americans have their own version of history.
The concept of a high level language was first imagined by Konrad Zuse in 1943.
Autocode by Alick Glennie in 1952 is thought to be the first compiled programming language.
FORTRAN by John Backus et al in 1957 is generally thought to be the first "real" compiled language.
COBOL did not arrive until 1960.
To my mind the first real high level language and compiler is Lisp in 1962. That was the first time you could write a compiler for a language in the same language. Lisp could compile itself.
Yep. C conks out at fibo(93). Mind you in the C language standard says that the type 'int' is implementation-dependent. That is to say that the fact that your program conks out at some point is due to limits imposed by you particular compiler not the C language itself.
Anyway as we see, COBOL's 36 digits is pathetic compared to what Python can do!
@phil
Do we need more fibo digits to see if that distribution flattens some more out up there?
Comments
Well, one might doubt the validity of that list. Given that Java, the language with no reason to exist is number 2. And C#, with even less reason to exist (we already had Java thanks) is number 5. Then they have CSS as number 8, WTF?
A further WTF is that PHP is third! I question the sanity of the respondents.
But let's take a different idea. From evolution.
Since the beginning, with FORTRAN, programming languages have mutated, cross bred, and generally progressed in a way that could be seen as evolutionary.
So what then is the driving force behind this evolution? Normally in the biological world we think of "survival of the fittest." That is to say the creatures that can survive in their environment go on to create more similar creatures. Whilst the variants that do not fit their environment wither and die.
How does this relate to programming languages?
Well let's imagine the languages as like creatures. Mutating and cross breeding with the help of humans that like to do such things.
Let's imagine the "environment" is the huge user base of programmers who use the languages.
So, survival of a programming language is nothing to do with how "good" or "terrible" you may think it is. It's all to do with how well it fits its environment, the mass of programmers and whatever it is they want to do with it.
There were no "respondents" here. As far a I understand this list all based on occurrences of the language in github and on stack overflow.
Well now, github might be a good start. It shows what people are actually using.
Stack overflow on the other hand only shows how many problems people are having with those languages!
What is wrong with a non recursive solution? Why it needs to be recursive?
Enjoy!
Mike
for ( c = 0 ; c < n ; c++ ) { if ( c <= 1 ) next = c; else { next = first + second; first = second; second = next; } printf("%d\n",next); }Where as the recursive version is a thing of beauty:int Fibonacci(int n) { if ( n < 2 ) return n; else return ( Fibonacci(n-1) + Fibonacci(n-2) ); }Which I'm sure you will agree is true. The recursive version very clearly expresses the definition of fibonacci numbers.More practically there have been many recursive fibos posted on this forum in various languages and language implementations along with their benchmark timings. It's a good test of function call overhead. So a COBOL recursive fibo result is in order.
Some offer dire warnings that the recursive fibo will blow up your stack for large n. This is true but overlooks the points that:
1) The execution time is O(fibo(n)) so you won't live long enough to blow up even a small stack.
2) The numbers get huge so even when using 64 bit ints you can only get up to fibo(92) before overflowing the number range (if your computer could live that long) like so:
2880067194370816120 = FIBO 90 4660046610375530309 = FIBO 91 7540113804746346429 = FIBO 92 9223372036854775807 = INT_MAX 12200160415121876738 = FIBO 93And that only requires a stack big enough for 93 recursive calls.You didn't expect a short answer did you?
I see the beauty and understand that it shows the function overhead. A completely not needed function overhead. Bloat. Pretty sure the iterative version is faster.
The presented code does in fact run all 93 iterations. Just without recursion. You are the Linux and command line guy. Just run it thru GnuCOBOL/OpenCobol and time it!
You even can look at the generated C code. Sadly GnuCobol uses curses/ncurses for SCREEN SECTIONS and BerkleyDB for Database (mostly ISAM) stuff. So no COBOL on the Prop. PropGCC can't handle this.
Emscripten might. Not even sure there.
But your local Linux thing can. Even the RasPi. Self hosted.
I think the recursive version of Fibonacci in COBOL would loose some of it beauty as you call it. Sure doable. But why?
COBOL sources are almost readable English language. Verbose but thru this well self-commented also. Honestly you could take the guy doing this on paper, show him the part of the listing and he was able to understand it. And tell you what's wrong. Putting recursion into something just because it looks cool thereby f...ing up all people working with that code later is uncool, I think.
And later can mean 50 years later or so. Think of the movie Idiocracy. COBOL will survive. JavaScript? Hmm....
As for the restriction of 32 or 64 bits. COBOL has some standard named data types for the ease of use. But you can declare without a problem a variable able to display the money America already spend in say cents and use it in calculations.
Enjoy!
Mike
Enjoy!
Mike
SpinScope
-Phil
Yes there is a lot of function call overhead in the recursive fibo. And yes the iterative version is far faster. The execution time of the recursive is proportional to fib(n) which obviously gets very big very quickly.
For sure I will be trying your code in open-cobol when I have a moment.
Having to have ncurses and BerklyDB in order to run the compiled code may be a show stopper for getting this running in JS in the browser. I'm not about to try compiling those to JS. Perhaps we can make tiny versions of any required ncurses/berkley functions in JS though. Perhaps recursive cobol is not so pretty. That recursive factorial thing looked OK though. Why do it? because that is the standard benchmark around here. That is true, especially in languages like C, but consider this version in Haskell:
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)That so beautifully and concisely expresses what it is. Much easier to read than any other language. Sadly it's also exponentially slow.Some languages can optimize away the overhead of recursion so that a recursive algorithm executes in the same time as an iterative loop. (See "tail call optimization"). This allows some code to be very much more readable when written recursively whilst also being speedy. Sadly rearranging that Haskell code to allow tail call recursion make it less readable again and is still fibo(n) run time.
It's cool to know that COBOL handles really big numbers. Sadly that could be an other issue in getting it to run in the browser in general. We would have to include a big number library.
I try "cobc -C fibo.cob" and get nothing but errors like "fibo.cob:1: Error: Invalid indicator 'R' at column 7"
$ cobc -free -C fibo.cobBut I had to remove the * comment line. Odd.Odd.
Runs nicely though.
It looks like this:
>>SOURCE FREE IDENTIFICATION DIVISION. PROGRAM-ID. fibonacci-main. DATA DIVISION. WORKING-STORAGE SECTION. 01 num PIC 9(6) COMP. 01 fib-num PIC 9(6) COMP. PROCEDURE DIVISION. ACCEPT num CALL "fibonacci" USING CONTENT num RETURNING fib-num DISPLAY fib-num . END PROGRAM fibonacci-main. IDENTIFICATION DIVISION. PROGRAM-ID. fibonacci RECURSIVE. DATA DIVISION. LOCAL-STORAGE SECTION. 01 1-before PIC 9(6) COMP. 01 2-before PIC 9(6) COMP. LINKAGE SECTION. 01 num PIC 9(6) COMP. 01 fib-num PIC 9(6) COMP BASED. PROCEDURE DIVISION USING num RETURNING fib-num. ALLOCATE fib-num EVALUATE num WHEN 0 MOVE 0 TO fib-num WHEN 1 MOVE 1 TO fib-num WHEN OTHER SUBTRACT 1 FROM num CALL "fibonacci" USING CONTENT num RETURNING 1-before SUBTRACT 1 FROM num CALL "fibonacci" USING CONTENT num RETURNING 2-before ADD 1-before TO 2-before GIVING fib-num END-EVALUATE . END PROGRAM fibonacci.Oh my frikken God. how could that be so huge and complicated ?!Compare to the Haskell version above.
It compiles and runs but I have no idea how to get a result out of it. If I type a small number on the command line after running it it immediately prints 000000 and exits like so:
$ ./fibo-exe 10 000000If I type a big number in in hangs up my whole machine for ages and then dies !I have no idea what to do with this. Any suggestions msrobots?
Mind you even then we were quite advanced. The output was line printed on line printers. Reams of that wide paper with green stripes would be in my pigeon hole in the morning after the card deck was run over night. Normally full of syntax errors or core dumps. It was nice to have the computer operator slaves to operate the machine for us but boy were they slow.
Does that mean to get this running under JS in the browser we have make a graphical simulation of the card punch and line printer?
This idea is getting out of hand.
You might have to pipe in a data file. Unix/Linux does do that...
Be very careful what you say. The guy that prints your paycheck might be a COBOL programmer.
In the code I see.
ACCEPT num CALL "fibonacci" USING CONTENT num RETURNING fib-num DISPLAY fib-numWhich, googling around I can assume to be:get num from user input
calculate fib-num as fibonacci of num
print fib-num
Which is what it does. As my session with it, posted above shows.
Problem is the results are all zero and it blows up for inputs like 40. Which by the way a recursive fibo should not do, even if the calculation takes for ever. This should not use a lot of memory.
I'm stuck with it for now.
Great that you are able to run COBOL, finally. You are old and grown up enough to cherish this language, I hope.
First example:
Iterative code, but up to 36 characters in the result. So we display Fibonacci(0) to Fibonacci(173)
just copy into some-file and use cobc -x -free some-file
and run it.
IDENTIFICATION DIVISION. PROGRAM-ID. "Fibonacci". DATA DIVISION. WORKING-STORAGE SECTION. 01 ix BINARY-C-LONG VALUE 0. 01 first-number PIC 9(36) VALUE 0. 01 second-number PIC 9(36) VALUE 1. 01 temp-number PIC 9(36) VALUE 1. 01 display-line. 05 display-num PIC Z(3)9. 05 display-number PIC Z(36)9. PROCEDURE DIVISION. START-PROGRAM. MOVE 0 to display-num MOVE first-number TO display-number DISPLAY display-line. MOVE 1 to display-num MOVE second-number TO display-number PERFORM VARYING ix FROM 2 BY 1 UNTIL ix = 174 DISPLAY display-line ADD first-number TO second-number GIVING temp-number MOVE second-number TO first-number MOVE temp-number TO second-number MOVE ix to display-num MOVE temp-number TO display-number END-PERFORM DISPLAY display-line . STOP RUN.You did mention a numeric overflow after Fibonacci(93) using C longs. Does not apply for COBOL. See above.
I also did get your recursive version running.
You are right. GnuCOBOL runs into some major stack issue there. Works fine below Fibonacci(30). But then it barfs somehow. Not coming back. No errors. Just hangs.
I guess GnuCobol 1,1 does not really support recursion. Not sure there. Never used recursion in COBOL before.
anyways runnable version for you:
>>SOURCE FREE IDENTIFICATION DIVISION. PROGRAM-ID. fibonacci-main. DATA DIVISION. WORKING-STORAGE SECTION. 01 num BINARY-C-LONG. 01 fib-num BINARY-C-LONG. PROCEDURE DIVISION. ACCEPT num CALL "fibonacci" USING num fib-num DISPLAY fib-num STOP RUN. END PROGRAM fibonacci-main. IDENTIFICATION DIVISION. PROGRAM-ID. fibonacci RECURSIVE. DATA DIVISION. LOCAL-STORAGE SECTION. 01 1-before BINARY-C-LONG. 01 2-before BINARY-C-LONG. LINKAGE SECTION. 01 num BINARY-C-LONG. 01 fib-num BINARY-C-LONG. PROCEDURE DIVISION USING num fib-num. EVALUATE num WHEN 0 MOVE 0 TO fib-num WHEN 1 MOVE 1 TO fib-num WHEN OTHER SUBTRACT 1 FROM num CALL "fibonacci" USING num 1-before SUBTRACT 1 FROM num CALL "fibonacci" USING num 2-before ADD 1-before TO 2-before GIVING fib-num ADD 2 to num END-EVALUATE . END PROGRAM fibonacci.Ugly, isn't it?
The iterative version is way faster then the recursive one, Way faster. Beauty or not. And does not hang.
Enjoy!
Mike
Got the fibonacci running! Thanks!
But now that I have not only seen, but tried to understand some Cobol code, I don't find it particularly easy to read. I'm not more sure about exactly what's going to happen than with any other computer language, in fact it's worse sometimes. So I'm not so sure about that part of the language. It was supposed to be one of its major points (the other being decimal calculations I guess).
-Tor
"Old and grown up"!? I never did pull off the "grown up" part very well and now I seem to be retrograding
I'll start cherishing immediately. Squinting a bit at COBOL I see it looks a lot like PASM. Seriously:
COBOL:
ADD first-number TO second-number GIVING temp-number MOVE second-number TO first-number MOVE temp-number TO second-number MOVE ix to display-num MOVE temp-number TO display-numberPASM:MOV temp_number, first_number ADD temp_number, second_number MOV first_number, second_number MOV second_number, temp_number MOV display_num, ix MOV display_number, temp_numberAnyway, well done and thanks.
It's impressive to see the big number results for fibo
fibo(173) = 638817435613190341905763972389505493
I wonder how the performance of that compares to using big integers in Python?
Surprisingly the recursive version does actually run properly on my machine at home. Gives the correct results instead of just zero. I don't know if that's because I have a 64 bit machine as opposed to my old 32 bit office machine. Or because I'm using Debian Jessie here instead of Wheezy. I seem to have the same OpenCOBOL 1.1.0 but perhaps some libraries it uses are newer.
fib(40) takes almost a minute!
$ time ./fibo-recursive 40 +00000000000102334155 real 0m53.979s user 0m51.164s sys 0m0.024sYep, it's damn ugly code. COBOL syntax just does not encourage such elegant coding style. How do you guys search a binary tree or any interesting data structure in COBOL without recursion?
Recursive fibo is well known to be very slow. Such code is not expected to be used in reality. It's an example of recursion, it's a benchmark.
Strangely, I wrote a recursive FFT in C. It was very much nicer to read than the normal approach of three nested loops. It reflected the algorithm nicely. It was of course slower than the more standard approach. But then surprisingly I found that for really big input arrays, tens or millions of elements, the recursive version started to beat the iterative. I still have not figured out why but I think it was down to how the CPU caches are used.
I think you have a point. Looking at this:
LOCAL-STORAGE SECTION. 01 1-before BINARY-C-LONG. 01 2-before BINARY-C-LONG. LINKAGE SECTION. 01 num BINARY-C-LONG. 01 fib-num BINARY-C-LONG.It looks like we are having to explain to the compiler where it will find it's local variables and where it will find it's parameters on the stack. Rather than have it work that out for itself. Now a days we see things like "section" in the output of a compilation.On the other hand I imagine even mainframes did not support arbitrary length integers so some real compilation work is going on somewhere. Did early COBOL compilers do that? I have no idea.
Whilst we are here. How come the iterative fibo code uses 36 digit numbers but the recursive uses BINARY-C-LONG?
Not that anyone would ever live long enough to see a result out of the recursive algorithm that required a C long to hold the result.
Fib(20000)=
25311623237323612422401550035206072917663564858024
85278951929841991312781760541315230153423463758831
63744348821921103768903367353146274288532972407155
51876180269316304491931589227713316423020303319710
98689235780843478258502779200293635651897483309686
04286099636444351455877215604369140415581957298497
17542785131124879858927182295933294835785314191488
05380281624260900362993556916638613939977074685016
18825858431232913952639355809684081297042295241855
89918557723068824425748555892371652199122382013111
84749075137322987656049866305366913734924425822681
33896650746385518023628358240986119921232383594789
11437654149133450084560220094557042108916377919112
65475167769704477334859109822590053774932978465651
02385144792060131010628895789430159250206156052813
12030727786774914434209218225907099104486173291561
35355464620891788459566081572824889514296350670950
82420824517066760172641709112799999994114991301042
45320468819582854094684632118975822150754365155840
16297874572183907949257286261608612401379639484713
10113812040467173219045132788143320102518402754169
61241144634886653593858709103314761566658894598320
92710304159637019707297988417848767011085425271875
58800867142249143400511528833434383777879228238357
67363414144102489940815648302023638205041900745045
66612515965134665683289356188727549463732830075811
85157496155866927884736327987059532009984467687945
71964325359733571283053902904713494802587518128903
14779723508104229525161740643984423978659638233074
46310036650057197723450846471007810258130482323543
65181450744828248129965116141619333133898896309353
20139507075992100561077534028207257574257706278201
30830264263467811259109184308266572169711783872643
17667411587435542988645609932555476084966868501858
04659790217122426535133253371422250684486113457341
82791162551712881544732595854791211324236720199067
22306813088191959410161560019619547002415765537507
37681552256845421159386858399433450045903975167084
25287684884808591015694160329342406779309727112880
68175149065316524077631183081623770334632035146575
31210413149191213595455280387631030665594589183601
57534002717299722248908163114472887362180552864876
85113689486395229755390469953957076889389788470846
21586473529546678958226255042389998718141303055036
06077200388777303842236691382039774855079317816722
01933460174300241344961411459918962277418425157189
97898627269918236920453493946658273870473264523119
13376544765329502288642917494265301465652190946961
31849836714314659349654894255159810675460873423483
50724207583544436107294087637975025147846254526938
44243564492823102786870139481909113291239747571378
75936127583648126875567251464566468789121692742192
09708166678668152184941578590201953144030519381922
27325266665267171752631860667675455617037935095634
20954556127802021999226153927855724817479134355608
66995432578680971243966868110016581395696310922519
80368583746079535838461801721546812288044225234368
45472336685023132393283526713181306042474604521341
21833305284398726438573787798499612760939462427922
91765926304633308400720805663199685631553969823402
29534522115056756291536378672526950569253452200840
20071611220575700841268302638995272842160994219632
68457536418016099188488509185825999629962714861445
66966614127450405199815755438048474639974223265638
97043803732970397488471644906183310144691243649149
54239469152497202393519063367282730611652571288295
91084342116524656211447020153366574595321340269152
14509960877430595844287585350290234547564574848753
11028110154593154722581176344171021745297966817802
52864601583246588529041057924724681089961354766372
12057508192176910900422826969523438985332067597093
45402192407710178421593653963880862442012145971828
60594018236142132143260042704717528027256258109537
87713898846144256909835116371235019527013180204030
16760156706426857382069794886898263090416468516178
30880765069643173037097085740527472044052827859656
04677674192569851918643651835755242670293612851920
69673232054556228611033214006591275155111013491625
62378848440013663666540550797219858167148039524293
01558096968202261698837096090377863017797020488044
82662881746286685432135678730563565357761987798799
81136679289548409720228335057085875619020234113989
15823487627297968947621416912816367516125096563705
174220460639857683971213093125
4180 digits in 6.96 seconds
$ time python fibo.py 52834471370566714419560525535867384494153583057216 21351795371852699380565993305819130488582901463001 13531644917277210696185365938153363501229589859192 50785121289763741656938144350170600403199279361530 69585389029119828901745583386581821098942041047634 71407230732239117941963382724665107313232657867320 79621221369837919954008619682868886101033314532121 27213867639799291808216214640990863797785772175365 03024079290326944006377235868434819808423479665326 12936842217535783309169189816200804348361919627098 25578687192953639810307571628023424579057997996144 92113097554866844793706692467315664088354130957606 04342144607499745894836518967508411264314371629226 30660496736325016878289773412212016180362607224853 51509763856942699016449188471760261995679151495375 64004022463929385748265911642339173894989579928212 41022903487517251584170676514107704187849441591168 23733423355610930417860012832991540265831950959514 74560011419360254647360087766208216098115941451731 09235371961219421571627938010240449291986024779682 16154063984337060693229229466636725331436538260501 75536548430202403237167198873788778886254004268266 45288153201031871741770805395458160051324015557690 86887050090723446188994312585525174277691947432065 58224849519009068976179359856314332238571445899029 99716416324476494282178812168314670440165368698690 27856593309619229273224021555733063113960754127045 64486593273122073057056590033512679747210123844198 89788659717087020809446599113051813663141409164215 25581290400078456299204492505581215267308185512907 36642712507684054419753505658395877200172306095765 40776091465894238597860696300007800108774500236849 11841310080085872974683244996335405604988354946831 01807676862961343894656837837420241431622269179936 03926731904521390663481825876555397805574581641266 03042367131394774215219426470163902092159435532184 71445393147804288771195332937027998752950765315380 39548831019276403158203335141217310045335408966285 87301603095771851141668175459476728102146588997712 91513090297002033227086843548706364851128376125000 29080102876114781760875018876831050315888103751042 85102868731557317212253497307863109209055424007544 25782363946836556312019884487184842756250040086540 02980147024554750554913672458983139368947919445512 53428957051772071794168770543845761991817916857784 71325780480431674763816932708678225723131941557017 92691046134159512481118882423632049782390558817221 79418933457408064212005540278089228936770957720952 23590497128088885439069235564000510521505653138658 24035605296265891467689522654699677586872656856872 88691841565169597548663664607359610602640845291266 95258464652804613766381756790139281301915503729229 89737626433789756551974563275968503839933276033653 40159286188106605773052853844105474128652371078598 36368825382256037181712718013988076030987505993772 82014583182443685653656237116737744811244462821133 29915603905619380329587001565703716632914238884556 63064520151060780324942778225699930065109894166860 80844761999988875178412417235508774047645780583254 74538385974976484931124227867951464360122637603120 79529386386686626499224475740422048900488742744109 01186179244123124583787176270515698036215967432467 80109896049927748554865433226380237370521808585335 77639135523783349060634159210946069315096971035007 41631941835129804484771839793875873520370185012123 81149962380882395476961575924903223814675882578893 64239552015764653122247679900621617933985959434951 86179399411969981048202826949967000796070765928325 68545347237064891145592130626199860709991318990513 61959215818381990736770676391694495878460832866192 67435329683076471006313686642626384307948345515511 64683241544622433143976826135115423376558948684614 77429164562986770439119756544300724060368696206786 44923636842503147922509737066047470068527710960332 74452294639403092373383562551818760312527585402575 25549752846828483510973818777147672271993654547228 58220097998407303479907222405278536127899569470761 88529736736600516850426270773729342253981235263420 32025075369219265771064587346908674546808495403240 27173699852613546011640541973278926176737588961804 33130527906654716069495917883755700839033392529449 73809801783338814806684275476989729637561905670208 48076572974323300481419549348503209475674176861323 78804362374570939505687075335775888564306778077947 73042517466539058877222063846322376873912851778950 70772110265276214960809581567619383180215777919254 53485063302210934238649307494286320385232279302861 82338506529854154150856476840248603246272292714927 80606587953051947958090288559473956935243283805381 28497988299672274775108848876166634268349388817006 00815558943440721229786098383651193120550232121931 13437882748012289292629586954056255902626354435788 60200905106279894112881174623217288690764710234309 81090690280140566317018628010773625031354428325229 12655760562994846585360312316340166967342064711027 80202519537586405519640853164065657934695830689372 17627031294215928395811185251377549467170203463701 13220246533785642891051659238090577939844285891051 28023162538621328736652338244509974910636168229316 50221355116786620818274219294740297440319140808708 27842225157237633447697027363235783625554518111579 07740353835987174520813608530239770777284925742550 16452661589476088551822613485009871682543669928524 15461460368842683759156063237061969402204478520065 39211366669526573168018885283812767676347842620558 99066657646460485294667427839204576784855541946872 28905082863965666253067132384814624181154256830244 35501389805255502365549524246249492552094490519403 72088657647146131198530195780869015512601012646002 87986229054492072102022306398809355345004056475049 50819030472228016127679582892880977032619496481718 11716615472576203874624094107777617040263650967596 88212753753358463238744581205849131235360138379085 96673093592651214833249585952722115340955111075998 84613222512782951193344645332974491268998945772956 886708037 real 0m0.093s user 0m0.056s sys 0m0.036s [code] memo = {0:0, 1:1} def fibo(n): if not n in memo: memo[n] = fibo(n-1) + fibo(n-2) return memo[n] print fibo(27557)That about wraps it up for COBOL around here!1: 464
2: 450
3: 406
4: 415
5: 443
6: 418
7: 385
8: 425
9: 393
It was not, to a statistically-significant degree. Here's the result for the computation directly above:
1: 573
2: 598
3: 563
4: 546
5: 596
6: 599
7: 567
8: 592
9: 548
It looks to be a lot more uniform.
-Phil
good you got it running.
As for the readability - it depends. Function are available with GnuCOBOL 2.0 not yet available in OC 1xx. But the syntax of functions is not much different from the call of Sub Programs shown in the recursive example. But without knowing COBOL at all, @Heater was able to translate to PASM by just squinting at it.
COBOL was the second language created by Grace Hopper. The first one was Flow-Matic. the first attempt to write a HLL and a compiler. Before that there where no compiler at all.
Grace Hopper invented the idea of a compiler and HLLs. So COBOL is a first gen. language. But most of it is there, branches and loops, even structures.
@Heater.
I used 36 digits in the first example to show larger numbers. Thus fibo(173) was doable. Your c version peters out at fibo(93) because of numeric overflow.
Enjoy!
Mike
No doubt you did that in Perl.
We are seriously geeking out here:)
As this is an anti-JavaScript thread my problem now is how to demonstrate that JS can also achieve such big fibo results? And how long will they take to run?
-Phil
Grace Hopper was amazing but as usual Americans have their own version of history.
The concept of a high level language was first imagined by Konrad Zuse in 1943.
Autocode by Alick Glennie in 1952 is thought to be the first compiled programming language.
FORTRAN by John Backus et al in 1957 is generally thought to be the first "real" compiled language.
COBOL did not arrive until 1960.
To my mind the first real high level language and compiler is Lisp in 1962. That was the first time you could write a compiler for a language in the same language. Lisp could compile itself.
Yep. C conks out at fibo(93). Mind you in the C language standard says that the type 'int' is implementation-dependent. That is to say that the fact that your program conks out at some point is due to limits imposed by you particular compiler not the C language itself.
Anyway as we see, COBOL's 36 digits is pathetic compared to what Python can do!
@phil
Do we need more fibo digits to see if that distribution flattens some more out up there?
-Phil