Fire Stations and the only fun part, probably.
Published
If you haven’t already, check the About part to have a tiny context into what I will tell you here. It will expand quickly. I have no formal “programming” education, that was what we called it back then, when I was a teenager. I am a native Turkish speaker, so bear with me if this sounds like nonsense to you and excuse me on cultural grounds: we wrote programs, not developed apps.
I had a Spectrum 48K as my start into programming with its own BASIC variant. I heard about Pascal and Niklaus Wirth and how he designed the language to teach programming to the masses so the logic clicked: What better way to continue the journey than with the very thing that will also teach me how to do it better. Turbo Pascal back then was a single .com file. Search hint on your favorite engine or AI companion: what are .com and .exe files? It was very easy to carry around on a floppy. It ran fast, I mean the name suggest it, right? It is one small executable and it is both the editor and the compiler which was huge.
I learned. The process is trial and error, reading any and all written material I can get my hands on, trying anything I had even just heard about being done on a computer and trying to code it myself. It paid, though I didn’t do it on purpose. Here is the good part. IT WAS FUN. Whatever I tried to do and even when I failed big, I never regretted the countless hours.
My PC at home was an 8088 clone. An 8 bit outward, 16 bit internal CPU. One more excuse to be slow but cheap. I was studying Industrial Engineering in İTÜ. There were exactly 8 80286 PCs in a locked room available to students of the faculty. Mostly off limits to me. The teaching staff had their own PCs but no better than that spec. Look up the speed and capabilities of a typical 80286, if you want. But the crucial piece that will shape this story, here, is that it was a CPU with no math co-processor support built in. A floating-point coprocessor (80287) was a separate chip, sold on its own and expensive and most machines never got one. With it installed, you need to modify the software to take advantage of it. Deliberately. Without it the CPU did not do floating-point math at the hardware level. Every real number in your program became a software routine: the processor pretending to be a calculator, one slow step at a time. Multiply two numbers with decimal points and the machine spent more time on the ceremony than a modern CPU would spend on a few tens, maybe even hundreds of thousands of them. Intel changed that later and you never see it mentioned anymore in specs, obviously. You are getting used to looking up AI execution capabilities nowadays.
My professor mentioned a project for the İstanbul municipality about the Fire Stations in the city. Details already lost in the fog of history. Probably they were planning to add more FSs and they wanted to be “scientific” about it and asked the University to optimize their placement. During the course of the project I got some interesting insights into how FSs work. All this may have changed but I am telling you what was standard back then.
I learned that the first 5 minutes after the Fire Department (all city) is alerted to a fire are crucial. If you arrive and step in within 5 minutes usually you are able to contain the fire with minimal or acceptable damage. After 5, the toll increased exponentially. That’s property damage and I will not put a number on human lives, thank you very much.
We (the Industrial Engineering Department) created a simulation which runs and calculates the effect of a year of fires on the city. You change the placement of the FSs and try to optimize the outcome. Same number of fires and less damage. Pretty neat, eh.
So, it matters where these FSs are. Hugely. Another tidbit: Every city has a “road parameter”. That’s a direct translation from Turkish, most probably wrong. But it is simple. You have your FS, your fire’s location and you multiply the distance as the crow flies between them by 1.6 in İstanbul to calculate the actual distance you need to travel by the Fire Truck. You also have a set of other multipliers for the time of the day, for traffic, for different zones, etc. But you’ve guessed it already with all the info I dumped on you.
You have a simulation, repeatedly calculating the distance between two points on the city grid, the FS (stationary) and the fire (dynamic). You do the multiplications and the square root. Then you sort the results to find out which FS (closest and available) sends the truck. Then when it arrives, and the fire is put out, calculate how much damage occurred.
Now, the last pieces of the puzzle for you. When I learned about the project, it was built already. All the necessary statistics were there, all parameters calculated for İstanbul. And the striking part: The simulation was written in GW-BASIC, the only language the “programmer” knew, a post-grad, probably.
It ran the 1 year simulation in 8 hours. Doing massive calculations. On an 80286 with no math-coprocessor. Which ran DOS which makes 640K memory available to your GW-BASIC.
Let that sink in.
The department was already running the simulation. The Operations: Put in the parameters, placement, etc. When leaving the office in the evening start the simulation. In the morning come back to the office. Hope the power was not interrupted in your area that night. Process the result that was dumped. During the day pick another placement, using other tools. Rinse and repeat. The department just went out and bought a UPS, not to lose the night run data and hoped the power would be back if it was cut, before the simulation finishes. Eight hours per data point is not engineering. It is a candle-lit vigil.
Oh my, what fun to have such a huge surface of attack.
First order of business: GW-BASIC is interpreted, Pascal is compiled. (Python is basically interpreted so you get my meaning)
A rewrite in a compiled language automatically promised gains. I had tears of joy when I went to speak with my professor.
Nah. “Hold your horses”, he told me.
Computers use random numbers in simulations. Well, a deterministic “machine” like a PC cannot produce real, honest to God random numbers. In fact smarter people than me call them pseudo-random numbers. You provide a seed (maybe a timestamp so it changes frequently); there is a generator algo in there somewhere that is shipped with the language (I can see the grin on your face).
So a rewrite does not produce the same string of random numbers even if you set the seed manually. GW-BASIC is always apples, Turbo Pascal is always oranges. You cannot compare the results, byte-by-byte, if you use the built-in random number generators. You can implement your own generator on both, but then you will probably face number precision challenges. I thought of that path briefly, but my skills were simply not on that level. So with the random number generators you have, you just look at the results and, with a confidence level, accept or reject the hypothesis that they (when the simulation is repeated enough times) will give you the same decision, in the end.
That was way above my paygrade (read knowledge level). The smarter people did the hard work by using the sample random numbers I generated from my tools against their tool and the verdict came:
“It’s ok. Go on.”
I rewrote the whole simulation in two months staying up at night, reading BASIC code from a hard copy, writing Pascal, at home on my 8088, even slower than the target 80286.
Pure joy. I had no idea what the outcome would be but it turned out remarkable. 2.5 hours on the same 80286. Staff was happy. Night time worries melted away. More than one simulation per day, what a luxury. And just when they were going through the “thanking me” rounds, I pulled the rabbit I glimpsed when I was working on the code out of my hat. (see, look at the code, always look) I said: “Now, if you allow me I will rewrite it once more, emphasis on ‘re’ but in my style. You have the 2.5 hours version, worst case scenario.” Puzzled looks. I did not bother to try to explain. They were mere engineers, not a programmer god like myself (well, small detail, they actually graduated, PhDs and a professor, small detail, I insist)
Back to my computer.
Now I will speed up the story telling. You can check all that will follow with independent sources and this is an account of things after 35 years, nothing written down. No artistic license, though, best as I can remember.
Obviously, calculating the distances is one of the bottlenecks (especially the square root, if you get my drift). Now the distances between points in a grid are a matrix. Stop, it is half a matrix: if you know the distance from A to B, you also know B to A. Half the memory, does it fit? Nah, it does not. But wait, you don’t even need half the matrix: The FSs don’t move and obviously you do not have a FS at all grid points, that’s the whole idea of the simulation. You don’t have them so where to put the limited number in the first place matters. The numbers I remember. İstanbul had back then 538 districts, there would be at most 109 FSs. Another cut to the matrix: from the half 538x538, a simulation only reads its own 538x109 slice, the columns of its 109 FS. Does it fit? Barely. With another catch; I will tell you later. Another round of “programming”. The distances are only calculated once, stored in memory, used repeatedly. Yeah, you caught me already. Why calculate them at the start of every simulation. İstanbul is not going anywhere. Calculate the half 538x538 ONCE. Write it to a floppy (or harddisk if you are lucky enough to have a PC with a HDD) At the start read the half 538x109 specific to that simulation. Never calculate square root of ((y2-y1)^2 + (x2-x1)^2). Ever.
Are you with me because you already know the next attack front. Come on, I mentioned it already. Read carefully.
The sort. Takes time.
For whatever the reason, I remembered the original sorting algorithm to be a bubble sort. Checked, my memory served right, it was a bubble sort in the BASIC code. (ok, I hid THAT fact, guilty as charged. Please do not complain: you like it when Agatha does it anyway).
The basic bubble sort code I found in the original code:
1750 '
1760 REM ************ GIDIS SURELERINE GORE SIRAYA DIZME ************
1770 '
1780 '
1790 FOR I=1 TO ISAYI-1
1800 FOR J=I+1 TO ISAYI
1810 IF GIDIS(I)>=GIDIS(J) THEN SWAP GIDIS(I),GIDIS(J):SWAP SIRA(I),SIRA(J)
1820 NEXT J
1830 NEXT I
1840 KK=1
1850 'But I turned it into a selection sort when converting to Pascal. Same complexity, fewer swaps but essentially takes just as long to sort the array, for the same n items. Another round of self-improvement. Research sorting algorithms. A couple of nights to learn about them and, most important, prove that I can CODE them.
The evidence. Here is the selection sort procedure Sirala (sort in Turkish), from FIREV3.PAS, which was the 2.5-hour GW-BASIC to Pascal translation:
Ekip[Birinci]:=Ekip[Birinci]+Giden1;
Ekip[Ikinci]:=Ekip[Ikinci]+Giden2;
Ekip[Ucuncu]:=Ekip[Ucuncu]+Giden3;
Gonder:=Giden1+Giden2+Giden3;
End;
Procedure Sirala;
Var Temp1,de1,de2:Ext;
Temp2,N,M,d1:Integer;
Begin
For N:=1 To Isayi Do Begin
De1:=Gidis[N];D1:=N;
For M:=N To Isayi Do If Gidis[M]<De1 Then Begin
De1:=Gidis[M];D1:=M;
End;
De2:=Gidis[N];
Gidis[N]:=De1;
Gidis[D1]:=De2;
Temp2:=Sira[N];
Sira[N]:=Sira[D1];
Sira[D1]:=Temp2;
End;
End;
Procedure SonucYaz;
Begin
Writeln(Dosya,Zaman:6:0,Yilce:3,Mahalle:4,Yrisk:2,Eksayisi:2,Sondsur:5:0,
Birinci:4,Var1:4:0,Giden1:2,Ikinci:4,Var2:4:0,Giden2:2,
Ucuncu:4,Var3:4:0,Giden3:2,Gonder:3:0,Dolu:3);
End;And here is the recursive quicksort function, this time named in English, the 17 min version, from FIREV4.PAS, same block (I kept leading and trailing code pieces, no editing):
Ekip[Birinci]:=Ekip[Birinci]+Giden1;
Ekip[Ikinci]:=Ekip[Ikinci]+Giden2;
Ekip[Ucuncu]:=Ekip[Ucuncu]+Giden3;
Gonder:=Giden1+Giden2+Giden3;
end;
procedure Sort(L,R:Integer);
Var
X,Y: Ext;
I,J,N:Integer;
begin
I:=L; J:=R; X:=Gidis[(L+R) DIV 2];
Repeat
While Gidis[i]<X Do inc(I);
While X<Gidis[J] Do dec(J);
If I<=J Then begin
Y:=Gidis[I]; Gidis[I]:=Gidis[J]; Gidis[J]:=Y;
N:=Sira[I]; Sira[I]:=Sira[J]; Sira[J]:=N;
inc(I); dec(J);
end;
Until I>J;
If L<J Then Sort(L,J);
If I<R Then Sort(I,R);
end;
procedure SonucYaz;
begin
Writeln(SonucD,Zaman:6:0,Yilce:3,Mahalle:4,Yrisk:2,
Eksayisi:2,Sondsur:5:0,Birinci:4,Var1:4:0,Giden1:2,
Ikinci:4,Var2:4:0,Giden2:2,Ucuncu:4,Var3:4:0,
Giden3:2,Gonder:3:0,Dolu:3);
end;Quick-sort was a bitch to implement (but easy after you get the logic) Swapped selection sort with the quick guy, literally (so many puns in one sentence). Quick used more memory than selection but we already saved some and now put the free space to good use. Did other small stuff. Many of them. But no big impact like these two.
17 minutes, ladies and gentlemen. The faculty 80286 was speechless. My professor, even more so. I cut down the project run time from 6+ projected months to a few weeks. Cue the applause.
Three years ago, we had lunch after maybe 20 years of almost no contact. He is about to retire, too. He told me he is still telling this story, year after year, semester after semester, at least once in every one of his classes. Naming ME. I invented flying without any visible means of propulsion and no wings attached, then and there. While working on this piece I reached out to him again. His recollection of run durations were even more amazing, I will stick by mine because else it will become his memory vs. my memory. He confirmed the municipality initiated the project as part of a bigger one and it ran from 1986 to 1988. I worked on the code in 1991 so the project was already delivered. My code flowed into a research paper two people published, one of them, my professor. I hunted the paper down. The count I used 538 was 550 local districts in the paper. That is not a discrepancy. From 1988 to 1991 İstanbul grew and probably they used the current number of data points whereas I inherited the data from 1988. It did not matter: they had the distance calculating program as well, they used it and there was no need to involve me. Beautiful. They also describe 25 experiments each reducing 109 stations down to 4 in 22 steps. This gives a total of 550 runs. If it were 8 hours each night, weekdays, with failed attempts, just over two years. But it was, as far as I recall, 17 minutes. With only 12-13 runs, less than 4 hours a work day, excluding weekends this will be about 2 months. Less if you push it. According to the publisher the paper’s revised form arrived November 1991 which gives the team 5 months to publication from the file dates (April 1991) of the copy of the floppy (not the original) on my backup HDD. My professor expressed his consent for me reproducing this account here.
The paper is behind a paywall, unfortunately, but you can read the abstract yourself.
https://www.sciencedirect.com/science/article/abs/pii/0305048392900286
Eight hours to seventeen minutes is twenty-eight times, and not one transistor of the hardware changed. People talk about fast machines. There were no fast machines in that story. There was the slow (by today’s standards) machine, and a decreasing number; one of those two things did all the work.
Here is the part I remember more clearly than the numbers, and I own it completely: those were probably the most fun times of my life with a computer. The numbers in front of me, decreasing. The (then) praise from the professor. Not a salary attached, not a deadline, not somebody else’s production system on fire. Not even a course assignment: I just jumped and took it on, as a challenge, with no visible return (ok, I KNEW it would look good on me). Nothing at work ever came as close. Probably nobody else in Industrial Engineering at İTÜ at that time had the stubbornness to rewrite a program almost twice for nothing but the decreasing numbers on the screen. That is not a compliment to me. It is a measurement of the room.
Research looked different then. There was no search box to ask which sorting algorithm suits your data. There were real paper books, and you read them until the answer fell out, and if the book did not have it, the answer stayed lost until you invented it. Today one prompt shows you every sorting algorithm side by side, the tradeoffs laid out like a menu. That is progress that comes with teeth: the same prompt also writes the code for you, and the way IT writes it, you do not know which algorithm is in there, if you do not check.
Checking is still my job. It was my job when the chip could not multiply or take a square root, decently.
I still chase decreasing numbers. The machines on my desk now have twelve cores, a GPU, and more memory than the PC lab with 8 80286s in total, sixteen thousand times over, and the joy comes out in the same shape: a number in front of me, going down, for reasons I can explain. The hardware got thirty years faster. The fun did not need to.