So, I’ll be on a break until the new year…
How to build a horse with programming…
Month: December 2021
Programming languages through the ages…
I love this fun look at programming languages through cartoons, from the Beholder website.
Why Python dependencies are just plain cruel
Last week I tried to download pilgram, a Python library for Instagram filters. Seemed simple to install and use… and it was. But things don’t always work like they should, and it’s often a problem with dependencies of some sort. I did have some teething problems, but that was attributed to a local “string.py” file which seemed to confuse the interpreter.
Dependencies really are Python’s Achilles Heel. In fact there is a term which sums up the issue quite nicely – “dependency hell“. I mean thank heavens for pip, the de facto Python package manager… imagine trying to make sure all dependencies for a given packaged were installed with the correct versions in the correct places? A nightmare right? Not that pip is perfect by any means. Dependency management is one of the most discussed topics related to Python, and likely one of the things people complain most about. While Python has access to somewhere over 137,000 different libraries, managing them isn’t exactly trivial… unless perhaps you use something like Poetry. Nut again, it’s something else that has to be installed.
None of this is made any easier by the fact that most older systems still have Python2 on them, and once you add Python3 you end up with a menagerie of folder with tools and libraries in them. Maybe things will improve once Python 2 is cleaned away in favour of Python 3… although my thinking is that although Python 2 was discontinued in 2020, the fact that Python3 is not completely backwards compatible may lead to some issues now that Python2 is essentially a legacy language. It’s one of the reasons I don’t exactly like Python – but I don’t blame Python. When you have that many add-on libraries, there is no guarantee that all will be deigned or implemented in the most effective or efficient manner.
When not to use recursion
Recursive algorithms are often the best solution when dealing with problems that are defined in recursive terms, a good example being Ackermann’s function. The non-recursive implementation of Ackermann’s function is decidedly inefficient. There are of course some recursive problems used to illustrate recursion which translate into a less than optimal recursive algorithms.
Fibonacci is a case in point, no one questions the viability of the recursive algorithm because it is so pervasive in textbooks. It is likely one of the quintessential examples of recursion because it is defined in recursive terms:
fibn = fibn-1 + fibn-2
In fact, Fibonacci offers a good counter-example of recursion, at least in the context of the binary recursive version most often presented. It works well for low values, but suffers computationally when faced with large values due to the number of re-calculations performed. In short it is inefficient, but because few introductions to recursive algorithms discuss the stack, it is more difficult for students to comprehend why it is inefficient – due in part to the tree-based topology of the recursive algorithm.
In fact, the explanation of the concept of recursive algorithm by such inappropriate examples has been a chief cause of creating widespread apprehension and antipathy toward the use of recursion in programming, and of equating recursion with inefficiency.
Niklaus Wirth, Algorithm + Data Structures = Programs, p.127-128
In reality, the iterative version of Fibonacci works exceedingly well, and there is no real need to delve into the world of recursion, unless one wishes to explore various forms of recursion as they relate to Fibonacci [2] in the context of a simple problem. Below is the iterative algorithm implemented in Fortran.
program fibonacci
integer :: i, n, f1, f2, fib
read(*,*) n
f1 = 1
f2 = 1
do i = 3,n
fib = f1 + f2
f1 = f2
f2 = fib
end do
write(*,'(i2, "th Fibonacci = ", i20)') n, fib
end program fibonacci
There are also linearly recursive versions of the Fibonacci algorithm, which use memoization, but they are rarely discussed. The other poor example of recursion is the ubiquitous Factorial. Calculating factorials, whilst being simple in the context of linear recursion, is again easier to express by means of simple iteration. Niklaus Wirth cites both Fibonacci and Factorial as examples of when not to use recursion and to avoid the use of recursion when there is an obvious solution by iteration [1].
In general, avoid the use of recursion where an intuitive iterative solution will suffice.
Refs.
- Wirth, N., Algorithm + Data Structures = Programs, Prentice-Hall (1976).
- Wirth, M.A., “Fibonacci beyond binary recursion”, Teaching Mathematics and Computer Science, 6(1), pp.173-185 (2008)
Fibonacci by linear recursion is better
As we have seen, deriving Fibonacci using binary recursion is just plain moronic. The better option is a linearly recursive version of Fibonacci where the two previous Fibonacci numbers are stored as parameters to a recursive function. Here is a version in C:
int fib_linearR(int a, int b, int n) {x
if (n <= 2)
return b;
else if (n > 2)
return fib_linearR(b,a+b,n−1);
}The Fibonacci numbers are calculated using the function call: fib_linearR(1,1,n). Note the two parameters a and b which hold two successive Fibonacci numbers. This linear recursive version takes linear time. For n=40 binary recursion facilitates 204,668,309 function calls and takes approximately 0.459 seconds (on a MacBook Pro with a 2.9 GHz Intel Core i5). Linear recursion conversely takes 39 function calls and 0.00002 seconds.
This is also a good example of tail recursion, as the call to fib_linearR() is the last statement performed in the function. Here it is not so much about the time taken, because from an algorithm runtime perspective, but more the number of function calls required. As a comparison, when I first did the binary recursive calculation in 2008, for n=40 it took 37 seconds. However it illustrates the problems that can occur with recursion that involves a lot of recursive calls, especially if there are substantial resources involved.
The tapering of technology
If we want to look at the real issue with the planet it is ultimately humans. We have effectively terraformed the planet over a couple of hundred years.
The problem may lie in humans over thinking many things. Solutions are often simple. Abating CO2 emissions could be partially achieved by planting more trees. Plastic could be better recycled, or less of could be used… perhaps more bioplastics. People could eat more sustainably. We could live without most of the garbage we manufacture. Years ago companies built products to last, now we have become a throw away society. A case in point are cameras. With analog cameras they lasted decades – even now cameras that were built in the 1930s still work. The downside of analog photography is of course the chemicals use to develop photographs. How many digital cameras do we all have? I probably have nearly ten sitting around, the majority obsolete technology. Batteries run their course and wear out, or the number of shutter activation’s is maxed out. Or the technology just becomes dated, due to lack of megapixels.
But we are now at a nexus – how much more can technology improve. It already pervades too much of our lives, and I would argue that improvements in many technologies have reached a plateau. There is a reason vinyl records have made a comeback, and even analog cameras. Analog cameras have reappeared because they provide photographs with character that digital lacks (partially this is because the younger generation have grown up using filters in apps like Instagram). The next evolution might be the creation of a digital film medium for analog cameras – a reusable film so to speak, to provide for the aesthetics of film.
Everything that is old is new again. Or maybe everything that is new is not necessarily better. This was he case with e-readers which were suppose to replace book… which didn’t happen. The truth is we don’t need so much technology. Even the latest iPhone is almost the same as the iPhone it replaced. iPhone 13… what more would it do for me? Except for the convenience of having a camera, and notepad where ever I go, and being able to google things… it doesn’t do much for me. Sure it has a “more powerful camera”… which doesn’t really help me because regardless of the app they are all harder to use than a real camera (from a usability perspective). I don’t need “super-intelligent” software to improve how I take photos, unless I just want the machine to do it (although the macro photography does seem cool). It actually seems like Apple is selling the iPhone as a camera + mobile social media now – may as well call it the iCamera. Despite all this, I imagine the battery is still horrible.
We need to cut back on technology and take a closer look at the way we use to live more… maybe get a better understanding of nature, because at the end of the day, you can’t eat a mobile device.
The best what?
I always find it funny when the Maclean’s higher education issue comes out every year. It almost always seems like I’m reading the same thing, year in, year out. “Canada’s BEST Schools”. Problem is, ranking rarely change that much – the top five in each category just swap around a bit. The most interesting part may be on how they come up with the rankings. 28% of the score is about students, which is fair enough. 24% relates to the “calibre of faculty”. They calculate this using things like winning major awards, “securing research grants, number of papers published, and number of times the published papers are cited. The strange thing is that of this 24%, they don’t actually indicate that any of it comes from the quality of teaching? Last time I looked, *most* young people who go to university do so to get an education. A small percentage of the masses go on to grad school. So they seem to heavily correlate the existence of research with the quality of the university, which may be reasonable were the issue on “Canada’s BEST Graduate Schools”. But it’s not. A failure to add any form of indicator relating to the teaching quality doesn’t make sense. Does pumping out a lot of research papers make someone a better teacher? I doubt it. It might be just as possible that good teachers concentrate more on teaching, and dedicate less time to research. That, and small scale research is very poorly funded in Canada.
Nine percent of the “Resources” bucket is attributed to libraries. Have you been in a university library recently? They may still buy books, but it seems like the only reason students use libraries is to study and drink coffee. I rarely see them actually in the stacks looking for books. In some libraries I have been to ( prominent ones no less), the dust is so thick on the books that it almost chokes you when you pull out a book. Look I get rankings, and students planning to go to university buy the issue (and the larger catalog of universities) to determine which is the best university. Frankly I think students should choose a place based on what they want to do, and where they want to live. If you’re taking a class like biology, where introductory classes can have 1000+ students in them (in most schools), it doesn’t matter how many research grants the instructor has, but it matters a whole lot more if they are interesting, can captivate their audience, and lets face it, actually teach. Maybe they should focus more on things like experiential learning, and the experiences of alumni?
The age of zombie apps
Ever download a really good app, and use it for a year only for the developer to stop caring about the app? It happens a lot. Usually you don’t notice until you upgrade your smartphone, or update the system software on the phone, and hey-presto, it no longer works. You go to search for an update and find that the software hasn’t been updated in years. These are what I like to call zombie apps. They work while the “host”, i.e. smartphone, provides the perfect environment, but once that ends, so does the app. It is strange because often the apps are quite good, otherwise you wouldn’t care I guess.
A good example of this is SKRWT, an app which corrects perspective distortion, and performs all-purpose lens distortion correction. It even won a “Best of” award in 2014 when it debuted on the app store. But now it is all but a zombie. The website still exists, but I doubt there is much going on there. There are of course tell-tale signs. The last Instagram post, touting a “Version 1.5” was December 2020. Half the links don’t work anymore. It’s a bit of a pity because the app itself works really well – the benefit of an app that does one thing and does it well. But unfortunately it’s an all too common story in the world of apps. Small-time developers loose interest in actually maintaining the code base of an app. Every time you update the operating system on a phone or upgrade the phone you basically have to purge all the apps that don’t work… and there are always too many.
It’s kind-of why I think the age of apps is done. I always manage to find very cool photo apps, but honestly they never last long, either becoming zombie, and eventually dead apps. Not that I download many apps at all these days. It’s actually hard to find the energy to download and use apps that may be pretty mediocre (and the net is full of articles why – apps that don’t work offline, poor security, poor design that doesn’t consider the user, lack of functionality, attempts to reproduce physical functionality in digital, apps that are slow, poor usability, etc.). It almost seems like people have little or no understanding about designing apps. Even when they do get it right, like SKRWT, it doesn’t translate to universal acceptance (or maybe it’s lackadaisical developers).
Bottom line is that if you are not willing to maintain an app for a reasonable amount of time, then don’t bother developing it, or develop it as open-source.
Fortran Re-engineering: Debt repayment schedule (vi)
The final thing that would be done is to remove the dependency on file input. This means just removing the file input code, and instead offer the user an interactive experience. This isn’t that difficult, the only caveat being that there has to be some means of choosing to do another calculation in the program. First we essentially remove all the file related code, and replace it with prompts and input statements (at the start of the loop).
write(*,*) 'Principal amount: '
read(*,*) amt
write(*,*) 'Interest rate (0-100%): '
read(*,*) iRate
iRate = iRate / 100.0
write(*,*) 'Delay (years): '
read(*,*) delay
write(*,*) 'Repayment period (years): '
read(*,*) numP
write(*,*) 'Start year: '
read(*,*) bdate
Lastly a series of statements are added to the end of the loop to ask the user if they want to perform another calculation.
read(*,*) answer
if (answer == 'no') then
exit
end if
Here answer is simple a string of length 3.
character (len=3) :: answer
Now when the program runs it looks like this:
Principal amount:
1000
Interest rate (0-100%):
4.7
Delay (years):
3
Repayment period (years):
10
Start year:
2021
Repayment Schedule
Loan date: Dec. 31, 2021
Amount borrowed: 1000.
Interest rate: 4.70%
Loan period: 10 years
Repayment to begin after 3 years
Future amount to repay: $ 1148.
repayment principal
year amount interest reduction balance
----------------------------------------------------------------
2025 146. 54. 93. 1055.
2026 146. 50. 97. 958.
2027 146. 45. 101. 857.
2028 146. 40. 106. 751.
2029 146. 35. 111. 639.
2030 146. 30. 116. 523.
2031 146. 25. 122. 401.
2032 146. 19. 128. 274.
2033 146. 13. 134. 140.
2034 146. 7. 140. 0.
Total interest charged: $ 465.
Perform another calculation? (yes/no)
no
Here is the full program:
program debtRepayment
implicit none
! debt repayment schedule
integer :: j, year, delay, numP, bdate, reason
real :: iRate, int, intamt, amt, cmpamt, pmtamt, balrd
character (len=3) :: answer
do
! Read in the data
write(*,*) 'Principal amount: '
read(*,*) amt
write(*,*) 'Interest rate (0-100%): '
read(*,*) iRate
iRate = iRate / 100.0
write(*,*) 'Delay (years): '
read(*,*) delay
write(*,*) 'Repayment period (years): '
read(*,*) numP
write(*,*) 'Start year: '
read(*,*) bdate
1 format(f7.0,f2.2,2i3,i4)
write(*,2) bdate,amt,iRate*100,numP,delay
2 format(20x,'Repayment Schedule'//5x, &
'Loan date: ', 'Dec. 31, ',i4,/5x, &
'Amount borrowed: ', f7.0,/5x &
'Interest rate: ', f5.2, '%',/5x, &
'Loan period: ', i3,' years',/5x, &
'Repayment to begin after ',i3,' years')
! Calculate the future amount via compound interest, A=P(1+r)^n
! where P=original amount, r=interest rate, n=no. periods before
! repayment begins
cmpamt = amt * (1.+ iRate)**delay
write(*,3) cmpamt
3 format(5x,'Future amount to repay: $',f8.0)
write(*,4)
4 format(/14x,'repayment',16x,'principal'/5x,'year',7x,'amount',4x, &
'interest',5x,'reduction balance')
write(*,*) repeat('-',64)
! Calculate repayment installments
pmtamt = cmpamt / (((1.+iRate)**numP-1.)/(iRate*(1.+iRate)**numP))
do j = 1,numP
year = bdate + delay + j
int = cmpamt * iRate
balrd = pmtamt - int
cmpamt = cmpamt - balrd
write(*,5) year,pmtamt,int,balrd,cmpamt
5 format(5x,i4,6x,f8.0,3x,f8.0,5x,f8.0,6x,f8.0)
end do
intamt = pmtamt * float(numP) - amt
write(*,6) intamt
6 format(/5x,'Total interest charged: $',f8.0)
write(*,*) 'Perform another calculation? (yes/no)'
read(*,*) answer
if (answer == 'no') then
exit
end if
end do
stop
end
Fortran Re-engineering: Debt repayment schedule (v)
The program does work, but suffers from some usability issues. Foremost, re-directly input can be efficient, but if we want to use the program interactively, we need to change how things work. This means adding a user interface, which could possibly change the way the input is handled. One of the first issues is allowing the used to input the filename, rather than using redirected input. This just requires a piece of code to deal with the user input of the filename, and making sure the file exists before proceeding. Below is the code which deals with the filename input and verification:
write(*,*) 'Filename? '
read(*,*) fname
inquire(file=fname, exist=lexist, form=formL, size=fsize)
if (.not. lexist) then
write (*,*) 'File does not exist.'
stop
else
open(unit=20,file=fname,status='old',action='read')
end if
This just requires the addition of a few variables:
integer :: fsize
character (len=25) :: fname
character :: formL
logical :: lexist
Also the pointer to the file has to be modified to “20” as indicated in the call to open().
read(20,1,iostat=reason) amt,iRate,delay,numP,bdate
The other issue is the output, which is a bit of a “dog’s breakfast”. Here is a run of the program:
Filename?
test.dat
1 Repayment Schedule
loan date dec. 31, 1978 amount borrowed 100000. interest rate 0.10
repayment to begin after 5 years
repayment principal
year amount interest reduction balance
161051.
1984 50807. 16105. 34702. 126349.
1985 50807. 12635. 38172. 88177.
1986 50807. 8818. 41989. 46188.
1987 50807. 4619. 46188. 0.
total interest charge 103228.
The output could do with some added information. The table seems okay, but the information surrounding it could be made clearer. Mainly the summary information above the table, which is also missing a key input, the number of years of loan repayments (which one could infer from the table, but best to make things clear. Below is one rendition of what an improved output would look like:
Repayment Schedule
Loan date: Dec. 31, 1978
Amount borrowed: 100000.
Interest rate: 10.00%
Repayment period: 4 years
Repayment to begin after 5 years
Future amount to repay: $ 161051.
repayment principal
year amount interest reduction balance
----------------------------------------------------------------
1984 50807. 16105. 34702. 126349.
1985 50807. 12635. 38172. 88177.
1986 50807. 8818. 41989. 46188.
1987 50807. 4619. 46188. 0.
Total interest charged: $ 103228.
The information is now much clearer. The interest rate is now expressed in terms of 0-100% versus 0-1.0%, which is not as readable. The rest of the information has just been moved around to improve its aesthetics. Here is the program, with associated changes made to the format statements. The addition of an extra format statement facilitated the need for an extra label.
program debtRepayment
implicit none
! debt repayment schedule
integer :: j, year, delay, numP, bdate, reason, fsize
real :: iRate, int, intamt, amt, cmpamt, pmtamt, balrd
character (len=25) :: fname
character :: formL
logical :: lexist
write(*,*) 'Filename? '
read(*,*) fname
inquire(file=fname, exist=lexist, form=formL, size=fsize)
if (.not. lexist) then
write (*,*) 'File does not exist.'
stop
else
open(unit=20,file=fname,status='old',action='read')
end if
do
! Read in the data (redirected from file)
read(20,1,iostat=reason) amt,iRate,delay,numP,bdate
if (reason < 0) then
exit
end if
1 format(f7.0,f2.2,2i3,i4)
write(*,2) bdate,amt,iRate*100,numP,delay
2 format(20x,'Repayment Schedule'//5x, &
'Loan date: ', 'Dec. 31, ',i4,/5x, &
'Amount borrowed: ', f7.0,/5x &
'Interest rate: ', f5.2, '%',/5x, &
'Loan period: ', i3,' years',/5x, &
'Repayment to begin after ',i3,' years')
! Calculate the future amount via compound interest, A=P(1+r)^n
! where P=original amount, r=interest rate, n=no. periods before
! repayment begins
cmpamt = amt * (1.+ iRate)**delay
write(*,3) cmpamt
3 format(5x,'Future amount to repay: $',f8.0)
write(*,4)
4 format(/14x,'repayment',16x,'principal'/5x,'year',7x,'amount',4x, &
'interest',5x,'reduction balance')
write(*,*) repeat('-',64)
! Calculate repayment installments
pmtamt = cmpamt / (((1.+iRate)**numP-1.)/(iRate*(1.+iRate)**numP))
do j = 1,numP
year = bdate + delay + j
int = cmpamt * iRate
balrd = pmtamt - int
cmpamt = cmpamt - balrd
write(*,5) year,pmtamt,int,balrd,cmpamt
5 format(5x,i4,6x,f8.0,3x,f8.0,5x,f8.0,6x,f8.0)
end do
intamt = pmtamt * float(numP) - amt
write(*,6) intamt
6 format(/5x,'Total interest charged: $',f8.0)
end do
stop
end
What has changed?
- The
formatstatement (lines 29-34) has been rationalized to produce better looking output, and make the code itself easier to read. Many items were put on their own line, and a line for the repayment period was added. - The “future amount to repay” has been given its own line, and removed from the table (lines 40-41). Essentially this was achieved by pushing the column headings down.
- A dashed line has been added below the column headings, using the
repeatfunction (line 46). - The “total interest changed” on line 60 has been cleaned up.
- Labels 4 and 5 in the reengineered program were changed to labels 5 and 6.
- The column heading were removed from
formatat label to and assigned their ownformatstatement associated with label 4.
The Craft of Coding 