Actually even reading the article I'm not completely certain where that 1000x comes from, I suppose it's when compared to the naive approach.
> This is three orders of magnitude less expensive (36 terms for n=9 and d=2)
Three orders of magnitude is 1000. Peter Norvig's approach was described above with:
> still expensive at search time (114,324 terms for n=9, a=36, d=2)
So 114,324 / 36 = 3,175, so "three orders of magnitude", and I suppose he went conservative by saying "1000x" rather than "3000x".
Actually even reading the article I'm not completely certain where that 1000x comes from, I suppose it's when compared to the naive approach.