2025年2月15日 星期六

砥礪前行

砥礪前行


曾慶潭 Ching-Tang Tseng
ilikeforth@gmail.com
Hamilton, New Zealand
16 February 2025


任何設計好的系統都必須經過長期考驗,執行考驗測試出結果卻是一種磨練,這種工作做起來並不比設計系統來得輕鬆。磨練系統需要範例,範例貴在具有創意,創意還得要有意義,範例才值得採用,有意義、有創意的範例就值得珍惜。自己能設想出來的範例是有限的,從網上尋求一些資源則是必要的,我在網上搜尋範例資源時,有過這些體會。

大家最熟悉的資源莫過於 Rosetta code 網頁: https://rosettacode.org/wiki/Category:Programming_Tasks
這個網頁的好處就在其資料公開的透明度是百分之百,提出來的範例題目毫無隱瞞,附貼出各種程式語言的程式解答也毫無隱瞞。不限制瀏覽、不限制下載、不限制貢獻、不限制引用,全球使用者均能受益,網頁受人尊重,貢獻者也多。

網上還有許多可用資源,這裡介紹另一知名之 Project Euler 網頁:https://projecteuler.net/archives
經過許多年的發展,這個網頁目前(20250216)的範例題目已經累積到將近有 1000 個了。網頁則要求使用者必須登記後才能參與活動,也才能看到題目的程式解答,使用起來有點不便。我大致瀏覽過其範例題目的內容,顯示出不少問題均涉及必須使用具有可程式化大數計算能力的系統才利於獲得答案。因此,能貢獻解答而貼出的範例程式就比較有限了,一般傳統的程式語言不具有大數計算的功能,還要能程式化,那就更不容易見到了。所以,參與活動者的貢獻也就因此而不如 Rosetta code 網頁來得多。當然,相較之下顯示出這個網頁內的範例資源題目比較艱深。

設計 ABC Forth 系統曾經留下的記錄,可以追溯到 1980 年代,剛開始時,主要目標放在為 Forth 系統設計出好用的中算符程式寫法。因為我個人的研究工作,常需要進行可程式化數學計算程式的設計,中算符的程式寫法省時好用,於是愛用 Forth 就愛屋及鳥的研發出 Forth 自我形成的中算符系統,中算符功能是設計出整個系統之構想的起源。

後來的發展則偏重於程式結構語法,BASIC 程式語言表達數學式子的方式方便好用,有利於數學計算方面之程式設計,於是 ABC Forth 的雛型應運而生,有了系統性的結構。由於它是架設於一般 Forth 系統上延伸出性能而成,它的特色就是 BASIC 式的程式可以跟傳統 Forth 程式混用,共享資源後執行出共榮結果。

可程式化的大數計算能力,是後來的發展,因為需要而加裝。加裝的過程中順便發現了設計出可程式化的複數計算能力、或比較罕用的可程式化常規分數計算能力、甚至於其他數系的可程式化計算能力都是類似的設計。原本的大數計算只考慮處理大整數問題,延伸性的研究,則設計出了能處理不限位數大浮點數問題的系統。

這個網頁過去公佈過的實際程式,都附有貼出時間。曾有好幾次在我發展出特殊性能而網貼成果時,網上都還見不到能執行出同樣性能的程式語言系統,網文貼出後,大家互相勉勵、互相砥礪,後來我就看到了別種程式語言性能上的進步。

互相觀摩別種程式語言設計出來的程式,能幫助自己設計 Forth 程式。公開 Forth 程式,當然也能幫助別人使用各自喜歡之程式語言設計程式。這裡刻意挑選了一個 Project Euler 網頁提出的範例『題目 8 』進行一次小小的貢獻。

為了砥礪前行,繼續發展 Forth ,這次,不用 BASIC 式的語法設計程式,純用 Forth 。

題目雖只採用一千位數來考驗程式設計,它卻是個形同『海底撈針』式的問題,舉例不用太誇張而使用海量位數,使用一千位數點到為止就夠了,用來研究問題才能恰到好處。

題目問你一千位數中連乘 4 位數者,那一個位置的數字最大。然後,再問你連乘 13 位數時又是那一個位置的數字最大?

題目從網頁擷圖展示如下,隨後附貼純用 Forth 寫成的程式及其執行後所得的答案。

所採用的系統為 ciForth 5.3.0 ,作業系統為 Ubuntu 20.04 。

鍾情於 Forth 的愛用者可以直接載入程式執行出結果。別種程式語言的愛用者,請勿嫌這個程式的冗長與複雜,它有助於了解求解問題的程式規劃步驟,指令名稱就是說明。

附記 : 由於三月份遠行返台一個月,貼文暫停兩次。四月份再見。

\ euler08.f

: cinumber ( addr -- n )
  0 0  rot dup 1+ c@ [char] . = >r
  $@ r@ if 1 /string then
  >number nip 0 = 
  if d>s r> if negate then 
  else r> drop 2drop 
  then ;

create chr 128 cells allot
create val 128 cells allot
create tmp 2 cells allot

s" 73167176531330624919225119674426574742355349194934" chr $!
s" 96983520312774506326239578318016984801869478851843" chr $+!
s" 85861560789112949495459501737958331952853208805511" chr $+!
s" 12540698747158523863050715693290963295227443043557" chr $+!
s" 66896648950445244523161731856403098711121722383113" chr $+!
s" 62229893423380308135336276614282806444486645238749" chr $+!
s" 30358907296290491560440772390713810515859307960866" chr $+!
s" 70172427121883998797908792274921901699720888093776" chr $+!
s" 65727333001053367881220235421809751254540594752243" chr $+!
s" 52584907711670556013604839586446706324415722155397" chr $+! 
s" 53697817977846174064955149290862569321978468622482" chr $+!
s" 83972241375657056057490261407972968652414535100474" chr $+!
s" 82166370484403199890008895243450658541227588666881" chr $+!
s" 16427171479924442928230863465674813919123162824586" chr $+!
s" 17866458359124566529476545682848912883142607690042" chr $+!
s" 24219022671055626321111109370544217506941658960408" chr $+!
s" 07198403850962455444362981230987879927244284909188" chr $+!
s" 84580156166097919133875499200524063689912560717606" chr $+!
s" 05886116467109405077541002256983155200055935729725" chr $+!
s" 71636269561882670428252483600823257530420752963450" chr $+!

: chr>val ( -- )
  val 128 cells erase
  chr $@ over + swap 
  do 
     tmp 2 cells erase 
     I c@ tmp $c+
     tmp cinumber val $c+
  loop ;

: mult13 ( add -- n )
  dup c@ swap 1+ dup 12 + swap
  do 
     I c@ * 
  loop ;

variable maxaddr
variable maxval

: 1000calculations ( -- )
  0 maxval !
  val $@ over dup maxaddr ! + swap
  do 
    I mult13 dup maxval @ >
    if   I maxaddr ! maxval !
    else drop
    then
  loop 
;

: check ( -- )
  maxaddr @  val $@ drop - 
  chr $@ drop + 13 type
; 

: main
  chr>val
  1000calculations
  cr ." greatest product 0f 13 adjacent digits are  " check 
  cr ." product value =  " maxval @ . ;

\s

Largest product in a series
Problem 8 
The four adjacent digits in the 1000-digit number 
that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number 
that have the greatest product. What is the value of this product?

Ans : 23514624000

greatest product 0f 13 adjacent digits are  5576689664895 <-- from 197 digits
product value =  23514624000  OK