…use a matrix of previous discharge rate intervals indexed by the charge at the time and the actual average discharge rate during that interval….
I've prototyped this, and wow, it's accurate. I've used floating point least squares regression to find the rate of discharge. This trivially takes into account battery cell configuration and battery chemistry data, and continually 'tweaks' itself with the new data, i.e. getting more accurate in shape as you discharge and charge each time.
Sub-screenshot of my test program
I've still got to work on interpolation of data where the percentage wasn't hit (the start and end for me, but might happen anywhere), but this is not a big problem.
I'm now optimising my code for speed, making a suitable gobjects for the data structures and testing like mad. I hope to have some other battery discharge and charge curves from stuff like OLPC and my nearly completely broken battery iBook.
Before people ask, the graph widget is the one used in gnome-power-statistics, and that screenshot was taken of a custom hacky application that has far too many graphs to fit on one screen.