Older blog entries for fzort (starting at number 57)

2 Feb 2007 (updated 2 Feb 2007 at 09:09 UTC) »
Google Code Jam, Round 2

I got pwned. Big time.

That is all.

1 Feb 2007 (updated 1 Feb 2007 at 15:59 UTC) »
fejj: the standard way to do that is to replace the division with a multiplication by the reciprocal, multiplied by some power of 2. Then divide the result by that power of 2, which can be done with a right shift. In the case of division by 7, you'd end up with the increasingly more accurate expressions:

q = ((a<<3) + a) >> 6

q = ((a<<6) + (a<<3) + a) >> 9

q = ((a<<9) + (a<<6) + (a<<3) + a) >> 12

q = ((a<<12) + (a<<9) + (a<<6) + (a<<3) + a) >> 15


and so on (in binary, 1/7 is .001001001...). Optionally, the result can be fixed with something like

r = a - q*7; while (r >= 7) { q++; r -= 7; }

The multiplication by 7 can be replaced with shifts and adds, of course.

31 Jan 2007 (updated 31 Jan 2007 at 13:24 UTC) »
Google Code Jam, Round 1

My performance was dismal. I did the easy problem, then moved straight to the hard one. Then I threw away 20 minutes because I jumped straight to the code before understanding completely the problem statement and then had to start all over again, wasted another 20 minutes tracking down a stupid off-by-one bug, panicked for about 5 minutes, and finally ended up submitting a /wrong/ solution. Guess I need to work on the think-crush-under-pressure thing.

What makes it so frustrating is that the problem was not really that hard, and I was able to concoct a correct solution (here) without major difficulties afterwards, when the time pressure was gone.


24 Jan 2007 (updated 24 Jan 2007 at 19:19 UTC) »
Google Code Jam

The qualification round was easier than I expected. It's probably just meant to filter out the curious. I was able to do both problems in about 30 minutes, and qualified to the next phase.

Tupper's Self-Referential Formula

... seems to be making the rounds on the internet. Two different people sent me the link. It's cute, but there's nothing magical about it, really - perhaps if some people look at it as a simple Perl script they'll realize that it's just a way to rasterize the big number, and the bitmap could be anything.

23 Jan 2007 (updated 23 Jan 2007 at 00:19 UTC) »

So, tomorrow is Google Code Jam Latin America. I'll give it a try, but I expect to get my arse kicked. Although I've been practicing a bit at SPOJ and acm.uva.es, I really suck at thinking under pressure. Ah well, let's see how it goes.



#define is_odd(x) (((x)&1) != 0)
#define is_even(x) (((x)&1) == 0)

2. if you're out to disprove the Collatz conjecture, use GMP or something.

30 Nov 2006 (updated 1 Dec 2006 at 00:13 UTC) »
mchirico, fejj: it's the Look and Say Sequence. See also: Conway's Cosmological Theorem.

It's all demonstrated in this wonderful IOCCC winner (hint file).

16 Oct 2006 (updated 21 Apr 2009 at 21:05 UTC) »


Free software

Haven't touched my personal projects in a while, partly because of lack of time, partly because of the SPOJ addiction, partly because of general pissedoffness, but anyway I packed together the minor changes I did on vulcan in the past couple of months (lots of bugfixes) and called it 0.3.1.

Speaking of SPOJ, I recently ordered Sedgewick's algorithms book with the specific purpose of improving my SPOJ score. Whee.

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?


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) »

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

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


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.

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