tag:blogger.com,1999:blog-56435391821439751382024-02-02T09:12:44.969-08:00Computer Science, Math and Clever DolphinsDhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.comBlogger33125tag:blogger.com,1999:blog-5643539182143975138.post-40267577521566134882012-04-03T19:52:00.000-07:002012-04-03T19:52:58.032-07:00Inductive reasoning, and why you should care<div dir="ltr" style="text-align: left;" trbidi="on">
Inductive reasoning, according Wikipedia:<div>
<br /></div>
<blockquote class="tr_bq">
<b style="background-color: white; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: -webkit-auto;">Inductive reasoning</b><span style="background-color: white; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: -webkit-auto;">, also known as </span><b style="background-color: white; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: -webkit-auto;">induction</b><span style="background-color: white; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: -webkit-auto;">, is a kind of </span><a href="http://en.wikipedia.org/wiki/Logical_reasoning" style="background-attachment: initial; background-clip: initial; background-color: white; background-image: none; background-origin: initial; color: #0b0080; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: -webkit-auto; text-decoration: none;" title="Logical reasoning">reasoning</a><span style="background-color: white; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: -webkit-auto;"> that constructs or evaluates </span><a href="http://en.wikipedia.org/wiki/Proposition" style="background-attachment: initial; background-clip: initial; background-color: white; background-image: none; background-origin: initial; color: #0b0080; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: -webkit-auto; text-decoration: none;" title="Proposition">propositions</a><span style="background-color: white; font-family: sans-serif; font-size: 13px; line-height: 19px; text-align: -webkit-auto;"> that are abstractions of observations of individual instances of members of the same class.</span></blockquote>
<br />
That probably conveys absolutely no value to you. The best way to understand what inductive reasoning is, is to apply it.<br />
<br />
In order to do that, we need some kind of problem which we can solve using a bit of induction.<br />
<br />
I'm going to a pick a math problem. Why, you say? Math is almost always the easiest way to understand reasoning, since math's primary device of "progress", so to speak, is reasoning.<br />
<br />
So, here's the problem:<br />
<br />
<blockquote class="tr_bq">
The plane is divided into regions by drawing a finite number of straight lines. Show that it is possible to color each of these regions red or green in such a way that no two adjacent regions have the same color.</blockquote>
<br />
If at first this doesn't strike you as a math problem, you probably haven't met this chap called <a href="http://en.wikipedia.org/wiki/Graph_theory">graph theory</a>, or maybe haven't been introduced to <a href="http://en.wikipedia.org/wiki/Bipartite_graph">bipartite graphs</a>.<br />
<br />
So, how do we go about solving this?<br />
<br />
Before reading on, try out some cases; one line, two lines, ten lines, and so on. Try and figure out some patterns.<br />
<br />
Now, I'll show you the solution.<br />
<br />
First we consider one line. So, we can color the regions on opposite sides of the line opposite colors (i.e. red and green), and, we're done.<br />
<br />
So, what happens when we add one line? Think about this for a moment. Can we try the same trick?<br />
<br />
Yes! What we can do is take one side of the new line we just put in, and swap all the colors on that side (so, red goes to green, green goes to red), and, we get a complete solution! So, every time we add a line, we can simply follow this algorithm and get the correct coloring. Of course, this isn't a fully rigorous proof, but, it shows what we're after.<br />
<br />
Inductive reasoning is taking a method you used to solve a problem for a set constraint (we knew how to do it for one line), and then extending that method to solve the problem without the constraint.<br />
<br />
If write code, you probably do this all the time (and just didn't know what this was called). If you've got a function that's misbehaving, you pass in a couple of values that you think are forming an edge case, and you've noticed that its going wrong for *one* of these values, you change the function definition so that the errors don't happen.<br />
<br />
But, you should use this kind of reasoning much more often. In nearly all problems where you are stuck on something going wrong on a constraint, try inductive reasoning. Of course, none of this actually happens consciously, but, if you try doing it consciously a couple of times, it "just happens" eventually.<br />
<br />
<br />
<br />
<br />
<blockquote class="tr_bq">
</blockquote>
</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com2tag:blogger.com,1999:blog-5643539182143975138.post-20792316977317185042012-04-03T19:24:00.002-07:002012-04-03T19:24:46.527-07:00The Travelling salesman problem<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
The travelling salesman problem is possibly the most famous and probably the most easy to understand of the so-called "NP-hard" problems computer scientists (and mathematicians) have found.<br />
<br />
The problem statement is quite simple.<br />
<br />
Consider you are a salesman, and you have, say, an $n$ number of cities you've got to cover by the end of the day. But, it would be best if you could minimize the distance that you have to travel between all of the cities, and, you know the coordinates of all the cities in reference to some point known as the *origin*. Given these coordinates, define an algorithm that would give you shortest possible path between the cities.<br />
<br />
Of course, this doesn't seem like much of a problem at all when you first start at it (like most other difficult problems); you could just try all the routes between the cities, find the route with the minimum distance covered, and, you're done!<br />
<br />
Let's see what that entails in terms of performance/scaling. With $n=5$ (i.e. five cities to visit), we have a total of $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ ways we can trace out the route between the cities, and we have to check all of these. That doesn't seem too bad for a computer.<br />
<br />
How about for $n=10$? Well, $10! = 3,628,800$, so, its quite a big jump from $120$, but, still manageable.<br />
<br />
Let's go up by another five; $n=15$. That gives: $15! = 1,307,674,368,000$. Holy cow. That's a lot. But, how did it jump that quickly?!<br />
<br />
To answer that question, we'll need a bit of math (if you understand big Oh notation, you can skip the next couple of paragraphs).<br />
<br />
Consider this situation. You have one car that's accelerating from a low speed, whereas another car is going at a higher speed, but, the second car's speed will not change. What do you think will happen if we let the cars go on forever? Of course, the car that's accelerating will overtake the car that's at a constant speed, right?<br />
<br />
That's what scaling algorithms is all about. You might have one algorithm that performs better at lowever "sizes" of the input, but, a second algorithm may overtake it if it can "scale better" (i.e. accelerate). So, when we say that an algorithm is $O(n)$, what we mean is that the algorithm performs *linearly*, i.e. for each unit increase in $n$, we get a certain unit increase in the time spent (or, whatever else you're measuring). Similarly, $O(n^2)$ means that for every unit increase in $n$, we get that much of change, but, squared in output.<br />
<br />
But, all of this still seems on some shaky ground, so, let's break out the equations (warning: if you don't know how limits work, skip this). This won't be a *completely* rigorous argument (which would require more math), but, it will be much better than the argument we have in place.<br />
<br />
How can we say that a linear time algorithm (i.e. $O(n)$) will scale better than $O(n^2)$? Well, what we're informally saying is that the $O(n^2)$ grows much quicker (i.e. worse) than $O(n)$ as $n \to +\infty$. If you remember that bit about relative rates of growth from first semester calculus; $\lim_{n \to +\infty} \frac{n^2}{n} = \lim_{n \to +\infty} n = +\infty$<br />
<br />
So, we've proved that $O(n^2)$ grows faster than $O(n)$, and therefore performs worse than $O(n)$.<br />
<br />
What does that mean in terms of the traveling salesman problem? The traveling salesman problem brute force solution is in fact $O(n!)$ (since the number of routes goes up like that).<br />
<br />
Why is this so bad?<br />
<br />
Consider a polynomial time solution (i.e. $O(a_n x^n + a_{n-1} x^{n-1} ... + a_o)$). Using a bit of calculus/limits, we can say, for certain, that factorial algorithms are much worse than polynomial time solutions as $n \to \infty$.<br />
<br />
That's what makes the travelling salesman problem interesting, because it has a non-polynomial solution, and, its something called a NP-Hard problem. What NP-Hard means is actually very complicated and heavily theoretical, but, it consitutes a very important part of the P vs NP problem, which, informally, asks (quoted from Wikipedia): "whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer" (s/quickly/polynomial time/g).<br />
<br />
So, that's what the travelling salesman problem is, and why people care.</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com1tag:blogger.com,1999:blog-5643539182143975138.post-76580135827683927332012-03-31T18:55:00.003-07:002012-03-31T18:55:43.002-07:00The new Blogger update ... sucks.<div dir="ltr" style="text-align: left;" trbidi="on">
I've been using Blogger to host this site, and, frankly, its probably been one of my worst experiences with Google software, ever.<div>
<br /></div>
<div>
First of all, let me cover the the good things about it (i.e. why I chose it in the first place). Its very quick to get started with a blog, its easy to add AdSense if you want it, and that's about it.</div>
<div>
<br /></div>
<div>
What's wrong with it?</div>
<div>
<br /></div>
<div>
First of all, the widgets model is broken beyond all belief. All of the widgets that are provided are pretty much useless, and most things like syntax highlighting and LaTeX involve tacking on bits of Javascript onto the page, which Blogger doesn't mix with all too well. </div>
<div>
<br /></div>
<div>
Secondly, the editor sucks. We're in 2012 here people, and it STILL escapes out when I hit tab. Why is this so difficult? Isn't Blogger now developed by the same company that makes Google Docs? </div>
<div>
<br /></div>
<div>
Then, once Google+ came along, all of the other "social" buttons have been pushed off to the side and made quite tiny, which, is understandable when considering it from Google's point of view, but, from my point of view, it doesn't make much sense.</div>
<div>
<br /></div>
<div>
The themes are also far from amazing (<a href="http://www.bloggerthemes.net/">http://www.bloggerthemes.net/</a> does try to remedy this), and the selection in font is pretty much non-existent. </div>
<div>
<br /></div>
<div>
And, most of all, Blogger, in general, seems to try to get in your way every single time you want to just "write a short entry", or "get this article on the internet". </div>
<div>
<br /></div>
<div>
So, what did the update fix/add?</div>
<div>
<br /></div>
<div>
It added some analytics directly on the front page; I was surprised to find out this blog had over 50,000 page views in the past 2 weeks. </div>
<div>
<br /></div>
<div>
Also, it cleaned up a editor a *tiny* bit (it still escapes out on the tab), and, the main replacement was just making the editing textarea/contenteditable larger.</div>
<div>
<br /></div>
<div>
The design is also much better and clearer.</div>
<div>
<br /></div>
<div>
But, they still completely ignored the actual problems that plague Blogger; so, I just can't keep waiting any longer, I'm going to try and pick from the enormous assortment of options (Posterous had caught by eye, but, its been acquired, so, I don't want to risk anything on it). </div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com7tag:blogger.com,1999:blog-5643539182143975138.post-11365041277793541422012-03-19T15:49:00.001-07:002012-03-19T15:49:49.592-07:00<div dir="ltr" style="text-align: left;" trbidi="on"><br />
<div style="text-align: left;"><br />
</div><div style="text-align: left;"><br />
</div><div style="text-align: center;"><br />
</div><div style="text-align: center;"><br />
</div><div style="text-align: left;"><br />
</div></div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com0tag:blogger.com,1999:blog-5643539182143975138.post-71094711459866298432012-03-18T00:20:00.000-07:002012-03-18T00:20:14.798-07:00Experiences in Go-ing<div dir="ltr" style="text-align: left;" trbidi="on">I've been messing around with Go for quite some time now and I wanted to share my experiences.<br />
<br />
When I first looked at Go, I put it aside as "just another language", and moved on with whatever I was doing.<br />
<br />
I mean, there are languages popping up every day that are worth nothing whatsoever because the ideas they bring to the table are too few to take the risk of using a language that isn't popular (less documentation, less support, less everything).<br />
<br />
That summer, I began writing some more low-level C/C++ code to implement a Bayesian classifier stock recommend-er thing. It was a complete disaster.<br />
<br />
Just some basic string parsing was a nightmare; C gave no utilities whatsoever, and C++ was good, until I hit an error and it gave me a 20 line long error report, and, I had to use all kinds of specialized templates for the simplest of things!<br />
<br />
And, the worst problem I faced was of sockets. Non-blocking, multi-plexed and cross-platform socket support with C is basically non-existent (unless I wanted to use libev or libevent, which has documentation scattered across the internet in small chunks). With C++, there are many choices, such as Boost.Asio (basically no documentation), ACE and ICE (this one I'm genuinely excited about, but, I hate their specialized object format crap I have to deal with).<br />
<br />
And, of course, there's no language support for anything so if I ever wanted to distribute my code, the client would have to have the libraries.<br />
<br />
I couldn't sacrifice performance (lots of number crunching was involved with costs tight), so, I couldn't pick Python.<br />
<br />
Then, I came back to Go, and looked at it again from a different perspective, and hoped it would offer me something that could rid me of all of this.<br />
<br />
I never did in fact write the Bayesian classifier thing (the idea wasn't much good anyway), but, the project introduced me to Go, which, I must say, is an amazing language.<br />
<br />
The first thing I immediately noticed is that they got rid of the parentheses in "if" and "for" statements. Coming from Python, I really like this.<br />
<br />
And, here's a language that's FINALLY SUPPORTING UNICODE FROM THE START!<br />
<br />
Closures are supported and functions can be passed around like salt shakers, its wonderful!<br />
<br />
All of the language seems well-thought out and cohesive; there aren't really any points that I felt like didn't match with the rest of system. Its very much like a suit without any stitch marks on it.<br />
<br />
As for the standard library, its no short of awesome. It includes a lot of things that I've frequently wanted with C/C++ as part of the runtime, such as json, xml, http, a cryptography package, even websocket support built right in.<br />
<br />
And, when they say it feels dynamic and interpreted, they actually mean it; the type system steps out your way for most of the time.<br />
<br />
The only thing I find lacking is that there are no books on the language as of yet, but, I expect that will be remedied once the language is "marketed" a bit more (Google hasn't put a ton of weight on it ... yet).<br />
<br />
It also has support for RPC which makes writing distributed computations really easy and quick.<br />
<br />
Unless I have to write some <i>really </i>low-level code, I refrain from using C/C++ these days and instead reach for Go; about the same speed with half the development time.<br />
<br />
I really encourage you to go check out Go, and just play around with it; you might start using it all the time.</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com18tag:blogger.com,1999:blog-5643539182143975138.post-8989656597782990542012-03-12T09:51:00.000-07:002012-03-12T09:51:50.876-07:00To all the people who say programming competitions are useless<div dir="ltr" style="text-align: left;" trbidi="on">There's been this general vibe on HN and r/programming that programming competitions (that involve problems one must solve) on the whole have little to do with programming in general.<br />
<br />
I beg to differ.<br />
<br />
99% of us can crunch out Javascript and some backend language pretty quickly; some ajax interaction, maybe some form validation and some Twitter and Facebook APIs. And, a lot of us can quickly learn new things when we need to. Need to learn Scala for next project? No problem. Client wants to use the Face.com API? Alright, let's do it.<br />
<br />
But, that's not the only stuff that matters.<br />
<br />
Your skills are *really* tested when you hit a roadblock that isn't covered by the abstractions you're working on.<br />
<br />
For example, the database inserts aren't happening fast enough, and the company doesn't want to buy any more servers to fix the problem, so, you've go to optimize it.<br />
<br />
Programming competitions don't test whether or not you can go about updating portions of code, they test whether you are able to write code to solve a problem you've likely never heard of under a time constraint.<br />
<br />
And, that's what companies would like in programmers.<br />
<br />
Math based problems are just one way of approaching timed problem solving, and they work quite well, since many of us are well versed in at least basic math, and are able to get our hands around the problem so that we can begin to think about implementing it.<br />
<br />
So, programming competitions *do* have to do with programming and the ability to solve problems, which is what development is all about.</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com0tag:blogger.com,1999:blog-5643539182143975138.post-68468171316166393362012-02-24T18:20:00.000-08:002012-02-24T18:20:06.213-08:00BIOS primer<div dir="ltr" style="text-align: left;" trbidi="on">Most of us know what a BIOS looks like, and have a some bits and pieces of an idea about what its supposed to be doing. This needs to rememdied, so, read the rest of this article!<br />
<br />
What happens when you hit the power button on a computer?<br />
<br />
It doesn't actually go directly to the CPU, first, the BIOS code is loaded, because that's what's able to hoist up the CPU, hard drive, display, etc.<br />
<br />
The BIOS is contained on an external chip (that's why some of you see your motherboard's manufacturer's name when you see the BIOS).<br />
<br />
A BIOS not only lets you set the boot order (which was was most of us have used it for), it has a couple of jobs.<br />
<br />
First of all, it configures your hardware.<br />
<br />
Some hardware is dependent on others, has specific settings, etc.<br />
All of this is handled by the BIOS, so that is ready for the bootloader.<br />
<br />
Also, all (well, nearly all) computers have a system clock, which doesn't actually tell you the "time" (again, it <i>could</i>), it counts ticks from a certain date, such as the epoch. The BIOS sets this up.<br />
<br />
It also selects what devices it can use as bootable, because there are certain types of storage devices that a BIOS cannot load of off (for example, random storage, volatile memory), and it identifies which are bootable.<br />
<br />
Then, comes the main job of the BIOS. It calls a bit of code that resides on the selected storage devices on the first 512 bytes of the first sector.<br />
<br />
In the early days of computers, 512 bytes was enough code to load the operating system, and things worked wonderfully.<br />
<br />
Of course, this is no longer the case considering that the Linux kernel is almost <b>15 million</b><span style="background-color: white; line-height: 19px; text-align: -webkit-auto;"><span style="font-family: inherit;"><b> lines</b> of code.</span></span><br />
<span style="background-color: white; line-height: 19px; text-align: -webkit-auto;"><span style="font-family: inherit;"><br />
</span></span><br />
<span style="background-color: white; line-height: 19px; text-align: -webkit-auto;"><span style="font-family: inherit;">So, these 512 bytes (known as the MBR) usually call *another* piece of code which then loads your operating system. Or, it could hold a list of sectors on your hard drive from which another piece of is then called.</span></span><br />
<span style="background-color: white; line-height: 19px; text-align: -webkit-auto;"><span style="font-family: inherit;"><br />
</span></span><br />
<div style="text-align: -webkit-auto;"><span style="line-height: 19px;">The BIOS also provides a small API for the MBR to use to write to the screen, make some interrupts, etc.</span></div><div style="text-align: -webkit-auto;"><span style="line-height: 19px;"><br />
</span></div><div style="text-align: -webkit-auto;"><span style="line-height: 19px;">Its pretty cool stuff...</span></div><span style="background-color: white; line-height: 19px; text-align: -webkit-auto;"><span style="font-family: inherit;"><br />
</span></span><br />
<br />
</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com0tag:blogger.com,1999:blog-5643539182143975138.post-31390179120902842132012-02-19T17:11:00.000-08:002012-02-19T17:11:11.905-08:00C Programmers: Don't write macros<div dir="ltr" style="text-align: left;" trbidi="on">Take pretty much any large C project today.<br />
<br />
If you look through a couple of files, you'll notice some things are written in CAPS LOCK AS IF THEY'RE YELLING AT YOU.<br />
<br />
These are macros.<br />
<br />
They're not as powerful as Lisp macros; they just replace themselves with a bit of code.<br />
<br />
C Macros are actually quite nice if they're used <b>in moderation</b>, because they allow you to type less.<br />
<br />
But when you have sixteen macros in one line, you really need to stop.<br />
<br />
Please.<br />
<br />
So, this is my plea to all of you C programmers, please stop writing more macros, because you're going to regret them when you have to go hire a new guy and he'll spend 19 weeks trying to figure out what all the YELLING ACTUALLY MEANS.<br />
<br />
<br />
<br />
<br />
</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com2tag:blogger.com,1999:blog-5643539182143975138.post-86247443241740680592012-02-13T09:33:00.000-08:002012-02-13T09:33:00.968-08:00My stance on JVM Languages<div dir="ltr" style="text-align: left;" trbidi="on">There have been JVM languages popping up all the time; there's Scala, Clojure, Groovy, etc.<br />
<br />
These are all excellent languages, without a doubt they are. I use them all the time, and I have come to enjoy them a lot.<br />
<br />
But, sometimes, I wonder about the <i>very </i>long-term (well, at least in the software world) consequences on using these languages.<br />
<br />
Java, as many of us consider it these days, is an "uncool" language. It is too verbose, too complicated and has too much over engineered crap that no one uses.<br />
<br />
It lacks the simplicity of something like C (notice I did not say C++ :P), where the manual for the ENTIRE LANGUAGE was a hundred something pages long.<br />
<br />
But, there is a ton of existing code in Java that no one wants to let go of, because people spent so many years trying to develop that code, and it took take many more years to replicate it in another language.<br />
<br />
So, people created JVM languages which run on the Java Virtual Machine, and they can interface pretty easily with Java. Then, you can write all your new code in a fast, hip language like Scala, but, you can still keep all of your legacy stuff around, and you don't have to rewrite a thing!<br />
<br />
This works wonderfully, except...<br />
<br />
Java, in my opinion, is slowly turning into another COBOL. Heavily used in large, high capital industries where a change is made every few centuries (roughly speaking), but, not used much elsewhere because its just too obsolete.<br />
<br />
So, if one creates languages on top of such a language, you're still hooking into the same old architecture. That's like writing a language that compiles to a COBOL virtual machine, people would laugh at you.<br />
<br />
Does this change anything for us, right now?<br />
<br />
Absolutely not.<br />
<br />
The term we're talking about (for Java to turn into COBOL), is just so long, that most companies won't even live to face the day.<br />
<br />
I'm still going to keep using JVM languages, because they're just plain awesome, but, I just wanted to put my thoughts out there.</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com4tag:blogger.com,1999:blog-5643539182143975138.post-2104672158403549252012-02-12T20:01:00.000-08:002012-02-12T20:01:36.788-08:00Graph databases explained quickly<div dir="ltr" style="text-align: left;" trbidi="on">Graph databases seem to be pretty important these days, with a social network popping up every time someone says "Facebook", so, I decided I'd do a small article on them.<br />
<br />
Take a traditional, SQL database.<br />
<br />
<b>What's it good at?</b><br />
<br />
Its good at specifying tables in which specific types of data lie.<br />
<br />
<b>Okay, what's it<i> </i>bad at?</b><br />
<br />
Well, a lot of things, one of which being that having one piece of data "linked" to others is a complete pain.<br />
<br />
<b>What does that mean?</b><br />
<br />
If you're a person, and and you have 500 friends, you need to be linked to 500 other people, all of which, in turn, are linked to you AND a bunch of other people.<br />
<br />
Now, let's consider a graph database.<br />
<br />
In a graph database, there are things called <b>nodes, properties and edges.</b><br />
<b><br />
</b><br />
Nodes are close like objects/structs to the OOP people, in that they are entities that can represent people, accounts, etc.<br />
<br />
Properties are information that nodes have, for example, if one of the nodes was "Person" its properties might be "Name", "Age" and "Address".<br />
<br />
Edges are the things that connect the nodes together, which are really the most important, since in a graph database, it matters a lot more about how the nodes are related than what the nodes actually contain.<br />
<br />
Hopefully that made sense, if not, drop a comment below!<br />
<br />
Follow if you liked it :)<br />
<br />
<br />
<br />
</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com2tag:blogger.com,1999:blog-5643539182143975138.post-32995181173421944632012-02-04T20:40:00.000-08:002012-02-04T20:40:17.138-08:00What's referential transparency?<div dir="ltr" style="text-align: left;" trbidi="on">You've probably heard about it before from all those crazy functional programming people, but, you don't *really* know what it means... I'm here to fix that!<br />
<br />
Consider a procedure/method written in an imperative language.<br />
<br />
In such a procedure, the program can do <b>anything it wants! </b><br />
<b><br />
</b><br />
Which means it could multiply two numbers, crash your car, and then save those numbers to a database.<br />
<br />
The things that it does that affect the outside world are called "side effects".<br />
<br />
In a purely functional programming language, side effects don't exist.<br />
<br />
But, in "almost" purely functional programming languages (in which you can actually do something practical stuff like writing programs that do things), the things that have "side effects" are confined to a couple of functions that interact with the outside, but, the rest of the functions (called pure functions) are entirely separated from the outside world, which means that they can be executed anywhere can we can expect the same results.<br />
<br />
Consider math for second.<br />
<br />
Mathematics is a purely functional language, because there's no way it can affect the "outside world" (atleast, mainstream math can't).<br />
<br />
Say you define a function called $f$:<br />
<br />
$f(x) = x^2$<br />
<br />
Now, what do you get when you compute $f(2)$?<br />
<br />
$f(2) = 4$<br />
<br />
Okay, so, what's so important about that?<br />
<br />
That simple statement means that no matter what the rest of the world is in, if you give the function $f$ a value of $2$, you can bet the farm that it will return $4$.<br />
<br />
The same holds true for pure functions in functional programming languages!<br />
<br />
And, that's what referential transparency means.<br />
<br />
Basically, we're saying that if we plug in some value $m$ into some function $f$, we can always expect to get the same value back ($f(m)$), regardless of the state of the rest of the stuff we're dealing with.<br />
<br />
Why's that useful?<br />
<br />
First of all, that's a heck of a lot an improvement for compilers/interpreters.<br />
<br />
If you're finding the value of $f(2)$ 40 million times, it will (usually) only find it once (this also has to do with how parse trees are replaced when parsing functional programming languages, but, the basic idea is here).<br />
<br />
This also lifts the idea of code running sequentially, because it can be run however it would run the fastest.<br />
<br />
Referential transparency makes code a lot easier to reason about and debug, since you KNOW that something will return a certain value when it receives a certain set of values as input.<br />
<br />
There you go, you should hopefully understand referential transparency.<br />
<br />
<br />
</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com0tag:blogger.com,1999:blog-5643539182143975138.post-23123229330381235482012-02-03T20:52:00.000-08:002012-02-04T19:03:43.762-08:00Functional programming explained<div dir="ltr" style="text-align: left;" trbidi="on">I've noticed a lot of confusion over why functional programming languages seem to be what the cool kids use these days, and why they can actually make a difference in your productivity as a developer, and I hope I can clear that up with this.<br />
<br />
Consider a standard, run-of-the-mill imperative language, like Java, or C.<br />
<br />
<div style="text-align: left;">Your procedures or methods typically look like this:</div><div style="text-align: left;"><br />
<script src="https://gist.github.com/1735350.js">
</script><br />
<br />
<br />
</div><div style="text-align: left;">Basically, you're taking two numbers as arguments, adding them, and returning them, and saving the result to a database somewhere in the middle.<br />
<br />
Not too shabby, right?<br />
<br />
Consider this situation. For some reason (your application isn't working), you need to check if this particular method is working.<br />
<br />
What's the problem? Well, you can't test this method separately, because it needs access to the Database class, which needs access to about 6 billion other things!<br />
<br />
The ability to test things separately from others is called "decoupling".<br />
<br />
Another issue with imperative languages is that they can modify all kinds of state in one function!<br />
<br />
So, in effect, when you call the function addNumbers, it could delete your database, empty your bank account and draw a circle on the screen. Why is that a problem, you ask? Well, that's a pain to debug, because you have no idea what types of functions can modify what types of state!<br />
<br />
Another issue are global/static variables, which cause no end of problems for Java programmers who find themselves changing static fields in certain objects affecting all the others in adverse ways, and this takes a ton of work to weed out.<br />
<br />
<br />
How does functional programming solve these problems?<br />
<br />
The first thing to understand about functional programming is that in a <i>completely pure </i>functional programming language, there is no way you can modify external state.<br />
<br />
That means you can't print to the screen (that's changing the state of the screen), access the web (changing socket state), or anything particularly useful.<br />
<br />
<br />
But, this wouldn't be terribly useful since you wouldn't be able to get any output shown, so, it would be practically useless (people get around this by writing languages that printing every calculation to the screen as a part of the language implementation, but, this just creates more confusion).<br />
<br />
However, that's not to say that they aren't used. An example of an ancient and hugely successful purely functional programming language is mathematics (there's no "print" command in math).<br />
<br />
So, languages like Haskell use this special idea (borrowed from mathematics, see my abstract algebra posts) called a Monad to "mark" special functions that do modify state so that they can be separated cleanly from the rest of the program.<br />
<br />
This nearly kills off the decoupling problem!<br />
<br />
Because there are very few non-pure functions in a typical functional piece of code, everything else IS decoupled from the environment!<br />
<br />
This is heaven when you need something debugged!<br />
<br />
And, this cleans up what functions can do and can't do; every pure function MUST return a value, so, you can expect something in return, not just a void (because that would mean its changing state, is therefore not a pure function), so, if you try to write to the database from a pure function, you can't do that, which keeps your code squeaky clean.<br />
<br />
Usually, functional languages come with malleable and nimble static typing, which means that you don't have to write out the types when you're declaring functions, but, they're there, so, when you try to pass a String to a function that wants an Integer, the compiler will tell you.<br />
<br />
All of these restrictions make it much more difficult to compile, but, once it does, it sure as heck won't crash (it might not do what you want it to, but, that's what unit tests are for).<br />
<br />
In functional languages, variables aren't really variables in that they can't be changed.<br />
<br />
You're probably saying "WHAT?!! How am I supposed to implement a counter then?!", and that's solved entirely by the fact that you can use recursion.<br />
<br />
<br />
So, that's why functional languages are awesome, and you should go <a href="http://learnyouahaskell.com/">check out Haskell!</a><br />
<br />
<br />
<br />
</div></div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com19tag:blogger.com,1999:blog-5643539182143975138.post-85283572145181405722012-02-02T16:29:00.000-08:002012-02-02T16:29:39.807-08:00Why is server configuration so annoying?<div dir="ltr" style="text-align: left;" trbidi="on">A lot of programmers these days are switching over to dynamic languages like Python and Ruby, mostly for their ease of development.<br />
<div><br />
</div><div>Sure, it entails that one must make sure that you aren't passing the wrong types to wrong functions, or you won't find out until runtime, but, if you're willing to take that risk, dynamic typing can be <i>amazing </i>to speed up your work process.</div><div><br />
</div><div>And, just like languages, nearly every other aspect of computer science/engineering has evolved for the simpler, more elegant approach, and, in this shift, many have profited.</div><div><br />
</div><div>For example, <a href="http://www.twilio.com/">Twilio</a>'s business model is based entirely on the fact that building phone systems in a modern programming language is just much too difficult for an average programmer, and, by simplifying the process by which developers can take advantage of phones, they've made quite a company. </div><div><br />
</div><div>And, people work everyday to simplify things that were previously immensely complicated, into black boxes in which the details are abstracted away.</div><div><br />
</div><div>As another example, take the humble Python list. It seems like a pretty simple idea; you can push and pop things, and you can delete things from the middle, you can sort and search them.</div><div><br />
</div><div>But, implementing a data structure like that in C is a formidable task, especially with all the optimization work that the Python folk have put into it. </div><div><br />
</div><div>And, things like this have lead to an explosion in Python's popularity.</div><div><br />
</div><div>But, I see one area where this type of stuff is immensely lacking, and that's server configuration. </div><div><br />
</div><div>First of all, why on Earth does Apache still use XML?! Is there literally no other format they can use?</div><div><br />
</div><div>Then, SSL shouldn't be so difficult to set up. It should take, at most, one shell script, or ANYTHING like that that'll generate a basic SSL virtualhost. </div><div><br />
</div><div>There need to be sensible defaults for log-files per vhost and so on.<br />
<br />
There need to be macros that we can use to have chunks of configuration with variables plugged in.<br />
<br />
And, in general, a lot of things need to be abstracted away into more usable and easy components.<br />
<br />
<br />
That's all I've got to say, but, do tell me what you think in the comment section below.<br />
<br />
Please follow if you liked this (top right). </div></div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com1tag:blogger.com,1999:blog-5643539182143975138.post-88446575917870515852012-02-01T17:06:00.000-08:002012-02-01T17:06:39.898-08:00The IRC mentality<div dir="ltr" style="text-align: left;" trbidi="on">In recent years, more hacker forums have sprouted up, moving away from the traditional "somebody asks, a bunch of people reply, and then there are replies to that", to some newer ideas.<br />
<br />
For example, there's <a href="http://stackoverflow.com/">Stackoverflow</a>.<br />
<br />
StackOverflow is an excellent idea.<br />
<br />
By introducing gamification into the idea of answering other people's questions for free, they've changed the entire scene of programmer forums. This causes people to think twice (well, for the most part) before posting useless questions, and the same for question answerers.<br />
<br />
This works with amazing efficiency; ask a fairly easy to understand question on StackOverflow (SO), and you'll get an answer within a couple of minutes (unless its something incredibly unpopular like running ARM assembly on a MBR), and the answers are immediately filtered out because the upvote-downvote system.<br />
<br />
As a added bonus, the interface is clean, succinct, and clear.<br />
<br />
Frankly, its just all out <b>awesome.</b><br />
<b><br />
</b><br />
Coming from places like <a href="http://daniweb.com/">Daniweb</a> (ads above the fold; aarrgh), its a welcome breath of fresh air.<br />
<br />
But, that's not where I started.<br />
<br />
I started on IRC.<br />
<br />
IRC is facing popularity issues these days; with all the new solutions for collaborating (for example, <a href="http://stripe.com/">Stripe</a> uses Campfire by 37signals).<br />
<br />
I'm not going to talk about how IRC is outdated, and, I'm not going to tell you that its the only "real" way to chat with people, because that's your decision.<br />
<br />
But, I will tell you about the community around IRC.<br />
<br />
When you're a beginning programmer, and you're starting to walk around the intricacies of a language, and you're faced with a problem you can't solve with, say, 10 minutes of work, what do you do?<br />
<br />
You try to ask for some help.<br />
<br />
Consider two scenarios, one on a website like StackOverflow, and one on IRC.<br />
<br />
You post it on SO, and you get a response in five or six minutes that tells you how to solve the problem, and tells you what you're doing wrong, and you're able to get your code working, you hope that the person who gave the answer has a nice dinner, and move on.<br />
<br />
Second, you go onto IRC, and you ask the question. Someone comes to your assistance. Then, the first thing they usually tell you is to check the "docs", and if you don't know what this is, they'll point you towards where it is. You search around for 10 minutes, find something you think might be right, and the person helps you get it working. But, he just gives you a few hints like "see, you're trying to pass in a string right there, but, $num is supposed to be a number", and at the end of an hour, you've finally solved your problem, and you feel amazing.<br />
<br />
What would you pick?<br />
<br />
I would pick the IRC experience.<br />
<br />
It teaches you HOW to go about solving problems in general, not just the solution to a particular problem that you're facing right at that current moment (well, that too), and you get a much more deep understanding of the problem you're facing, and you'd be apply the same knowledge of "check docs, figure out function, pass in right types" to hundreds of other problems you'll face pretty soon.<br />
<br />
Now, this is for a new programmer.<br />
<br />
If you're an experience programmer, and have been trying to solve something for 4 hours without success and think you're missing one small quote somewhere, or you're getting a NULL pointer, you'd be better off on SO, but, for new programmers, IRC is important.<br />
<br />
That's what I think, do tell me what you think in the comments section below!<br />
<br />
Follow if you like it (top right).<br />
</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com2tag:blogger.com,1999:blog-5643539182143975138.post-29603111374952721172012-01-30T20:28:00.000-08:002012-01-30T20:48:29.326-08:00The education system is broken, and here's how to fix it<div dir="ltr" style="text-align: left;" trbidi="on">As most of you know, I'm a high school student (freshman).<br />
<div><br />
</div><div>This year I complete my 10th year of being a full-time student (including kindergarten), and, I must say, I am sick and tired of the way people are "educated".</div><div><br />
</div><div>Take your typical mathematics class (my favorite subject inside and out of school) in the United States.</div><div><br />
</div><div>The teacher starts by checking the night before's homework (most of the time checking if people have done it), asks people if they're having any difficulties with it. If so, then he/she does that problem on the board and explains it. Then, introduces a topic like "rational functions", "imaginary numbers" or "the Pythagorean theorem", from the "textbook" which has a few examples in it.</div><div><br />
</div><div>The lesson usually consists of beginning by showing the formula for that chapter or section or unit or whatever the heck its called, and then having the students see a simple exercise in which they plugin a few numbers into this magical formula which then spits out the answers. </div><div><br />
</div><div>Then, the teacher then picks a more "difficult" problem, in which the same formula is used, but, its a "real world application", in which students find things like the distance between two campsites or figure out how long it will take Bob to run around the track if he's going at so and so miles per hour.</div><div><br />
</div><div>And, the homework is handed out, which are exactly the same problems, just redressed with different numbers, and the cycle begins once again the next day.</div><div><br />
</div><div>So, what do people learn at the end of the chapter?</div><div><br />
</div><div><b>Absolutely Nothing.</b></div><div><b><br />
</b></div><div>Here's the problem.</div><div><br />
</div><div>First of all, the students are never given the idea about what <i>how the formula actually came into existence. </i></div><div><i><br />
</i></div><div>Basically, the current system dictates that it doesn't really matter where it came from, for all your concerns, someone just thought about it one fine day and wrote it down, you have a test coming up next week, so you'd better stop getting distracted and get the formula memorized or you'll fail.</div><div><br />
</div><div>So, this causes students to go about the "textbook" skipping everything but the formulas, and then memorizing those. Then, when the test comes along, those who had time to memorize their formulas do excellent, and those that had something going on get low grades.</div><div><br />
</div><div>Then, as soon as they're done with the test, they put in all of their efforts into memorizing the next set of formulas and have nothing left from the last set that they memorized except "I love *whatever the topic is*, I got a 96% on that test".</div><div><br />
</div><div>And, the "textbooks" have "real world applications", which involve doing things that people would never even DREAM about doing (there are an incredible amount of problems about outdoor activities), because they're just plain stupid (do you measure the distance between the department stores in your town with the Law of Cosines?). </div><div><br />
</div><div>So, this causes students to think "when am I going to use any of this stuff anyway?", which is something I would think about very often if I hadn't taken the time to read a bit more about math.</div><div><br />
</div><div>These facts need to change. </div><div><br />
</div><div>First of all, you might have noticed that I keep saying textbooks in quotes, and there's a reason for that. </div><div><br />
</div><div>The textbooks <b>suck</b>.</div><div><br />
</div><div>Pick up any standard, run-of-the-mill textbook about "Algebra II" or "Precalculus", and you'll see a very similar picture.</div><div><br />
</div><div>The chapter begins, promising incredibly lackluster "real world applications". Then, goes into the first section, in which it tells you the formula in a conveniently highlighted box, which basically tells students not to read the rest of the passage, since its only there to make the book fatter anyway. </div><div><br />
</div><div>Then, there are pictures of people doing sports and things considered "fun", and are related to the subject of matter extremely lightly, but, the publishers and authors assume that if you put in some pictures about sports, the students will "learn better" (a.k.a memorize formulas in a shorter amount of time). </div><div><br />
</div><div>Then, there are a few examples in which the formula is used (again, no explanation of where it came from, or why it is needed), and ends with a horribly stale application, and then commences onto the exercises.</div><div><br />
</div><div>There are 110+ exercises in each section, about five of which are actually worth doing, since all the others are just slight deviations from the examples. </div><div><br />
</div><div>At the end of it all, you haven't solved a single problem by thinking it out yourself, all you've done is plug in some numbers.</div><div><br />
</div><div>The biggest thing that these textbooks and curriculum lack are <b>real problems. </b></div><div><br />
</div><div><b></b>Right now, almost every high paying job (with a good success rate; e.g. you cannot count football players, since less than 1% of them make a high pay) in the world deals with <b>solving problems.</b></div><div><b><br />
</b></div><div><b>Developers/Engineers? </b></div><div><b></b>We solve general problems like "An easy way to share pictures is needed; we have to build it", but, we also solve problems like "The search results are taking way to long, is there some kind of way we can speed them up?"</div><div><br />
</div><div>Obviously, these are difficult problems, and there's no general "formula" to plug things into that'll spit out the right solution. </div><div><br />
</div><div><b>We have to <i>invent </i>things as we go along.</b></div><div><b><br />
</b></div><div><b>Doctors? </b></div><div>When a patient comes to you, you don't have a set method of identifying "he has so-so, and he needs this to fix him up". </div><div><br />
</div><div>First of all, he gives you about 98 different things that are happening to him, and from there, you need to understand which ones are important and then find out what's wrong with him (assuming that the symptoms you said are important <i>really are </i>important)</div><div><br />
</div><div><b>You have to take a small amount of information given to you, and </b><i style="font-weight: bold;">synthesize </i><span style="font-weight: bold;">a solution.</span></div><div><span style="font-weight: bold;"><br />
</span></div><div><b>Lawyers?</b></div><div><b><br />
</b></div><div>You have a set number of rules you have to follow, and some conditions given with some more information, you need to <b><i>derive </i>a conclusion. </b></div><div><b><br />
</b></div><div><b>All of these things are what the current curricula lack.</b></div><div><b><br />
</b></div><div>There are no difficult problems that one must think about in order to find the solution, they are just things that as long as you don't make any mistakes, you'll be perfectly fine.</div><div><br />
</div><div><span class="Apple-style-span" style="font-size: large;"><b>This makes students entirely neglect the point of mathematics</b>!</span></div><div><span class="Apple-style-span" style="font-size: large;"><br />
</span></div><div>The point of math isn't to find out the probability of Jimmy wearing red socks on Tuesday, or to memorize the Rational Root Theorem word for word, because you probably will never use those things in your entire life, but, the point of math is to show how clear headed thinking and problem-solving are executed.</div><div><br />
</div><div>Given a difficult problem, one must <i>invent, synthesize and derive </i>in order to find a solution, which may involve failed approaches, but, the result is much more lasting.</div><div><br />
</div><div>And, this cut-and-dried approach to math is useless, because as soon as you take advanced math courses in college, you'll realize that the "proof" sections in the book actually mattered!</div><div><br />
</div><div><b>Okay, so, I've stated all the problems, now, how about a solution?</b></div><div><b><br />
</b></div><div>First and foremost, get rid of the "Algebra II" and "Geometry" subdivision junk that's going on, its entirely useless. </div><div><br />
</div><div>Math wasn't invented like that, and therefore should not be taught that way. </div><div><br />
</div><div>Mathematics isn't a bunch of blocks of knowledge that you use parts of to do exercises, its this whole continuum where a problem, if not solvable by the methods in one field, can be moved to another.</div><div><br />
</div><div>Second, the textbooks are horrible and need to be rewritten.</div><div><br />
</div><div>To do that, we begin by placing a limit on the size of the textbook to 300 pages or so (sounds a bit Legalist, no?)</div><div><br />
</div><div>Then, we take out the horribly expensive and useless color pages (except for 4th grade and below; I really liked the colors then, because the textbook didn't really mean much), and replace them with black and white.</div><div><br />
</div><div>Since its all black and white, we'd might as well throw out the pictures of people surfing as well, since people draw mustaches on those anyway. </div><div><br />
</div><div>Then, we rid ourselves of the idea of sections, since they get in the way anyway and constrict our overall "view" of mathematics too much.</div><div><br />
</div><div>Now, each chapter deals with each topic in a very conversational way, where the motivation of each step (all proofs included) is shown, and how one step leads to the next is very clearly shown.</div><div><br />
</div><div>There is one textbook that is currently in use that I would like to point out that does this incredibly well, which is <b>Linear Algebra and Its Applications by Gilbert Strang. </b></div><div>Matrix multiplication isn't just thrown out as a formula, but, its developed conversationally from the idea of linear systems (certain higher level textbooks do much better in this regard). </div><div><br />
</div><div>And, the topics within a chapter are connected, one cannot just jump, everything is continuous. </div><div><br />
</div><div>However, chapters can jump around math as much one would like, from Number Theory to Geometry and then to Combinatorics. </div><div><br />
</div><div>All the exercises need to replaced with a few, well-selected sets of problems which not only extend the material, but, provide new insight as to how to take a simple idea and use it on a complex problem (Pigeonhole principle-esque stuff). </div><div><br />
</div><div>Then, the section of textbooks would be quite solid.</div><div><br />
</div><div>Teachers need to be retrained, and paid a heck of a lot more than right now (think six figures), to make it a much more competitive field. Teaching needs to based around problems, starting lessons with problems, and then allowing the students to have a go at the problem, giving hints in between to lead them closer and closer to the solution. </div><div><br />
</div><div>If we are able to make a large portion of these changes, we would be far better off than right now in terms of what students can take away from mathematics classes, regardless of what they study in the future.</div><div><br />
</div><div>That's my idea of how this would work, and I would love to hear yours, so, please drop it in the comment section below. </div><div><br />
</div><div>If you liked this post, please tell me about it, so I'm encouraged to write more, and please follow (there's a button at the top right). </div><div><br />
</div><div>Questions, comments, etc. all welcome!</div><div><br />
</div><div><br />
</div><div><br />
</div><div><br />
</div></div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com9tag:blogger.com,1999:blog-5643539182143975138.post-55537661374834680922012-01-23T08:22:00.000-08:002012-01-23T08:23:33.381-08:00Rotation Matrices for developers<div dir="ltr" style="text-align: left;" trbidi="on">Hi!<br />
<br />
So, why the heck would you care about Rotation matrices?<br />
<br />
Well, a rotation matrix is a "easy" (once you're used to it) way to specify how to rotate a certain plane with reference to the origin, so, if you're doing any kind of graphics programming (WebGL is all the rage these days), you should know this stuff pretty well.<br />
<br />
First of all, what's a matrix?<br />
<br />
A matrix, despite how complicated it sounds, is JUST a collection of data. Developers know that better than most, since many of us use two dimensional arrays all the time, and call them matrices, but, many times we don't really do any "proper" math with them.<br />
<br />
So, if its just a collection of data, why's it useful? Well, the idea is that if you are able to lay out your data in a sort of a table form, it makes it much easier to reason about mathematically, because you can consider rows and columns in different ways.<br />
<br />
One very important thing to realize about matrices is that if someone gives you this matrix:<br />
<br />
<br />
$\begin{array}{ccc}<br />
1& 1 & 0 \\<br />
1 & 2 & 2 \\<br />
2 & 3 & 1 \end{array}$<br />
<br />
You can't assume <i>anything </i>about it (except for a couple of very unhelpful things, like you can consider it in rows and columns), so, you must have some idea about what the matrix is about. For example, this one could be a group of simultaneous equation's coefficients.<br />
<br />
You might have noticed that so far I haven't <i>really </i>explained how a rotation matrix actually works.<br />
<br />
Before I begin, you should have a basic understanding of <a href="http://hyperphysics.phy-astr.gsu.edu/hbase/vect.html">vectors</a>, which are incredibly simple (just an arrow, with a point at the head and another at the tail).<br />
<br />
Basically, what does rotation actually <i>mean? </i>It means that we're taking vectors on a plane, and we're moving them so that they represent different vectors (as if we rotated the plane itself).<br />
<br />
Now, take a step back, and pretend as if, instead of moving about the vectors, we are rotating the plane in which they reside. A bit like this:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjxPzid66K9vjG2THWtLAu8w2Y02YtKZKEthZIjl4j_CFMJxrG9BO9wSBj13IVm6eIcwur8mJUUoxL5mtiIKf91A37jbGwsQs59WcvR6gTZc1h3VGEwJebVM3D92lfgXopoiyD7C3bD2dp0/s1600/rotation-diagram.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="258" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjxPzid66K9vjG2THWtLAu8w2Y02YtKZKEthZIjl4j_CFMJxrG9BO9wSBj13IVm6eIcwur8mJUUoxL5mtiIKf91A37jbGwsQs59WcvR6gTZc1h3VGEwJebVM3D92lfgXopoiyD7C3bD2dp0/s320/rotation-diagram.png" width="320" /></a></div><br />
(That took me almost an hour to make, so be grateful!)<br />
<br />
Where the red axes are that of the rotated plane.<br />
So, how do the values map out?<br />
<br />
What I'm asking is if we take an arbitrary point $(x,y)$ and then we rotate it about the origin by some angle $\theta$, what will the new point be, in terms of $x$ and $y$? Diagrams always help:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgVQHXOGi-1sVrS-DHz_qvTfjbcf8Ma9ZIWMLGsE7zowGJ0FcUpvP6SL-fJ2-EcTK96koMwhHnB2odNyAqbqgB2KwIglibrNdlQK0Pfhyf4mY7NCaTttAc9Myz8qRHcSYiElN24926ybH3S/s1600/rotation-trig.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="515" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgVQHXOGi-1sVrS-DHz_qvTfjbcf8Ma9ZIWMLGsE7zowGJ0FcUpvP6SL-fJ2-EcTK96koMwhHnB2odNyAqbqgB2KwIglibrNdlQK0Pfhyf4mY7NCaTttAc9Myz8qRHcSYiElN24926ybH3S/s640/rotation-trig.png" width="640" /></a></div><div class="separator" style="clear: both; text-align: center;"><br />
</div><div class="separator" style="clear: both; text-align: center;"><br />
</div><div class="separator" style="clear: both; text-align: left;"><br />
</div>As you can see the original point is $D$, which have rotated around the origin ($E$) by a certain angle $\angle FED$ to the point $F$.<br />
<br />
So, lets say that $D$ has the coordinates $(x, y)$, and we're trying to find $F$ in terms of $x$ and $y$.<br />
<br />
Some immediate conclusions (since $D = (x, y)$):<br />
<br />
<div style="text-align: center;">$DH = y$</div><div style="text-align: center;">$EH = x$</div><div style="text-align: center;"><br />
</div><div style="text-align: left;">To make our lives easier (mostly my life easier) let's give the angles some symbols:</div><div style="text-align: center;"><br />
</div><div style="text-align: center;">$\angle{DEH} = \phi$</div><div style="text-align: center;">$\angle{FED} = \theta$</div><div style="text-align: center;"><br />
</div><div style="text-align: left;">And, since we are rotating about the origin, these must be true:</div><div style="text-align: left;"><br />
</div><div style="text-align: center;">$EF = ED$</div><div style="text-align: center;">Let $EF=ED=r$</div><div style="text-align: center;"><br />
</div><div style="text-align: left;">So, considering $\triangle{FEG}$, we can say:</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">$\cos{FEG} = EG/EF = EG/r ... (1)$</div><div style="text-align: left;">$\sin{FEG} = FG/EF = FG/r ... (2)$</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">Notice that $EG$ is the $x$ coordinate of $F$ and $FG$ is the $y$ coordinate of $F$, which is what we've set out to find. </div><div style="text-align: left;"><br />
</div><div style="text-align: left;">And, we notice this:</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">$\cos{FEG} = \cos{\theta+\phi} = \cos{\theta}\cos{\phi}-\sin{\theta}\sin{\phi} ... (3)$</div><div style="text-align: left;">$\sin{DEH} = \sin{\theta+\phi} = \sin{\theta}\cos{phi}+\sin{\phi}cos{\theta} ... (4)$</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">Equating (1) with (3), and (2) with (4):</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">$EG = r(\cos{\theta}\cos{\phi}-\sin{\theta}\sin{\phi})$</div><div style="text-align: left;">$FG = r( \sin{\theta}\cos{phi}+\sin{\phi}cos{\theta})$</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">Now, we simplify using the simple idea that $\cos{\theta}*r = x$ and $\sin{\theta}*r = y$,</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">And, we get:</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">$EG = x*cos{\phi}-y*\sin{\phi}$</div><div style="text-align: left;">$FG = y*\cos{\phi}+x*\sin{\phi}$</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">And, that's what we wanted!</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">You might be wondering: "What does this have anything to do with matrices?"</div><div style="text-align: left;">If you weren't thinking about that, please pretend you were at this point.</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">So, in the equations that we found above, the only parts dependent on $\phi$ (the angle by which we rotate) are the trig functions, so, what if we just represented them separately and then we'd be able to concisely represent all kinds of rotations on a plane?</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">Basically, what we're doing this this:</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">$\text{Rotated vector} = \text{Some witchcraft}\cdot \text{Initial vector}$</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">So, in a bit clearer terms:</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">$\begin{array}{cc} x' \\ y' \\ \end{array} = \text{Some witchcraft} \cdot \begin{array}{cc} x \\ y \\ \end{array}$</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">(where the columns of numbers are vectors, I can't get the brackets to display, sorry)</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">That $\text{Some witchcraft}$ is a matrix!</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">And, that's because matrix multiplication is defined in such a way that we can multiply a matrix and a vector together, and get equations resembling those that we got for $EG$ and $FG$!</div><div style="text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="http://upload.wikimedia.org/wikipedia/en/math/d/f/a/dfa9eccf5f8f2de1ac8ee1134ba88a86.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://upload.wikimedia.org/wikipedia/en/math/d/f/a/dfa9eccf5f8f2de1ac8ee1134ba88a86.png" /></a></div><div style="text-align: left;"><br />
</div><div style="text-align: left;">That right there is the matrix we use (pretend that the $\theta$ is actually $\phi$), and we multiply that with the $<x, y$ vector to get the equations we got for $EG$ and $FG$, because matrix multiplication is <i>defined that way! </i></div><div style="text-align: left;"><i><br />
</i></div><div style="text-align: left;">You might think this is all a "rigged game", and it is, but, the amazing thing is, despite this seemingly arbitrary operation of matrix multiplication, it works in all kinds of different places, because it is based one of the most important computations in mathematics, known as a <i>linear combination</i>. </div><div style="text-align: left;"><br />
</div><div style="text-align: left;">And, matrices are used EVERYWHERE!</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">From analytic geometry to simultaneous equations to economics and game theory, and that's mostly because of the fact that you are allowed to make any assumptions about the data you would like, and idea of matrices allow you to perform on math on that data with a few constructs that applicable pretty much anywhere.</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">I would love your feedback on this article, and ideas for new ones!</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">If you like this, please consider following this blog, it gives me motivation to keep writing blog posts, and you'll be notified as soon as a new one comes out.</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">For the people who like the abstract algebra series, I took a little break from it because I was a bit bored with it, and I couldn't think of the next topic easily. </div><div style="text-align: left;"><br />
</div><div style="text-align: left;">I'd be happy to answer questions, so, you can put them in the comments section below (I'll usually respond immediately), or email me at dhaivatpandya AT g m a i l DOT com.</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">And, just before I close, I'm doing a startup called <a href="http://nimblenot.es/">NimbleNotes</a>, which allows to write productively (this blog post was written entirely with NimbleNotes), and currently is in closed beta, with an <a href="http://www.indiegogo.com/NimbleNotes">IndieGoGo project</a>.</div><div style="text-align: left;"><br />
</div><div style="text-align: left;">Have a nice day :)</div><div style="text-align: left;"><br />
</div><div style="text-align: left;"><br />
</div></div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com2tag:blogger.com,1999:blog-5643539182143975138.post-13738074509549633912012-01-13T17:42:00.000-08:002012-01-13T17:42:48.882-08:00Please don't do dates and times like this!<div dir="ltr" style="text-align: left;" trbidi="on">So, you might have read <a href="http://poincare101.blogspot.com/2012/01/stupid-coding-errors.html">my last post</a>.<br />
<br />
And, that covered only one website, namely http://samsclub.com/.<br />
<br />
The problem is much, much worse than that. So, this is what happened.<br />
<br />
I downloaded the free Camtasia Studio trial for 30 days, and I really, really enjoyed it. But, like all other trials, its time came, it prompted me to drop some Franklins or it wouldn't let me use it. And, I was about to close out the application (hey; I didn't actually <i>need </i>it), when I thought maybe I would try making my system time go back a bit, and see if that did anything.<br />
<br />
<b>And it did.</b><br />
<b><br />
</b><br />
It happily pretended like it was 1/7/12 instead of 1/13/12, and I could continue to use my trials for another 6 days (and, after that I could repeat the same trick again, or, I could just sent it farther back to begin with). That struck me that maybe a lot of <i>other </i>applications depend on system time.<br />
<br />
And, I promise you, there are a LOT of them.<br />
<br />
Skype is a big one, if you move your time back, and look at Skype conversations and enter in a new one, it goes back onto old conversations.<br />
<br />
So, please, please don't get dates and times from the system! You need to get them from a synchronized UTC timeserver.</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com2tag:blogger.com,1999:blog-5643539182143975138.post-34911822255453791192012-01-05T19:18:00.000-08:002012-01-05T19:18:42.320-08:00Stupid coding errors<div dir="ltr" style="text-align: left;" trbidi="on">This funny thing occurred, and I thought it might be interesting.<br />
<br />
I was watching someone make a monthly payment on some financed item on <a href="http://www.samsclub.com/sams/homepage.jsp">Sams Club</a>, and was having some trouble.<br />
<br />
The problem was, the computer had a incorrectly configured clock, which had the date set as February 6th, 2012 (this took place on January 5th, 2012).<br />
<br />
And, Sams Club's website was using that date as the default value for the payment date.<br />
<br />
I thought "Okay, that's not too bad, I can probably just change the date on it". Wrong.<br />
<br />
Since SamsClub.com was using Javascript (bad idea) to get the date, it was also setting it as the MINIMUM date, which meant you cannot put in a date before that!<br />
<br />
Now, what's the problem with that?<br />
<br />
Well, say I'm a week late on my payment. To make that payment on time, all I have to do is set my system's clock to one week ago, and Sam's club will happily take the payment as if it was delivered a week ago.<br />
<br />
Lessons learned:<br />
<br />
Never, ever use Javascript to figure out the current date.<br />
<br />
Atleast check the date before inserting it into the database.<br />
<br />
Hopefully this will reach someone at Sam's Club, and they'll fix it...<br />
<br />
</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com0tag:blogger.com,1999:blog-5643539182143975138.post-71885462367414788182012-01-01T13:32:00.000-08:002012-01-27T20:14:53.575-08:00Abstract Algebra presented in a non-intimidating way (esp. for developers) - cryptography<div dir="ltr" style="text-align: left;" trbidi="on"><br />
<div style="text-align: -webkit-auto;"><span style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px;">Hi!</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Hopefully you read the last post, and if you didn't, you really should (<a href="http://poincare101.blogspot.com/2011/12/abstract-algebra-presented-in-non.html"><span style="color: black;">http://poincare101.blogspot.com/2011/12/abstract-algebra-presented-in-non.html</span></a>), because I'll be building on that stuff this time around.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">This time, we'll be going over an very interesting and applicable subject (if you've ever used a computer, you've experienced it in action), called cryptography, and more specifically, public-key cryptography.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Let's get started.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">From the dawn of humans, there's always been one human who wants another one dead, and as time as gone has gone by, we have invented better and better (or, worse and worse) of accomplishing this.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">One of such inventions was cryptography.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Communication is incredibly important in war, and Caesar (yes, that Caesar, the guy from Rome you learned about in history class and promptly forgot about after the test) needed a way to communicate with his generals spread out throughout the Roman empire in way such that even if the messenger was captured, the bad guys wouldn't be able to read the message.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">So, he (and presumably his team of scholars he kept handy) developed the Caesar cipher. I won't go into a ton of detail here, mostly because I wrote an entire blog entry about it (<a href="http://poincare101.blogspot.com/2011/10/encryption-and-ciphers-part-1-this-is.html"><span style="color: black;">http://poincare101.blogspot.com/2011/10/encryption-and-ciphers-part-1-this-is.html</span></a>).</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Basically, you shift over the alphabet over the message by a certain amount (that certain amount is called the key) to get the encrypted message, and, the person who wants to decrypt it shifts back the message by that certain key.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">There worked for a little bit, but, it involved the fact that the people who Caesar sent his messages to had to be told of the key and Caesar didn't trust them enough for that, so this system was abandoned, and Caesar most likely returned to the time-tested and expensive method of sending a messenger with soldiers armed to the teeth.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">People entirely overlooked this (rather important, as we'll see later) problem, and instead concentrated on the fact that the Caesar Cipher was easily cracked with statistical methods (all of this is explained quite thoroughly in the blog post I linked above).</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Slowly, cryptography turned into a pastime for amateurs and enthusiasts, and it was not much of a subject by itself, until more and more developments followed, and the subject was looked upon by mathematicians.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">One of these new and better ciphers is called the Vigenere (I refuse to take the time to put the accents in the right places) Cipher.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;">I wrote a blog post about this one too: <a href="http://poincare101.blogspot.com/2011/10/encryption-and-ciphers-part-2.html">http://poincare101.blogspot.com/2011/10/encryption-and-ciphers-part-2.html</a></span><br />
<br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;">The basic idea was that it no longer kept the frequency of the original text (often called plaintext) intact, making it immune to the statistical methods that could be used on the Caesar Cipher, but, there were other methods it was vulnerable to.</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;"><br />
</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;">One very large problem was still overlooked: both parties need to transact the key before hand, or this procedure wouldn't work.</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;"><br />
</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;">Finally, some clever chap came up with the revolutionary (like, really revolutionary) idea of public key cryptography.</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;"><br />
</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;">The concept is quite brilliant.</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;"><br />
</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;">Say, you have Alice and Bob and they want to transact encrypted messages. In public key cryptography, both Alice and Bob each have a public key and a private key. </span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;"><br />
</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;">The public keys are published somewhere that *everyone* can access them (not necessarily only Alice and Bob).</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;">Now, Alice wants to send Bob a message. She finds Bob's public key and encrypts her message with it, and the sends off this encrypted message to Bob, who then decrypts it with his private key.</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;"><br />
</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;">That means that the key that is used to decrypt the messages is never transacted, and Alice never needs to know it!</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;"><br />
</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;">That means that if Caesar had used public key cryptography, he wouldn't have faced the problem he had, because his generals would never have to know his private key!</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;"><br />
</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;">Of course, there's a problem (actually, a few of them) with that (otherwise there wouldn't be a NSA). </span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;">The private key and the public key must somehow be related to each other, so, theoretically, given as much time as needed, it would be possible to derive the private key from the public key, so, the solution to that is to use a computationally hard problem to generate the public and private keys, so it would take much too long to get the private key from the public key for it to be practical.</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;"><br />
</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">You might have noticed that I've been quite vague so far; I haven't specified HOW the keys are actually generated, and the encryption is carried out to turn plaintext into ciphertext.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">That's where the math begins.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">I mentioned that we had to generate the keys with a "computationally hard" problem. What on earth does that mean?!</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Its a pretty simple idea, it means that as you increase some parameter, the time taken to complete the problem skyrockets (not a perfect definition, but, it will suffice).</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">One such problem is called the Discrete Logarithm Problem (DLP, for short).</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Basically, you have a prime $p$, and $g, h$ such that both are part of the $mod p$ set (i.e. between $0$ and $p-1$ inclusive).</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">The problem is to find an $x$ such that:</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">$h \equiv g^{x} \pmod {p}$</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Let's see why that's so hard.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Let's set:</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">$p = 7$</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">$h = 6$</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">$g = 3$</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Basically, the only approach to this is we try different values for $x$, find $g^x$, then find $g^x \pmod {p}$, and keep going until we find an $x$ such that</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">$h \equiv g^{x} \pmod {p}$</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">If you try this (and I highly encourage you to do this), you will find that $x = 3$ works. This is a pretty small example, but, turn up the numbers, and it becomes a pretty formidable problem.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Let's look a bit more deeply into this matter, why is this so hard?</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Well, because we don't have any way find out an answer without brute-force.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Okay, why don't we have another way?</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Because it deals with $\mod p$, for which we don't have a ton of tools to deal with.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Exactly! Primes often occur in such problems, because we don't have a complete picture of how primes operate, because as far as we understand it today, they don't form some kind of equation that we can plug numbers in and get (all) primes out.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Alright, now, how are we going to turn this into a key?</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">There's something called the Diffie Hellman key-exchange system, which is outlined as follows (with Alice and Bob trying to communicate):</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">1. There's a publicly listed prime number that is decided, in our example, it will be 19 ($p = 19$), and $g=2$, which is also publicly declared.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">2. Alice picks a secret number (say, 6), and computes:</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"> </div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"> $2^6 \equiv 64 \equiv 7 \pmod 19$</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"> </div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"> and, sends this result off to Bob, and we call this result $A$.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">3. Bob does the same (but, with his secret number, which is 13),</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"> $2^13 \equiv 3 \pmod 19$</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"> </div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"> We'll call this $B$.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">4. Now, Alice takes the number she received ($B$), and raises it to her secret number (call it $a$):</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"> </div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"> $B^a \equiv 3^6 \equiv 7 \pmod 19$</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">5. Bob does similarly:</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"> </div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"> $A^b \equiv 7^13 \equiv 7 \pmod 19$ </div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">As you can see, at the end, both of them share one key, despite having started from completely different keys, and since this is based on the DLP, it is incredibly hard to solve, even with a supercomputer for (very) large values for $p$ (200+ digits).</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><span style="background-color: initial;"><br />
</span></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">So, what does any of this have to do with groups?</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Well, I'm glad you asked.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Groups (and abstract algebra in general), lets us generalize.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Using the definitions of cyclic groups that define only the properties we need, we can say this (quoted verbatim from Wikipedia):</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><ol style="background-color: white; font-family: sans-serif; line-height: 19px; list-style-image: none; margin-bottom: 0px; margin-left: 3.2em; margin-right: 0px; margin-top: 0.3em; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;"><li style="margin-bottom: 0.1em;">Alice and Bob agree on a finite <a href="http://en.wikipedia.org/wiki/Cyclic_group" style="background-attachment: initial; background-clip: initial; background-color: initial; background-image: none; background-origin: initial; color: #0b0080; text-decoration: none;" title="Cyclic group">cyclic group</a> <i>G</i> and a <a href="http://en.wikipedia.org/wiki/Generating_set_of_a_group" style="background-attachment: initial; background-clip: initial; background-color: initial; background-image: none; background-origin: initial; color: #0b0080; text-decoration: none;" title="Generating set of a group">generating</a> element <i>g</i> in <i>G</i>. (This is usually done long before the rest of the protocol; <i>g</i> is assumed to be known by all attackers.) We will write the group <i>G</i> multiplicatively.</li>
<li style="margin-bottom: 0.1em;">Alice picks a random <a href="http://en.wikipedia.org/wiki/Natural_number" style="background-attachment: initial; background-clip: initial; background-color: initial; background-image: none; background-origin: initial; color: #0b0080; text-decoration: none;" title="Natural number">natural number</a> <i>a</i> and sends <i>g<sup style="line-height: 1em;">a</sup></i> to Bob.</li>
<li style="margin-bottom: 0.1em;">Bob picks a random natural number <i>b</i> and sends <i>g<sup style="line-height: 1em;">b</sup></i> to Alice.</li>
<li style="margin-bottom: 0.1em;">Alice computes (<i>g<sup style="line-height: 1em;">b</sup></i>)<i><sup style="line-height: 1em;">a</sup></i>.</li>
<li style="margin-bottom: 0.1em;">Bob computes (<i>g<sup style="line-height: 1em;">a</sup></i>)<i><sup style="line-height: 1em;">b</sup></i>.</li>
</ol></div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">This immediately makes the system a LOT more powerful, because now, instead of dealing with just numbers, we can deal with ANY cyclic group we want, they can even be chess moves, if you can somehow wrangle them into a cyclic group.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Why is that helpful?</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Well, if you're using natural numbers to do your bidding (since they form a cyclic group), you're still not fully secure, and there are other cyclic groups thought to be "more secure" (because of various properties of the groups themselves), and a popular such cyclic group are the points on an elliptic curve.</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">To explain *why* this actually happens, requires a great deal more knowledge, but, the idea of using groups to specify how the system works is profound; you can swap in any system you'd like to make a "cyclic group"</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">Hopefully you enjoyed that :)</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">All feedback is greatly appreciated!</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;"><br />
</div><div style="font-family: HelveticaNeue-Light, 'Helvetica Neue Light', 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; line-height: 20px; text-align: -webkit-auto;">If you have any questions (or feedback), please drop a comment below, and I'll do my best at answering them!</div></div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com10tag:blogger.com,1999:blog-5643539182143975138.post-28719704748229673892011-12-15T12:24:00.000-08:002012-01-01T18:11:26.620-08:00Abstract Algebra presented in a non-intimidating way (esp. for developers) part 2<div dir="ltr" style="text-align: left;" trbidi="on">Hi!<br />
<br />
If you haven't read <a href="http://poincare101.blogspot.com/2011/11/abstract-algebra-presented-in-non.html">the last one</a>, I encourage you to do so, since I'll be using a lot of the terminology from the last post in this one, and I will be building on those topics.<br />
<br />
This post is largely background info for the next post, which will be on cryptography, but, for you to understand the next post, it is essential that you understand this one quite thoroughly.<br />
<br />
Lets begin with some history. Pure mathematicians when group theory was invented didn't really care what the physicists thought of them and how well they fared at parties, so, they developed all this theory about groups and none of them really cared about how it would apply to "real life".<br />
<br />
Then of course, there were these pure mathematician misfits, who were also physicists, and they realized that group theory could actually be pretty useful, and there was this stream of physicists and chemists trying to get in on the abstract algebra action.<br />
<br />
Up until then, most of the groups that were being studied were infinite (like $Z$ on addition), or something very specific that the physicists and chemists did not care about, and then mathematicians<br />
Before we get into the group theory today, I want to introduce you to something I call "<b>clock arithmetic</b>".<br />
<br />
Clock arithmetic is just like regular arithmetic, but, its carried out on a clock. I'll explain that with an example.<br />
<br />
Let's try to find out what 12+6 would be, on a clock with the twelve numbers on it (not the weird Italian ones with 24 numbers on them, they don't deserve to be called clocks). Okay, so, thinking about this, we can see that this would <b>not be 18, </b>because 18 isn't on the twelve hour clock, and, what happens is, if we start at <b>12 </b>and then rotate an additional 6 hours, we end up on the <b>6 </b>mark.<br />
<br />
Let's do another example. Let's try to find 6+9. Again, this is a similar case, where we set the hand to <b>6</b>, it rotates around to 12 after 6 hours, and then, we still have 3 hours left to rotate a total of 9 hours, so, we end up at <b>3. </b><br />
<b><br />
</b><br />
Okay, that's not too bad.<br />
<br />
As exercises, try finding out:<br />
<br />
<ul style="text-align: left;"><li>1+19 = ?</li>
<li>2+26 = ?</li>
</ul><div>If we're doing $1+19$ on a twelve hour clock, we usually write it as:</div><div><br />
</div><div>$1+19 \equiv 8 (\mod{12})$</div><div><br />
</div><div>I can hear you saying, "What? Why does that equal sign have another line? This is heresy!"</div><div><br />
</div><div>That extra line is telling us that $1+19$ isn't necessarily equal to $8$, but, it is under this funny clock arithmetic with this twelve hour clock we've developed.</div><div><br />
</div><div>If you did those two exercises, you might have noticed something. The observation should have been that if you add 1 and 19 using the "regular" arithmetic, and then take the remainder by 12, you still get the same answer! </div><div><br />
</div><div>Now, with a little bit of thought and some intuition, you can see why that's true (I encourage you to try this; hint, try starting at an arbitrary hour, like 1, and then seeing what happens in reference to this point). </div><div><br />
</div><div>I won't bore you with the formal proof (it doesn't use any clever arguments), but, I would really like it if you would try to get some intuition about why the above is true.</div><div><br />
</div><div>Okay, now, not all clocks are 12 hours long, right? How about some clocks that are, eh, three hours long? It's still the same idea!</div><div><br />
</div><div>Say, we're doing $12+20$. We first find out its $32$, and then take $\mod 3$ (remainder by 3), to get $2$. </div><div><br />
</div><div>Read the last sentence again. See how I used $mod$ to mean remainder? Okay, good. </div><div><br />
</div><div>Because clock arithmetic are pretty much remainders, and mathematicians like using large words, this clock arithmetic is called <b>modular arithmetic</b>. </div><div><br />
</div><div>You might have also noticed that we can take the remainder of the two numbers were adding up <b>separately</b>, and then add up those two remainders to get our answer. Let's try proving that in general (note: what matters isn't really the proof, but, how the reasoning goes in the proof, follow it closely). Stated "mathematically", this comes out to be:</div><div><b><br />
</b></div><blockquote class="tr_bq">If $a \equiv b (\mod {n})$ and $c \equiv d(\mod{n})$<b>, </b>then, $a + c \equiv b + d (\mod{n})$</blockquote>Let's try to think of this in terms of remainders. Since $a$ has a remainder $b$ when divided by $n$, we get that $a$ can be written as $kn + b$, for an some integer $k$.<br />
<br />
Then,<br />
<br />
$a-b = (kn+b)-b = kn$<br />
<br />
Therefore (since $a-b$ has to be divisible by $n$),<br />
<br />
$a-b \equiv 0 (\mod{n})$<br />
<br />
Similarly, we can argue that<br />
<br />
$c-d \equiv 0 (\mod{n})$<br />
<br />
Now, think about it this way, if we add two numbers that are divisible by a certain number $n$, you will always get a number that is divisible by $n$. A quick proof:<br />
<br />
$p = k_1n, q=k_2n$<br />
$p+q = n(k_1+k_2)$<br />
<br />
So, we can add the two congruences we got, so that we have:<br />
<br />
$(a-b) + (c-d) \equiv (a+c)-(b+d) \equiv 0 (\mod n)$<br />
<br />
Again, we have to use a bit of thinking here. If you have a number $m$, and $m-k$ is divisible by $n$, then, that means that $m$ has a remainder $k$ when divided by $n$ (from the definition of a remainder).<br />
<br />
So, we can use that to say:<br />
<br />
$a+c \equiv b+d \mod(n)$<br />
<br />
Nice!<br />
<br />
You probably did not understand ALL of the proof, and if that was the case, please read it again. The approach that we're using, using algebra and divisibility at the same time is very important, and will probably show up again.<br />
<br />
Alright, so, how has any of this got anything to do with abstract algebra and groups and stuff?<br />
<br />
Well, let me introduce you to this concept of a <b>cyclic group</b>.<br />
<br />
A cyclic group is a group in which all of the elements of the group can be generated by one element of the group on which the operation of the group is applied over and over.<br />
<br />
What the heck does that mean?<br />
<br />
This is best illustrated with an example.<br />
<br />
Let's say we have a group, with the operation $+$. You know, like normal addition.<br />
We start out with the element $1$, and add $1$ do it, and get $2$.<br />
<br />
Then, we add $1$ to $2$ again. To get $3$. And so, so forth, until we've generated all the integers (we can also apply the inverse operation, which would be to subtract), so, we can say the the set of integers ($Z$) is cyclic under the operation of addition.<br />
<br />
Then, there are <b>cyclic subgroups</b>.<br />
Cyclic subgroups are groups whose elements are a subset of those of a cyclic group. Cyclic subgroups are (usually) finite.<br />
<br />
Here's where you need to pay attention.<br />
<br />
A cyclic group can be something like:<br />
<br />
${1,2,3,4,5,6,7,8,9,10,11,12}$ on the addition operation.<br />
<br />
Hey ... that's like a clock! <b>So, cyclic groups can model modular arithmetic!</b><br />
<b><br />
</b><br />
<b><span class="Apple-style-span" style="font-weight: normal;">So, all the stuff we established in the last post is automatically applicable to this one :)</span></b><br />
We can now prove some stuff about modular arithmetic using groups!<br />
<br />
We can even prove that multiplication (i.e. repetitive addition) forms a cyclic group ($G$) under modular arithmetic with a $\mod p$ where $p$ is prime. This is so because:<br />
<br />
<br />
<ul style="text-align: left;"><li>Closure: any two elements that we take in this set and multiply them together cannot give a result which $0$ and therefore not in the set.</li>
<li>Associative: Its multiplication; not much work here.</li>
<li>We have an identity, and its 1</li>
<li>All of them have an inverse so that they have a remainder of 1 $\mod {p}$</li>
</ul><div>This allows us to say:</div><div>$m^{p-1} \equiv 1 (\mod {p})$, for all $m \epsilon G$</div><div><br />
</div><div>Why? Because if you think about, the multiplication sort of "wraps around" the set, because all of the results of the multiplication are a part of the set of the group $G$ (if you are confused about this, drop a comment below and I'll definitely help, this confused me for a really long time).</div><div><br />
</div><div>So, let me pose a problem:</div><div><br />
</div><blockquote class="tr_bq">Find the $7^{37} \mod {13}$. Don't reach for that calculator. And, no, you can't use Python.</blockquote>That looks really hard!<br />
<br />
But, we can simplify that a bit. From what we know from above, we can say ($13$ is a prime):<br />
<br />
$7^{12} \equiv 1 (\mod {13})$<br />
<br />
<br />
Okay, that helps us, because we can write $7^37$ as:<br />
<br />
$7^{37} \equiv (7^{36})\cdot(7) \equiv (7^{12})^3\cdot(7) \equiv 1\cdot7 \equiv 7 \mod{13}$<br />
<br />
Nice!<br />
<br />
On top of that, all cyclic groups are abelian/commutative (try proving this; its a good exercise), which opens up an entire new set of possibilites.<br />
<br />
But, why does any of this matter? But does this "modular arithmetic" idea matter aside from solving problems like the one above, which you would have probably plugged into a computer?<br />
<br />
Let me tell you, cyclic groups are not-so-abstract-algebra. They have a TON of applications.<br />
<br />
Well, if you've ever written a website (or, even used one), or logged into SSH, or logged into a computer, it definitely does matter.<br />
<br />
There's this "little subject" called cryptography, which deals with storing information in different forms, and it uses modular arithmetic intensively.<br />
<br />
And, if you are a physics type person, Lie groups and such are quite similar to cyclic/symmetric groups.<br />
<br />
If you liked the $7^37$ problem, and would like to continue in this direction, I highly recommend you check out <a href="http://projectpen.files.wordpress.com/2008/10/pen-vol-i-no-1.pdf">this free set of problems</a> (not by me). They are much more advanced than these, but, if you get some background on number theory, they should be fun.<br />
<br />
I promise the next one will be much cooler in terms of CS related stuff, but, I had to provide some background on cyclic groups, otherwise the next one wouldn't have made any sense.<br />
<br />
<b>Also, I've started a project called NimbleNotes </b><a href="http://indiegogo.com/nimblenotes" style="font-weight: bold;">here</a><b>, and I really am trying to get it off the ground, so pledges and tweets are highly appreciated :) </b>This blog entry was written with NimbleNotes, with a MathJax plugin I wrote.<br />
<br />
<br />
</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com7tag:blogger.com,1999:blog-5643539182143975138.post-48511923425171527382011-12-09T14:22:00.000-08:002011-12-09T14:22:44.396-08:00Small update to followers<div dir="ltr" style="text-align: left;" trbidi="on">Yeah ... I messed up.<div><br />
</div><div>Once I wrote the Abstract Algebra post, and got a bunch of feedback on it, I immediately set out on writing another one, and the reason that went all wrong was that I decided I would introduce Automata theory, and I wrote two posts on it, then, I realized that Automata theory is pretty abstract, and would be hard to understand without a thorough knowledge of groups and rings, so, I'll be postponing that.</div><div><br />
</div><div>I'm currently writing the next post; should be up by tomorrow. Thanks :)</div></div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com0tag:blogger.com,1999:blog-5643539182143975138.post-49742500681201437782011-11-27T17:50:00.000-08:002011-11-27T22:44:25.430-08:00Abstract Algebra presented in a non-intimidating way (esp. for developers)<div dir="ltr" style="text-align: left;" trbidi="on">Hi.<br />
<br />
I think math is really cool, but, most people (sadly) don't think so. This includes many programmers who in fact enjoy many of the same things that mathematicians do, but, are more practical for most of the time.<br />
<br />
I'll show you why abstract algebra (in particular, group theory) is really cool, and why you don't have to be a freaking genius to get it. <br />
<br />
Firstly, in order to understand most of this, you'll need to understand a tiny bit of <a href="http://en.wikipedia.org/wiki/Set_theory">Set theory,</a> and to save time, I'll just refer you to wikipedia for that one (you just need to understand basic unions and intersections). <br />
<br />
Let's begin with a simple definition, of a group (note: for hardcore types, this isn't fully rigorous because I haven't defined what an operation is, but, you get the idea). <br />
<br />
A group is defined:<br />
<br />
1) <br />
<br />
A set (usually called $S$) with an operation attached (we call the operation $*$), so, if $G$ is a group,<br />
$G = <S, *>$<br />
<br />
2) Closure is one property that all groups must have in order for them to be a group. Closure means:<br />
<br />
If $G = <S, *>$ and $x \epsilon S$ and $y \epsilon S$, then $x*y \epsilon S$<br />
<br />
Note: $*$ does NOT NECESSARILY MEAN MULTIPLICATION!<br />
<br />
3) <br />
<br />
All groups have an identity element $e$, such that ( we are still considering the group $G$ with operation $*$):<br />
<br />
For all $x \epsilon S$, $x*e = x$<br />
<br />
4) <br />
<br />
All elements in a group have an inverse,<br />
<br />
If $a \epsilon S$, $a^{-1} \epsilon S$ such that:<br />
<br />
$a * a^{-1} = e$<br />
<br />
5)<br />
<br />
The operation $*$ is associative. That means:<br />
<br />
$(a*b)*c = a*(b*c)$<br />
<br />
Alright, why in the world would anyone in their right mind define something like that?!<br />
<br />
Let's take a step back, and understand where this comes from. <br />
<br />
Around the 19th century or so, people realized that elementary algebra wasn't the only type of algebra that existed. There were all kinds of other algebras, like matrix algebra, and vector algebra and boolean algebra, and all these new all these new kinds of algebras kept cropping up with all these new rules (like, matrix multplication isn't commutative, that means: $A*B$ is not necessarily equal to $B*A$ when $B$ and $A$ are matrices) because mathematicians now had to solve all kinds of new problems.<br />
<br />
And, the problem was, mathematics was losing its "connectivity", all these new algebras had little to no connection to each other, and it was very difficult to make progress in a few of these algebras at once. <br />
<br />
Then, there was a clever idea. All of these algebras still were only doing a few operations on a set (or crossproducts of sets) and then were equating those operations on sets. That's how abstract algebra came along. Mathematicians realized that they could define "algebraic structures" (i.e. define algebraic systems so they followed a few axioms), and prove things about those algebraic structures, and any algebra that was then invented that could be proven to fit that algebraic structure would automatically have all the properties that people had proved about those structures!<br />
<br />
Basically, if you came up with a new algebra, called "Cheese Algebra" and it has all these funny rules, but, it handles only one operation and you can prove that Cheese Algebra has all the properties of a Group, you're done! That means that all the things people have proven for Groups are automatically true for Cheese Algebra!<br />
<br />
Isn't that awesome?<br />
<br />
Let's try it.<br />
<br />
The definition of a group is pretty simple, but, there are a few catches. First and foremost, the $*$ operation is not multiplication. Read the sentence over again. And again.<br />
<br />
Secondly, in a group $a*b$ is not necessarily equal to $b*a$. Groups in which this is true are called Abelian groups and they make your life much easier, but, not all groups are like that. <br />
<br />
Then, there are some basic theorems about groups that can be proven, and these are some important ones:<br />
<br />
<ul><li>A group has a single, unique identity element</li>
<li>Every element of a group has a single, unique inverse</li>
<li>$(a_1*a_2*a_3* ... * a_n)^ {-1} = (a_n^{-1} * a_{n-1}^{-1} * a_{n-2}^{-1} * ... * a_1^{-1})$</li>
<li>$(a^{-1})^{-1} = a$</li>
</ul>Let's prove a couple of them.<br />
<br />
The first one is pretty easy, we assume there are two identities, $e_1$ and $e_2$ for a group $G = <S, *>$ and this would mean,<br />
<br />
$e_1*e_2 = e_1$ (consider $e_2$ as the identity element)<br />
$e_1*e_2 = e_2$ (consider $e_1$ as the identity element)<br />
<br />
Which means $e_1=e_2$, which is a contradiction.<br />
<br />
The second one is really similar, so, I won't go into the details.<br />
<br />
The third one is a bit different, you first prove $(a*b)^-1 = b^{-1} * a^{-1}$ and then use the associative property of groups.<br />
<br />
Okay, so, what does this mean?<br />
<br />
Well, each of these properties hold for every algebraic system that's a group!<br />
<br />
So, for example, matrices (the ones that do have inverses) form a group under the operation of multiplication, so, we've figured out a bunch of cool properties about matrices, like<br />
<br />
<em>The inverse of the inverse of a matrix is the matrix itself.</em><br />
<br />
And, we haven't dealt with a single $a_ij$ component (although we would in proving that "inverseable" matrices do indeed form a group under multiplication)! <br />
<br />
Also, the real numbers (excluding zero) form a group under multiplication, so, we can say this, too,<br />
<br />
<em>The reciprocal of the recipocral of a real number is the real number itself.</em><br />
<br />
And, vectors form a group under addition (this one's really easy to prove, I suggest you try with the axioms given, hint: the identity is the vector <0,0,0>), too:<br />
<br />
<em>If you negate the negative of a vector, you get the vector itself.</em><br />
<br />
Notice that the inverse operations change with each of them, but, the idea is still the same, so, with the single idea of a group, we've solved problems in a bunch of different areas of mathematics.<br />
<br />
Let's try something a bit more complex, let's solve an equation on a group. What does that mean? Well, we can't use our knowledge of existing algebra, we can only use the axioms about groups, and the things we proved from them in order to solve the equation. <br />
<br />
Now, I'll show you the equation, but, try solving it first if you can before looking at the solution, it'll give you a different kind of appreciation for the solution.<br />
<br />
Solve the equation $a*x*b = c$ for $x$ in terms of $a, b, c$, which are constants.<br />
<br />
<br />
<br />
<br />
Solution<br />
=======<br />
Multiply both sides by $b^{-1}$,<br />
<br />
$a*x*b*b^{-1} = c*b^{-1}$<br />
<br />
Since $b*b^{-1} = e$,<br />
<br />
$a*x*e = c*b^{-1}$<br />
<br />
Since, $a*x*e = (a*x)*e = a*x$,<br />
<br />
$a*x = c*b^{-1}$<br />
<br />
Now, since each element of the group has a unique inverse, we can take the inverse of both sides of the equation, and the equation will still hold true:<br />
<br />
$(a*x)^-1 = (c*b^{-1})^{-1}$<br />
<br />
Which is the same as:<br />
<br />
$x^{-1}*a^{-1} = b*c^{-1}$<br />
<br />
Multiply both sides by $a$,<br />
<br />
$x^{-1} = b*c^{-1}*a$<br />
<br />
Take the inverse of both sides again, and notcie $(a^{-1})^{-1}$,<br />
<br />
$x = a^{-1}*c*b^{-1}$<br />
<br />
Yay!<br />
<br />
Now, what's (again) really cool, is that this works for every, single freaking algebraic system that you can think of that's a group. Matrices with multiplication? Done. Real numbers with multiplication (aside from 0)? Done. Vectors with addition? Done. <br />
<br />
Abstract algebra doesn't stop there, it defines all these structures that have similar properties like Rings and Fields that you can use to prove things in a bunch of different algebras in one fell swoop.<br />
<br />
I hope you liked this article, and I'd love your feedback, email me at dhaivatpandya at g mail dot com, or comment below :)<br />
<br />
EDIT: I forgot to mention some applications to CS.<br />
<br />
Alright, you guys know how <a href="http://haskell.org/haskellwiki/Haskell">Haskell</a>?<br />
<br />
Haskell (and any ML-type language, really) uses something known as Algebraic data types, which basically let you specify datatypes that follow certain axioms, in a way.<br />
<br />
Even though it is completely your responsibility to make sure that these structures form some kind of helpful algebra, the relation is still there.<br />
<br />
And, about classes in OOP languages, there's a very close correlation.<br />
<br />
You can very nearly think of classes as a algebraic structure that have many operations (methods) and elements (fields, variables, etc.), but, this isn't a perfect correlation because of many things that OOP languages let you do that are functionally "impure", and mathematics is a completely pure functional language (which is why it maps to Haskell so nicely), there is no state.</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com51tag:blogger.com,1999:blog-5643539182143975138.post-42855998084325774292011-11-25T12:44:00.000-08:002011-11-25T12:44:15.525-08:00Node.js is pretty awesome<div dir="ltr" style="text-align: left;" trbidi="on">This'll be a small post, so, yeah.<br />
<br />
I first started event-based loops with Twisted (<a href="http://twistedmatrix.com/trac/">http://twistedmatrix.com/trac/</a>), and I had absolutely NO idea what I was doing.<br />
<br />
I was doing all kinds of nonsensical things (I still have my code), like trying to read user input from stdin with raw_input() in a callback function. I slowly got better, and gradually learned more about what types of functions blocked, etc. etc. But, that took a while. And, if I needed to write production-ready code straight off the bat, I wouldn't have been able to do it (i.e. I would have written the code, it just would really, really suck).<br />
<br />
Then, I tried out eventmachine and libeio, and they were all pretty similar, and I still had to be pretty careful about what type of code I was writing (one has to think less and less about this type of stuff the more you do it), and it wasn't really flowing.<br />
<br />
Then, I found out about node.js.<br />
<br />
Unlike a lot of people, I wasn't drooling over it or anything, mostly because it uses Javascript, and I didn't really think that moving Javascript over to the server side would help any. This conclusion was mostly rooted from the fact that I always troubled myself with writing cross-browser JS, and that's a painful task. But, with node, that disappears. There's only V8, to hell with all the other parsers and compilers that developers have come up with.<br />
<br />
Javascript, if written for only one interpreter/compiler, is pretty usuable, and actually pretty fun. The prototype object system stops getting in the way, because you're provided with Object.create() which IE ... let's not talk about IE :)<br />
<br />
The point with node is, its really, really hard to write completely blocking code, because javascript doesn't have anything like File IO that blocks with which you can shoot yourself in the foot!<br />
<br />
The things I could write in a short amount of time literally skyrocketed, because I didn't have to worry so much about putting the wrong call in the wrong place, and could just concentrate on getting the application logic down.<br />
<br />
There are, however, a few cinches that you have to deal with. Firstly, there's no tail call optimization in v8, even though it has been requested (<a href="http://code.google.com/p/v8/issues/detail?id=457">http://code.google.com/p/v8/issues/detail?id=457</a>). This is mostly because of some stupid things done in the spec, but, Node would be a lot better for me if this request was fulfilled. Secondly, if you are a server-side developer, getting used to JS will be pretty ... different, that's not really bad, but, it might slow you down.<br />
<br />
So, all in all, I highly recommend you check out Node.js, and try writing something simple (like a chatroom or something).<br />
<br />
Feedback welcome.<br />
</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com0tag:blogger.com,1999:blog-5643539182143975138.post-44809769179080488502011-11-19T20:09:00.000-08:002011-11-19T20:15:28.001-08:00PHP sucks (but, some frameworks don't)<div dir="ltr" style="text-align: left;" trbidi="on">I started web development with PHP, and I've decided I've had enough. Why? Keep reading.<br />
<br />
<br />
<span class="Apple-style-span" style="font-size: large;"><b>PHP (the language) sucks. There, I said it. </b></span><br />
<span class="Apple-style-span" style="font-size: large;"><br />
</span><br />
<br />
<ul style="text-align: left;"><li>1029380128301928301823 Globals</li>
<li>Object system hacked on</li>
<li>C extension system sucks</li>
<li>Documentation sucks (read more; no, I'm not drunk)</li>
<li>Has a terrible community</li>
<li>All in all, designed by total idiots. </li>
</ul><br />
You've probably heard this a ton of times before, but, here it is again. THERE ARE JUST WAY TOO MANY GLOBALS. Why in the world does md5() need to be global? Do you seriously use md5() in <i>every single file?</i><br />
<i><br />
</i><br />
This is also a common occurrence, why on the planet are things like the order of <i> haystack </i>and <i>needle </i>the same everywhere? Is it really that hard to do?<br />
<br />
All in all, the language lacks <i>continuity; </i>it lacks grace. It doesn't have any precise definitions for anything, there are always exceptions (a bit like the English language), unlike something like Python, which tries its best to be properly defined and easy to relay to someone. In my eyes, if a language has a simple grammar, but, it is still powerful enough for use, I consider it excellent (Lisp/Clojure comes to mind).<br />
<br />
The Object System. Everyone's probably saying, "Hey! Its just like Java, what's wrong with it?!". Firstly, Java isn't the all-glorious object system everyone wants. Secondly, atleast most libraries and APIs in Java are based around objects and classes, whereas for PHP, its just a few bajillion globals, with classes if anyone wants to use them (which new programmers conveniently ignore because they can, and it leads to projects with a few hundred functions, and no classes and everything held together with <?require's and <?include's and global mutable state).<br />
<br />
Another horrific massacre is the C extension system for PHP. If you haven't tried (I have), don't do it, you'll regret it in your later years when macros will show up as nightmares. It shows you that the interpreter is this humongous blob of macros, held together by large if-else statements and switch'es, and it also tells you that you have to deal with this if you want to get any work done with the so-called "API". And, there's all this stuff that's dependent on Zend, and if they change their mind about something in the API, it all comes crashing down on you. Almost NOTHING is optimized. The things that have been optimized turn out to be this convoluted mess of unnecessary variables and unused heap space.<br />
<br />
Documentation. Everyone seems to be telling me that the documentation for PHP is absolutely wonderful. When I type in "php mysql" into google, I get <a href="http://php.net/manual/en/book.mysql.php">http://php.net/manual/en/book.mysql.php</a>. Which would be all fine and dandy if I was a new web developer that just needed to get my darn code to connect to mysql, but, dig deeper and you'll find out that this actually references the dangerous "mysql_" set of functions, which should have never been invented, and everyone should have been using PDO instead. Of course, the documentation doesn't tell me ANY of this, and just tells me how to install it, and how to go about making dangerous commands to MySQL. And, the comments on the documentation contain possibly the <b>worst code that has ever put foot on planet earth</b>, and newbies (especially on #php on Freenode) use them quite freely and get very confused and disappointed when their website gets hacked, or the code refuses to work when another user is running, etc.<br />
<br />
The community is also terrible. Every time I try to tell someone that they should maybe put the cryptographic functions in their own class, they (basically) accuse me of heresy and remind me what the Spanish Inquisition did to heretics. The community loves newbies, definitely, but, the people who aren't experts with PHP end up giving really bad advice (like not using PDO because its too complicated for small projects), and the ignorance just keeps spreading.<br />
<br />
If you look at the interpreter code, it'll be quite obvious why I say my last bullet point. The lexing code has a ton of repeated rules, crap that's never actually used in the parse tree and even more inconsistencies that are defaulted, and, whenever an elegant solution is possible the code is instead splattered with regular expressions. The parser gets even worse in this regard, with part of the <i>lexing done in the parser.</i><br />
<i><br />
</i><br />
Now, here's another statement I'm making about PHP.<br />
<br />
<span class="Apple-style-span" style="font-size: large;"><b>(some of) PHP's frameworks and their developers are excellent.</b></span><br />
<span class="Apple-style-span" style="font-size: large;"><b><br />
</b></span><br />
A good example is Kohana (<a href="http://kohanaframework.org/">http://kohanaframework.org/</a>). This framework is well thought out, expressive, and easy to use. Takes a couple of hours to learn and gives you full MVC out of the box, with database connectivity and everything. The developers really know what they're doing, and they try to make sure that Kohana is top quality code and stays well maintained. These developers have climbed the difficult hills of PHP with all its intricacies, and have come out victorious and you can see that in their code.<br />
<br />
But, that still doesn't cut it for me.<br />
<br />
Its a bit like trying to build the Eiffel Tower on top of a wooden log house. Yes, the eiffel tower is a great feat of engineering, but, its built on a log house, you can't expect it to be too stable. That's the case here, Kohana is AWESOME, but, its built on PHP, and I'd still be much more productive in Python or Ruby or maybe even Perl!<br />
<br />
What's the alternative?<br />
<br />
I highly suggest Python and Flask (<a href="http://flask.pocoo.org/">http://flask.pocoo.org/</a>) as an excellent combination for beginners, and Django for more experienced Python developers.<br />
<br />
There are also many other options, such as Ruby on Rails (I like this too, but, the lack of documentation sort of makes it difficult for me), Node.JS, Web::Simple (for Perl, not too popular, but excellent, IMO), etc. etc.<br />
<br />
<br />
<i><span class="Apple-style-span" style="font-size: large;">Stay away from PHP if you're a freelancer if $10/hr seems bad</span></i><br />
<i><span class="Apple-style-span" style="font-size: large;"><br />
</span></i><br />
Because PHP has such a low barrier for entry, there are hordes of terrible developers that are up for hire on websites such as freelancer.com, and others. They sink to bottom prices, deliver terrible quality work, and there's thousands of them.<br />
<br />
There's this funny story that I usually use to give an example. Before I realized I wouldn't make any money, I used to be quite active on freelancer.com, usually bidding on PHP projects. For one such project (it basically consisted of writing PHP for a AJAX app that needed to continuously poll), I bid $\$150$ (which is quite low for all the code I had to write, about $\$15$/hr), and there was another man (who had not-so-good ratings), who said he would do it for $\$40$. I warned the employer that he would not do the job properly, and you'd have to hire someone for a rewrite of the code, but, he (obviously) disregarded my arguments, and hired the $\$40$ guy. And, what happened? The $\$40$ guy procrastinated and delayed, wrote a bunch of crap code that basically checked the server every 10 seconds for this <i>static </i>file, which he modified with this Perl script that he set up a cronjob for, and it was overall a terrible hackjob. After 2 weeks, the employer had to hire again (he did hire me this time around).<br />
<br />
Because of these types of scenarios, its very difficult to do well as a freelancer in PHP, IMHO.<br />
<br />
So, I'm moving away from PHP to greener pastures, and I hopefully won't have to come back.<br />
<i><br />
</i></div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com11tag:blogger.com,1999:blog-5643539182143975138.post-28397845968506855982011-11-02T11:17:00.000-07:002011-11-02T15:27:48.692-07:00Encryption/Ciphers Part 3 - Knapsack Cryptosystem (a)<div dir="ltr" style="text-align: left;" trbidi="on">Encryption/Ciphers Part 3 - Knapsack Cryptosystem (a)<br />
<br />
Hi everyone. As always, if you haven't done so, I highly recommend atleast skimming through the last two articles, as I use terminology from them in this article. And, I'll be adding more posts about the encryption series, so, if you would like to keep updated, I would suggest you follow this blog. <br />
<br />
Also, the Knapsack Cryptosystem will be broken into two parts, one that describes the Knapsack problem and the next that shows Knapsack cryptography.<br />
<br />
Also, I made a mistake last time (which, unfortunately, no one noticed early enough), I forgot to do a push on the github repo, so the Vigenere code was not up, well, now it is.<br />
<br />
So, lets get started.<br />
<br />
The Knapsack Cryptosystem was invented in the late 70's, and now has been broken, but, it still is an awesome introduction to public key cryptography, and is quite a bit more elegant than RSA, which involves a lot more complicated math.<br />
<br />
So far, we've talked about a monoalphabetic cipher (the Caesar Cipher), and a polyalphabetic cipher, which both require one piece of information to encrypt and decrypt. Now, we will consider a new type of cryptography, known as a public key cryptosystem. The most simple (in my opinion) example of this type of system is known as the Knapsack Cryptosystem, or Backpack Cryptosystem, or Volumes Cryptosystem, you'll see why these why all these names mean the same thing in just a minute. <br />
<br />
Firstly, what's a public key cryptosystem? Well, in such a system, there is not just one piece of information needed to encrypt and decrypt (the shift index in the Caesar Cipher or the passphrase in the Vigenere cihper), there are two things needed, one key to encrypt the plaintext, and another to decrypt the ciphertext. Usually, the two keys are called public keys and private keys. Every recipient in the system has a public key that everyone knows about (including possible attackers), but, messages encrypted with that public key can only be decrypted with the recipient's personal private key, which is kept secret from everyone. <br />
<br />
That concept is sometimes hard to bend your mind around, and there's no better way to understand it than an example given by Wikipedia (http://en.wikipedia.org/wiki/Public-key_cryptography), so, I'll just quote it:<br />
<br />
"An analogy to public-key encryption is that of a locked mailbox with a mail slot. The mail slot is exposed and accessible to the public; its location (the street address) is in essence the public key. Anyone knowing the street address can go to the door and drop a written message through the slot; however, only the person who possesses the key can open the mailbox and read the message."<br />
<br />
Notice I said usually a lot for the definition of public key cryptosystems, because there are other uses known as digital signatures, which aren't the focus of this article (but, maybe later on). <br />
<br />
So, getting more particular, what's a Knapsack cryposystem? Well, firstly, we'll look at the Knapsack problem. <br />
<br />
Say you have Knapsack (or backpack, or bag, or whatever the heck you call it in your country) of volume $V$, and you have $n$ items of various volumes $a_1, a_2, a_3 ... a_n$, using none or multiple of each of these items, is it possible to completely fill the Knapsack?<br />
<br />
Lets make an equation out of that:<br />
<br />
$V = a_1x_1 + a_2x_2 + a_3x_3 ... a_nx_n$<br />
<br />
This problem, when given $V$ and $\{a_1, a_2, ... , a_n\}$, may have none, one or many solutions. Finding a solution to an arbitrary Knapsack problem is extremely difficult, in fact, all the approaches currently available (more on this later) are not very far from just using bruteforce to try out all $2^n$ combinations. That makes it an ideal candidate to base an encryption system on. <br />
<br />
But, due to reasons that you'll find out about, if the equation has multiple solutions, it doesn't work for public key cryptography. So, when does it have a unique solution (if any at all)? <br />
<br />
Lets call a sequence of $a_i$ "superincreasing" when each $a_i$ is larger than the sum of all the preceding ones; that is,<br />
<br />
$a_i > a_1 + a_2 + a_3 + ... a_{i-1}$<br />
<br />
If the $a_i$ are superincreasing, the Knapsack problem has a unique solution (again, if any). Let's look at an example to see why this is true:<br />
<br />
Say we have the equation<br />
<br />
$11 = 2x_1 + 3x_2+6x_3+13x_4$<br />
<br />
Since $13>11$, $x_4 = 0$. So,<br />
<br />
$11 = 2x_1 + 3x_2 + 6x_3$<br />
<br />
$2+3<6$, so, we must include atleast one item of volume $6$, so $x_3 = 1$.<br />
<br />
$5 = 2x_1 + 3x_2$<br />
<br />
Again, we operate the same way, noting $2<3$, and then getting $x_1 = 1, x_2 = 1$.<br />
<br />
And, we've solved it! A proof of why all Knapsack problems containing $a_i$ that are superincreasing is not difficult to formulate, and I encourage you to try it yourself (consider it an excercise, if you'd like). Also, the Knapsack problem is an excellent introduction to dynamic programming (that's how I learned DP), and, if you care about such things, I would check this out: http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf<br />
<br />
I'll be posting the next part of the Knapsack cryposystem blog in a day or two. I split it into two parts because the Knapsack problem and the cryptosystem both together are at on of material to have to digest so quickly. <br />
<br />
As always, feedback extremely welcome, and thanks for the upvotes, Redditors. If you would like to keep updated with this series, I highly encourage you to follow this blog.</div>Dhaivat Pandyahttp://www.blogger.com/profile/13242388218485061290noreply@blogger.com0