一百個例題 (56 ~ 60)
Ching-Tang Tseng
Hamilton, New Zealand
19 September 2024
FORTH:慶的世界。 本網頁為中華民國(Republic Of China)FORTH語言協會 永久性網頁
2024年9月18日 星期三
第(56)個範例是一個強行使用 Forth 來模擬出一個益智問題的程式。
問題為：一瓶啤酒 2 元，兩個空瓶可以換一瓶啤酒，四個瓶蓋也可以換一瓶啤酒，請問 n 元可以喝到幾瓶啤酒？
這個問題據說是蘋果公司招考員工時的考試題目，我不想考究。網上也有不少人談論這個問題，看了都只覺得那些網貼是話太多、胡扯的多、強辯無益者更多，所以，大可不必去網搜，我也保證此前沒有以 Forth 程式解出此問題之答案的網貼。
問題取材的來源，是臉書上一位武陵中學高我八屆的莊姓學長所提出的問題，這位學長知道我用電腦設計系統，於是轉貼了這則網上買啤酒的熱門話題，問我有何看法？也問我單用程式來解題的話，程式要怎麼寫？我想了一想，就先以解析法給了他一個答案：就說它是一種物質不滅定律的延伸，姑且就叫作價值不滅定律吧。用10元除以啤酒淨值0.5元/瓶，得20瓶，但奇數塊錢不能這樣解析。至於程式解法，我隔天再試寫給他看，於是就寫出了這則範例程式。程式執行的結果，獲得的答案是 15 瓶，不是 20 瓶。我當這件事是個可貴的經驗，於是將程式設計的結果，留作範例而收集。
不要小看這則問題，也不要小看這個程式，程式是典型的模擬設計，直接全程模擬如何按照條件買啤酒，買到最後，就知道能買得幾瓶了，這裡面沒有解析性的投機演算，直接採用暴力算法(brute force algorithm)模擬實際問題。這是有了電腦以後，人類才可以妥善使用電腦計算能力的解題用法：直接進行模擬。
詳細解法的中文說明，範例程式中已經記錄， 此 Forth 程式的特點則在使用 value 定義變常數，而不使用 variable 來宣告出純變數的資料結構。好處是可以少用 fetch(@) 指令，讓程式易於閱讀。 Forth 系統中泛用的可以加存 +to 或 +! 指令，都對解這類問題而設計程式有很大的幫助。注意迴路結束條件，就在模擬到買不下去時，就得終止。我們分析問題、建立模式、設計程式、獲得解答，整個過程，在口語式的問題中並沒有提供，你得有點本事自己想得出來才行。
模擬程式中的運算，主要依賴一個 Forth 中特有的除餘(/MOD)運算指令，它執行兩個輸入數字相除後會在堆疊上留下商數與餘數兩個數字的結果。80 年代，只有 Forth 程式語言採用除法運算後能直接獲得餘數的指令，後來，其他程式語言才跟進使用。
範例程式中使用了 begin ..... until 的迴路結構指令組， until 前面的迴路終止條件，就是再也無法取用空瓶或瓶蓋換出新啤酒來了的狀況。
程式除了模擬這個問題外，還必須能適用於各種狀況：無論啤酒、空瓶、瓶蓋各自的價值如何變化，也無論問題換用多少錢作為起始，程式都要能夠涵蓋所有的狀況才行。
:
問題為：一瓶啤酒 2 元，兩個空瓶可以換一瓶啤酒，四個瓶蓋也可以換一瓶啤酒，請問 n 元可以喝到幾瓶啤酒？
這個問題據說是蘋果公司招考員工時的考試題目，我不想考究。網上也有不少人談論這個問題，看了都只覺得那些網貼是話太多、胡扯的多、強辯無益者更多，所以，大可不必去網搜，我也保證此前沒有以 Forth 程式解出此問題之答案的網貼。
問題取材的來源，是臉書上一位武陵中學高我八屆的莊姓學長所提出的問題，這位學長知道我用電腦設計系統，於是轉貼了這則網上買啤酒的熱門話題，問我有何看法？也問我單用程式來解題的話，程式要怎麼寫？我想了一想，就先以解析法給了他一個答案：就說它是一種物質不滅定律的延伸，姑且就叫作價值不滅定律吧。用10元除以啤酒淨值0.5元/瓶，得20瓶，但奇數塊錢不能這樣解析。至於程式解法，我隔天再試寫給他看，於是就寫出了這則範例程式。程式執行的結果，獲得的答案是 15 瓶，不是 20 瓶。我當這件事是個可貴的經驗，於是將程式設計的結果，留作範例而收集。
不要小看這則問題，也不要小看這個程式，程式是典型的模擬設計，直接全程模擬如何按照條件買啤酒，買到最後，就知道能買得幾瓶了，這裡面沒有解析性的投機演算，直接採用暴力算法(brute force algorithm)模擬實際問題。這是有了電腦以後，人類才可以妥善使用電腦計算能力的解題用法：直接進行模擬。
詳細解法的中文說明，範例程式中已經記錄， 此 Forth 程式的特點則在使用 value 定義變常數，而不使用 variable 來宣告出純變數的資料結構。好處是可以少用 fetch(@) 指令，讓程式易於閱讀。 Forth 系統中泛用的可以加存 +to 或 +! 指令，都對解這類問題而設計程式有很大的幫助。注意迴路結束條件，就在模擬到買不下去時，就得終止。我們分析問題、建立模式、設計程式、獲得解答，整個過程，在口語式的問題中並沒有提供，你得有點本事自己想得出來才行。
模擬程式中的運算，主要依賴一個 Forth 中特有的除餘(/MOD)運算指令，它執行兩個輸入數字相除後會在堆疊上留下商數與餘數兩個數字的結果。80 年代，只有 Forth 程式語言採用除法運算後能直接獲得餘數的指令，後來，其他程式語言才跟進使用。
範例程式中使用了 begin ..... until 的迴路結構指令組， until 前面的迴路終止條件，就是再也無法取用空瓶或瓶蓋換出新啤酒來了的狀況。
程式除了模擬這個問題外，還必須能適用於各種狀況：無論啤酒、空瓶、瓶蓋各自的價值如何變化，也無論問題換用多少錢作為起始，程式都要能夠涵蓋所有的狀況才行。
:
\ (56)Beers.f \ 一瓶啤酒 2 元，兩個空瓶可以換一瓶啤酒，四個瓶蓋可以換一瓶啤酒。 \ 請問 n 元可以喝到幾瓶啤酒？ \ t : 可得啤酒總數 \ r : 循環回收次數 \ a : 暫態計算結果 \ b : 空瓶數 \ c : 瓶蓋數 5 values t r a b c \ 只對偶數的起始費用有效，奇數元必須先扣除1元 : Init ( n -- ) 0 to r 2 /mod dup dup to t to b to c if cr ." 1 dollar redundant." then ; : Recycle ( -- ) 0 to a b 2 /mod +to a to b c 4 /mod +to a to c a +to t a +to b a +to c ; : main ( n -- ) Init begin 1 +to r Recycle a 0= until cr ." Total = " t . cr ." 回收次數 = " r . cr ." 剩餘空瓶數 = " b . cr ." 剩餘瓶蓋數 = " c . ; \ 經過分析可得下列結論 \ 啤酒的純脆價值為每瓶0.5元，每個空瓶為1元，每個瓶蓋為0.5元。 \ 因此，若以 n 元購此啤酒，兌換到最後，必定只剩 1 個空瓶，3 個瓶蓋。 \ 以此結論，各樣東西的價值不會無中生有，也不會無中消失，故 \ ( n - 1 - ( 3 * 0.5 ) ) / 0.5 便為可獲得之所有啤酒瓶數的等效金錢。 \ 但此式只對偶數的起始金錢有效，奇數金錢，一開始就必須結餘1元，不列入計算。 \ 例如：花 23元，可獲得 ((23-1)-2.5) / 0.5 = 39 (瓶) \S 10 main Total = 15 回收次數 = 6 剩餘空瓶數 = 1 剩餘瓶蓋數 = 3 ok 23 main 1 dollar redundant. Total = 39 回收次數 = 9 剩餘空瓶數 = 1 剩餘瓶蓋數 = 3 ok 57 main 1 dollar redundant. Total = 107 計回收次數 = 13 剩餘空瓶數 = 1 剩餘瓶蓋數 = 3 ok 100 main Total = 195 回收次數 = 15 剩餘空瓶數 = 1 剩餘瓶蓋數 = 3 ok
第(57)個範例是個解不等式問題的典型範例。
此範例的收集，與我在 20170301 個人網頁貼出的 ”Daily using in ABC Forth” 文章有關，那篇文章用來向全世界推介我設計的系統，所以全用英文。文章內題目的來源，都是從一個叫做 Brilliant.org 的網頁內取得的網貼內容。該文貼出時，一口氣展示了 13 個題目的程式解法，內容已經非常多了，不宜再添加，所以這一題沒有補進該文，我將其收集進百例此處，以供永久留參。
還有一個特別的因素，我才沒有將此範例補貼於上述該文。那篇文章內所有的程式解法，我都採用 BASIC 式的語法設計程式，如果是使用純 Forth 語法設計出來的程式，我就不補進該文，改為自己收集。
從上述的差異說明，大家可以仔細比對，看看用 BASIC 語法或用 Forth 語法設計解數學問題的程式時有什麼不同？這個範例只需用到一個非常簡單的邏輯判斷來取得結果，連一個變數的資料結構都不需要先行宣告出來，就能完成任務了。
可是算式的寫法：
( n^2 - 2 ) ( n^2 - 20 ) < 0
就相當傷腦筋了，我自己若要回查，不看這一列說明，也得花不少時間才能重新從程式倒寫得出這個不等式來。
這一個例題是使用純脆的 Forth 語法寫成的。您能自己改用我給的 BASIC 語法方式另外寫出解這個問題的程式嗎？寫成之後，可以比較一下，就能感覺出它們的不同處到底在那裡了。
我完成系統設計後，長期絞盡腦汁設想過許多問題來考驗系統。沒有網路的時代，只能靠讀書來找問題，有了網路之後，方便多了，但早期可用網頁的資料，還是非常欠缺，需要時間來累積。我在步向這條路途的過程中，也見過許多網頁起起伏伏的興衰，許多網頁早就從網上徹底消失了。目前，雖仍還有不少網頁仍能參考，但總覺得他們都缺乏系統性的規劃，能用材料都屬於點到為止的東西，不是可以猛下功夫去全面追隨，然後重新實現於 ABC Forth 的理想對象。
我接觸過的 Brilliant.org 例題，大該是最平易近人題目的來源。類似 Rosetta code 的網頁例題，則是比較通俗性的題目來源，類似的網頁也有很多個，有偏重于生物學方面的範例網頁，也有偏重于天文學方面的範例網頁，我都大量造訪過，然後取材來磨練自己。題目比較高深難解的網頁，則是專論理論數學方面的網頁，例如 Euler’s 問題網頁，我也曾一口氣下載了幾十個問題一一解出答案，但因這個網頁要加入該組織、登錄個人資料後才能自由出入，我不想惹事，就放棄了，沒去參與。百例的取材大部份是這樣形成的。
事實上，我並不鍾情於以上述資源來設計程式，取得成果，它們都屬於只是為了向大家舉例，才不得不為之的事情。
我個人真正的喜好，是從優質論文中取得的資源。已經寫過不少了，也還有不少題目尚未實現，題目都很大，技術也不容易全面仔細學得通，但值得做。
我個人真正的願望，是找幾項專業工程，精細的實現整套的應用實務。例如：設計出全套的機械工程套裝程式，或是完成整套的數值分析實用庫存程式。
回顧這個範例，令我想到 Forth 的未來，確實是越來越難再走下去。介紹百例能有效果的大前題，是大家應該都已熟知了 Forth 基本指令與程式語法了才行。可是，我自知，這已是苛求了，將來會更難。所以，推介也好、喜好也好、願望也好，都不要期待太高，永久這樣使用 Forth ，是為自己而用它一輩子。
:
此範例的收集，與我在 20170301 個人網頁貼出的 ”Daily using in ABC Forth” 文章有關，那篇文章用來向全世界推介我設計的系統，所以全用英文。文章內題目的來源，都是從一個叫做 Brilliant.org 的網頁內取得的網貼內容。該文貼出時，一口氣展示了 13 個題目的程式解法，內容已經非常多了，不宜再添加，所以這一題沒有補進該文，我將其收集進百例此處，以供永久留參。
還有一個特別的因素，我才沒有將此範例補貼於上述該文。那篇文章內所有的程式解法，我都採用 BASIC 式的語法設計程式，如果是使用純 Forth 語法設計出來的程式，我就不補進該文，改為自己收集。
從上述的差異說明，大家可以仔細比對，看看用 BASIC 語法或用 Forth 語法設計解數學問題的程式時有什麼不同？這個範例只需用到一個非常簡單的邏輯判斷來取得結果，連一個變數的資料結構都不需要先行宣告出來，就能完成任務了。
可是算式的寫法：
( n^2 - 2 ) ( n^2 - 20 ) < 0
就相當傷腦筋了，我自己若要回查，不看這一列說明，也得花不少時間才能重新從程式倒寫得出這個不等式來。
這一個例題是使用純脆的 Forth 語法寫成的。您能自己改用我給的 BASIC 語法方式另外寫出解這個問題的程式嗎？寫成之後，可以比較一下，就能感覺出它們的不同處到底在那裡了。
我完成系統設計後，長期絞盡腦汁設想過許多問題來考驗系統。沒有網路的時代，只能靠讀書來找問題，有了網路之後，方便多了，但早期可用網頁的資料，還是非常欠缺，需要時間來累積。我在步向這條路途的過程中，也見過許多網頁起起伏伏的興衰，許多網頁早就從網上徹底消失了。目前，雖仍還有不少網頁仍能參考，但總覺得他們都缺乏系統性的規劃，能用材料都屬於點到為止的東西，不是可以猛下功夫去全面追隨，然後重新實現於 ABC Forth 的理想對象。
我接觸過的 Brilliant.org 例題，大該是最平易近人題目的來源。類似 Rosetta code 的網頁例題，則是比較通俗性的題目來源，類似的網頁也有很多個，有偏重于生物學方面的範例網頁，也有偏重于天文學方面的範例網頁，我都大量造訪過，然後取材來磨練自己。題目比較高深難解的網頁，則是專論理論數學方面的網頁，例如 Euler’s 問題網頁，我也曾一口氣下載了幾十個問題一一解出答案，但因這個網頁要加入該組織、登錄個人資料後才能自由出入，我不想惹事，就放棄了，沒去參與。百例的取材大部份是這樣形成的。
事實上，我並不鍾情於以上述資源來設計程式，取得成果，它們都屬於只是為了向大家舉例，才不得不為之的事情。
我個人真正的喜好，是從優質論文中取得的資源。已經寫過不少了，也還有不少題目尚未實現，題目都很大，技術也不容易全面仔細學得通，但值得做。
我個人真正的願望，是找幾項專業工程，精細的實現整套的應用實務。例如：設計出全套的機械工程套裝程式，或是完成整套的數值分析實用庫存程式。
回顧這個範例，令我想到 Forth 的未來，確實是越來越難再走下去。介紹百例能有效果的大前題，是大家應該都已熟知了 Forth 基本指令與程式語法了才行。可是，我自知，這已是苛求了，將來會更難。所以，推介也好、喜好也好、願望也好，都不要期待太高，永久這樣使用 Forth ，是為自己而用它一輩子。
:
\ LessThan.f \ How many integers n satisfy this inequality? \ ( n^2 - 2 ) ( n^2 - 20 ) < 0 \ Can you find them all? \ use FORTH code solve it as following: : main ( n -- ) dup dup * dup >r 2 - r> 20 - * 0 < if cr . else drop then ; : TellMe ( to from -- ) do I main loop ; \S \ Usage: 100 -100 TellMe -4 -3 -2 2 3 4 ok
第(58)個範例是用來檢討暫態數據可以被放置在系統內何處的問題。
只有 Forth 程式語言允許使用者能夠看透整個系統，也允許使用者能夠更動系統的內容。當然，後果得自行負責。
不能達到上述目的的 Forth 系統，我是一概不用，因為我必須在 Forth 系統上建立自己的延伸性附屬系統，能夠擁有上述功能者，我才願意使用這樣的 Forth 系統。 AIM65 Forth, Micromotion Forth-79, F83, eForth, FPC-Forth, Win32Forth, ciForth ..... 等等，都是符合上述規格的系統，所以我用。其他的系統，我若願意討論，都只是輕描淡寫地玩一玩就算了，絕不浪費時間去深入探討或使用。
能把 Forth 系統玩通，有兩件事情必須掌握，一個就是指令結構，另一個就是規劃出來的系統記憶體圖譜。目前市面上販售的 Forth 系統與歐洲推行的系統，都不鼓勵使用者這樣子用系統，如： Swift Forth, MVP Forth, iForth, gForth ..... 等都是。這些系統我都用過，但不公開討論，也不鼓勵任何人去用，因為系統不透通，用了就等於被害、被綁死，沒有發展的價值。其他許多上不了檯面的殘障 Forth ，我就不提了，連碰也懶得碰，碰了就是浪費時間。
為什麼先批評一段 Forth 的各種系統再談今天的範例？因為這個範例牽扯到系統的概念，必須先搞懂系統結構才行。
我在長期使用 Forth 之後，知道使用者經常會有暫態數據必須處理的問題。於是，就會問自己，如果不宣告出變數來用時，數據可以擺在那裡？又因 Forth 程式語言強調使用堆疊來運轉系統，堆疊上數據的擺放秩序，嚴重影響執行需求，設計程式時，經常就得把堆疊上的數據進行翻來覆去的處理，被處理的數據就是暫態數據，不找個地方暫時放著，就難以翻來覆去的搞出正常的秩序。還有，每當我見到 Forth 指令或變數的頭部長得這麼龐大、耗掉這麼多記憶體時，我就會想用經濟可靠的記憶體使用方式處理暫態數據，而不想規規矩矩的使用宣告出變數名稱的方法來儲存暫態數據了。
關於儲存暫態數據的技術，有很多可行辦法，方法不是只有這一種，這個範例只是其中比較通用的一種，也是比較傳統的使用方法。我在程式說明中介紹了一個可以存放於三處的使用範例，並且只拿處理堆疊上數據放置秩序當例題，展示現象，都能得到正確的結果。然後，我強調了直接設計出沒有儲存上限的浮動陣列式使用方法解決問題，給了一個通用性的 [PAD] 陣列結構，能被萬用。我後來再設計系統、加添許多固定功能時， [PAD] 被永久固定在我的系統中了，只是名稱可能有點不同，每個陣列單元記憶體的控留量，也會因環境的不同而有點差異，如此而已。
使用本範例中的記憶體位置來儲存暫態數據時，必須注意一項要點，由於儲存位置都是浮動的，因此，只宜在系統沒有編譯新的程式進入系統時使用，系統編譯納入新指令時，這些儲存位置所依賴的 HERE , PAD 指標，都會跟著浮動變化掉。而回返堆疊指標，也必須在編譯完一個指令後歸原，所以程式中的暫態數據，只能臨時放一放，編譯完成前，回返堆疊的指標必須恢復正常。
我設計過許多儲存暫態數據的不同程式，這是個龐大的題目，沒有碰到實際程式時，我們就不討論，碰上一種就談一種。如果您也想自行設計系統，各種技巧就都得深入探討。而且，這類技術也算是保護技術的一種方式，當別人不知道暫態數據被放在何處時，程式就難以追蹤，想要搞反編譯來破解系統時，就會遭遇到重大的阻礙。
:
只有 Forth 程式語言允許使用者能夠看透整個系統，也允許使用者能夠更動系統的內容。當然，後果得自行負責。
不能達到上述目的的 Forth 系統，我是一概不用，因為我必須在 Forth 系統上建立自己的延伸性附屬系統，能夠擁有上述功能者，我才願意使用這樣的 Forth 系統。 AIM65 Forth, Micromotion Forth-79, F83, eForth, FPC-Forth, Win32Forth, ciForth ..... 等等，都是符合上述規格的系統，所以我用。其他的系統，我若願意討論，都只是輕描淡寫地玩一玩就算了，絕不浪費時間去深入探討或使用。
能把 Forth 系統玩通，有兩件事情必須掌握，一個就是指令結構，另一個就是規劃出來的系統記憶體圖譜。目前市面上販售的 Forth 系統與歐洲推行的系統，都不鼓勵使用者這樣子用系統，如： Swift Forth, MVP Forth, iForth, gForth ..... 等都是。這些系統我都用過，但不公開討論，也不鼓勵任何人去用，因為系統不透通，用了就等於被害、被綁死，沒有發展的價值。其他許多上不了檯面的殘障 Forth ，我就不提了，連碰也懶得碰，碰了就是浪費時間。
為什麼先批評一段 Forth 的各種系統再談今天的範例？因為這個範例牽扯到系統的概念，必須先搞懂系統結構才行。
我在長期使用 Forth 之後，知道使用者經常會有暫態數據必須處理的問題。於是，就會問自己，如果不宣告出變數來用時，數據可以擺在那裡？又因 Forth 程式語言強調使用堆疊來運轉系統，堆疊上數據的擺放秩序，嚴重影響執行需求，設計程式時，經常就得把堆疊上的數據進行翻來覆去的處理，被處理的數據就是暫態數據，不找個地方暫時放著，就難以翻來覆去的搞出正常的秩序。還有，每當我見到 Forth 指令或變數的頭部長得這麼龐大、耗掉這麼多記憶體時，我就會想用經濟可靠的記憶體使用方式處理暫態數據，而不想規規矩矩的使用宣告出變數名稱的方法來儲存暫態數據了。
關於儲存暫態數據的技術，有很多可行辦法，方法不是只有這一種，這個範例只是其中比較通用的一種，也是比較傳統的使用方法。我在程式說明中介紹了一個可以存放於三處的使用範例，並且只拿處理堆疊上數據放置秩序當例題，展示現象，都能得到正確的結果。然後，我強調了直接設計出沒有儲存上限的浮動陣列式使用方法解決問題，給了一個通用性的 [PAD] 陣列結構，能被萬用。我後來再設計系統、加添許多固定功能時， [PAD] 被永久固定在我的系統中了，只是名稱可能有點不同，每個陣列單元記憶體的控留量，也會因環境的不同而有點差異，如此而已。
使用本範例中的記憶體位置來儲存暫態數據時，必須注意一項要點，由於儲存位置都是浮動的，因此，只宜在系統沒有編譯新的程式進入系統時使用，系統編譯納入新指令時，這些儲存位置所依賴的 HERE , PAD 指標，都會跟著浮動變化掉。而回返堆疊指標，也必須在編譯完一個指令後歸原，所以程式中的暫態數據，只能臨時放一放，編譯完成前，回返堆疊的指標必須恢復正常。
我設計過許多儲存暫態數據的不同程式，這是個龐大的題目，沒有碰到實際程式時，我們就不討論，碰上一種就談一種。如果您也想自行設計系統，各種技巧就都得深入探討。而且，這類技術也算是保護技術的一種方式，當別人不知道暫態數據被放在何處時，程式就難以追蹤，想要搞反編譯來破解系統時，就會遭遇到重大的阻礙。
:
\ (58)PadHere.f \ 20151201 \ 利用 PAD, HERE, Return Stack存放變數的技巧 \ 只適用於 4 個數字時使用 : test ( 1 2 3 4 -- 4 3 2 1 ) here ! pad ! swap >r >r here @ pad @ r> r> ; \ 均適用於整數、實數、複數，故一個單元就取 4 個 cells \ : [PAD] ( n -- addr ) \ 4 * cells pad + ; \ 比較理想的設計為包括也考慮 bytes/float = 10 的情況 \ 如果記憶體用量根本不是問題時，每一 單元乾脆就取 80 Bytes.字串也能使用 : [PAD] ( n -- addr ) 80 * PAD aligned + ; : [PAD]N.S ( from to -- ) CR 1+ SWAP DO I [PAD] @ . LOOP ; : [PAD]F.S ( from to -- ) CR 1+ SWAP DO I [PAD] F@ FS. LOOP ; : [PAD]Z.S ( from to -- ) CR 1+ SWAP DO I [PAD] Z@ Z. LOOP ; : ntest ( 1 2 3 4 -- 4 3 2 1 ) CR .S 1 [pad] ! 2 [pad] ! 3 [pad] ! 4 [pad] ! 1 4 [PAD]N.S 1 [pad] @ 2 [pad] @ 3 [pad] @ 4 [pad] @ CR .S ABORT ; : ftest ( f: 1e 2e 3e 4e -- 4e 3e 2e 1e ) CR F.S 1 [pad] f! 2 [pad] f! 3 [pad] f! 4 [pad] f! 1 4 [PAD]F.S 1 [pad] f@ 2 [pad] f@ 3 [pad] f@ 4 [pad] f@ CR F.S ; \ Usage: \ 1 2 3 4 ntest \ 1e 2e 3e 4e ftest
第(59)個範例也是展示 Brilliant.org 網頁問題的程式，採用暴力算法時，介紹另種用法，若另掺入分析技巧，便能將程式擴展應用至非常大數字之問題去了。
問題為： n^n 級數所有方次加起來後的總和之最後一位數到底是多少？
運算後溢量(overflow)的問題，永遠都是個困擾電腦計算技術的問題，尤其是在利用電腦執行暴力算法時更甚，使用於 32 位元環境時，大約是十億左右， 64 位元環境，雖能處理得更大，大到十八位數。實際上，對研究大數問題而言，容量仍是相當有限。這個範例中的程式，就在展示能表現數字位數受限時的影響。我故意不強調我的系統能算大數，才能讓溢量問題凸顯出來。範例程式後面，列有執行結果，小心比對最後計算出來的大數字，就能明白系統在方次多大時，顯示出來的結果是溢量數字了。
問題的主要精神，也是在強調應該分析問題後才解題目， 10 的 10 次方，就是十億了，使用暴力算法硬解此題，顯然是會弄爆可用整數上限的，改換 64 位元來處理，也不過是只能夠提高幾位數而已，我展示了算到 15 次方還不會有問題。這些展示，只是提醒自己，要注意數字處理上限，真正的解題技巧，不能完全只用暴力，採用分析，就能減輕負擔。因為問題只問您 n^n 級數所有方次加起來後的總和之最後一位數到底是多少？
只問最後一位數，我們就可以回頭考慮方次與加法的運算，不管您怎麼算，最後一位數是可以完全納入掌握的數字，於是，我們就能設計自己的程式，單純的只專注於最後一位數，可被留供後續演算，便能解決方次很大時溢量的問題。
demo1 與 demo2 兩套暴力算法，都只能處理到 11 次方。我不以可解決小方次問題時的能力為滿足，所以擴充設計， test 便能讓您使用到非常大的方次，因為每次算完都只留最後一位數，問題便能迎刃而解。
分析後才設計程式的處理要點，都以註解說明的方式寫在程式後面了，本文不再說明。
我在分析問題時，另外想知道最後一位數是不是也有限制規格？於是，又設計了一個 main 指令，測試的結果，顯示這個所謂的最後一位數，從 0 到 9 都有可能。所以，分析問題時，也不必再從這方面找規則來簡化程式了。電腦、系統、思考、樂趣都是不花錢的組合，多寫幾個程式滿足自己的認知，不亦樂乎？
:
問題為： n^n 級數所有方次加起來後的總和之最後一位數到底是多少？
運算後溢量(overflow)的問題，永遠都是個困擾電腦計算技術的問題，尤其是在利用電腦執行暴力算法時更甚，使用於 32 位元環境時，大約是十億左右， 64 位元環境，雖能處理得更大，大到十八位數。實際上，對研究大數問題而言，容量仍是相當有限。這個範例中的程式，就在展示能表現數字位數受限時的影響。我故意不強調我的系統能算大數，才能讓溢量問題凸顯出來。範例程式後面，列有執行結果，小心比對最後計算出來的大數字，就能明白系統在方次多大時，顯示出來的結果是溢量數字了。
問題的主要精神，也是在強調應該分析問題後才解題目， 10 的 10 次方，就是十億了，使用暴力算法硬解此題，顯然是會弄爆可用整數上限的，改換 64 位元來處理，也不過是只能夠提高幾位數而已，我展示了算到 15 次方還不會有問題。這些展示，只是提醒自己，要注意數字處理上限，真正的解題技巧，不能完全只用暴力，採用分析，就能減輕負擔。因為問題只問您 n^n 級數所有方次加起來後的總和之最後一位數到底是多少？
只問最後一位數，我們就可以回頭考慮方次與加法的運算，不管您怎麼算，最後一位數是可以完全納入掌握的數字，於是，我們就能設計自己的程式，單純的只專注於最後一位數，可被留供後續演算，便能解決方次很大時溢量的問題。
demo1 與 demo2 兩套暴力算法，都只能處理到 11 次方。我不以可解決小方次問題時的能力為滿足，所以擴充設計， test 便能讓您使用到非常大的方次，因為每次算完都只留最後一位數，問題便能迎刃而解。
分析後才設計程式的處理要點，都以註解說明的方式寫在程式後面了，本文不再說明。
我在分析問題時，另外想知道最後一位數是不是也有限制規格？於是，又設計了一個 main 指令，測試的結果，顯示這個所謂的最後一位數，從 0 到 9 都有可能。所以，分析問題時，也不必再從這方面找規則來簡化程式了。電腦、系統、思考、樂趣都是不花錢的組合，多寫幾個程式滿足自己的認知，不亦樂乎？
:
\ (59)LastDigit.f
((
https://brilliant.org/practice/level-2-3-operations/
What is the last digit of this sum?
Find the last digit when
1^1 + 2^2 + 3^3 + .... + 9^9 + 10^10
is written out as an integer.
))
6 integers i j k l p s
: demo1 ( n -- ) \ maximum less than 11
[[ j ]] !
basic
10 let k = 0
20 for i = 1 to j
30 print " " ; i ; " ^ " ; i ; " = " , i ^ i
40 let k = k + i ^ i
50 next i
60 print " Sum( " ; j ; " ) = " , k
70 end
;
: demo2 ( n -- ) \ maximum less than 11
[[ j ]] !
basic
10 for k = 1 to j
20 let s = 1
30 for i = 1 to k
40 let s = s * k
50 next i
60 print s
70 next k
80 end
;
: test ( n -- ) \ maximum can up to very huge
[[ j ]] ! \ 最高方次為 j (highest power is j)
basic
10 let s = 0
20 for k = 1 to j \ k 表從 1 開始，做到最高方次 j (k terms)
30 let l = 1
40 for i = 1 to k
50 let l = ( l * k ) mod 10 \ 每自乘一次均只留單個尾數 l (last digit)
60 next i
80 let s = s + l \ s 為所有尾數之和 (summation of last digits)
90 next k
100 let s = s mod 10 \ 取得尾數總和之最後一位尾數
110 run s .
120 end
;
: main ( -- )
basic
10 for p = 0 to 20 \ 算出最高方次 p(power) 為從 0 到 100 的所有結果
20 print " Last power = " ; p ; " last digit is "
30 run p test
40 next p
50 end ;
\ page main
\ 執行 main 後，結果顯示，0 到 9 都有可能。
\S
ok
10 demo1
1 ^ 1 = 1
2 ^ 2 = 4
3 ^ 3 = 27
4 ^ 4 = 256
5 ^ 5 = 3125
6 ^ 6 = 46656
7 ^ 7 = 823543
8 ^ 8 = 16777216
9 ^ 9 = 387420489
10 ^ 10 = 1410065408 ----> overflow
Sum( 10 ) = 1815136725 ok
ching@ching-H81M-S2H:~$ cd lina64
ching@ching-H81M-S2H:~/lina64$ ./f5082
AMDX86 ciforth 5.2.1
include lastdigit.f
I : ISN'T UNIQUE
J : ISN'T UNIQUE
OK
15 demo1
1
4
27
256
3125
46656
823543
16777216
387420489
10000000000
285311670611
8916100448256
302875106592253
11112006825558016
437893890380859375 OK
第(60)個範例是一個我個人發展系統程式時的工具，用來觀察整數及其平方後的二進制數值位元花樣。
我花過幾千塊錢台幣，買過 NC4000 Forth CPU 發展套件，後來從未用過，只是為了支持當時的 Forth 發展而買，因為台灣的易符公司下了很大的資本，每個月透過丁陳老師給 Charles Moore 五千美金，拖了好幾年，才得以有這個第一套 Forth CPU 面世，並在台灣出售，當然，隨套件附贈的文件有一大堆，我沒發展，所以也沒細看。
聽過丁陳老師講過，Forth CPU 內的開平方，是一個 CPU 的工作時脈就能完成工作的現成指令，我看不到，也沒摸成過，只把此事記在心中。
我學過數位電路，對數位運算的邏輯電路有點概念，聽丁陳老師說過，那個開平方指令，是用平移電路完成的，在 CPU 內部的震盪時脈，可以是 CPU 外在工作時脈的幾十或幾百倍，因此，善用移位電路，就能讓 CPU 以一個工作時脈執行出開平方指令。
2016 年 3 月，我從網上訊息，看到 Intel 公司公告過，新造的 CPU 改善了 division 與 sqrt 指令的執行速度，但 sqrt 指令作用於不同的暫存器時，也還仍然需要 4.5c 至 7.5c 的耗用時脈，實際運作時的潛伏期(latency)時脈，更長，從 13.1c 到 18.1c 左右。顯然，一般再好的 CPU ，也沒辦法僅耗單一個時脈，執行出開平方指令。
談這些硬體細節，可能太深奧了，也不是我這種人能接觸得了的東西，所以我僅拿一點關於硬體搞開平方的事情起頭，告訴大家為什麼我要自己設計這個範例，用來作為了解以右移(rshift)指令設計開平方程式的研究工具。
前曾述及，我長期收集過各種開平方的程式，也深入探討過這個問題，並且實際測量過各種方法的真實速度，最後，才將結論固定於自己設計的系統中。
我的系統中，隨著環境的不同，也都各有不同之整數開平方的執行辦法，不是固定的只用一套，有的時候，我只考慮自己的需要，不求速度最高，把值得留下來的技術保留在我自己設計的系統中，永久留參。
因此，以 rshift 達到開平方目的所設計程式，也仍留在我後來開發的新系統中。以軟體 rshift 模擬而成的結果，當然沒有以真正做 rshift 的硬體速度快，但速度快不是我搞研發的目的，就算我一輩子也沒機會接觸能罩刻出開平方所需元件的硬體單晶生產圖檔，只要能搞懂它的道理，不能接觸又有什麼關係？
這個範例，是為了滿足我個人求知慾望時所設計的工具，能用在模擬軟體被執行時，看到真正位元花樣的變遷狀態。我只能告訴大家， Forth 在研究軟硬體介面的過程中，確實是個好東西，這麼簡單的程式，就能看清數位訊息的存儲花樣，我用過它。
若要簡談開平方的道理，我可以講一套最簡單的暴力算法得到解答，事實上也真能這樣得到答案，就是不管怎樣，就從 1 開始自乘，當結果比所給值大時，前一個整數就是開平方的所得，只用乘法與比較邏輯。
所以，設計出開平方的程式，不是難題。程式精簡，算得快，功能必須覆蓋整個定義域，算得正確，才是要求重點。
想要純用硬體實現一個工作時脈就能執行出開平方的指令，得先搞出可以模擬硬體的軟體，然後去燒 FPGA 試一試。最後，才花錢向台積電買罩刻晶體的圖檔，生產您心目中的 CPU 。這事，我一輩子都幹不了，只能滿足自己的好奇心，以軟體模擬技術測試性能，這個範例就是研究過程中用到的工具。
:
我花過幾千塊錢台幣，買過 NC4000 Forth CPU 發展套件，後來從未用過，只是為了支持當時的 Forth 發展而買，因為台灣的易符公司下了很大的資本，每個月透過丁陳老師給 Charles Moore 五千美金，拖了好幾年，才得以有這個第一套 Forth CPU 面世，並在台灣出售，當然，隨套件附贈的文件有一大堆，我沒發展，所以也沒細看。
聽過丁陳老師講過，Forth CPU 內的開平方，是一個 CPU 的工作時脈就能完成工作的現成指令，我看不到，也沒摸成過，只把此事記在心中。
我學過數位電路，對數位運算的邏輯電路有點概念，聽丁陳老師說過，那個開平方指令，是用平移電路完成的，在 CPU 內部的震盪時脈，可以是 CPU 外在工作時脈的幾十或幾百倍，因此，善用移位電路，就能讓 CPU 以一個工作時脈執行出開平方指令。
2016 年 3 月，我從網上訊息，看到 Intel 公司公告過，新造的 CPU 改善了 division 與 sqrt 指令的執行速度，但 sqrt 指令作用於不同的暫存器時，也還仍然需要 4.5c 至 7.5c 的耗用時脈，實際運作時的潛伏期(latency)時脈，更長，從 13.1c 到 18.1c 左右。顯然，一般再好的 CPU ，也沒辦法僅耗單一個時脈，執行出開平方指令。
談這些硬體細節，可能太深奧了，也不是我這種人能接觸得了的東西，所以我僅拿一點關於硬體搞開平方的事情起頭，告訴大家為什麼我要自己設計這個範例，用來作為了解以右移(rshift)指令設計開平方程式的研究工具。
前曾述及，我長期收集過各種開平方的程式，也深入探討過這個問題，並且實際測量過各種方法的真實速度，最後，才將結論固定於自己設計的系統中。
我的系統中，隨著環境的不同，也都各有不同之整數開平方的執行辦法，不是固定的只用一套，有的時候，我只考慮自己的需要，不求速度最高，把值得留下來的技術保留在我自己設計的系統中，永久留參。
因此，以 rshift 達到開平方目的所設計程式，也仍留在我後來開發的新系統中。以軟體 rshift 模擬而成的結果，當然沒有以真正做 rshift 的硬體速度快，但速度快不是我搞研發的目的，就算我一輩子也沒機會接觸能罩刻出開平方所需元件的硬體單晶生產圖檔，只要能搞懂它的道理，不能接觸又有什麼關係？
這個範例，是為了滿足我個人求知慾望時所設計的工具，能用在模擬軟體被執行時，看到真正位元花樣的變遷狀態。我只能告訴大家， Forth 在研究軟硬體介面的過程中，確實是個好東西，這麼簡單的程式，就能看清數位訊息的存儲花樣，我用過它。
若要簡談開平方的道理，我可以講一套最簡單的暴力算法得到解答，事實上也真能這樣得到答案，就是不管怎樣，就從 1 開始自乘，當結果比所給值大時，前一個整數就是開平方的所得，只用乘法與比較邏輯。
所以，設計出開平方的程式，不是難題。程式精簡，算得快，功能必須覆蓋整個定義域，算得正確，才是要求重點。
想要純用硬體實現一個工作時脈就能執行出開平方的指令，得先搞出可以模擬硬體的軟體，然後去燒 FPGA 試一試。最後，才花錢向台積電買罩刻晶體的圖檔，生產您心目中的 CPU 。這事，我一輩子都幹不了，只能滿足自己的好奇心，以軟體模擬技術測試性能，這個範例就是研究過程中用到的工具。
:
\ (60)SquarBitServey.f : test ( n -- ) dup dup * >r >r cr decimal r@ 10 .r binary r> 20 .r cr decimal r@ 10 .r binary r> 20 .r decimal ; : main ( -- ) page 11 0 do cr i test cr loop ;
訂閱：
張貼留言 (Atom)
沒有留言:
張貼留言