Long

From int to long

The past few days, I have been working on a programming assignment to develop efficient multiplication algorithm. I have passed all graded test cases but got stuck at the non-graded challenge task, task Y. The requirement is 500k-digits numbers multiplication in 2 seconds.

My algorithm made use of both Karatsuba algorithm and a technique to combine neighbouring digits together (similar to converting from decimal to a large base).

Initially, I used int for all the variables, which allowed me to combine 8 digits at a time. This got me 2/10 points for the task. Then I thought why not use long? (I was using Java so no long long, and we were prohibited from using BigInteger) After changing my variables to long, I discovered that I could only increase the max digits from 8 to 10 before errors in the result showed up. I knew that theoretically the max digits should be around 16, but I did not bother finding out why and assumed that other parts of my code is limiting the max digits.

Two days later, after exhausting other possible optimization techniques, I still could not get better than 2/10, so I decided to investigate the issue with max digits. This time, I used the debugger and checked all the intermediate steps carefully. And I finally found out what was wrong: I constructed an array with base 10 raised to different powers, for combining the digits. However, the array was in the int range, therefore causing the error when increased the threshold for max digits. After resolving the issue (changing it to long), I was able to get 4/10 for the task. It might be that I need a much better algorithm for full marks, but at that point of time, I was filled with joy for figuring the bug out.

Long term goal

Setting a long term goal is important. I only truly appreciated it after experiencing regrets. When I started playing games, I was always able to identify an ultimate goal for me and work towards it. If I found out that the goal was too hard to achieve, I would drop the game. If I managed to achieve the goal after putting in a lot of effort, I will look for another one.

However, game is too short compared to life. What I thought was the long term goal was too short. Before I graduated from junior college, all I wanted was entering a good university with good computer science department. I assumed that this would lead me to my next goal naturally. Now it looks like I was thinking too short term. I failed to see many other factors that would affect the really long term, like the well-being of the IT industry, the general perception of technology and what I envision myself to be 20 years down the road.

It is funny that I actually did an exercise back in junior college on “what I imagine myself to be in 20 years”. It was my best chance to plan for long term. However, I wasted it by putting down vague descriptions like “working in a company of global scale”, without actually thinking through what it meant.

Now I really need a long term goal, but how long? Should it be more than 5 years? Or even 10 years? Going back to the discussion of games, it should be challenging, and it should take a lot of effort. Obviously getting an internship would not fulfill the criteria of challenging, neither would graduating from NUS with a job offer. This time, I need to think through, considering the feasibility and the challenge, the possible avenues and obstacles.

TBC…

Leave a Reply