下の PostScript を 6 倍ほど高速化できないものか。

の下 1000 桁を計算する（anarchy golf - Modular Exponentiationです）プログラムなのですが、16 秒ほどかかってしまいます。

[2 249{0}repeat]100{[1 4]{/a 2 index def{/b exch def[0 0 1 249{/i exch def 0 i
-1 0{/j exch def exch a i j sub get b j get mul add dup 10000 mod exch 10000
idiv 3 2 roll add}for}for pop]}repeat}forall}repeat aload length{10000 add 5
string cvs 1 4 getinterval print}repeat

Karatsuba 法とか FFT とかで速くなるかなあ。
追記：Karatsuba 法の真似事をしたら所要時間が長くなった。