Older blog entries for fxn (starting at number 468)

29 May 2007 (updated 29 May 2007 at 11:16 UTC) »

Segway Tour

After several months using the Monty DPie on a regular basis I know I like this kind of machines for transportation.

The Monty DPie is cheap, kind of a toy, three wheels, not much autonomy, not enough power for real, everyday urban transportation, ..., and was a way to test whether I'd actually use such a thing with small risk in money. If it turned out it didn't work it wasn't a big deal. I have had a great time riding it, and great times with my daughter. And well, the actual usage has gone much further than I expected, so the next step is to buy a Segway as soon as I can afford it.

I could enumerate a list of reasons why I like these machines, no maintenance (a Segway costs 0.01 € per km, that's 30 € a year with regular usage), they are clean, agile, ..., but the most important one for me is that transportation becomes fun. That's the point, fun.

Of course before you buy a Segway you'd better test one and see whether it's for you. So this weekend my wife and I took a Barcelona tourist tour in HTs. Two hours and a half, about 10 kms. Man, that machine is really, really impressive. The easy of use, the astonishing stability, the robustness, ..., really outstanding. So yes, test passed wih grade. This review reflects very accurately our experience, it feels like that.

Let's see whether some day I can blog I own one of those :-).

19 May 2007 (updated 20 May 2007 at 07:37 UTC) »

CPAN

CPAN is, no doubt, one of the great things about Perl. I am not talking about the amount of modules, but about the repository itself.

A central repository is certainly good, but what I think makes CPAN fantastic are the consequences of having such a thing:

  • If you need a module you know where you to go to search for it.
  • Since there's a shared way to do things, people are able to create tools around this, like cpan(1), skeleton generators for new distributions, IRC bots that announce releases, etc.
  • If you want to contribute a module the path is clear and well-defined. I am convinced that makes easier for people to become module authors and explains the amount of work there.
  • It makes viable the existence of volunteers that test modules in their machines and report the results back in an organized way. You can see your test suite PASS or FAIL in multiple platforms. See for instance the CPAN Testers reports of my modules. Man I think that's invaluable.
  • Style in documentation, distributions, module testing, etc., converge because such a centralized repository gives a context where your work can naturally fit.
  • And more ...
Those are some implications of the existence of CPAN, which I believe greatly amplify its benefits.

Algorithm::Combinatorics

Precisely thanks to a CPAN Tester, David Cantrell, I knew the last release of Algorithm::Combinatorics was broken on Perl 5.6.2. David was so kind as to provide me with a shell account in his machine to be able to debug the problem. I could run Valgrind in his Linux this way, how kind and helpful of him, thank you dude!

The sympton was that 2 tests out of about 300 in the suite gave a segfault. I've spent some nigths this week working on that problem, and finally I discovered the culprit.

You know Perl has scalars, that's a type of data that can store strings, integers, doubles, references, ... The C structure that represents scalars is called SV. My module constructs private arrays of indices and performs the combinatorics on those arrays. When a tuple is generated a wrapper in Perl-land slices the original array of data and that's what iterators return. OK, since those are private integers the XS code can rely on that, and used the macro SvIVX which goes directly into the IV slot of a SV. It can in fact act as an lvalue. That is, in the code we assume the SVs actually hold integers.

Perl 5.8.x tries to preserve IVs, but 5.6.x did not, I had forgotten that. Just about any arithmetic you did on an integer gave a double behind the scenes, that's what the following NV means:


  $ perl5.6.2 -MDevel::Peek -e '$a = 1; $b = $a + 1; Dump $b'
  SV = NV(0x180a810) at 0x1807730
    REFCNT = 1
    FLAGS = (NOK,pNOK)
    NV = 2
and so my assumption was broken. The subroutine partitions() has some of that simple arithmetic involving indices. The code read the IV slot, which contained garbage, and that had the side-effect of an invalid memory access later. Once I understood what happened the fix was trivial, which is to base the code on the SvIV macro instead. That macro returns an integer doing conversions if necessary. I published today a new release with the correct XS.

I published tonight a maintenance release of Algorithm::Combinatorics to indicate the module is alive, it has been months since the last release. A directory with benchmarks has been added to the distribution. We compare there the performance of some iterators to the ones provided by the alternative pure Perl solution.

28 Apr 2007 (updated 28 Apr 2007 at 18:51 UTC) »

Enhancing nil in Ruby

In Ruby nil is, you guessed it, an object. It is an instance of the singleton class NilClass. Indeed, it responds to a handful of methods, for example:


    irb(main):001:0> nil.object_id
    => 4
    irb(main):002:0> nil.to_s
    => ""
    irb(main):003:0> nil.to_i
    => 0
but some stuff is still invalid:

    irb(main):001:0> 1 + nil
    TypeError: nil can't be coerced into Fixnum
            from (irb):1:in `+'
            from (irb):1

I am working in an application that shows some numbers, and by convention if any of those numbers are nil they are rendered as the empty string. Imagine you are working with invoices, an empty invoice has no total, so you simply do this:


    <%= format_money_as_decimal(@invoice.total) %>
and no total is shown if @invoice.total is nil, fine.

Some of those quantities, however, need to be shown with the sign reversed. Let's suppose all quantities in the footer of the invoice, like a discount, are represented as they are, and added or substracted to compute the total. In that case, you want to render something like this:


    <%= format_money_as_decimal(-@invoice.discount) %>

Problem here is that you cannot take the opposite of nil:


    irb(main):002:0> -nil
    NoMethodError: undefined method `-@' for nil:NilClass
            from (irb):2
and so in each place where that occurs I'd need to write this ugly thing:

    <%= format_money_as_decimal((-@invoice.discount rescue nil)) %>
or some equivalent verbose code.

Weird, and brittle. But hey, this is Ruby and even NilClass can be reopened:


    class NilClass
      def -@
        nil
      end
    end
Voilà! We can now just use the idiom we wanted and it works through all the application:

    <%= format_money_as_decimal(-@invoice.discount) %>

Much better.

I want to give StevenRainwater a big THANK YOU. The site is not only alive but evolving fast, at this rate there won't be any gap to fill by MyAdvogato. Keep up the good work!

model_auto_completer 1.1

I just uploaded a new release of model_auto_completer. We now provide a callback to let the user do something when a model is selected. This hook receives the model ID among other stuff, so for example you could issue an Ajax call back to the server to update the page with model attributes or whatever.

10 Mar 2007 (updated 31 Mar 2010 at 15:24 UTC) »

Perfect Square Test

A few days ago there was a question in ruby-talk regarding how to test whether a given integer is a perfect square. You know, an integer is a perfect square if its square root is an integer. As Python and others, Ruby provides builtin support for arbitrary-precision integers, but their floats are C types under the hood:


  irb(main):051:0> a = 2**512
  => 134078079299425970...(155 digits)
  irb(main):052:0> Math.sqrt(a**2) == a
  (irb):52: warning: Bignum out of Float range
  => false

and the OP needed to be able to test any integer.

There are libraries such as Pari that offer that test, but I couldn't compile its Ruby binding on my Mac and was nonetheless intrigued by the challenge. I recalled a course on Number Theory where in addition to the proper math we saw some algorithms in the lab, following Henri Cohen's A Course in Computational Algebraic Number Theory. At the beginning of that book the stuff needed to solve that problem is explained, so I visited the library of the faculty. This is the approach libraries follow.

The first piece is a way to compute the integer square root of an integer. Given a positive integer n, we define the integer square root of n to be the integer m such that m^2 ≤ n < (m + 1)^2. The algorithm in the book translated to Ruby is (my notation):


  # Algorithm 1.7.1.
  def isqrt(n)
    x0 = n
    loop do
      x1 = (x0 + n/x0)/2
      return x0 if x1 >= x0
      x0 = x1
    end
  end

Looks like magic isn't it. That's Newton's method applied to the function x^2 – n, though we use only integer arithmetic. Note that "/" is integer division in Ruby.

If you think for a moment, you'll realise squares are rare. As n gets bigger n^2 gets even bigger. Thus, between squares there are lots of numbers. If we could find a quick test for non-squares we would speed up the test a lot in mean, discarding soon true negatives.

That's the main point of Algorithm 1.7.3. We use the fact that if n is a square, then it is a square modulo m for all m. Of course the reciprocal is not true, for instance any odd integer is a square mod 2. Now, that implies that if n is not a square modulo m for some m, then it is not a square for sure. If you take a few well-chosen ms the probability that a non-square is a square modulo all of them can be less than 1%, this happens with the ones proposed in the book:


  # Cache the squares modulo 11, 63, 64, and 65.
  $squares = {}
  [11, 63, 64, 65].each do |m|
    $squares[m] = [false] * m
    (0...(m/2)).each {|i| $squares[m][i**2 % m] = true}
  end

Now we join the pieces together to get the test:


  # Algorithm 1.7.3.
  def issquare(n)
    return false unless $squares[64][n % 64]
 
    r = n % 45045 # 45045 = 63*65*11
    return false unless $squares[63][r % 63]
    return false unless $squares[65][r % 65]
    return false unless $squares[11][r % 11]
 
    q = isqrt(n)
    return q**2 == n ? q : false
  end

Chicago, it was explained by robogato in this entry.

7 Feb 2007 (updated 8 Feb 2007 at 12:21 UTC) »

Five Tidbits You Didn’t Know About Me

OK, so jao tagged me. Here we go:

  1. My father tried to register me in the Conservatori Superior de Música del Liceu when I was four years old. They didn't accept children so young, and we waited until I was six. I studied music until I was fourteen, including four years of flute. After that I had some bands, composed a few songs, and enjoyed music as a fundamental part of my life. I sacrificed music when I entered the math faculty, there was not enough time for both.

  2. When I was a teenager I decided to practice table-tennis seriously. I joined the school of one of the best clubs in Spain (set a nou, in Passeig de Gràcia by then), and did regular training. I did well. After some months of good progress, when I started to exercise my arm was kind of blocked, as if my brain was unable to order the right movements. Rigid. This normally lasted a few minutes and then those so well-trained movements returned.

    The first time I entered an official Catalan competition I was practically unable to unblock in my first game. I quit soon and never explained my problem to anybody. I was fifteen or so by then.

  3. From the ones I know, my preferred language is Catalan. It sounds beautiful to me, and conveys something to the tone and attitudes of people speaking it that I like. I like English as well, for different reasons perhaps, it is a pity my English is so weak. I dislike a bit my other mother tongue, Spanish. I feel that the Spanish of Spain as talked in most regions carries some kind of assertiveness that results in less fluency and smoothness in conversations.

  4. I read a book about skydiving just for the sake of curiosity. I have never jumped and do not plan to.

  5. I was into pool for a couple of years, playing 8 and 9 ball in clubs. As in any activity in life, there's a point where you need to spend a lot of time to keep or improve your level. I realized some day, or should I say some night, I was spending more time in pool than I should, I was in the faculty by then. I quit and have never touched a cue again unless it was for fun with friends and the like.

And thus, I won't be the one who dares to break the rules, so I nominate cerquide, ncm, chalst, Mark Jason Dominus, and Tomy Pelluz to follow the chain. Beware, the story goes people who break the chain end up with lifetime jobs maintaining Visual Basic applications.

459 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!