大綱

數值塔 Numerical tower

什麼塔?

什麼是數值塔(Numerical tower)?

  • 任何的數字,都可以被組織在一個子集的塔,塔中每一層是上一層的子集

numerical-tower.png

類型到定義

  • 當數值塔被建立起來,就可以依據每一層對應一種抽象的數值對象
  • 而抽象的數值對象,則可以用函數定義,如 number? , complex? , real? , rational?
  • 由於數值對象具有子集層層包含的關係,在電腦中處理會變得複雜
    • 多重表示 :數值塔越底層的對象,可以被更多重的表示
    • 例如:整數可以被表示為有理數、實數和複數
  • 這個概念主要在 Scheme 被提出,Clojure 也使用這個概念
  • 題外話,網路上也有一些 Python 和數值塔的討論

絕對值函數 ( abs )

  • 為了解決數值塔的問題,我們首先看 Clojure 的絕對值函數:
(defn abs "(abs n) is the absolute value of n" [n]
  (cond
   (not (number? n)) (throw (IllegalArgumentException.
           "abs requires a number"))
   (neg? n) (minus n)
   :else n))
  • 這邊蠻容易可以觀察出來,解決數值塔的問題就從塔最上層開始檢查
  • 一路往下層的子集去檢驗,這邊只對非數值(number?)分流出去丟錯誤

最大公因數函數 ( gcd )

  • 這邊也可以看到,gcd 先對 a 或 b 兩個都要是整數做處理,不是整數就丟錯誤
  • 接著就是實現 gcd 的數學問題,這邊可以注意到特別判斷了有一數是 0 的情況
(defn gcd "(gcd a b) returns the greatest common divisor of a and b" [a b]
  (if (or (not (integer? a)) (not (integer? b)))
    (throw (IllegalArgumentException. "gcd requires two integers"))  
    (loop [a (abs a) b (abs b)]
      (if (zero? b) a,
    (recur b (mod a b))))))
  • 迷之音:很美的實現!

最小公倍數函數 ( lcm )

  • 最小公倍數的算法有特殊公式,可從 gcd 反推回來,所以很普通
(defn lcm
  "(lcm a b) returns the least common multiple of a and b"
  [a b]
  (when (or (not (integer? a)) (not (integer? b)))
    (throw (IllegalArgumentException. "lcm requires two integers")))
  (cond (zero? a) 0
        (zero? b) 0
        :else (abs (mult b (quot a (gcd a b))))))

指數函數 ( expt )

  • 接著我們看稍微複雜的指數函數,首先對於容易計算的做個過濾
(defn expt
  [base pow]
  (if (and (not (float? base)) (integer? pow)) 
    (cond
         ... ;; 不是浮點數為底且指數次方為整數者,接著處理 ( -> 進入第二層 )
   )
    (Math/pow base pow))) ;; 太複雜的就直接 pow 函數來吧!
  • 不容易計算的,就直接硬幹帶入 Math/pow 函數中處理

指數函數 ( expt )

  • 第二層開始分正的次方、零的次方、負的次方做處理
...
(cond
 (pos? pow) (expt-int base pow) ;; 正的次方 -> 用專門算整數次方的函數計算
     (zero? pow) (cond   
                      ...       ;;  0 的次方 -> 0 的次方基本上是 1 ( -> 進入第三層 )
                 )
     :else (/ 1 (expt-int base (minus pow)))) ;; 負的次方 -> 轉成正的次方處理,並做個倒數
...
  • 0 的次方是 1 ,是數值塔最下層的元素,那回傳應該依照什麼型別呢?

指數函數 ( expt )

;; 零的次方
...
(cond
  (= (type base) BigDecimal) 1M
  (= (type base) java.math.BigInteger) (java.math.BigInteger. "1")
  (when-available clojure.lang.BigInt (= (type base) clojure.lang.BigInt))
  (when-available clojure.lang.BigInt (bigint 1))
  :else 1)
...
  • 這邊可以觀察到,是根據底數(base)的型別做回傳,因為主角就是底數
  • 這邊同時處理 clojure 與 java 的數值型別,而不單單只是 clojure
  • clojure 部分有套一個 when-available 函數,若有誤就丟錯誤

數值塔幫助思考

  • 這邊就能發現,數值塔需要去捕捉輸入的型別,可能會讓輸出延續那個型別
  • 這邊就要考慮,輸入、輸出與數學函數運算過程中會遇到的型別問題
  • 此外,像 Clojure 與 Java 可以互相使用的話,彼此的數字型別也要照顧到
  • 這給予我們一個範例,若要在 Clojure 中建立一個數學相關的 library
  • 不過,事情還沒結束!我們可以透過 defprotocol 與 extend-type 做得更好

defprotocol 與 extend-type

數值型別 + 數學函數 = 類(Class)?

  • 當在處理數值塔,能發現我們不斷在處理數值型別判斷與數學函數的運算
  • 感覺就是很物件導向(?)進一步思考,或許可以使用 defprotocol
  • 使用 defprotocol 這個 macro 來提供一個方法(Method)的簽名,對應一個數學函數
  • 再透過 macro - extend-type 來將數學函數對應到不同的 type 的處理
  • 個人觀察:感覺是需要頻繁上下數值塔的 type 才需要這樣做,例如高斯類型的函數(floor, ceil)

defprotocol 與 extend-type

extend-type.png

defprotocol

  • 看個 defprotocol 的例子,這邊可以看到只是做個簽名
(defprotocol MathFunctions
  (floor [n] "(floor n) returns the greatest integer less than or equal to n.
If n is an exact number, floor returns an integer, otherwise a double.")
  (ceil [n] "(ceil n) returns the least integer greater than or equal to n.
If n is an exact number, ceil returns an integer, otherwise a double.")
  (round [n] "(round n) rounds to the nearest integer.
round always returns an integer.  Rounds up for values exactly in between two integers.")
  (integer-length [n] "Length of integer in binary")
  (sqrt [n] "Square root, but returns exact number if possible."))
  • 隨後也緊跟著 declare 宣告 sqrt-integer, sqrt-ratio 與 sqrt-decimal
  • 用來在 extend-type 中實現如何處理不同類型的方根

extend-type

  • 也來看兩個 extend-type 的處理
;; 整數的 extend-type : 整數做 floor, ceil 與 round 根本不變
(extend-type
 Integer MathFunctions
 (floor [n] n)  (ceil [n] n)  (round [n] n) 
 (integer-length [n] (- 32 (Integer/numberOfLeadingZeros n)))
 (sqrt [n] (sqrt-integer n))) ;; 處理整數的方根問題,另代函數處理
;; 雙精度浮點數的 extend-type : 直接套公式
(extend-type
 Double MathFunctions
 (floor [n] (Math/floor n))  (ceil [n] (Math/ceil n)) 
 (round [n] (Math/round n))  (sqrt [n] (Math/sqrt n)))

exact-integer-sqrt 與 sqrt-integer

  • 在處理對整數取方根的問題時,我們遇到回傳問題,如果回傳要保持整數的話:
    • 取距離整數開根號之後的值,最小的整數?
  • 0 的次方是 1 要回傳整數或浮點數,是一個數值塔「下層」往「上層」處理
  • 現在是一個「下層」運算完到「上層」,會需要做取捨才能回到「下層」
  • 類似於整數除整數的問題
  • 所以在 Clojure 中,就特別用 sqrt-integer 表示回傳最接近方根的整數
  • 用 exact (精確) 回傳 double 的方根值,確切近似精確的方根數值

研究心得

研究心得

  • 數值塔是個很不錯的概念,可以對應到代數中封閉性的問題
  • 本 library 是一個很好的範例,提供很多命名、控制流程的參考:

1 . 遞迴表示數學函數( gcd, integer-sqrt )

2 . 用 when 和 if 控制數值塔的上上下下,對輸入做立即檢查和丟錯誤

3 . 透過 defprotocol 與 extend-type 來將函數代入型別做各自的實現

4 . 透過 exact 函數前綴,來處理回傳型別是否和輸入保持相同型別

5 . 還有更多 clojure 與 java 處理基本型別的函數(BigDecimal, BigInt)

Thank You

fatfingererr@gmail.com