Older blog entries for fzort (starting at number 49)

7 Oct 2006 (updated 7 Oct 2006 at 20:04 UTC) »
StevenRainwater: you rule. Thank you!

Where can we find the updated mod_virgule code?

SPOJ

Phew. This took a lot of work. I exchanged the first place with the guy that's currently second several times until finally changing algorithms and getting to the first place with a decent margin.

Changelog, ex posto facto:

  • 0.1: trial division followed by Fermat primality test.
  • 0.2: Rabin-Miller.
  • 0.3: accelerated a bit multiplication followed by division operations in the modular exponentiation code (from now on referred to as expmod) with x86-specific inline assembly (it has 32-bit -> 64-bit multiplication and a 64-bit -> 32-bit division and remainder instructions).
  • 0.4: found a "cheat" that allowed me to go back to Fermat test, at a big performance win.
  • 0.5: lots of micro-optimizations. Used a sliding bit window in expmod. Got to the first place for the first time.
  • 0.6: realized that the only way to get faster would be to eliminate the division operation in expmod. Replaced the division with multiplication by the inverse (some call this "Barrett reduction"). Was a teeny weeny bit faster on my machine, but slower at spoj. The reduction involved a 64-bit multiplication (three multiplication instructions on 32-bit x86). :/
  • 0.7: Montgomery exponentiation!

For future reference, here's a neat trick to find the multiplicative inverse of a number modulo 2^k, lightning fast (this was needed in the pre-calculation phase of Montgomery). First, two facts:

  • a^-1 = y*(2 - a*y) (mod 2^k), where y = a^-1 (mod 2^{k-1}). We can use this fact alone to derive a moderately fast algorithm to get a^-1 mod 2^k.
  • if q = 2^{k/2}*a + b (with b odd), then q*(2*b - q) = b^2 (mod 2^k), so q^-1 = (2*b - q)*((b^2)^-1) (mod 2^k).

To get q^-1 (mod 2^k), with k even, first get (b^2)^-1 from a table (for e.g. k=32 it will be a small table) and then use fact #2. With k odd, do that for k-1 and then use fact #1.

19 Sep 2006 (updated 21 Sep 2006 at 14:39 UTC) »
Advogato

It would be really sad to see it go away. wingo put it nicely.

While it's still here, I'll keep on rambling...

SPOJ

I fell a bit behind on work and personal projects due to a recently-acquired addiction to the oddly-named website Sphere Online Judge. It's full of programming problems, mostly algorithmic. You post a solution and it gets compiled and tested automatically. Each problem has a ranking with the best solutions. It accepts everything from C to Haskell to Common Lisp to Intercal (really). This is my current status.

Hopefully I have the addiction firmly under control now. On the plus side, working on the problems is giving me the motivation I needed to finally do something about the gaping lacunae in my knowledge of algorithms.

21 Aug 2006 (updated 13 Sep 2006 at 11:09 UTC) »
9 Aug 2006 (updated 9 Aug 2006 at 10:43 UTC) »
haruspex: of course it's not about efficiency, it's about how it does it. I don't know about you, but it took me a while to figure it out...
4 Aug 2006 (updated 4 Aug 2006 at 14:33 UTC) »
Typespeed says I'm a typing god (with the English dictionary). Unfortunately, that seems to be the result of statistical fluctuation - my average score appears to be much lower. Bummer.

On other news - clever population-count function, via pmk:

int f(unsigned x) { unsigned y=0; int j; for (j=0;j<32;j++) y += (x<<j) + (x>>32-j); return -y;}

1 Aug 2006 (updated 1 Aug 2006 at 22:41 UTC) »
vulcan

    Released version 0.3 of vulcan a few days ago. I'm not happy at all with the move generation code, though. What chess programs such as Crafty and (recent versions of) GNU Chess seem to use are bitmaps and lots of wizardly bit-twiddling to parallelize operations in the move generator. Vulcan could benefit from that sort of stuff. So I got crazy yesterday and started by throwing away a couple thousand lines of code. Woo-hoo.

Ghost in the Shell 2: Innocence

    Awe-inspiring visuals. Beautiful, haunting soundtrack. Long, utterly implausible dialogues between street-hardened cops about such pressing issues as Descartes' mind-body dualism. Had me feeling most of the time like a small kid who flips through the pages of a book and marvels at the pretty pictures, but can't understand the words. People who thought that Hollywood junk like "The Matrix" was intellectually stimulating should watch this one.

    Minor quibble: call me squeamish if you will, but I could do without the extreme violence.

15 Jul 2006 (updated 15 Jul 2006 at 19:39 UTC) »
freshmeat weirdness

Even though my new baby seems to have a freshmeat page now, the announcement didn't make it to the front page. :(

Oh well. I'll be releasing a version 0.2 soon. Who knows, then...

14 Jul 2006 (updated 14 Jul 2006 at 15:00 UTC) »
vulcan

I was planning to do much more before releasing it, including some major code cleanup, but then thought why not. So I just hacked a quick page, packed it as vulcan-0.1.tar.gz, and submitted to freshmeat. Release early, release often!

6 Jul 2006 (updated 6 Jul 2006 at 21:04 UTC) »
gicmo: you're hardly alone in your dislike of Maradona.

Pointless waste of bandwidth

Okay, so when did posting images to advogato's recentlog become socially acceptable? Anyway, here comes a screenshot of the personal project I've been working on. Please feel free to rate my diary down.

It's the 3D chess game from Star Tr^W^W^W "inspired" by a certain well-known science fiction TV show. It's sort of playable right now, but I still need to squish some bugs and improve the user interface a bit before it hits version 0.1 (and freshmeat).

20 Jun 2006 (updated 20 Jun 2006 at 17:00 UTC) »
Back in the zone

After a couple of months with no serious coding (not counting what I've been doing for work, of course), it's good to be back. More info on the project I've been working on in the next few days.

Chess

While searching for ways to improve my playing, I recently discovered chess problems. The stuff is more addictive than Sudoku. Here is a nice collection of easy ones, for beginners like me.

My playing still sucks, though.

40 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!