SBCL：Fixnumの最適化

Question

私は、最適化とfixnumsを使用して、少し二次ソルバーの速度を上げようとしています。ここに私のコードです：

1: (defun solve-x (d) 
2: (declare (optimize (speed 3)) 
3:    (type fixnum d)) 
4: (let ((x 1) (y 1)) 
5:  (declare (type fixnum x y)) 
6:  (loop while (/= (- (* x x) (* d y y)) 1) do 
7:  (if (> (- (* x x) (* d y y)) 1) 
8:   (incf y) 
9:   (incf x))) 
10:  (list x y))) 

SBCLコンパイラは6行と7行を正しく最適化できないようです。このような警告が多く表示されています。

forced to do GENERIC-- (cost 10) 
     unable to do inline fixnum arithmetic (cost 2) because: 
     The first argument is a (INTEGER 1 21267647932558653957237540927630737409), not a FIXNUM. 
     The second argument is a (INTEGER 
           -98079714615416886892398913872502479823289163909206900736 
           98079714615416886871131265939943825866051622981576163327), not a FIXNUM. 
     The result is a (VALUES 
         (INTEGER 
         -98079714615416886871131265939943825866051622981576163326 
         98079714615416886913666561805061133780526704836837638145) 
         &OPTIONAL), not a (VALUES FIXNUM &REST T). 
     unable to do inline (signed-byte 64) arithmetic (cost 5) because: 
     The first argument is a (INTEGER 1 21267647932558653957237540927630737409), not a (SIGNED-BYTE 
                         64). 
     The second argument is a (INTEGER 
           -98079714615416886892398913872502479823289163909206900736 
           98079714615416886871131265939943825866051622981576163327), not a (SIGNED-BYTE 
                            64). 
     The result is a (VALUES 
         (INTEGER 
         -98079714615416886871131265939943825866051622981576163326 
         98079714615416886913666561805061133780526704836837638145) 
         &OPTIONAL), not a (VALUES (SIGNED-BYTE 64) &REST T). 
     etc. 

わかりません。私はすでに乗算、除算、および減算の周りに 'fixnum'を挿入しようとしましたが、それはさらに悪化しました。

どのようなアイデア、これを速くするには？

Answer 1

数字がオーバーフローしないことが確実な場合は、(SAFETY 0)を最適化に追加できます。また、計算結果の周囲に(THE FIXNUM ...)を追加して、結果がfixnumとして扱われることをSBCLに伝えます。 3つの引数*は、2つの別々の呼び出しに分割する必要があります。

お客様のコードは現在ループ内で(- (* x x) (* d y y))を2回計算しています。代わりに変数に代入する必要があります。また、ループ内でXまたはYしか変更されないので、もう一方の部分をもう一度計算する必要はありません（これらの計算が何であるかわからないので、私はちょうどFOO、BARおよびQUUXと呼んでいます）。

(defun solve-x (d) 
    (declare (optimize (speed 3) (safety 0) (debug 0)) 
      (type fixnum d)) 
    (let ((x 1) (y 1)) 
    (declare (type fixnum x y)) 
    (loop with foo of-type fixnum = (* x x) 
      with bar of-type fixnum = (* (the fixnum (* d y)) y) 
      for quux of-type fixnum = (- foo bar) 
      while (/= quux 1) 
      do (if (> quux 1) 
       (setf y (1+ y) 
         bar (* (the fixnum (* d y)) y)) 
       (setf x (1+ x) 
         foo (* x x)))) 
    (list x y))) 

式を2回書く必要がないように、#n=リーダーマクロを使用できます。 XとYもという変数リストに移動してLETとDECLAREを取り除くことができます。 XとY以来

(defun solve-x (d &aux (x 1) (y 1)) 
    (declare (optimize (speed 3) (safety 0) (debug 0)) 
      (type fixnum d x y)) 
    (loop with foo of-type fixnum = #1=(* x x) 
     with bar of-type fixnum = #2=(* d (the fixnum (* y y))) 
     for quux of-type fixnum = (- foo bar) 
     while (/= quux 1) 
     do (if (> quux 1) 
       (setf y (1+ y) 
        bar #2#) 
       (setf x (1+ x) 
        foo #1#))) 
    (list x y)) 

常に1ずつ増加、あなたは前の値をインクリメントすることにより、いくつかの乗算を避けることができます。

(defun solve-x (d &aux (x 1) (y 1)) 
    (declare (optimize (speed 3) (safety 0) (debug 0)) 
      (type fixnum d x y)) 
    (loop with foo of-type fixnum = 1 
     with bar of-type fixnum = d 
     for quux of-type fixnum = (- foo bar) 
     while (/= quux 1) 
     do (if (> quux 1) 
       (setf bar (+ bar (the fixnum (* d y))) 
        y (1+ y) 
        bar (+ bar (the fixnum (* d y)))) 
       (setf foo (+ foo x) 
        x (1+ x) 
        foo (+ foo x)))) 
    (list x y)) 

Answer 2

問題は、fixnumはあまり役に立ちません。特に、aとbがfixnumの場合、(* a b)は次のようにはよくないと考えられます。(* most-positive-fixnum most-positive-fixnum)：これはfixnumではありません。

したがって、良い型を持つ引数を宣言する必要があります。具体的には、算術演算がbignumにオーバーフローしないように、fixnumよりも十分小さい型があります。 64ビットプラットフォームを使用していると仮定すると、これはかなり簡単です。