Monday, April 15, 2013

The Extended Euclidian Algorithm in Perl

This week I learned about the extended Euclidian algorithm for finding a linear combination of two numbers that yields their GCD. For example, the GCD of 213 and 171 is 3, and -4*213 + 5*171 = 3. This algorithm is important in the RSA encryption scheme.

I had quite a difficult time getting myself to fully understand how it works. I jumped between Wikipedia, my data structures textbook (don't buy it), a YouTube video, and this excellent number theory class lecture.The lecture is the best, though I think there may be a typographical error in the recursive formula.


The basic idea uses recursion with an easy base step. We call Euclid(a,b) with  b:

  • The base case is when b is 0. The GCD of x and 0 is always x, and the coefficients to produce a GCD of 0 are 1 and 0 (or anything else): 1*x + 0(or anything)*0 = x. So the base case returns (1,0)
  • Any other step starts by recursively calling Euclid(b, a mod b). We know that the GCD of a and b is the same as the GCD of b and a mod b (lemma 12 in the lecture). This recursive call is guaranteed to eventually get to the base case of b = 0.
  • After finding the coefficients for producing the GCD from b and a mod b, we can calculate the ones for producing the GCD from a and b, because a mod b can be put in terms of a and b (see the code comments for the formulas).


To really help myself understand the whole thing, I wrote a Perl script to illustrate it. I put in lots of comments as I worked my way through it.

use strict;
use strict;
use warnings;
use 5.010;
#start with a >= b
my @nums = sort {$b <=> $a} @ARGV;

gcd(@nums);

#input: two numbers (a,b) a >= b > 0
#output: the coefficients which which yield their GCD; 
sub gcd {
 my ($a, $b) = @_;
 
 #base case; the GCD of x and 0 always x;
 #and the coefficients will always be 1 and 0 (or anything) because
 #1*x + 0*0 = x
if($b == 0){ say "GCD is $a"; say "(a,b) = ($a,$b), coefficients = (1,0)"; say "1x$a + 0x$b = $a"; return (1, 0); } #otherwise, we evaluate u and v for k = ub + vr, where r is a mod b #gcd(b, a%b) gives the same value my $remainder = $a % $b; my ($u, $v) = gcd($b, $remainder); #now we can find k in terms of a and b because we know r in terms a and b #r = a - bq, where q = the whole part of a/b #k = ub + vr = ub + v(a - bq) = va + b(u-qv) #so the coefficient on a is v, and the coefficient on b is 1-qv my $x = $v; my $q = int(($a/$b)); my $y = $u - $q*$x; say "(a,b) = ($a,$b), coefficients are ($x,$y)"; say "${x}x$a + ${y}x$b = " . ($x*$a + $y*$b); return ($x, $y); }

Feel free to leave a comment if you think that something could be stated more clearly. I hope it helps anyone else trying to learn how the extended Euclidian algorithm works.

Sunday, April 7, 2013

Running Perl with Sublime Text 2

I've been having fun trying out Sublime Text. It's pretty, fast, and extremely extensible.

The first thing that I wanted was to be able to work well with Perl. I installed Package Control, followed by SublimeLinter, which has the  perlcritic command built in. Making this useful requires a little finagling; perlcritic is by no means a quick program (being a really thorough linter for a language which is complex to parse), and the defaults for SublimeLinter cause it run over and over again as you type. To fix this, I edited Packages/SublimeLinter/SublimeLinter.sublime-settings and changed the "sublimelinter" setting to false. Now, in order to lint the current file, I have to press ctrl+alt+l. (Update: I don't recommend this for Sublime Text 2 because of speed problems. See this issue on Github. ST3 should be fine, though.)

Next, I wanted to be able to run my Perl scripts. Sublime has the ctrl+b shortcut for running a build for the current file. What the build actually does is specified in either a build file or the project file. To create a new build file for perl, go to Tools->Build System -> New Build System. The build file I've seen on different sites for Perl looks like this:

{ "cmd": ["perl", "$file"], "file_regex": ".* at (.*) line ([0-9]*)", "selector": "source.perl" }

Save this as perl.sublime-build. With this, whenever you are working on a Perl file and hit ctrl+b, the command "perl -w your_file.pl" will be run. This, however, was not good enough for me. Most of the time I am working on tests for a Perl module, so I have to run perl -Ilib t/my_test_file.t. I also want to be able to run individual tests as well as prove using shortcuts.

To do this, we need to turn the module directory into a Sublime Text project. This is pretty simple. First, open the module directory in Sublime Text. Select Project->Save Project As, then choose the name of the project and save it in the top directory of the module. Paste the following simple contents into the project file:

{ "folders": [ { "path": "." } ] }

All this does is add the entire directory to the project. Next, we edit the Perl build file to reference the root of the project so we can add the top-level lib directory to our include path:

{ "cmd": ["perl", "-Ilib", "$file"], "working_dir": "$project_path", "file_regex": ".* at (.) line ([0-9])", "selector": "source.perl",
}

Great! Now we can run Perl on tests contained in module directories. This still works fine for standalone scripts, too.

Now I'd like to run my whole test suite using prove. By default, ctrl+shift+b runs a build variant with the name "Run", so we'll just make a prove variant with that name. I'd much rather give it a more descriptive name, but the Sublime shortcut requires this name. You can change the shortcut, but then you wouldn't be able to use the shortcut for other builds (other languages). It's all up to you. Here is the final build file:

{ "cmd": ["perl", "-Ilib", "$file"], "working_dir": "$project_path", "file_regex": ".* at (.) line ([0-9])", "selector": "source.perl", "variants": [ { "cmd": ["prove", "-vlr", "--merge"],
"working_dir": "$project_path",
"name": "Run", "windows": {
  "cmd": ["prove.bat", "-vlr", "--merge"]
  }
} ] }

Note that I needed a Windows variant for prove since the Sublime editor doesn't work the same as cmd. You could, alternatively, add '"shell":true' to use the system's command shell so you don't need a separate command for Windows.

With this build file in place, I can now press ctrl+b to run any Perl script, with it's project lib directory in @INC, and ctrl+shift+b to run prove. Voila!

Here are the final files:
project file (put a copy in your project root folders)
Perl build file (only one is needed per ST installation)