Burnikel和Ziegler算法的Eiffel實現中的錯誤2

Question

我需要另一組眼睛來告訴我Burnikel和Ziegler的部門的Eiffel實現有什麼問題，特別是「算法2 - 3n/2n」。埃菲爾功能如下所示。類似「Current」的類型是ARRAYED_LIST [NATURAL_8]。換句話說，該實現使用包含8位值的數字（即分支），因此數字以256爲基數。以下是一個失敗呼叫的手動追蹤。 （對不起，參數非常大，但我無法用較短的值重現此錯誤。）在這種情況下，執行步驟在步驟3b之後。

這是問題所在。該算法對第5步似乎沒有問題，其餘部分「r」以除數後的數字結束。我相信這個錯誤是在步驟3b中，也許是調用了「假設」提供「Beta^n - 1」值的'ones'。 （也許我不明白乙&個Z「測試^ N」符號

這裏是艾菲爾代碼：

three_by_two_divide (a, a3, b: like Current): TUPLE [quot, rem: like Current] 
     -- Called by `two_by_one_divide'. It has similar structure as 
     -- `div_three_halves_by_two_halfs', but the arguments to this 
     -- function have type {JJ_BIG_NATURAL} instead of like `digit'. 
     -- See Burnikel & Zieler, "Fast Recursive Division", pp 4-8, 
     -- Algorithm 2. 
    require 
     n_not_odd: b.count >= div_limit and b.count \\ 2 = 0 
     b_has_2n_digits: b.count = a3.count * 2 
     a_has_2n_digits: a.count = a3.count * 2 
    local 
     n: INTEGER 
     a1, a2: like Current 
     b1, b2: like Current 
     tup: TUPLE [quot, rem: like Current] 
     q, q1, q2, r, r1: like Current 
     c, d: like Current 
    do 
     n := b.count // 2 
      -- 1) Split `a' 
     a1 := new_sub_number (n + 1, a.count, a) 
     a2 := new_sub_number (1, n.max (1), a) 
      -- 2) Split `b'. 
     b1 := new_sub_number (n + 1, b.count, b) 
     b2 := new_sub_number (1, n.max (1), b) 
      -- 3) Distinguish cases. 
     if a1 < b1 then 
       -- 3a) compute Q = floor ([A1,A2]/B1 with remainder. 
      if b1.count < div_limit then 
       tup := school_divide (a, b1) 
      else 
       tup := two_by_one_divide (a, b1) 
      end 
      q := tup.quot 
      r1 := tup.rem 
     else 
       -- 3b) Q = beta^n - 1 and ... 
      q := ones (n) 
       -- ... R1 = [A1,A2] - [B1,0] + [0,B1] = [A1,A2] - QB1. 
      r1 := a + b1 
      if n > 1 then 
       b1.shift_left (n) 
      else 
       b1.bit_shift_left (zero_digit.bit_count // 2) 
      end 
      r1.subtract (b1) 
     end 
      -- 4) D = Q * B2 
     d := q * b2 
      -- 5) R1 * B^n + A3 - D. (The paper says "a4".) 
     r1.shift_left (n) 
     r := r1 + a3 - d 
      -- 6) As long as R < 0, repeat 
     from 
     until not r.is_negative 
     loop 
      r := r + b 
      q.decrement 
     end 
     check 
      remainder_small_enough: r.count <= b.count 
       -- because remainder must be less than divisor. 
     end 
     Result := [q, r] 
    ensure 
    -- n_digit_remainder: Result.rem.count = b.count // 2 
     quotient_has_correct_count: Result.quot.count <= b.count // 2 
    end 

在跟蹤，箭頭指向一條線，我相信是壞的，但我不知道該怎麼辦這裏是跟蹤：。

three_by_two_divide (a = [227,26,41,95,169,93,135,110], 
        a3 = [92,164,19,39], 
        b = [161,167,158,41,164,0,0,0]) 

    n := b.count // 2 = 4 
     -- 1) Split `a'. 
    a1 := new_sub_number (n + 1, a.count, a) = [227,26,41,95] 
    a2 := new_sub_number (1, n.max (1), a) = [169,93,135,110] 
     -- 2) Split `b'. 
    b1 := new_sub_number (n + 1, b.count, b) = [161,167,158,41] 
    b2 := new_sub_number (1, n.max (1), b) = [164,0,0,0] 
     -- 3b) Q = beta^n -1 and ... 
--> q := ones (4) = [255,255,255,255]   <-- Is this the error? 
     -- ... R1 = [A1,A2] - [B1,0] + [0,B1]. 
    r1 := a + b1 = [227,26,41,96,75,5,37,151] 
    b1.shift_left (n) = [161,167,158,41,0,0,0,0]       
    r1.subtract (b1) = [65,114,139,55,75,5,37,151] 
    d := q * b2 = [163,255,255,255,92,0,0,0] 
    r1.shift_left (n) = [227,25,135,184,172,220,37,151,0,0,0,0] -- too big! 
    r := r1 + a3 - d -= [227,25,135,184,8,220,37,152,0,164,19,39] -- too big! 

我知道這是很長，但任何幫助表示讚賞

Answer 1

我建議檢查r1 = [65,114,139,55,75,5,37,151]我在做r1.shift_left (n)之前，它仍然是一樣的。有兩種選擇：

1. d := q * b2影響r1雖然它不應該。最有可能的是有一些別名，即r1別名與其他一些更新的變量，這種別名應該被刪除。
2. r1仍然是d := q * b2後相同。問題出在shift_left，它無法（重新）初始化一些數據或使用它不應該使用的全局數據。