Karatsuba Multiplication

Everyone knows how to multiply large numbers. But there is a faster way. What’s interesting is that it was only discovered as recently as the 1960s, by Karatsuba. It makes me wonder how many other things are right under our noses that millions(billions?) of people know about over the course of centuries but nobody has thought of a better way… yet.

I implemented the algorithm bellow in C. The key idea is that it’s possible to save a multiplication by doing arithmetic.

In defense of PHP

This past weekend, I took a quick overnight trip to NYC to attend Code Montage’s, Coder Day of Service in Manhattan. It’s a great event where people donate their technical skills and time to help others who don’t have technical skills but have needs in the nonprofit realm. I worked with a woman who wanted to build a website to bring awareness to a cause she was passionate about.

She wanted the website to include posts with links to resources around the issue and testimonials from others involved with the same issue to build a community. It was great working with her and helping her address her needs.

What I found the most interesting from a technical standpoint was some of the previous advice she received about how to go about building such a website. Someone else at the hackathon had previously recommended that she look into Victory-Kit, a static-based website generation project which hasn’t seen any pull requests or other activity for over four months. It’s generally a bad idea to build any kind of website for end-users based on a dormant project: abandoned code means numerous unpatched bugs, undeveloped features. These sites are also really hard to support once the hackathon is over and the end user has to go to someone else for code maintenance.

Another person at the table recommended we do it using Jekyll with Chef. Chef’s a really great option for programmers because it allows maximum flexibility and control, but it’s only great for people who really know what they’re doing and have the time to devote to development. This was not a great idea for a non-technical user working on non-profit projects with tons of other things on her plate.

Interestingly enough, although it was the obvious solution nobody thought to use WordPress. It just works, it’s a mature technology, it has a vibrant community around it, tons of plugins, many free themes and many more premium themes that end-users can customize fairly easily without any programming knowledge.

There is a distaste for any PHP based technology in the web development community and I suspect I know why. A lot of blogs and comment boards disparage PHP recommending to use Ruby, Python, NodeJS or anything else, as long as it’s not PHP. I wonder if most of these haters formed their opinion of PHP a decade ago and haven’t looked at it since.

I bet most critics have no idea what modern PHP or PHP frameworks look like. I am glad the PHP community largely ignores the hate and continues to produce excellent code that just works.

Radiation in 5 minutes

Every time I talk to family/friends/read news article about Fukushima/Chernobyl/Nuclear Energy I run into a lot of ignorance about what radiation actually means. What surprised me when I did some research on the topic a few years back is how you don’t need a lot of sophisticated mathematics to be able to understand the risks. You need at most elementary level mathematics and some basic facts.

Two questions to ask about any radiation news story:

What type of radiation is it?(alpha,beta,gamma)

Alpha is only deadly if ingested or inhaled. Beta doesn’t travel far and won’t penetrate thick clothing. Gamma will penetrate in the deep tissue and cause cancer.

How much radiation?(rems,sieverts or grays).

Death from cancer in population is 20% before any radiation exposure listed bellow. That means 1 out of 5 people in the world will die from cancer. Usually cancer happens later in life.

LINEAR HYPOTHESIS: model used in radiation protection to quantify radiation exposition and set regulatory limits. It assumes that the long term, biological damage caused by ionizing radiation (essentially the cancer risk) is directly proportional to the dose.

Linear Hypothesis appears to be biased with a pessimistic outlook on effects of low radiation exposure for humans.

Measuring Radiation: milliSievert

0.1 uSv = Eating a banana
7 uSv = Dental X-Ray
3.1 mSv/year = US from all sources including medical
Fukushima 1.42uSv/hr for 2 weeks = Additional 0.16 mSv

2.0 Sieverts = 10% chance increase of cancer
1.0 Sieverts = 5% chance of increase of cancer
0.2 Sieverts = 1% chance increase of cancer
All in addition to the 20% you already have

Additional risk of exposure after two weeks at Fukushima? 0.008% increase of cancer.

CLJ-DS is worth checking out

I like Clojure. I really like it. I think it’s the best language available on the JVM. Why would anyone want to use Clojure? One word: Concurrency. Clojure is largely designed to address the needs of dealing with concurrency without resorting to primitive constructs such as locks.

Unfortunately using Clojure on projects isn’t always a feasible option because many projects are locked into the existing Java paradigm technically, culturally and economically. I often end up writing concurrent code in Java so having good data structures that minimize locking is a must. I find that most code I inherit that uses a lot of “synchronized” can often be rewritten to drastically cut down on the number of locks thanks to java.util.concurrent and java.util.concurrent.atomic. The part I always missed was an immutable data structure that could be returned to the calling code. This could be achieved by returning defensive copies of every mutable data structure but there is a slicker way.

CLJ-DS is another solution to the problem. It’s a library of Clojure’s persistent data structures ported back to Java with nice Generic type signatures and convenience static methods.

Here’s a typical example of code I often inherit. All the business logic and business variable names have been removed.

Some obvious problems with this code?

  • Since ‘getElements’ returns a mutable set, there is no guarantee that some code outside of ‘FooManager’ won’t ‘.clear()’ or mutate the returned set any further.
  • This code has subtle differences depending on ‘uuid’ existing in idToSet. When ‘results’ is null there might be an expectation of the empty set to be referenced by ‘idToSet’ just as it is in the non-null case.
  • Once the calling code gets a handle on the synchronized ‘results’ from ‘getElements’ it’s not guaranteed that everything is safe since ‘addElement’ uses a different lock to writes to the set in the non-null case.

There’s a better way using CLJ-DS and java’s concurrent package:

No subtle mutations of state and a lot fewer locks and by definition less lock contention. I consider the revised version a lot easier to reason about in no small part because of CLJ-DS library. PersistentMap and PersistentSet implement java.util.Map and java.util.Set respectively.