Day 22/100 Fibonacci and Factorial Trailing Zero

Day 22/100 Fibonacci and Factorial Trailing Zero

Failure at Grade School Arithmetic

So, I was at conversation the other day, where the other person was touting the virtues of Python, and dissing C language. You know, the language I'm using to do 100 Days of Code challenge. Truthfully, I did encounter a few "Segmentation Fault" core dump error, but I simply took it in stride. What I didn't know, I soon find out. It's part of the learning process.

Why would anybody do it differently? Why would you blame the programming language when you're supposed to increase your own skill so that you no longer make mistakes, instead of expecting the computer to catch yours?

If you look at my programs, you'll see my tendency to be light on error checking routines. What can I say? I don't make that many mistakes. Sure I made some. Everybody does. The difference between me and other people is that I learn from my mistakes and not repeat them. I don't see that kind of commitment from your average coder. This is why I wonder if the oft claimed "Coding makes you smarter" is incorrectly attributed to survivor bias.

Pardon me for having a dim view of the situation. I have seen too many stupid people who don't know what they're doing, make bold claims that are obviously false. Let's not spread more misinformation than what is already out there.

The title above is being honest. The failure does not lie in coding, regardless of platform or programming language chosen. The failure is at grade school level of arithmetic. I'm talking about 5th grader arithmetic here! Add, subtract, multiply, and divide. It doesn't even involve any fraction! How hard can that be?

Very hard, it turns out. Let's take a look at fibonacci code I've written. I did it twice: First is my take on it. The second is what is commonly done by the community, assuming neither Dynamic Programming (memoization) nor Recursion is involved. This is LeetCode 509:

long long fib1(int n) {
  int i=1;
  long long m[2];
  if (n<1)  return 0;
  if (n>92) return -1; //oob
  for (m[0]=1,m[1]=1;--n;i=1-i) m[i]+=m[1-i];
  return m[i];
}

long long fib2(int n) {
  int i=0; long long a=0;
  long long b=1;long long c=1;
  if (n<1)  return 0;
  if (n>92) return -1; //oob
  for (a=0,b=1,c=1;--n;) {
    a=b; b=c; c=a+b;
  }
  return b;
}

As you can see, my version is more compact than what is usually done. It uses only 2 variables, stored as array, so that I can flip between them. Testing does take a while, but if you pride yourself as a software engineer, then you would want to do it that way! Although mathematicians can resort to recursive solution, software engineer cannot do that! For you to take pride in your coding skill as software engineer, the code has to be extremely tight, and no waste either running time (recursion) or memory (memoization). 

The second solution is actually acceptable. It's very commonly done by people who aren't mathematically sophisticated. It's kind of like FizzBuzz challenge. Sure, it's easily done, but is it optimum? Not really. So, the second solution is acceptable, but nothing to be proud of.

As far as recursion and memoization? In my very strong opinion, those are failures! Waste of cycles and bytes! Very unprofessional! I always say that my code is at amateur hobbyist level, but looking at some of these professional coding, I wonder if I'm not already better than most of them.

A second example is even more telling than the fibonacci problem. The problem is to count the number of trailing zeros in factorial. LeetCode 172. Now, we're talking deep into mathematical realm. Sure, leet coder act like it's an easy thing to figure out. But is it? If you can figure out the deep mathematical issues, then surely you can also figure out the most efficient way to compute it? 

Nope! That's a fail! As far as I'm concerned, this kind of question does not belong in the interview process. Fundamentally, either you ran into the problem already, and remember the solution, or alternatively, you haven't run into it previously, and will now have to compute large samples of factorials to try to determine some kind of patterns that you can recognize. Oh, do you know that in these kind of interviews you cannot use any kind of help including computers and browsers? That's right! You only have the white board to do it.

What that tells me is that the company who does these kind of things will fill up their ranks with people who memorize LeetCode problems, instead of the smart coder who can readily research the issue. What's that Einstein, Feynman, et al said? "Do not memorize things that can be looked up?" Exactly!

Let's see what the typical answer is involved. You can probably google this in just a few minutes:

int trail1(int n) {
  int c; int i;
  for (c=0,i=5;n/i>=1;i*=5) {
    c+=(n/i);
  }
  return c;
}

Looks nice and easy, doesn't it? But it's deceptively tricky. Can you even work out the problem even after looking at the code? I certainly cannot! I'm no mathematician. I need to see rows of factorials and count the zeros to get some kind of pattern recognition going. This question is not an easy question, despite the brevity of the solution.

So, am I a failure? Maybe as a mathematician. However, as a coder? Not only would I pass, those people who give the answer above are all failures! Remember, we're evaluating coding skills, here, not math skills. The only math skill you need is grade school level arithmetic! That's right! No more than arithmetic. Hence the failure is of at grade school level. Now tell me, what kind of highly skilled, highly experienced, highly paid, professional computer programmer would fail grade school math? Only impostors do.

You need to have proper foundation in your skills! This goes double if you want to be a professional! No short cuts! If you cannot do grade school arithmetic, I suggest taking up coding as a hobby, rather than being a professional.

Here is the proper solution to the question:

int trail2(int n) {
  int c=0;
  for (;n/=5;c+=n);
  return c;
}

One division, and one addition. That's it! 

Look, coding is hard. I understand that. What I don't understand is why would people fail at grade school arithmetic! The usual solution as shown above features 2 divisions and a multiply. How is that better? It's not better. It's not professional at all!

How many years ago did you first learn arithmetic? Are you still at that level? Sigh.

Sorry to be so negative about things, but I'm seeing way more incompetence going on lately than what it used to be. Unfortunately, it seems that people just don't care anymore. That's a dangerous attitude to have. In the worst case scenario, it will mean the whole destruction of the industry as we know it. Don't laugh. It happened before. Look up "Dot Com Meltdown" if you don't believe me. That's the equivalent of "Game Industry crash" or even "Great Depression" level of apocalyptic event. Let's not have another one, okay?

Sigh.

I keep telling people to learn fundamentals, but people just don't bother. They refuse to do so. Why would they? A convenient library is just a download away! Until one day, one of those library disappear and if you google "... brought down the internet", you will find some incredible stories that shouldn't happen, but that they happened!

Study your fundamentals!

Lookit dem Smileys...

int d8(int B) {
  int              O;
  return  (O=  (B  /=  5)
  )?  O+   d8  (B  ):  0;
}

One more thing: Python isn't English! That distinction belongs to Literary Programming as pioneered by Dr. Donald Knuth. Alternatively, you can pull up just about any Design Document. Are you a Rockstar computer programmer?