Vinod Kurup

Hospitalist/programmer in search of the meaning of life

On Factoring Large Numbers

I wonder how many of my blog posts are based on stories from This American Life. Probably not enough. Every time I start to listen to a show, I’m certain that I’m not going to be interested and within a minute I’m trapped and can’t stop listening. It’s that good. A recent show was about people who people who pursued crazy ideas. The first story was about a mathematician named Frank Nelson Cole. Marin Mersenne had claimed in the 17th century that 267-1 was a prime number. He was prominent enough that the claim was felt to be accepted wisdom and there was certainly no way to test the claim in the days before computers. That’s a big honking number: 147,573,952,589,676,412,927.

In 1903, Frank Nelson Cole walked into a meeting of mathematicians to present his talk. The title was boring, something like “On the factoring of large numbers”. Without speaking a word, he walked up to the chalkboard and started to write a large number, followed by another large number and then started to multiply them together. It took a while, but by the time he started to get towards the solution, the crowd of mathematicians understood that he was proving that he had found two numbers whose product was the famous “prime” number 267-1. As he came close to finishing, the anticipation peaked and cheering began. He finished the calculation and sat down, never speaking a word.

Stories like that give me the chills. Can you imagine how excited he must have been when he found those 2 roots? I get that sensation every once in a while when I make a programming breakthrough, solving a problem which I had been banging my head on for a while. It’s nowhere as profound as what he did, but I think I can understand the exhilaration he must have felt.

I decided to see what those 2 roots are, using my new favorite language, Clojure. I’m by no means an expert in anything, let alone programming and especially functional programming, but here’s how I went about it. The REPL is such a fun way to explore things like this:

  1. I need a range of numbers which I’ll then test one-by-one to see if they divide into 267-1 evenly.

     user=> (def n 18)
     user=> (range 2 n)
     (2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17)
  2. I need a way to take a square root. (There’s no need to check numbers higher than the square root of 267-1)

     user=> (Math/sqrt n)
  3. So the numbers I need to test are:

     user=> (range 2 (inc (int (Math/sqrt n))))
     (2 3 4)
  4. I need to find the remainder of a division (Of note, mod also does the same thing, but rem is a lot faster)

     user=> (rem 9 2)
  5. Can I find all the lower roots of a number? The #(...) syntax is syntactic sugar for an anonymous function. The % is a placeholder for the value which is being iterated over. So the following function takes each value in the list returned by range and supplies it to rem. If that rem function is equal to zero, then the #(...) anonymous function returns true and filter keeps the value.

     user=> (def n 100)
     user=> (filter #(= (rem n %) 0) (range 2 (inc (int (Math/sqrt n)))))
     (2 4 5 10)
  6. Now let’s map over each of those values, finding the corresponding higher root for each value. vector creates a vector (think list) with the first value being the supplied value and the second value being the other root (/ n %):

     user=> (map #(vector % (/ n %)) (filter #(= (rem n %) 0) (range 2 (inc (int (Math/sqrt n))))))
     ([2 50] [4 25] [5 20] [10 10])
  7. Based on that experimentation, here’s my first stab at the function:

     user=> (defn roots [n]
              (let [lower-factors (range 2 (inc (int (Math/sqrt n))))
                    is-factor? (fn [a] (= (rem n a) 0))]
                (map  #(vector % (/ n %)) (filter is-factor? lower-factors))))
     user=> (roots 294)
     ([2 147] [3 98] [6 49] [7 42] [14 21])
  8. Now let’s get our big number (267-1)

     user=> (dec (Math/pow 2 67))
  9. Hmmm… that looks like it might not be a precise value. Oh well, let’s try it:

     user=> (roots (dec (Math/pow 2 67)))
     ([2 7.378697629483821E19] [3 4.9191317529892135E19] [4
     3.6893488147419103E19] [5 2.9514790517935284E19] [6
     2.4595658764946067E19] [7 2.108199322709663E19] [8
     1.8446744073709552E19] [9 1.6397105843297378E19] [10
     1.4757395258967642E19] [11 1.3415813871788765E19] [12
     1.2297829382473034E19] [13 1.1351842506898186E19] [14
     1.0540996613548315E19] [15 9.838263505978427E18] [16
     9.223372036854776E18] [17 8.6808207405692006E18] [18
     8.1985529216486892E18] [19 7.7670501362987581E18] [20
     C-c C-c (ABORT, ABORT!!!)
  10. OK, that didn’t work. It clearly found way too many roots, because 267-1 was an approximation. We have to use BigIntegers which have appropriate precision even with large numbers.

     user=> (def two67minus1 (dec (.pow (BigInteger. "2") 67)))
     user=> two67minus1
  11. Cool, that looks more precise than our previous value. To see the difference, check their type.

     user=> (type (dec (Math/pow 2 67)))
     user=> (type (dec (.pow (BigInteger. "2") 67)))
  12. OK, Time for the big test:

     user=> (roots two67minus1)
     ([193707721 761838257287])
  13. Cool!!! It works! Those are the roots of 267-1. How long did that take to compute? (We need doall to make the time command wait for all of the values to be calculated, otherwise it will return after the first value is calculated. This has something to do with the laziness of clojure sequences)

     user=> (time (doall (roots two67minus1)))
     "Elapsed time: 2.2697318183297E7 msecs"
     ([193707721 761838257287])

6 hours 18 minutes. I’m sure there’s a quicker way to do this. I do a lot of redundant testing. For example, once we know that 2 is not a factor, we shouldn’t check any more even factors. I’d be interested in any advice to make it run faster.

I can’t even fathom how you’d go about doing this without a computer. Can you imagine how frustrating it must’ve been any time you had a simple error? Just amazing…

ClojureScript and PhoneGap

Phonegap is a tool that allows you to develop apps in HTML5 + javascript and makes it easy to deploy them to multiple mobile platforms, including Android and iOS.

ClojureScript is a dialect of the awesome language, Clojure, that compiles to Javascript (after a pass through the Google Closure optimizer). Because Clojure, ClojureScript and Google Closure can be confusing terms, I’ll use CLJS instead of ClojureScript for the remainder of this post.

What I wanted to do: Write a simple CLJS app that runs on my Android phone using these tools.

Get HelloWorld working with PhoneGap

Following these instructions will get the Android SDK, Eclipse plugin and PhoneGap working. If you already have the Android SDK, you’ll be able to skip most of it. I’m most comfortable in Emacs, so I’ll be using that instead of Eclipse. Here is the command-line command for creating your project (the -t refers to your android target which you can find by doing android list avds):

$ android create project -n HelloPhoneGap -t 2 -p HelloPhoneGap -k com.phonegap.helloworld -a App

By the end of these instructions, you should have a copy of an app called HelloPhoneGap on your phone which, when clicked, shows a ‘Hello World’ screen.

Setup CLJS

Follow the simple instructions, recreated here because they’re just so simple.

$ git clone git://
$ cd clojurescript
$ ./script/bootstrap

That’s it. The CLJS compiler and REPL are ready to work.

Get HelloWorld working via HTML

Follow the instructions under the heading Using ClojureScript on a Web Page to build a Javascript file and associated HTML file for testing.

Put CLJS and PhoneGap together

OK, let’s make something a little interactive on the phone. I’m going to build a BMI calculator that takes a person’s height and weight in Imperial (i.e. American) units and calculates a Body Mass Index. BMI is simply weight divided by the square of height, with units of kg/m2.

Here’s the CLJS file:

(ns bmi)

(defn height [feet inches]
  (-> feet (* 12) (+ inches) (* 2.54) (/ 100)))

(defn weight [lbs]
  (/ lbs 2.2))

(defn bmi [h w]
  (js/Math.round (/ w (* h h))))

(defn ^:export alertDismissed []

(defn ^:export displaybmi [form]
  (let [h (height (js/parseInt form.f.value) (js/parseInt form.i.value))
        w (weight (js/parseInt form.l.value))]
    (js/navigator.notification.alert (bmi h w) hello.alertDismissed)))

Basically, we create simple functions to convert Imperial heights and weights to metric values, calculate a BMI and then use displaybmi to parse form parameters, calculate the BMI and show that result in an Android notification popup. alertDismissed is a callback that gets called when the user dismisses the notification. (I’m just discarding the information here). Those are the only 2 functions that are needed by the HTML file, so those are the only 2 that need the :export metadata tag. navigator.notification.alert is a PhoneGap API call that does the actual notification.

The calls prefixed by js/ are understood by the CLJS compiler to refer to the global JavaScript namespace. If you didn’t include that prefix, the compiler would assume you meant a call in the local bmi namespace, which would obviously fail.

Here’s the HTML file (in HelloPhoneGap/assets/www/):

    <title>BMI calculator</title>
    <script type="text/javascript" charset="utf-8" src="phonegap-1.0.0.js"></script>
    <script type="text/javascript" charset="utf-8" src="bmi.js"></script>
    <h1>BMI calculator</h1>

      Height: <input name="f" size="2"> ft. <input name="i" size="2"> in. <br>
      Weight: <input name="l" size="2"> lbs.<br>
      <input type="button" value="Calculate BMI" onclick="bmi.displaybmi(this.form)">

Now compile the CLJS and move the compiled JS file to HelloPhoneGap/assets/www/

$ ./bin/cljsc bmi.cljs '{:optimizations :simple :pretty-print true}' > bmi.js
$ cp bmi.js ~/dev/HelloPhoneGap/assets/www/

The :simple value for optimizations and the true value for pretty-print make it so that we can read the resulting JS file, but can be changed to :advanced and false respectively when ready for production.

Now, go back into the HelloPhoneGap Android project and compile it and send it to the emulator (C-c C-c i in emacs). You should now have a simple BMI calculator working on Android.

Next steps

The promise of PhoneGap is that you could use similar HTML/Javascript to create iOS versions as well, but I haven’t done that yet. There are tons of API calls available on both platforms which are supposed to give you the same access that native apps have. Using ClojureScript means you get to use a modern functional language to create your app, while getting access to the features that only JavaScript APIs provide.

Fixing Wireless on eeePC

I have an ASUS eeePC 1000, running Ubuntu 10.10. Wireless worked flawlessly at home, which is where I use it 99% of the time. On our most recent trip, however, it wasn’t working. It couldn’t connect to a WPA-secured network. Here are the relevant error messages:

NetworkManager[770]: <warn> Activation (wlan0/wireless): association took too long.
NetworkManager[770]: <warn> (wlan0): link timed out.
NetworkManager[770]: <warn> Activation (wlan0) failed for access point (linksys)
NetworkManager[770]: <warn> Activation (wlan0) failed.
NetworkManager[770]: <info> (wlan0): deactivating device (reason: 0).

After a little googling on my phone, I found out that others had this problem with the rt2860sta wireless driver. Fortunately, there is a solution, which involved downloading the source code for the latest driver, modifying it a bit and rebuilding the driver. Here are the instructions:

Step 1: Download the driver

Download the latest rt2860sta driver.

Step 2: Rename and extract the downloaded file

Mine was named download.php, but it’s really a tar file:
[email protected]:~ $ mkdir test
[email protected]:~ $ mv download.php test/driver.tar
[email protected]:~ $ cd test/
[email protected]:~/test $ tar xf driver.tar
[email protected]:~/test $ mv 2010_07_16_RT2860_Linux_STA_v2.4.0.0 driver
[email protected]:~/test $ cd driver

Step 3: Apply patch

Step 4: Backup old driver
[email protected]~/test/driver/ $ sudo ifconfig wlan0 down
[email protected]~/test/driver/ $ sudo rmmod rt2860sta
[email protected]~/test/driver/ $ mkdir backup
[email protected]~/test/driver/ $ sudo mv /etc/Wireless/RT2860STA backup/
[email protected]~/test/driver/ $ sudo mv /lib/modules/2.6.35-30-generic/kernel/drivers/staging/rt2860/rt2860sta.ko backup/

Step 5: Install and activate new driver
[email protected]:~/test/driver $ sudo make install
[email protected]:~/test/driver $ sudo depmod -a
[email protected]:~/test/driver $ sudo modprobe rt2860sta

Step 6: Fix problems with hibernation

A separate problem is that wireless has been flaky when the computer wakes from hibernation, but it’s also fixable.

Add the following lines to /etc/modprobe.d/blacklist.conf:

blacklist rt2800pci
blacklist rt2800lib
blacklist rt2x00usb
blacklist rt2x00pci
blacklist rt2x00lib

Create a new file called /etc/pm/config.d/unload_wireless with the following line:


Reboot and you should have WPA-compatible, hibernatable wireless.


  1. rt2860sta driver installation
  2. Proper hibernation
  3. Ubuntu Forums thread

Surprise, I’m 40!

Have you ever been in one of those dreams where everything seems normal and then a flying car (or something equally crazy) comes out of nowhere? I’m used to having experiences like that when I’m dreaming, but it was quite surreal to have it during waking hours.

Mala and Kavi had gone ahead (surreptiously to plan a surprise party for someone else!). We were to meet at the ferris wheel at the Navy Pier. I found her and she took my hand. She started leading me through the crowds of tourists. I could sense excitement in her demeanor, but didn’t think anything of it. She led me towards a group of people and I caught a glimpse of someone who looked like my Dad. That’s weird… why would he be here? It’s at that point that neurons started to malfunction and I began to feel like I was in a dream. Then I saw Mala’s mom and got even more confused. Slowly the group of strangers came into focus and revealed themselves as my friends and family from around the country. It was, without a doubt, the best birthday present that I have ever received, or expect to receive. Thanks to Mala for months of planning, and for wanting to make me feel special even though I feel this way every day when I wake up next to her. Thanks to all my friends and family who could make it and to the ones who couldn’t. If this is the culmination of 40 years on this earth, I can’t wait for the next 40!

Mala’s Bolognese

I have just had the most amazing Italian meal that I’ve had outside of Roberto’s in the Bronx. Mala made fresh homemade Pappardelle and a Bolognese sauce that she just learned at Revolution’s cooking class. The thing is, she made this yesterday, and I just tried it today as leftovers and it was still amazing. This sure is going to make going lo-carb impossible.

Kids and Computers

I’m sure it’s probably too early to worry about this, but I often wonder about the best way to introduce Kavi and Anika to computers. ‘Introduce’ isn’t the right word because even Anika has more experience with computers than I did at that age. So far, though, computers are something that Daddy and Mommy use to do work, not things that are for them. We’ll show them a Sesame Street video on YouTube or family pictures on Facebook, but they don’t spend any significant amount of time on it. They’re easily entertained without computers. I know that will change as they get older, but for now at least, they prefer their toys and their imagination to TV or computers. Even at their young age, that is rare.

The dilemma is that I do want them to learn about technology and learn how to use it in their lives without being controlled by it. I don’t see anything wrong with exposing them to things like computers, iPads, YouTube, etc., as long as it is monitored. I just want it to be a healthy portion of their leisure time, not all of it. So many children’s entertainment options are spoon-fed propaganda. They are meant to be passively enjoyed, and the child just sits and absorbs it. The source of the content is often questionable. Advertisers for big corporations or government trying to get their message to kids either overtly or subtly.

I like my childhood experience. My first major exposure to computers was an Apple IIe. There was nothing organized about it. I spent a large majority of my time playing games, but those were just the gateway drugs to get me to realize that there was much more power in those machines. The entire experience was about tinkering. Trying to figure out how it worked, how to make it work for me, how I could make it do things. The most exciting days in my childhood were the days that the inCider magazine arrived with pages of DOS code listings in the back. Retyping those code listings, making alterations, trying to figure out how things worked… that is much more healthy than just watching a video over and over again. I, of course, was much older than Kavi is now, so I’m not too worried. I just don’t want them to get addicted to a certain concept of what technology is for, before they have the skills to really take advantage of it.

Switching to Octopress

You may have noticed that I’ve rearranged the furniture a little. It’s been almost 2 years since I last redesigned my blog, so I’m way overdue for a pointless redesign. I’m now using Octopress which basically takes Jekyll and adds nice HTML5 templates, cross-browser stylesheets, jekyll plugins, and a few build scripts to automate common tasks.

Enjoy my new site and let me know if you find any issues. The source code for my site, as always, is at github. Please let me know if you have questions about it. I’m also taking bets on how long this design lasts.

Our Weight Loss Regimen

After writing yesterday’s post about how Mala and I have been losing so much weight over the past 8 months, I thought I should post a small sampling of the food that Mala has made for us in that time. Yes, I am a lucky, lucky man.

Red Wine Pot Roast Brisket Sandwich
Salad Steak
Valentine’s Brownies Beer Can Chicken
Homemade Pizza Homemade Pizza
Dulce de leche cupcakes Flank Steak
Steak, aligot, broccoli and red wine Homemade fried chicken
Beatty’s chocolate cake Peanut butter pie
Aligot (mashed potatoes with cheese) Fried chicken
Triple Chocolate Mousse Cake Triple Chocolate Mousse Cake
Strawberry Shortcake Curious George Cake
Elmo Cupcakes French Silk Pie
French Silk Pie Hot Dogs and Flank Steak (my only contribution to this page)

Hungry yet?

Why We Get Fat Review

Dear patients,

I am sorry. I have been giving you bad dietary advice. In medical school we learned that fat in your diet causes fat to accumulate in your arteries, causing heart attacks and strokes, so I told you to eat a low fat diet. Of course, looking back, we had no evidence to support that conclusion, but it just seemed rather obvious. Obvious ideas are often the most dangerous ideas of all. When you see a study that might confirm your obvious idea, you give it extra weight. When you see a study that might refute your obvious idea, you find problems with the study. When the idea is less certain, then you tend to give the empirical evidence more weight. This is what we’ve done with the hypothesis that dietary fat causes heart disease.

I just finished Gary Taubes’ ”Why We Get Fat. It’s not a perfect book, but I do recommend it. He dispels myths about why obesity occurs, explains what really causes it, and discusses why our current medical and public health approaches to obesity are hurting rather than helping. He starts out by dispelling the myth that obesity is caused by an imbalance of “Calories In” versus “Calories Out”, and more specifically, that obesity can be fixed by reversing that imbalance. This is something I certainly believed. I’ve always told patients to eat less and exercise more. It doesn’t work. Instead of calorie imbalance causing obesity, he states that obesity (and growth in general) causes a calorie imbalance. The increased amount of fat cells require more energy for sustenance, and therefore our bodies find a way to increase the amount of calories that we take in, compared to what we expend. So, while it is true that taking in more calories than you expend causes your weight to go up, it is not true that you have much control over your calorie intake or expenditure. That’s determined by hormones. This is the part that is counter-intuitive. It would seem that I could control the amount of calories that I eat or that I spend. You might have some control over what foods you put in your mouth, buy you have no control over how the calories are extracted or absorbed. You also have no control over the lower level hormonal signals that make you hungry. Those signals have evolved over millions of years to be very powerful because in prehistoric periods, if they didn’t work, you died. It’s hard to overcome that kind of evolutionary power with “willpower”. Even if you are successful in decreasing the calories that you eat, your body will naturally decrease the calories that you burn. The variables are dependent on each other.

This leads to the next question: Why do we get obese? If it’s not a simple matter of eating more calories than we expend, then why do we get fat? The culprit is insulin. Insulin causes the cells of our body to deposit fat. Insulin, in turn, is released whenever there is glucose in our system, which is preferentially caused by carbohydrate intake. The villain is carbs. Taubes goes into great detail about the workings of the endocrine system, explaining why insulin is such a powerful factor in causing fat deposition. It also explains the phenomenon of why people who have plenty of fat still get so ravenously hungry. Insulin prevents fat from being turned into energy so muscle cells have to use carbohydrates, a much smaller pool of energy. Once it runs out, intense hunger sets in and the eating cycle starts again. Reading these chapters took me back to my med school physiology courses. I learned all of this in med school, but we were never taught to connect these well accepted facts with the things that we were being taught in our dietary lectures.

Eliminating carbs from our diet without restricting any other nutrient will stop the fat deposition process, which in turn will decrease our calorie requirements, which will cause us to lose weight. There is quite a bit of genetic variation from person to person, so some individuals will be able to tolerate more carbs than others, and not everyone will be completely lean even without any carbs.

He spends a lot of time going over the history of dietary research dating back centuries. The danger of carbs was well understood and accepted in all scientific and nonscientific circles until the last 50 years or so, when there was a change that attributed obesity to behavioral weakness. This was started by the acceptance of the calorie imbalance hypothesis. Once people accepted the thinking that taking in more calories than you expend causes obesity, it was a short step to blaming obesity on the individual for not controlling their diet or exercising more. The focus of scientific research was taken off of fat deposition and on to behavioral changes.

I had been coming around to this conclusion slowly over the past few years (and am embarrassed that it has taken me this long). I remember reading about the Atkins Diet about 10 years ago and thinking how reckless Dr. Atkins was being by suggesting something which was so obviously wrong. My thinking started to change a few years back when I saw Mala struggle to lose weight despite strictly following an 800 calorie diet. I didn’t think that kind of calorie restriction was possible, but I watched with my own eyes as she did it and still barely saw results. That opened my eyes, and over the past few years, I’ve seen more and more results with low carb diets. Results which include weight loss, better cholesterol profiles, and overall better health. Interestingly, the diet recommendations that are provided in the book are from Eric Westman, MD, a UW trained physician who works just down the street from me.

Mala and I have been trying to get healthier over the past 8 months. My brother started a Biggest Loser competition amongst a bunch of us, and Mala won the first season. We’ve been exercising with more regularity and eating better. Together, we’ve lost over 80 lbs. To complicate the points that I’ve been making in this post, we have NOT been following a strict low carb diet, and we have been counting calories. On the other hand, I’m certain we’re eating less carbs than we did before. But Mala’s focus has been on making delicious (gourmet!) fresh food using “real food” ingredients. She’s tried to cut processed food completely out of our diet. I think that makes a huge difference. We’re not meant to eat chemicals and we have no idea what these chemicals are doing to us. Optimizing food for specific criteria, whether that’s low-fat, low-carb, or whatever, is bound to have unintended consequences. In that vein, I agree with Michael Pollan’s recommendation to “Eat Real Food”.

At some point, I’d like to review all the science behind the conclusions in Taubes’ book, just so I can have a better understanding for myself. I recommend that anyone treating patients (nurses, doctors, nutritionists, trainers) or anyone trying to get healthier read this book.

Some other much more entertaining and useful links:

Getting Through the Start of a Run

I love running. Wait, that’s a lie. I love running after I’ve finished my run. I also love it during those periods where I get my runner’s high, usually around the 30 minute mark, but often it happens multiple times after that point. I don’t love running when I’m contemplating going for a run. There are rare occasions where I’m just itching to go for a run, but usually I’m only able start a run by forcibly suppressing the compelling rationalizations that my brain develops. My brain is really good at finding reasons not to run. One trick that seems to work is to tell my brain that I have the right to turn around when I get to the mailbox at the end of the driveway. Of course, once I’ve done the mechanics of getting my shoes and starting, I never turn around. My brain is so gullible.

I also don’t love my run during the first 10 to 15 minutes. Those are always a struggle. Always. Stretching beforehand makes it less of a struggle, but I hate stretching, so I rarely do that. I have a few techniques to get myself through the beginnings of my runs.

  1. Count: Just count from 1 to 100. Once you get to a hundred, start over. This one works the best. That’s why it’s first!
  2. Mantra: Repeat a mantra to yourself. My favorites are: Keep covering ground (inspired by my favorite running book, Once a Runner) and Just keep swimming
  3. Food: Start thinking about what I’m going to eat after the run. OK, this rarely helps, but I can’t stop thinking about it.
  4. Slow: If I’m really feeling sluggish, then I force myself to slow down. As I’ve mentioned before, running slow is probably the most important running technique I have. It’s counter-intuitive, but it always work. Running slower than I think I should always makes the run go faster than I thought it would.
  5. Shorten: Shorten your stride. I aim to get 3 strides per second, which seems really quick to me. In order to do that I shorten my stride. I think most runners would benefit from a shorter stride. It automatically improves your form.

Basically, all of these are tricks to get your mind to focus on something else besides the pain of the run. One thing that also helps is to listen to music or podcasts. It works by the same principle of getting your mind off the pain, but I found that my best runs were always the ones where I left the iPod at home. It certainly makes the beginning of the run harder, but it frees my brain up to really listen to my body. I would otherwise find myself adjusting my pace to the beat of the music, rather than to the pace that my body naturally wanted to go. I also tend to have my deepest thoughts (don’t laugh!) when I’m running and having music pumped in would drown those out. I consider it my meditation practice, since I suck at real meditation. Finally, it’s a safety issue. When running in the woods, you never know what kind of creature will attack:

Take my advice for what it’s worth… running advice from a part-time runner who is slower than molasses. I’d love to hear any other running tricks you have!