教えてください。

２４ビット true color のビットマップを減色して２５６個のパレットをもつ８ビットのピクセル形式にしています。
パレットのエントリは予め決まっており、現在は NearestColor という方法で減色しています。

オリジナルのピクセルの色に「最も近い色」は、現在

distance2 = (r1-r2)^2 + (g1-g2)^2 + (b1-b2)^2

が最小になるようなパレットエントリを探して決定しています。結果には不満はないのですが、すべてのピクセルについて
distance2 を２５６回求めなければならず処理が遅くて困っています。なにか有効なアルゴリズムみたいなものを
ご存じありませんでしょうか。