Author: Daniel Lobato Garcia

Infinite bits and the rule of product

Before I arrived in the US, I struggled with one subject during a whole year in my home university. Discrete math. It is definitely not that hard, but the approach the professor took leaded most of my class to fail – I think only three guys passed the subject on continuous evaluation –

So, blind and with very few material me and most of my classmates were to take an exam of the whole subject in June. Not a big deal you may argue, but it was right after the second semester exams. Stressed as hell I finally passed the subject thanks to Rosen’s book, Discrete Mathematics and its applications (not an amazon affiliate link) and some help from Berkeley’s online course.

It truly taught me a couple of things that will always make me think, aside from obviously a lot of combinatorics, number theory and advance graph theory that truly matters, but having already taken graph theory and cryptography, it was not that hard.

One of these things that actually left me thinking was counting. The rule of sum, the rule of product and the pigeonhole principle can apply to many problems, and simple as they are, applied to infinite sets they allow us to show a number of things, and I want to focus in how far we are from the future even though we know that something is waiting for us right there. Weird, huh?

Let us explain this with a simple example. Forgive me if I have some details wrong, I just want to make the big picture clear.

Computer screens are essentially several tiny dots that get filled with a color within a very very wide range of tonalities. This is essentially what allows us to show any image that can be imagined on a screen.

This tiny dots are not filled with a color by themselves. The computer fills them assigning a certain value. The way the computer likes to think about this is usually using the RGB color space. The red, green and blue colors use 8 bits each, which have integer values from 0 to 255. This makes 256*256*256=16777216 possible colors. Each pixel in the LCD monitor displays colors this way, by combination of red, green and blue LEDs (light emitting diodes). When the red pixel is set to 0, the LED is turned off. When the red pixel is set to 255, the LED is turned fully on.

Easy thus far. What about thinking of it from a different perspective? If we can control the device that picks a number between 0 and 16777216 (and we can), we could try assigning every simple pixel on the screen every single number. So we would have every possible combination of colored dots on the screen. What’s this? All possible images that can be shown. Either from the past or from the future. How your computer screen will be in 30 minutes – it’s there.  Imagine a picture of Hitler and your grandmother kissing in the middle of Kakariko Village from Zelda OOT – it will be there. A picture of what you saw when you were 5 years old and you went for the first time to school – I assume the human eye can capture a much wider range of colors but essentially, you would get the picture. Now think of a bigger screen with smaller dots. See where I want to get?

Let us extrapolate this to very different situations. Imagine you could build an infinite binary file. Even if it is not infinite, it will work in our example. If we had a 64mb binary file and we are able to write all the combinations of 0s and 1s, then we are able to create any program that could fit in that size. If the size is not a problem (it really is not) whatever thing you can imagine would be represented there. Firefox 20000? There it is. Windows Longhorn? There it is. Ubuntu Sacred Unicorn? Yup.

If the binary file example did not convince you, you can think sets of characters to be distributed in a lot of space in a source file. You would end up with all possible programs for all possible languages. Interesting.

Then, why don’t we just focus our efforts on this? First let’s try to understand the rule of product.

When you decide to order pizza, you must first choose the type of crust: thin or deep dish (2 choices). Next, you choose the topping: cheese, pepperoni, or sausage (3 choices).Using the rule of product, you know that there are 2 × 3 = 6 possible combinations of ordering a pizza – Wikipedia

And here’s where discrete math helped me to understand the enormous amount of possibilities that we are creating doing this. We can illustrate how the previous examples would work according to the rule of product.

The screen

1080p resolution is the new trend. That is 1080 rows of pixels with 1920 pixels in each row. 2073600 pixels that have to be filled with all possible combinations of 16777216 colors. I like to think of this problem as putting golf balls of a certain color on a lot of beakers.

In this case when we decide to fill this, we have 16777216 options on each step, since colors may be repeated, this makes the astonishing number of 16777216 ^ 2073600 of possible images to create. Some studies say that there are 2.0 × 10^83 atoms… in the visible universe.

The binary file

Let’s say we pick up a rusty old pendrive of 1gb. This is 8,589,934,592 bits. In this case, we do not have as many options to fill the spaces. In fact 2 options, 1 or 0 is all we need to make this as complex as it gets.

So 2 options, so much space, we can repeat options and this is.. 2 ^ 8,589,934,592. Jesus christ. Goddamn. Oh my gosh. According to worldwidewebsize.com, the internet contains more or less 45 billion pages as of December 2011.

2^9000 is this, just so you get the picture.

————–

The problem here is to build stuff that can produce this amount of data, where do we store this data and how the hell can we distinguish the useful combinations from the trash ones. I am not very versed in this at all, nonetheless I am sure some of you guys can probably help with this.

 

In case you want to learn more, infinitary combinatorics kind of studies this type of operations to a deeper level.

Refactoring a Rails controller

I have been contributing a little bit to a project called WikiCausality. This project basically tries to set up a webpage that shows links between environmental issues and suggests causal links so it’s easier to depict this causal links.

Anyway, back to the code, what I have done here is to refactor the method create from issues_controller.rb. What this method does is to create a new issue, link issues that already exist, and accept suggestions, create an issue for them, and link them. Quite a lot for just a method in my opinion. So what I did was to clear this and try to remove as much duplication as I could.

I think one of the main problems here was that it is not recommended to use an instance variable in your controller or view unless you created that instance variable. I tried to follow this as closely as possible and the result worked.

Still, the endless switch (case) statement drove me a little bit crazy but I found no way of translating the enormous list of ifs to anything easier to debug and more importantly, with less duplication. I chose to extract everything into two switch mainly because switches are implemented with an indexed branch table in Ruby – i.e  its quite faster. Take a close look at this one and help me to refactor it!

Here’s the original file:

And this is the refactored one:

Dramatic Innovation: we’re not quite there

A few days ago I came across this discussion in Hacker News. Summing up, Bren Victor, a rather famous human computer interaction designer at Apple during the last few years, criticized the vision that some people have about how the future is going to look like in terms of user interfaces design. He complains that the current approach we have to user interaction, which is mainly clicking on some kind of glass with our fingertips is not disruptive enough and he thinks we should challenge ourselves much more than that. So he purposes to exploit the highly-sensitive devices that our hands are to communicate ourselves with the machines, hence trying to follow a 3d sort of approach. Whether this is right or not, can be a source of an argument between those who like to research about this kind of stuff (Human Computer Interaction researchers and UI designers mainly). So, in order not to feel short-sighted just listening to one of the parts, I decided to read a bit about this discussion and I especially liked this opinion:

The article focuses on “everyday object” manipulation, but he’s right about technology too: there are a wealth of common HCI tools that glass cannot accommodate. – The textual keyboard remains one of the fastest methods of text entry. It can be used without looking, offers high bandwidth, affords both serial and chorded inputs, and works well for precise navigation in discrete spaces, like text, spreadsheets, sets of objects like forms, layers, flowcharts, etc. – MIDI keyboards are comparable, but trade discrete bandwidth for the expressiveness of pressure modulation. – The joystick (and associated interfaces like wheels, pedals, etc) are excellent tools for orienting. They can also offer precise haptic feedback through vibration and resistance. – The stylus is an unparalleled instrument for HCI operations involving continuous two dimensional spaces. It takes advantage of fine dexterity in a way that mice cannot, offering position, pressure (or simply contact), altitude, angle, and tip discrimination. – Trackballs and mice are excellent tools for analogue positional input with widely varying velocities. You can seek both finely and rapidly, taking advantage of varying grips. Trackballs offer the added tactile benefits of inertia and operating on an infinite substrate. – Dials, wheels. A well-made dial is almost always faster and more precise than up-down digital controls. They offer instant visual feedback, precise tuning, spatial discrimination, variable velocities, can be used without looking, and can be adapted for multiple resolutions. – Sliders. Offers many of the advantages of dials—smooth control with feedback, usable without looking—but in a linear space. Trades an infinite domain for linear manipulation/display, easier layout and use in flat or crowded orientations. And these are just some of the popular ones. You’ve got VR headsets for immersive 3d audio and video, haptic gloves or suits, sometimes with cabling for precise pressure and force vector feedback, variable-attitude simulators, etc. There are weirder options as well—implanted magnets or electrode arrays to simulate vision, hearing, heat, taste, etc… Dedicated interfaces can perform far better at specific tasks, but glass interfaces offer reconfigurability at low cost. That’s why sound engineers have physical mixer boards, writers are using pens or keyboards, artists are using Wacom tablets, nuclear physicists are staring at fine-tuning knobs, and motorcyclists are steering with bars, grips, and body positioning; but everyday people are enjoying using their ipad to perform similar tasks. Glass isn’t going to wipe out physical interfaces; it’s just a flexible tool in an expanding space of interaction techniques. More and more devices, I predict, will incorporate multitouch displays along dedicated hardware to solve problems in a balanced way.

He makes a good point here and I honestly am unaware of what the history of text entry is and how come the earliest device we invented to solve this problem (the keyboard, right?) remains to be the best solution by far. I think that he made sort of a good point here and I started to think that the humanity is getting a tad apathetic compared to previous generations. Our parents grew up dreaming about having people walking on the moon, that was really a turning point in history and I don’t really see how people is doing anything similar since the born of the internet. Some people address that odd centuries are more about incremental development instead of coming up with completely different things. For example, America was discovered in the late 15th century, whilst it was more or less clear that we had a new continent in the early 16th century. America was occupied by the Spanish during that century. They basically settled and took an advantage of their new possessions during the 17th century. Something similar happened during the 18th and 19th centuries with the industrial revolution. We started the information/globalization era in this last century (20th). Will the 21st century be all about incremental changes, debugging and refining this, or are we going to come up with anything REALLY new?

So, back to the UI lack of innovation rant, here’s newest Nokia research team video. Kind of fiddling around with some of the concepts that this guy came up with just a few weeks ago. Still timid but a dramatic change from what I have seen lately.

PS: I had a lecture with Don Patterson a few days ago in which he showed us the Nokia Morph Concept. It really left me speechless, but I think were at least 10 years away from this technology.

Nokia Morph

 

Computer Science Drop-Outs

Disclaimer: this article is not aimed to those of you who already made the decision. If you feel like you will be better off dropping out just read it and keep that in mind.

Yes. I was one of those guys who liked to advise you to get the degree and work afterwards. During the last year I have been thinking about this a lot and I’d like to share my thoughts after much reflection.

There are two very different groups of people that drop out, the talented/skilled ones and the ones who just don’t wanna make the cut.

About the former group, I basically ended up thinking that no matter if you can prove yourself as a great developer without a BS, I will get mine just for the sake of getting the most of my education. There are tens of topics that I’m sure I wouldn’t be very well-versed (if not completely ignorant) if I hadn’t gone through the dullest lectures I could ever have thought of. If I were to list the topics that I wouldn’t have studied on my own to the depth I do at college (compilers, language theory, statistics, programmable devices… and a bunch more) I’d be writing the longest post of the internet so I better stick to the ones that I mentioned. I’ve met some brilliant people that either have a very promising future (@pasku1) or they are already well respected within coworkers in this vast field that CS is and still lack the BS. A lot of people think that learning such diverse stuff is not strictly necessary to work as a software engineer, however I haven’t found a single person that can really argue that learning such topics is just a waste of time and it doesn’t help at all when it comes to actual work. If you don’t feel that way, I’d love to grab a coffee and have a pacific argument with you or you can just drop off a comment below 🙂

The second group is dramatically different from the first one, still they share some characteristics that you would easily notice by taking a quick glance at this list.

There’s several things that I noticed about people who dropped out of CS after having spent very few time in college:

  • They were convinced they were amazing at math and sciences. I’m not saying they they were bad at math, but people never take into account that maybe being the best at a high school that didn’t have a particularly good math and science curriculum probably contributed to their lack of preparation for science and engineering at a university level. Doing well on the math SATs means nothing, that shit is algebra/precalc. If anything, getting a 4 or 5 on the AP Calc II test is a better indicator as to how you’ll do in science and engineering when you reach university.
  • They didn’t realize that it meant endless hours in the lab. For things like CS, bugs don’t magically go away when you want them to go away, you could be hunting down a semicolon for hours. Most people can’t deal with that, that’s fine, but that probably means CS isn’t for you.
  • Lack of a support group. You’re less likely to drop out if you have friends you can suffer with together, science and engineering are majors that have pretty steep learning curves and sometimes the professor makes no sense. Usually group collaboration helps out in these situations. Plus being alone and hungry in a cold lab with no windows is very demoralizing. Go find a friend! Don’t be put off by the asshole nerd that probably wants to shoot everyone from the clocktower anyways, they’re usually never helpful.
  • You didn’t ask for help. We have TAs for a reason, professors have office hours, who the fuck cares if you go every week to every session. You might be making fun of the Melvin who goes to every one of these, but at least that guy is going to pass. Trying to look hardcore by not asking for help will just end up fucking yourself over. Moreover, sometimes the TA or the professor is a pushover, beg them to hint at what’s on the test, sometimes they cave, it doesn’t hurt to ask. The worst they can do is just say ‘no’.
  • Lack of a network. That guy with the heavy accent, I bet all the upperclassmen know about him and how to deal with/avoid him. BE FRIEND WITH UPPERCLASSMEN, they are willing to lend/pass down books, they know who to take and who not to take, they’ve walked through the shit the hard way. There’s no reason for you to trailblaze a new path if they can already tell you, “That guy is an dick who fails everyone, wait a semester, the spring quarter guy is easy.”

*There are a few people who make it through science and engineering without needing help, friends, and can roll into tests and blow everyone away without having gone to a single lecture, these people probably don’t actually have to be in university. Most of us are not these people. *

PD: I know how weird it is to write this as the first article of the blog but whatever. If you wanna know more about me just click on the tabs above or just ask me on twitter (@elobatoss)

Empty classroom