An intriguing mistake
Sep. 30th, 2011 04:21 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sawylImplementing what should have been a relatively straightforward bit of mathematics, I was completely baffled by its obvious inability to produce the right results. I checked the array indices for Obi-Wan errors and scrutinised the logic of the logic of the tests, but everything appeared to be working as expected. So, suspecting a higher order problem, I went away and chased down another description of the algorithm and suddenly the root cause was obvious: the browser had incorrectly rendered a minus sign in one of the equations in the first description (the sign was there when I checked the page source) and as result I'd multiplied the terms instead of subtracting them...
ETA: Embarrassingly, the fancy version of the algorithm runs at around a third of the speed of the simple one it was supposed to replace. So, like bad workmen the world over, I'm going to blame my tools: in this case python's less than stellar numerical performance. Maybe, if I can be bothered, I'll drop the core code into C or Fortran just to see what happens...
ETA 2: I was right: shifting the heavy lifting into C makes the fancy version of the algorithm outperform the naive one by an order of magnitude. And as a biproduct, it also makes it trivially easy to massively reduce the memory footprint by switching the primary data structure from a python list to a series of bit fields. Excelsior!
ETA: Embarrassingly, the fancy version of the algorithm runs at around a third of the speed of the simple one it was supposed to replace. So, like bad workmen the world over, I'm going to blame my tools: in this case python's less than stellar numerical performance. Maybe, if I can be bothered, I'll drop the core code into C or Fortran just to see what happens...
ETA 2: I was right: shifting the heavy lifting into C makes the fancy version of the algorithm outperform the naive one by an order of magnitude. And as a biproduct, it also makes it trivially easy to massively reduce the memory footprint by switching the primary data structure from a python list to a series of bit fields. Excelsior!
