評估擴展歐幾里得演算法的實作

經過一些實驗和搜索，我想出了以下定義：

emcd' :: Integer -> Integer -> (Integer,Integer,Integer)
emcd' a 0 = (a, 1, 0)
emcd' a b = 
  let (g, t, s) = emcd' b r
  in (g, s, t - (q * s))
    where
      (q, r) = divMod a b

我會評估emcd' 56 15到最內層，例如：

  emcd' 56 15 
= let (g, t, s) = emcd' 15 11 in (
    let (g, t, s) = emcd' 11 4 in (
      let (g, t, s) = emcd' 4 3 in (
          let (g, t, s) = emcd' 3 1 in (
            let (g, t, s) = emcd' 1 0 in (
              (1, 1, 0)
            ) in (g, s, t - (3 * s))
          ) in (g, s, t - (1 * s))
        ) in (g, s, t - (2 * s))
      ) in (g, s, t - (1 * s))
  ) in (g, s, t - (3 * s))

• 我的評估是否朝著正確的方向發展？

編輯：

根據 Will Ness 的評論，我正在更新評估。

uj5u.com熱心網友回復：

總體方向是正確的，但它包含已經執行的遞回呼叫，因此不能在那里。相反，它是

  emcd' 56 15 
= let (g, t, s) = (
    let (g, t, s) = (
      let (g, t, s) = (
          let (g, t, s) = (
            let (g, t, s) = (
              (1, 1, 0)
            ) in (g, s, t - (3 * s))
          ) in (g, s, t - (1 * s))
        ) in (g, s, t - (2 * s))
      ) in (g, s, t - (1 * s))
  ) in (g, s, t - (3 * s))

在接下來的內容中，我推匯出以下偽代碼（其中a where { ... }代表let { ... } in a）：

= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(2*s))
        where { (g, t, s) = (g, s, t-(1*s))
           where { (g, t, s) = (g, s, t-(3*s))
              where { (g, t, s) = (1, 1, 0) } } } } } 

兩者確實是等價的，但where我認為使用偽代碼更具可讀性。

稍微重構一下定義，就變成了

foo a 0 = (a, 1, 0)
foo a b = (g, s, t-(q*s))
          where { (q, r) = divMod a b 
                ; (g, t, s) = foo b r } 

然后我們用偽代碼where代替let，使用基本的剪切和粘貼替換，

foo 56 15
= (g, s, t-(q*s))
  where { (a, b) = (56, 15)      --
        ; (q, r) = divMod a b
        ; (g, t, s) = foo b r }
= (g, s, t-(q*s))
  where { (q, r) = divMod 56 15    --
        ; (g, t, s) = foo 15 r }
= (g, s, t-(q*s))
  where { (q, r) = (3, 11)           --
        ; (g, t, s) = foo 15 r }
= (g, s, t-(3*s))
  where { (g, t, s) = foo 15 11 }      --
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(q*s))
     where { (a, b) = (15, 11)             --
           ; (q, r) = divMod a b
           ; (g, t, s) = foo b r } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(q*s))
     where { (q, r) = divMod 15 11
           ; (g, t, s) = foo 11 r } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(q*s))
     where { (q, r) = (1, 4)
           ; (g, t, s) = foo 11 r } }  
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = foo 11 4 } }  
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(q*s))
        where { (a, b) = (11, 4)
              ; (q, r) = divMod a b
              ; (g, t, s) = foo b r } } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(q*s))
        where { (q, r) = divMod 11 4
              ; (g, t, s) = foo 4 r } } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(q*s))
        where { (q, r) = (2, 3)
              ; (g, t, s) = foo 4 r } } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(2*s))
        where { (g, t, s) = foo 4 3 } } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(2*s))
        where { (g, t, s) = (g, s, t-(q*s))
           where { (a, b) = (4, 3)
                 ; (q, r) = divMod a b
                 ; (g, t, s) = foo b r } } } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(2*s))
        where { (g, t, s) = (g, s, t-(q*s))
           where { (q, r) = divMod 4 3
                 ; (g, t, s) = foo 3 r } } } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(2*s))
        where { (g, t, s) = (g, s, t-(q*s))
           where { (q, r) = (1, 1)
                 ; (g, t, s) = foo 3 r } } } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(2*s))
        where { (g, t, s) = (g, s, t-(1*s))
           where { (g, t, s) = foo 3 1 } } } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(2*s))
        where { (g, t, s) = (g, s, t-(1*s))
           where { (g, t, s) = (g, s, t-(q*s))
              where { (a, b) = (3, 1)
                    ; (q, r) = divMod a b
                    ; (g, t, s) = foo b r } } } } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(2*s))
        where { (g, t, s) = (g, s, t-(1*s))
           where { (g, t, s) = (g, s, t-(q*s))
              where { (q, r) = divMod 3 1
                    ; (g, t, s) = foo 1 r } } } } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(2*s))
        where { (g, t, s) = (g, s, t-(1*s))
           where { (g, t, s) = (g, s, t-(q*s))
              where { (q, r) = (3, 0)
                    ; (g, t, s) = foo 1 r } } } } } 
= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(2*s))
        where { (g, t, s) = (g, s, t-(1*s))
           where { (g, t, s) = (g, s, t-(3*s))
              where { (g, t, s) = foo 1 0 } } } } } 

現在我們已經達到了基本情況：

= (g, s, t-(3*s))
  where { (g, t, s) = (g, s, t-(1*s))
     where { (g, t, s) = (g, s, t-(2*s))
        where { (g, t, s) = (g, s, t-(1*s))
           where { (g, t, s) = (g, s, t-(3*s))
              where { (g, t, s) = (1, 1, 0) } } } } } 
= (1, s, t-(3*s))
  where { (t, s) = (s, t-(1*s))
     where { (t, s) = (s, t-(2*s))
        where { (t, s) = (s, t-(1*s))
           where { (t, s) = (0, 1-(3*0)) } } } } 
= (1, s, t-(3*s))
  where { (t, s) = (s, t-(1*s))
     where { (t, s) = (s, t-(2*s))
        where { (t, s) = (1, 0-(1*1)) } } } 
= (1, s, t-(3*s))
  where { (t, s) = (s, t-(1*s))
     where { (t, s) = (-1, 1-(2*(-1))) } } 
= (1, s, t-(3*s))
  where { (t, s) = (3, (-1)-(1*3)) } 
= (1, (-4), 3-(3*(-4)))
= (1, (-4), 15)

希望這里沒有剪切和粘貼錯誤。一般的想法只是以純粹機械的方式進行直接的替換。

_{旁注：(g,t,s)=foo a b=== g==gcd a b && g==t*a s*b。}

標籤：哈斯克尔 评估 欧几里得算法

上一篇：理解擴展歐幾里得演算法的實作

下一篇：在Haskell中合并兩個串列