The amazing adventures of Doug Hughes

Archive for the ‘Uncategorized’ Category

Testing for Perfect Numbers in Java with Streams

I was challenged recently to write a Java method that could validate whether a provided number was “perfect” or not. A perfect number is one where the sum of its divisors (excluding itself) add up to the number. For example, 28 is a perfect number because it’s divisors are: 1, 2, 4, 7, and 14. If you add these up you get 28, the original number.

However, consider 16. It’s divisors are: 1, 2, 4, 4, and 8. If you add these up you get 19. Therefore, 16 is not perfect.

This calculation was to be done via a static method that accepted an argument num. The method was to return a boolean indicating whether the number provided was perfect or not.

My first attempt was naive. I stared by using a for loop to loop backwards from one less than the number being tested to 1. I tested each step to determine if the number was divisible by the step. If so, I collected both numbers into a tuple which I collected into a HashSet to remove duplicates. I then iterated over the set and summed the values in the tuple and added 1. It worked, but was considerably inefficient.

It was pointed out to me that, because I was looping backwards, I was doing two times the amount of work needed. If I looped forward to half the number being tested I could simply create a sum of the valid divisors. Understanding this, I decided to try a few other approaches…

First, I wanted to see if I could make a one-line solution to this puzzle. In particular, I wanted to experiment with streams of numbers in Java. My first attempt used a stream of integers. I reduced this to those which were valid divisors of the number being tested and summed the resulting set. If this was equal to the number, the validation passed. If not, it didn’t. This is the code:

public static boolean reduceIsPerfect(long num) {
  return LongStream.rangeClosed(2, num / 2)
    .reduce(1, (sum, test) -> num % test == 0 ? sum + test : sum) == num;
}

Mission accomplished! It’s one (wrapped) line of code. However, this led me to wonder if I could parallelize this. So, my next test was to make a parallel stream of numbers that I then filtered to those that cleanly divided the number being tested. I then summed these, checked for equality to the original number, and returned that.

public static boolean parallelFilteredIsPerfect(long num) {
  return LongStream.rangeClosed(1, num / 2)
    // make this a parallel stream so we can find the whole divisors more quickly (ideally)
    .parallel()
    // filter out any non-whole divisors
    .filter(test -> num % test == 0)
    .sum() == num;
}

This too worked, though arguably it’s more than one line of code.

This success made me wonder how much (if at all) more efficient this method was than my first attempt. I wrote tests for the first six perfect numbers and found that the sixth one, 8,589,869,056, took quite a while to process. My first attempt with reduceIsPerfect() took about 45 secs to validate. My second attempt, parallelFilteredIsPerfect() took 23 seconds, so it was about two times faster. But, this left a bad taste in my mouth. 23 seconds is a really long time.

I tried a few other approaches, but found that, in general, most of my attempts tested in the 45 to 50 second range, which was disappointing.

So, next, I did what any good programmer would do, I turned to Google. I reasoned that the part of the process that takes the most time is determining if a number is a divisor or not. Google led me to a more efficient algorithm.

The way I was testing for perfection was by looping from 1 to half the number being tested. At each step I tested to see if the number could be divided cleanly. For example, with 28 I was doing this:

Start with a sum of 0. Loop from 1 to 14 (inclusive).

  1. 28 % 1. Yes! Add 1 to sum. sum is now 1.
  2. 28 % 2. Yes! Add 2 to sum. sum is now 3.
  3. 28 % 3. No!
  4. 28 % 4. Yes! Add 4 to sum. sum is now 7.
  5. 28 % 5. No!
  6. 28 % 6. No!
  7. 28 % 7. Yes! Add 7 to sum. sum is now 14.
  8. 28 % 8. No!
  9. 28 % 9. No!
  10. 28 % 10. No!
  11. 28 % 11. No!
  12. 28 % 12. No!
  13. 28 % 13. No!
  14. 28 % 14. Yes! Add 14 to sum. sum is now 28.

So, 28 is perfect.

But, Google pointed out to me that half of this information is already known by the time I calculate it. The divisors are 1, 2, 4, 7, 14, 28. As soon as I discover 1 I can quickly determine that it’s paired with 28. 2 is paired with 14, and 4 with 7. I don’t need to continue working at all once I’ve gone to 4! This is less than the square root of 28, 5.291502622129181.

So, if I loop from 1 to the square root of the number being tested, I can just take the number being tested as well as it’s paired divisor at the same time. Add these to the sum and I’m in business:

Start with a sum of 1. Loop from 2 to the square root of 28 (rounded down to 5) (inclusive).

  1. 28 % 2. Yes! Add 2 and 14 to sum. sum is now 17.
  2. 28 % 3. No!
  3. 28 % 4. Yes! Add 4 and 7 to sum. sum is now 28.
  4. 28 % 5. No!

And, again, I’ve confirmed that 28 is perfect.

With this in mind, I rewrote my original one line solution like this:

public static boolean reduceSqrtIsPerfect(long num) {
  return LongStream.rangeClosed(2, (long) Math.sqrt(num))
    .reduce(1, (sum, test) -> num % test == 0 ? sum + test + (num / test) : sum) == num;
}

And viola, my test of 8,589,869,056 went from taking 23 seconds to 3 milliseconds!! After all, rather than looping from 1 to 4294934528 and testing each step along the way, I am now looping from 2 to 92681! This is significantly less work.

And so, I’m fairly happy with the result. That, and, after all that, it’s just one line of code.

The full code and tests for this project have been posted to Github here.

Will the Real Doug Hughes Please Stand Up?

I heard that someone going by the name of Doug Hughes landed a gyrocopter on the lawn of the capitol building in DC. Sorry, but I am not that Doug Hughes.

It’s been fun and amusing to receive calls of support for the other Doug Hughes. I’ve received half a dozen calls for him. Most have been people gushingly praising him. Some have offered legal and financial support. Others have asked for interviews. Perhaps I should have accepted the cash and given the interviews?

Anyhow, I do support the other Doug’s ideas. We need to get the influence of cash out of our government. Corporations are not people, cash is not free speech, etc, etc.

I recently got ahold of the other Doug’s email address. I’m going to see if he minds me forwarding on these messages, but for now it’s safe to assume that I’m not able to forward these messages.

I’ve Always Wanted a Gyrocopter

Ye Olde GyrocopterI’ve Always Wanted a Gyrocopter!

I hear there may be one up for auction in DC soon.

Hmm…..

Please find a way to explain anti-vaxxer politicians to me!

Recently Chris Christie and Rand Paul made some comments supportive of the anti-vaxxer “movement”. This is really gives me pause.

These two are also both in the climate change denial camp. I always assumed that climate change denying politicians only did so because they receive money from climate change denying businesses, and/or pandering to the climate change denial demographic.

You see, I honestly picture politicians as being quite smart and savvy. (I’m not sure whether this is cynical or optimistic of me.) They have to be smart to weasel their way into power. It takes a degree of brilliance to convince the masses that something which is economically bad for them is actually somehow good for them. You’ve got to be sharp to pander effectively to a constituency without actually doing anything for them. You’ve got to be intelligent to find every way to increase your, your friends’, and your corporate overlord’s power and wealth without inciting the population to rise up with pitchforks and torches.

In other words, I have a hard time believing that politicians are actually dumb. I figured they actually believe in climate change, they just have a strong incentive to deny it and legislate against it. I figured they knew it was dumb to disallow scientists from advising the EPA.

But this anti-vaxxer situation makes me wonder if these politicians legitimately don’t understand science. Where’s the political advantage? The anti-vaxxer community can’t be nearly large enough to risk pandering to. And where’s the financial advantage? It’s not like Big Pharma is going to advocate for making less money.

Perhaps that’s it. If more people get sick with preventable illnesses they’ll be able to sell more medications, thereby making more profit? (Perhaps I need to make a tinfoil hat?) This doesn’t pass the smell test.

They only option I am left with is that these two politicians at least actually are scientifically illiterate. They must legitimately not understand the scientific method, how it is used test theories, find evidence, and draw conclusions. You can’t scientifically say that there is no climate change because it gets cold in winter. The evidence doesn’t match the theory.

If these two jackasses are representative of any significant portion of politicians, then we are all well and truly fucked. I for one, will require a lot of pandering to convince me it’s somehow good for me.

Should The Tech Sector do Blind Interviews?

I was on my way home today and switched on Marketplace on NPR. They were reporting on how Google and other tech companies are making efforts to diversify their work forces. From there, they branched off into a story of how the New York Symphony diversified their musicians.

It used to be that the symphonies were dominated by white males. To counteract this, the New York Symphony instituted (mostly) blind auditions. They went to great lengths to prevent the judges from seeing the auditioning musician, or being able to determine any other facts about them such as gender, height, weight, etc. This resulted in a 50% increase in the hiring of women!

So, if Google and others wish to (and should!) remove bias from their hiring practices, maybe they should find a way to prevent interviewers from seeing or even hearing candidates?

Consider this, large companies almost always have online forms that candidates fill out to apply for a job. These necessarily collect potentially telling information. For example, a name or email address can suggest a gender and ethnicity. The duration of past employment and schooling can suggest age. When you show up for an interview, whether on the phone or in person, more judgements can be, and are, made.

What if a hiring manager only received the bare bones information about a potential hire? Maybe they see an unsigned cover letter, a list of previous employers, previous responsibilities, areas of expertise, etc, but not length of employment. The hiring manager could exclusively communicate with the user via an anonymized email address generated for the user, or directly through the HR software being used. The phone would not be used. This would help avoid any hints from the user’s email address or voice.

Instead of a traditional interview, an online meeting could be established where there is either a third party relaying messages back and forth (like translation services for phone calls) or they communicate exclusively though instant messaging. Questions are asked, answers given, etc. Additionally, screen sharing and other collaboration tools could be used for things like coding tests, white boards, etc. Now the hiring manager can only judge the candidates based on their responses. With this more restricted type of communication, I think there’s a better chance that implicit bias could be removed from the process.

As I think about, all of the various tools exist, but perhaps not in one place. Perhaps this approach could even be facilitated by the major job boards and/or HR software? They could provide the tools I described in one integrated package, allowing hiring managers to be blind.

Would this be a perfect system? No. But, could this be a better system? Maybe. It might help lead to increased diversity, which has been shown to improve financial performance.

What do you think?

 

Alagad Inc is Hereby Closed. Long Live Doug Hughes, LLC

To paraphrase Monty Python:

It’s not pinin’! It’s passed on! This business is no more! It has ceased to be! It’s expired and gone to meet it’s maker! It’s a stiff! Bereft of life, it rests in peace! If Doug hadn’t dragged it out so long, it’d be pushing up the daisies! It’s metabolic processes are now ‘istory! It’s off the twig! It’s kicked the bucket, it’s shuffled off this mortal coil, run down the curtain and joined the bleedin’ choir invisible!! THIS IS AN EX-COMPANY!!

As of the first of October, 2014 I have officially ceased operating as Alagad Inc. This has  been a long time in coming, but the time has arrived. At the ripe age of 18 Alagad has ended. Enter Doug Hughes LLC, stage right.

Running Alagad was a wild, amazing, horrifying, unforgettable, stressful, heartbreaking, astonishingly awesome experience. I founded Alagad in 1996, while still in high school. Initially it was supposed to be a graphic design company, but that didn’t take off. Around 1997 it started to gain traction as a web development company. Throughout college it fed me, kept me housed, and stocked me with plenty of beer.

In the years since I have had the pleasure of working with a diverse range of more than 80 companies and organizations around the world. (I think… part of me wonders if that number gets bigger every time I say it…) I have worked with dozens of employees and contractors. I have worked tirelessly with some very awesome teams.

But now I’m moving into a new phase of my life. I’ve stopped imagining that Alagad will someday be my ticket to retirement. I am now working with a single steady client, less than 40 hours a week. I’m not working on any side projects or a Next Big Thing. I’m idling and recuperating and I couldn’t be happier about it.

As I idle I’m working with new hobbies such as engineering a homemade CNC machine, 3D printing (eventually), wood working, reading, spending time with my kids, any anything else that strikes my fancy. I’ve even returned to college via Arizona State University Online to finish up a bachelor’s in Software Engineering.

I’m also on what I call a Unicorn Hunt. What is this Unicorn Hunt, you may ask? Well, I’m keeping my ears to the ground for an amazing opportunity as a traditional employee. This opportunity would allow me to learn and use new programming languages, techniques, frameworks, approaches, etc. I would be a junior to mid-level team member working under some amazingly brilliant people from whom I can learn new things. I would be working on a single project that I believe in and which is interesting and challenging. And I want to be paid like an executive (or at least what I am currently making) and be able to either work remotely or within 15 minutes of home. Oh, and I want my own pet unicorn too!

If you have an opportunity, checkout my resume!

Doug Hughes LLC is the new Alagad Inc. Eventually I’ll move good blog entries from alagad.com to doughughes.net. If you have my doug@doughughes.net email address in your contacts you may wish to update it to doug@doughughes.net. My phone number is still 651-252-4234.

So, for now I idle. Life goes on.

Change, Fear, Life After Death

Back in 2009 my company, Alagad, had what I think of as The Big Layoff.  We went from about 13 employees and contractors down to three people in a matter of a fifteen minute phone call.  This wasn’t the first round of layoffs I’ve had to do, but it was the hardest.  I loved the people who worked with me.  I cared about them and their families and I felt as though I had personally failed them. Frankly, I did.  I’m sure that I could have done more to protect them, their jobs, and their families.  That said, they’ve all gone on to bigger and better things and I’m extremely happy for them.

In the year or so leading up to these layoffs I was constantly assaulted with panic attacks. My chest would seise, I’d get tunnel vision, my mind would shut down everything except worry.  White hot worry. I worried about the people who worked for me and the overwhelming responsibility I had to them.  I worried about paying my bills.  I worried about my family.  Through the support of my family, the remaining employees, and the miracle of modern pharmacology I somehow made it through that period.

Sometimes I wonder if I didn’t completely fry my nerves. I wonder this because I am again tearing Alagad down.  Three weeks ago we were faced with the very real fact that we would likely go out of business.  Both my personal and business accounts were overdrawn and we couldn’t make payroll.  Again.  We had to leave the PEO that provided our health benefits and payroll service.  The walls were coming down.

So I held a call with all four of us, three family members and one employee who may as well be family at this point.  We talked about shutting down and what that would mean.  Throughout this experience I felt calm.  Not happy, but calm, collected.  Worried too, but not like in 2009.  I sincerely felt as though I had done everything I could and that, if we failed, no one could blame me for not trying.

What’s interesting to me is that I don’t feel the same panic I did in 2009.  I don’t feel like a hole is being burrowed in my chest.  I can breath and sleep. I’m not entirely sure why.

I imagine that when death is imminent – when you are terminally ill – that a certain peace and calmness comes from that knowledge.  I imagine that you release your desperate grip on everything that holds you to the physical world. Nothing can harm you now.  There are no more consequences. You transcend fear.

That’s where I am. Nothing can hurt me now. And strangely, because of this, I am free.  I can do anything I want.  I can take tremendous risks without fear.  I am like the terminally ill patient who decides to live each day as if it were their last, because it might be.

Much to my surprise, out of that phone meeting was born an entirely new strategy we’re calling Alagad 2.0.  I’ve detailed it on an all-new Alagad.com website and will spare you the details here.  Suffice it to say it’s not the traditional way of running a software company.

I feel like the terminally ill patent who is given experimental treatment.  It might save their life, but might just kill them even faster.  There’s only one way to find out and I’m comfortable with this.

I can’t lie and say that I’m entirely at peace.  I still worry.  We don’t currently have health insurance and we depend on our prescriptions for our mental well being.  Many have criticized our new approach saying that we don’t understand the business.  But others have suggested it’s might actually be a good idea.

Maybe I’m just delaying the inevitable, but I’m ok with that. The picture that has emerged to me is that there is in fact life after death.  It’s a rebirth of some sort – a renaissance.  A new start. I look forward to it with an open and calm mind.

Tag Cloud