第 6 章數學 · coffeescript技術文檔

# 6數學 ### 數學常數 ### 問題你需要使用常見的數學常數，比如 π 或者 e 。 ### 解決方案使用 Javascript 的 Math object 來提供通常需要的數學常數。 ~~~ Math.PI # => 3.141592653589793 ? ? # Note: Capitalization matters! This produces no output, it's undefined. ? Math.Pi # => ? ? Math.E # => 2.718281828459045 ? ? Math.SQRT2 # => 1.4142135623730951 ? ? Math.SQRT1_2 # => 0.7071067811865476 ? ? # Natural log of 2. ln(2) ? Math.LN2 # => 0.6931471805599453 ? ? Math.LN10 # => 2.302585092994046 ? ? Math.LOG2E # => 1.4426950408889634 ? ? Math.LOG10E # => 0.4342944819032518 ~~~ ### 討論另外一個例子是關于一個數學常數用于真實世界的問題，是數學章節有關[弧度和角度](http://coffeescript-cookbook.github.io/chapters/math/radians-degrees)的部分。 ### 更快的 Fibonacci 算法 ### 問題你想計算出 Fibonacci 數列中的數值 N ，但需迅速地算出結果。 ### 解決方案下面的方案（仍有需改進的地方）最初在 Robin Houston 的博客上被提出來。這里給出一些關于該算法和改進方法的鏈接： - [http://bosker.wordpress.com/2011/04/29/the-worst-algorithm-in-the-world/](http://bosker.wordpress.com/2011/04/29/the-worst-algorithm-in-the-world/) - [http://www.math.rutgers.edu/~erowland/fibonacci](http://www.math.rutgers.edu/~erowland/fibonacci) - [http://jsfromhell.com/classes/bignumber](http://jsfromhell.com/classes/bignumber) - [http://www.math.rutgers.edu/~erowland/fibonacci](http://www.math.rutgers.edu/~erowland/fibonacci) - [http://bigintegers.blogspot.com/2010/11/square-division-power-square-root](http://bigintegers.blogspot.com/2010/11/square-division-power-square-root) - [http://bugs.python.org/issue3451](http://bugs.python.org/issue3451) 以下的代碼來源于：[https://gist.github.com/1032685](https://gist.github.com/1032685) ~~~ ### ? Author: Jason Giedymin <jasong _a_t_ apache -dot- org> http://www.jasongiedymin.com https://github.com/JasonGiedymin ? CoffeeScript Javascript 的快速 Fibonacci 代碼是基于 Robin Houston 博客里的 python 代碼。見下面的鏈接。 ? 我要介紹一下 Newtonian，Burnikel / Ziegle 和Binet 關于大數目框架算法的實現。 ? Todo: - https://github.com/substack/node-bigint - BZ and Newton mods. - Timing ? ### ? ? MAXIMUM_JS_FIB_N = 1476 ? fib_bits = (n) -> #代表一個作為二進制數字陣列的整數 ? bits = [] while n > 0 [n, bit] = divmodBasic n, 2 bits.push bit ? bits.reverse() return bits ? fibFast = (n) -> #快速 Fibonacci ? if n < 0 console.log "Choose an number >= 0" return ? [a, b, c] = [1, 0, 1] ? for bit in fib_bits n if bit [a, b] = [(a+c)*b, b*b + c*c] else [a, b] = [a*a + b*b, (a+c)*b] ? c = a + b return b ? divmodNewton = (x, y) -> throw new Error "Method not yet implemented yet." ? divmodBZ = () -> throw new Error "Method not yet implemented yet." ? divmodBasic = (x, y) -> ### 這里并沒有什么特別的。如果可能的話，也許以后的版本將是Newtonian 或者 Burnikel / Ziegler 的。 ### ? return [(q = Math.floor x/y), (r = if x < y then x else x % y)] ? start = (new Date).getTime(); calc_value = fibFast(MAXIMUM_JS_FIB_N) diff = (new Date).getTime() - start; console.log "[#{calc_value}] took #{diff} ms." ~~~ ### 平方根倒數快速算法 ### 問題你想[快速](https://en.wikipedia.org/wiki/Fast_inverse_square_root)計算某數的平方根倒數。 ### 解決方案在 Quake Ⅲ Arena 的[源代碼](#)中，這個奇怪的算法對一個幻數進行整數運算，來計算平方根倒數的浮點近似值。在 CoffeeScript 中，他使用經典原始的變量，以及由 [Chris Lomont](http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf) 發現的新的最優 32 位幻數。除此之外，還使用 64 位大小的幻數。另一特征是可以通過控制[牛頓迭代法](https://en.wikipedia.org/wiki/Newton%27s_method)的迭代次數來改變其精確度。相比于傳統的，該算法在性能上更勝一籌，這歸功于使用的機器及其精確度。運行的時候使用 coffee -c script.coffee 來編譯 script：然后復制粘貼編譯的 JS 代碼到瀏覽器的 JavaScript 控制臺。注意：你需要一個支持[類型數組](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Typed_arrays)的瀏覽器參考： 1. [ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip](#) 1. [http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf](http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf) 1. [http://en.wikipedia.org/wiki/Newton%27s_method](http://en.wikipedia.org/wiki/Newton%27s_method) 1. [https://developer.mozilla.org/en/JavaScripttypedarrays](https://developer.mozilla.org/en/JavaScripttypedarrays) 1. [http://en.wikipedia.org/wiki/Fastinversesquare_root](http://en.wikipedia.org/wiki/Fastinversesquare_root) 以下的代碼來源于：[https://gist.github.com/1036533](https://gist.github.com/1036533) ~~~ ### ? ? ? Author: Jason Giedymin <jasong _a_t_ apache -dot- org> http://www.jasongiedymin.com https://github.com/JasonGiedymin ? 在 Quake Ⅲ Arena 的源代碼 [1](ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip) 中，這個奇怪的算法對一個幻數進行整數運算，來計算平方根倒數的浮點近似值 [5](http://en.wikipedia.org/wiki/Fast_inverse_square_root)。 ? 在 CoffeeScript 中，我使用經典原始的變量，以及由 Chris Lomont [2](http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf) 發現的新的最優 32 位幻數。除此之外，還使用 64 位大小的幻數。 ? 另一特征是可以通過控制牛頓迭代法 [3](http://en.wikipedia.org/wiki/Newton%27s_method) 的迭代次數來改變其精確度。 ? 相比于傳統的，該算法在性能上更勝一籌，歸功于使用的機器及其精確度。 ? 運行的時候使用 coffee -c script.coffee 來編譯 script： ? ? 然后復制粘貼編譯的 JS 代碼到瀏覽器的 JavaScript 控制臺。 ? 注意：你需要一個支持類型數組 [4](https://developer.mozilla.org/en/JavaScript_typed_arrays) 的瀏覽器 ? ### ? ? approx_const_quake_32 = 0x5f3759df # See [1] approx_const_32 = 0x5f375a86 # See [2] approx_const_64 = 0x5fe6eb50c7aa19f9 # See [2] ? fastInvSqrt_typed = (n, precision=1) -> # 使用類型數組。現在只能在瀏覽器中操作。 # Node.JS 的版本即將推出。 ? y = new Float32Array(1) i = new Int32Array(y.buffer) ? y[0] = n i[0] = 0x5f375a86 - (i[0] >> 1) ? for iter in [1...precision] y[0] = y[0] * (1.5 - ((n * 0.5) * y[0] * y[0])) ? return y[0] ? ### 單次運行示例 ? ? testSingle = () -> example_n = 10 ? console.log("Fast InvSqrt of 10, precision 1: #{fastInvSqrt_typed(example_n)}") console.log("Fast InvSqrt of 10, precision 5: #{fastInvSqrt_typed(example_n, 5)}") console.log("Fast InvSqrt of 10, precision 10: #{fastInvSqrt_typed(example_n, 10)}") console.log("Fast InvSqrt of 10, precision 20: #{fastInvSqrt_typed(example_n, 20)}") console.log("Classic of 10: #{1.0 / Math.sqrt(example_n)}") ? testSingle() ~~~ ### 生成可預測的隨機數 ### 問題你需要生成在一定范圍內的隨機數，但你也需要對發生器進行“生成種子”操作來提供可預測的值。 ### 解決方案編寫你自己的隨機數生成器。當然有很多方法可以做到這一點，這里給出一個簡單的示例。 *該發生器絕對不可以以加密為目的！* ~~~ class Rand # 如果沒有種子創建，使用當前時間作為種子 constructor: (@seed) -> # Knuth and Lewis' improvements to Park and Miller's LCPRNG @multiplier = 1664525 @modulo = 4294967296 # 2**32-1; @offset = 1013904223 unless @seed? && 0 <= seed < @modulo @seed = (new Date().valueOf() * new Date().getMilliseconds()) % @modulo ? # 設置新的種子值 seed: (seed) -> @seed = seed ? # 返回一個隨機整數滿足 0 <= n < @modulo randn: -> # new_seed = (a * seed + c) % m @seed = (@multiplier*@seed + @offset) % @modulo ? # 返回一個隨機浮點滿足 0 <= f < 1.0 randf: -> this.randn() / @modulo ? # 返回一個隨機的整數滿足 0 <= f < n rand: (n) -> Math.floor(this.randf() * n) ? #返回一個隨機的整數滿足min <= f < max rand2: (min, max) -> min + this.rand(max-min) ~~~ ### 討論 JavaScript 和 CoffeeScript 都不提供可產生隨機數的發生器。編寫發生器對于我們來說將是一個挑戰，在于權衡量的隨機性與發生器的簡單性。對隨機性的全面討論已超出了本書的范圍。如需進一步閱讀，可參考 Donald Kunth 的 *The Art of Computer Programming* 第 Ⅱ 卷第 3 章的 “ Random Numbers ” ，以及 *Numerical Recipes in C* 第二版本第 7 章的“ Random Numbers ”。但是，對于這個隨機數發生器只有簡單的解釋。這是一個線性同余偽隨機數發生器，其運行源于一條數學公式 Ij+1 = (aIj+c) % m，其中 a 是乘數，c 是加法偏移量，m 是模數。每次請求隨機數時就會執行很大的乘法和加法運算——這里的“很大”與密鑰空間有關——得到的結果將以模數的形式被返回密鑰空間。這個發生器的周期為 232。雖然它絕對不能以加密為目的，但是對于最簡單的隨機性要求來說，它是相當足夠的。randn() 在循環之前將遍歷整個密鑰空間，下一個數由上一個來確定。如果你想修補這個發生器，強烈建議你去閱讀 Knuth 的 * The Art of Computer Programming * 中的第 3 章。隨機數生成是件很容易弄糟的事情，然而 Knuth 會解釋如何區分好的和壞的隨機數生成。不要把發生器的輸出結果變成模數。如果你需要一個整數的范圍，應使用分割的方法。線性同余發生器的低位是不具有隨機性的。特別的是，它總是從偶數種子產生奇數，反之亦然。所以如果你需要一個隨機的 0 或者 1，不要使用： ~~~ # NOT random! Do not do this! ? r.randn() % 2 ~~~ 因為你肯定得不到隨機數字。反而，你應該使用 r.rand(2)。 ### 生成隨機數 ### 問題你需要生成在一定范圍內的隨機數。 ### 解決方案使用 JavaScript 的 Math.random() 來獲得浮點數，滿足 0<=X<1.0 。使用乘法和 Math.floor 得到在一定范圍內的數字。 ~~~ probability = Math.random() 0.0 <= probability < 1.0 # => true ? ? # 注意百分位數不會達到 100。從 0 到 100 的范圍實際上是 101 的跨度。 ? percentile = Math.floor(Math.random() * 100) 0 <= percentile < 100 # => true ? ? dice = Math.floor(Math.random() * 6) + 1 1 <= dice <= 6 # => true ? ? max = 42 min = -13 range = Math.random() * (max - min) + min -13 <= range < 42 # => true ~~~ ### 討論對于 JavaScript 來說，它更直接更快。需要注意到 JavaScript 的 Math.random() 不能通過發生器生成隨機數種子來得到特定值。詳情可參考[產生可預測的隨機數](http://coffeescript-cookbook.github.io/chapters/math/generating-predictable-random-numbers)。產生一個從 0 到 n（不包括在內）的數，乘以 n。產生一個從 1 到 n（包含在內）的數，乘以 n 然后加上 1。 ### 轉換弧度和度 ### 問題你需要實現弧度和度之間的轉換。 ### 解決方案使用 JavaScript 的 Math.PI 和一個簡單的公式來轉換兩者。 ~~~ # 弧度轉換成度 ? radiansToDegrees = (radians) -> degrees = radians * 180 / Math.PI ? radiansToDegrees(1) # => 57.29577951308232 ? ? # 度轉換成弧度 ? degreesToRadians = (degrees) -> radians = degrees * Math.PI / 180 ? degreesToRadians(1) # => 0.017453292519943295 ~~~ ### 一個隨機整數函數 ### 問題你想要獲得兩個整數（包含在內）之間的一個隨機整數。 ### 解決方案使用以下的函數。 ~~~ randomInt = (lower, upper) -> [lower, upper] = [0, lower] unless upper? # 用一個參數調用 [lower, upper] = [upper, lower] if lower > upper # Lower 必須小于 upper Math.floor(Math.random() * (upper - lower + 1) + lower) # 最后一條語句是一個返回值 ? (randomInt(1) for i in [0...10]) # => [0,1,1,0,0,0,1,1,1,0] ? ? (randomInt(1, 10) for i in [0...10]) # => [7,3,9,1,8,5,4,10,10,8] ~~~ ### 指數對數運算 ### 問題你需要進行包含指數和對數的運算。 ### 解決方案使用 JavaScript 的 Math 對象來提供常用的數學函數。 ~~~ # Math.pow(x, y) 返回 x^y ? Math.pow(2, 4) # => 16 ? ? # Math.exp(x) 返回 E^x ，被簡寫為 Math.pow(Math.E, x) ? Math.exp(2) # => 7.38905609893065 ? ? # Math.log returns the natural (base E) log ? Math.log(5) # => 1.6094379124341003 ? Math.log(Math.exp(42)) # => 42 ? ? # To get a log with some other base n, divide by Math.log(n) ? Math.log(100) / Math.log(10) # => 2 ~~~ ### 討論若想了解關于數學對象的更多信息，請參閱 [Mozilla 開發者網絡](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math)上的文檔。另可參閱[數學常量](http://coffeescript-cookbook.github.io/chapters/math/constants)關于數學對象中各種常量的討論。