Monday, March 05, 2007
Karatsuba
I'm pretty sure I owe Jenn an apology for something like this when I was in CS 134 and implementing a class that could handle arbitrarily large integers with the common operations (addition, subtraction, multiplication, division, exponentiation).
I wanted to implement Karatsuba multiplication. It's marginally faster than gradeschool long multiplication. Yup, you heard right: marginally faster. And there was no bonus marks to be had. And hell, implementing multiplication was only worth like .1% of your final mark. And I was trying to optimize *JAVA*. Definitely a missing-the-forest-for-the-trees moment. I didn't end up seeing the results I expected, so fine, I said, fuck it!
And I went on to other pursuits.
But then... like the crescendo of a great concerto, the explosion of a whole sky's worth of fireworks and the crash of thunder all at once, it became clear to me: I was being sloppy with object creation in a tight loop!
And I think I also owe Jenn similar apologies for SE 141 (fastest clock rate on the Xilinx boards for project #3), CS 241 (removing the arbitrary restriction on the number of local variables supported by my implementation of SL) and ECE 354 (corner case where A5 gets destroyed on the MCF5307 when context switching).
Side note: Jenn and I had an epiphany after seeing a bike store on Hamilton Street in Vancouver. If we ever live in Hamilton, we will dispense with our cumulative 8 years of study of math and engineering to be the proprietors of a bike shop named the Hamiltonian Cycle.
I wanted to implement Karatsuba multiplication. It's marginally faster than gradeschool long multiplication. Yup, you heard right: marginally faster. And there was no bonus marks to be had. And hell, implementing multiplication was only worth like .1% of your final mark. And I was trying to optimize *JAVA*. Definitely a missing-the-forest-for-the-trees moment. I didn't end up seeing the results I expected, so fine, I said, fuck it!
And I went on to other pursuits.
But then... like the crescendo of a great concerto, the explosion of a whole sky's worth of fireworks and the crash of thunder all at once, it became clear to me: I was being sloppy with object creation in a tight loop!
And I think I also owe Jenn similar apologies for SE 141 (fastest clock rate on the Xilinx boards for project #3), CS 241 (removing the arbitrary restriction on the number of local variables supported by my implementation of SL) and ECE 354 (corner case where A5 gets destroyed on the MCF5307 when context switching).
Side note: Jenn and I had an epiphany after seeing a bike store on Hamilton Street in Vancouver. If we ever live in Hamilton, we will dispense with our cumulative 8 years of study of math and engineering to be the proprietors of a bike shop named the Hamiltonian Cycle.
