BASIC 叫用 BASIC

BASIC 叫用 BASIC

Ching-Tang Tseng

Hamilton, New Zealand

16 December 2018

ilikeforth@gmail.com

http://forthfornight.blogspot.com

先貼示程式再進行解說:

8 integers D N L I S T P count

: test          

basic

10 let p = 0

20 let N = T

30 let D = N mod 2

40 if D = 0 then 220

50 let D = N mod 3

60 if D = 0 then 220

70 let L = sqrt ( N ) + 1

80 for I = 6 to L step 6

90 let D = N mod ( I - 1 )

100 if D = 0 then 210

110 let D = N mod ( I + 1 )

120 if D = 0 then 210

130 next I

140 let P = 1

150 goto 300

210 run 2drop

220 let P = 0

300 end

;

\ testing is started from 8, jump over 2, 3, 5, 7.

: main

basic

10 print " Input a specified number S = "

20 inputi S

30 let count = 4

40 let T = 8

130 run test

140 if P = 1 then 160

150 goto 180

160 let count = count + 1

170 if count = S then 210

180 let T = T + 1

190 goto -130

210 print N

220 end

;

main

Input a specified number S =

? 6

                  13  OK

main

Input a specified number S =

? 101

                 547  OK

main

Input a specified number S =

? 1001

                7927  OK

main

Input a specified number S =

? 10001

              104743  OK

main

Input a specified number S =

? 100001

             1299721  OK

main

Input a specified number S =

? 1000001

            15485867  OK

此前，本網頁經常貼示的展示程式，大部份都是只須單一個 BASIC 型式的程式就能完成的成果‧

這一次，換個方式，使用一個 BASIC 型式的程式 ，直接叫用另個 BASIC 型式的程式，展示求解問題的方法‧

問題很簡單: 第幾個質數是多少?

舉例而言，質數的序列是這樣的: 2, 3, 5, 7, 11, 13, 17, 19…等等,.

我們稱第5個質數是11，那麼，第一百萬零一個質數，應該是多少?

這種問題，不用費腦筋去想了，非用程式來解不可，上列展示就是我寫的程式‧

質數問題在電腦程式界出現時，通常都以不要錢的方式，當作公益軟體，提供大家使用與參考‧我也不例外，它不能用來賺錢，卻對世人有益‧

拿質數來問問題，也變化多端，列出所有的質數可以當問題，列出一段數字區間的質數也可以當問題，一個數字是不是質數?也能當問題，甚至於拿一堆質數任意炒作後問結果，也都能夠拿來當問題‧

這幾十年來，我寫過也收集過無數與質數問題有關的程式了，網上也有無數的資訊探討質數的問題‧

我還曾發現美國田納西大學把32位元以下能表示的質數，拿來建表，當作可被搜索獲得的參考資料‧這樣的資源，有點像早年大家使用之三角函數的函數表，是個早已不再需要的東西‧印成大本的書，就浪費了大量的紙張，貼進大量的網頁，也浪費了龐大的網上資源空間‧

有感於此，我在設計這個展示程式時，花費了一點心思，採用不建質數表的方式達到目的‧不管你問第幾個質數，都不查表，直接算出來‧

上列名為test 的程式，實際上是一個原本我就發展完成後庫存起來留用的程式，原來的用途只做判斷一個任意輸入的數字是不是質數？列用在此處時，它的執行結果，簡單修正為若是質數，就把變數 P 的內容設定為  1，否則為 0 .

第二個主程式 main 則以簡單清楚的流程，顯示了找到指定質數的方法，這樣寫程式，實在不需要再進行細部的解說了，程式放它50年，到時，我仍然能夠輕鬆的看懂‧

展示程式時，小小群聚的程式，前後分開一列，就能更清楚地看懂彼此的關係，也讓能夠任意GOTO指令的功能呈現自然的規矩‧

能夠使用 BASIC 叫用 BASIC的特殊性能，化解了BASIC 程式語言曾被大家詬病為麵條式規格的缺點‧

最後，必須強調的是，我若不說，大家必定很難理解，這樣的BASIC 式性能，程式的流程，在許多地方都任意穿透了結構性邊界，系統卻還能夠正常執行，不用FORTH來設計，確實很難實現‧

字串

字串

Ching-Tang Tseng

Hamilton, New Zealand

2 December 2018

ilikeforth@gmail.com

http://forthfornight.blogspot.com

貼文只是我的義務，不是責任。所以，我有空才貼，逐次貼。這一篇，慢慢貼。

1. 字串元素的建立

此處，

我們把傳統的包封字串稱為小字串，相關操作指令盡量以小寫的 s 起首。

我們把現行巨型包封字串稱為大字串，相關操作指令盡量以 ＄ 號為起首。

\\\\\\\\\\

以 Forth 程式語言描述此種字串之資料結構的建立方法為 ：

: string

 create allot align   ( n -- )    創建時

 does>              ( -- addr ) 執行時

;

這樣的設計，對大小字串而言，同樣適用，創建時的宣告範例如 ：

   40  string   name1  小字串

4000  string   name2   大字串

\\\\\\\\\\

事實上，可以不必這麼麻煩。上列程式，只是為了解說方便而寫，確實能夠達到資料結構的宣告目的。

改成下列的宣告方式，產生的結果，將完全相同，我們卻可以在系統中省下一個多餘指令 string 的用名。

解決一件事情的方法，如果可以有好幾個，那麼，最簡單的一個，就是最好的一個。

正規的宣告方式，可以經由下列所示完成 ：

create   name1     40 allot   小字串

create   name2     4000 allot   大字串

2. 輸出顯示字串元素的內容

2.1 小字串

想要印出字串時的執行方法 ：

name1   count    type

count  的執行工作 ：

count   ( addr – addr+1 len )

type    的執行要求 ：

type    ( addr+1 len -- )

2.2 大字串

想要印出字串時的執行方法 ：

name2    $@    type

$@   的執行工作 ：

$@   ( addr --- addr+cell len )

type  的執行要求 ：

type   ( addr+cell len -- )

請注意！ 大字串直接使用 type 印出字串的方式，與小字串使用的方式類似。差別僅在大字串使用 $@，小字串使用 count 。

3. 輸入字串放進字串元素

採取能夠自動形成包封字串的指令 S” ……..” 直接輸入字串時，大小字串的程式寫法也類似。

例如 ：

S” 此字串將存入小字串元素 name1”   name1   s!    小字串

S” 此字串將存入大字串元素 name2”   name2   $!    大字串

這樣的寫法，也可以寫進程式中使用。利用 2 中已介紹過的印出字串方法，則可以驗證執行結果。

S” ……..”    的執行結果，提供了s! 及 $! 所需要的前兩個參數，name1或name2則提供出第三個所需要的參數。

S” ……..”    也可以提供type執行前所需要的兩個參數。

S” ……..”    ( -- addr len )

s!   ( addr1 len addr2 -- )   憑三個參數，將addr1處的指定字串，放進小字串元素addr2內。

在Lina64中，沒有現成的 s! 指令，簡單的高階定義設計如下：

: s!    ( addr1 len addr2 -- )

 2dup c!  1+ swap  cmove   ;

$!   ( addr1 len addr2 -- )   憑三個參數，將addr1處的指定字串，放進大字串元素addr2內。

4. 存取字串元素內容所需要的額外指令

字串元素的內容經常需要被進行額外的運作，尤其是常須逐漸地加大、加長，我可以舉出許多個自己曾經用過的這種例子。

例如：

想要逐次增加一個內容為龐大規模的字串，最後形成一個檔案。

字串可被分成幾個小段的文字，要先行組合完畢後，才能整串拿來當命令使用。

舉凡，大數字的輸出，都得逐個字元轉換，轉換完畢後，才一次性的印出來。不這樣做，系統的執行速度就會非常慢。

等等。

因此，在初次宣告出字串元素時，我們經常會先行配給較多或較大量的記憶體，供字串元素使用。

字串內容增長的方式具有規律性，是較為常見的需求，配合這種需要，系統提供現成的指令。

每次只增加單一個字元於字串尾部時，指令的慣用名稱為：

: sc+ ( c addr -- )    小字串

  dup >r dup c@ + 1+ c! 1 r> c+! ;

$c+   ( c addr -- )    大字串

每次要增加一個字串於原有字串的尾部時，指令的慣用名稱為：

: s+! ( addr1 len addr2 -- )   小字串

  dup c@ >r 2dup c+! 1+ r> + swap cmove ;

$+!   ( addr1 len addr2 -- )   大字串

在Lina64系統中，另有兩個現成較為常要用到的字串操作指令，此處僅列示其執行效果，不做深究。

這些大字串操作指令的功能，同樣適用於小字串，為什麼？請自行體會。這就是為什麼一開始我就把字串的結構設計成那種規格的主因。

String find accorging to c :

$^ ( addr1 len c -- addr2 )

String split according to c :

$/ ( addr1 len1 c -- addr2 len2 addr3 len3 )

5. 字串元素的函數

像數學體系一樣，字串元素所形成的集合，也能進行函數方式的運算。這方面的擴展應用非常廣泛，無法窮舉，此處僅列舉一些用來建立概念的範例。

特別聲明：前兩個指令的原始設計人是 Hugh Aguilar，原始程式曾經由作者公開張貼於國際論壇，我將源程式修改成在 Lina64 系統可以使用的格式，特此致謝，表示尊重。

這幾個指令，都同樣可以使用於大或小字串的操作上，理由同上。

比較兩個字串是否一樣？所得結果為真或為假之值。

: str= ( adrA lenA adrB lenB -- flag )  \ compare the strings for equality
  2 pick <> if  drop drop drop  false exit then
  tuck + swap 
  ?do                        \ -- adrA
       dup c@  I c@  <> if  drop false  unloop exit then
       1+
  loop
  drop true ;

將一個字串的內容就地反轉，產生的結果仍然放在原位址上，但為與原字串反向排列的新字串。

: $reverse ( addr len -- )
  2dup + -rot                  \ -- limit-adr adr cnt
  2/  over + swap
  ?do  1-          \ -- last-adr
       dup    c@  I c@            \ -- last-adr last-char char
       2 pick c!  I c!
  loop
  drop ;

將兩個字串相加，結果放在後一個字串的內容上。

: $+ ( addr1 len1 addr2 len2 -- addr2 len3)
  2swap swap 2over + 2 pick cmove + ;

6. 實際應用範例

整理出上述有關字串指令的資料，是為了用來解決實際問題。

我所設計的 ABC FORTH 系統，過去，只專注於純粹的數學計算，忽略了字串處理。

自從需要處理網路訊息的要求全面到來之後，電腦程式語言就必須面對夾雜了字串處理要求的問題。

我從不久前國際論壇論及的一個知名網站，取用一個簡單問題作為範例，也應特此聲明，表示尊重。

求解這種類似的問題，需要數學計算與字串處理雙方面配合起來應用，才能解決問題。


網址在：

https://projecteuler.net/problem=4

題目為：

Largest palindrome product
Problem 4
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

程式解：

create xy 4 cells allot
create yx 4 cells allot

: str= ( adrA lenA adrB lenB -- flag )      \ compare the strings for equality
    2 pick <> if  drop drop drop  false exit then
    tuck + swap  ?do                        \ -- adrA
        dup c@  I c@  <> if  drop false  unloop exit then
        1+  loop
    drop true ;

: $reverse ( addr len -- )
  2dup + -rot                  \ -- limit-adr adr cnt
  2/  over + swap
  ?do  1-          \ -- last-adr
       dup    c@  I c@            \ -- last-adr last-char char
       2 pick c!  I c!
  loop
  drop ;

4 integers a b x n

: main
basic
10 let n = 0
20 for a = 999 to 100 step -1
30 for b = a   to 100 step -1
40 let x = a * b
50 if x > n then 70
60 goto 120
70 run x (.) 2dup xy $! yx $! yx $@ $reverse
80 if xy $@ yx $@ str= then 100
90 goto 120
100 let n = a * b
110 print " a = " ; a ; " b = " ; b
120 next b
130 next a
140 print " n = " ; n
150 end
;

main

執行結果：

ching@center:~/lina64$ ./f

AMDX86 ciforth 5.3.0
fload palindromic.f
a : ISN'T UNIQUE                                               
b : ISN'T UNIQUE                                               
n : ISN'T UNIQUE                                               

a = 995 b = 583
a = 993 b = 913
n = 906609  OK
.s

S[ ] OK

最終的答案是：906609

大整數計算能力加入Lina64系統

大整數計算能力加入Lina64系統

Ching-Tang Tseng

Hamilton, New Zealand

16 November 2018

ilikeforth@gmail.com

http://forthfornight.blogspot.com

國際論壇網站曾於今年九月三日公開貼出Lina64作者推介我如何使用這個系統的推薦文章，那時，我尚未將大整數的計算功能加入系統，現在，加入。

加入後的特色，在讓大整數計算可以程式化，程式執行完畢後，系統不會耗用記憶體而回到原點。

我這一次的努力，則顯現在獨特的大數字顯示方式上：起頭處有總位數列印。大整數旁有邊標 (Side marks) ， 每 50 個數字一標。底部有字元尺 (Bottom ruler)，每10個數字一標，尺長共50個字。這樣的顯示法，算是我個人創作的專利，引用者必須得到我的同意，否則我會公開貼文，痛斥瓢竊者，而且日後我就不再公佈任何創意。

下列兩個簡單易懂的大數計算程式，供大家參考。一是計算 Fibonacci 級數的結果，另一則為計算大階乘 (Factorial) 的結果。

1.  Fibonacci numbers 程式

程式受輸出位數最多為10000位數的限制，下列程式使用上限，N大約為四萬七千多。

2 INTEGERS I N

0 BIGVARIABLE F(N)   10000 ALLOT

0 BIGVARIABLE F(N-1) 10000 ALLOT

0 BIGVARIABLE F(N-2) 10000 ALLOT

: EnterN BASIC

10 PRINT " Enter n =: "

20 INPUTI N

30 END ;

: MAIN BASIC

10 RUN EnterN

20 LET B{ F(N-1) = I>BIG ( 1 ) }B

30 LET B{ F(N-2) = I>BIG ( 1 ) }B

40 FOR I = 1 TO N

50 LET B{ F(N) = F(N-1) + F(N-2) }B

60 LET B{ F(N-2) = F(N-1) }B

70 LET B{ F(N-1) = F(N) }B

80 NEXT I

90 PRINT " Fibonacci ( " ; N + 2 ; " ) = "

100 RUN F(N) BIG.

110 END ;

執行結果：

2. 階乘 (Factorial) 計算

程式：大階乘

INTEGER I

INTEGER N

0 BIGVARIABLE X

0 BIGVARIABLE Y 40000 ALLOT

: BIG!. ( n -- )

[[ N ]] !

BASIC

10 LET B{ X = BIG0 }B

15 LET B{ Y = BIG1 }B

20 FOR I = 1 TO N

30 LET B{ X = X + BIG1 }B

40 LET B{ Y = Y * X }B

50 NEXT I

60 RUN Y BIG.

70 END ;

: BIG! ( n -- addr )

[[ N ]] !

BASIC

10 LET B{ X = BIG0 }B

15 LET B{ Y = BIG1 }B

20 FOR I = 1 TO N

30 LET B{ X = X + BIG1 }B

40 LET B{ Y = Y * X }B

50 NEXT I

70 END

B{{ Y }}B ;

執行結果：

來自第三方的資源

來自第三方的資源

Ching-Tang Tseng

Hamilton, New Zealand

2 November 2018

ilikeforth@gmail.com

http://forthfornight.blogspot.com

1. 前言

長期以來，研發軟體時，我早就經歷過無數次的失敗，再失敗一次也不足為奇。只是，不該氣餒，要把問題的根源找出來，又敗了，也要敗個明明白白。我在尋找第三種浮點運算可能的基本設計方法時，沒有成功，這篇貼文就記錄這樣的測試過程後留參。

最近，我回過台灣，當面請教了許多能夠參訪這個網頁者的實際情況，我才知道，能自動找上門來的同胞並不多，主要的讀者，大部份是國際人士。有此狀況的原因，一方面是以搜索方式獲得此網頁所需輸入的關鍵字，不符合現代人力求精簡的原則。另方面是本網頁內的網文題材與內容，不合現代人閱讀的胃口。貼文的風格需要改變，表達的方式需要改善，敘述應該盡量直接了當。

我在32位元的環境，完成過全套使用硬體數學運算處理器的浮點系統設計。我在64位元環境，也完成過藉著傳統整數四則運算設計出來的全套純軟體浮點系統設計。兩套資源都能建成浮點系統。

我也曾經想過，我們慣用的CPU內，後來才額外增加的暫存器名稱為XMMreg者，主要應用於多媒體影像處理方面，也有浮點計算的現成指令，不知能否用來設計浮點系統？我不必假裝自己可以完全獨立閱讀指令手冊後設計出能被測試的程式，我借用了網上前人的公益貼文來了解情況。

還是那句老話，引用別人的資料時，要尊重創作，明講來源，這是基本道德。

參考網頁如下：

http://cs.lmu.edu/~ray/notes/nasmtutorial/

2. 引用資源

該網頁中有一個可以直接輸入整數後，計算出浮點平均數的組合語言程式average.asm。

我的測試環境是在64位元的Ubuntu 16.04作業系統中，安裝Nasm組合語言編譯器(Assembler)進行測試。

轉貼源程式以及曾經進行修改後才測試的記錄如下：

程式中，凡尾部有 ***** 五個星號處，是需要注意的地方。

; -----------------------------------------------------------------------------

; 64-bit program that treats all its command line arguments as integers and

; displays their average as a floating point number.  This program uses a data

; section to store intermediate results, not that it has to, but only to

; illustrate how data sections are used.

; -----------------------------------------------------------------------------

        global      main

        extern   atoi

        extern   printf

        default    rel

        section    .text

main:

        dec      rdi                       ; argc-1, since we don't count program name

        jz             nothingToAverage

        mov         [count], rdi              ; save number of real arguments

accumulate:

        push     rdi                      ; save register across call to atoi

        push     rsi

        mov      rdi, [rsi+rdi*8]            ; argv[rdi]

        call          atoi                         ; now rax has the int value of arg *****

        pop      rsi                               ; restore registers after atoi call

        pop      rdi

        add      [sum], rax                    ; accumulate sum as we go

        dec      rdi                       ; count down

        jnz           accumulate              ; more arguments?

average:

        cvtsi2sd   xmm0, [sum]                            ; *****

        cvtsi2sd   xmm1, [count]                 ; *****

        divsd    xmm0, xmm1            ; xmm0 is sum/count

        mov         rdi, format               ; 1st arg to printf

        mov         rax, 1                       ; printf is varargs, there is 1 non-int argument

        sub      rsp, 8                   ; align stack pointer

        call          printf                      ; printf(format, sum/count)

        add      rsp, 8                 ; restore stack pointer

        ret

nothingToAverage:

        mov         rdi, error

        xor           rax, rax

        call          printf                                              ; *****

        ret

        section    .data

count:  dq       0

sum:    dq       0

format: db      "%g" , 10 , 0                            ; *****

; for 1 0 0  input testing         

; "%1.20f" , 10 , 13 , 0 

; "%1.40f" , 10 , 13 , 0
; "%1.20e" , 10 , 13 , 0

error:  db       "There are no command line arguments to average", 10, 0

; Usage:

; $ nasm -felf64 average.asm && gcc average.o && ./a.out 19 8 21 -33

; 3.75

; $ nasm -felf64 average.asm && gcc average.o && ./a.out

; There are no command line arguments to average

程式中，atoi是被叫用來處理整數輸入的外在功能程式。

尾綴有sd的兩個指令：cvtsi2sd 及 divsd，就是用來進行浮點運算的專用指令。前者將整數轉換成浮點數，後者執行浮點數的除法，尾綴的sd表這個指令係對64位元數字資料進行操作。

執行結果是藉由叫用C程式語言系統中的printf庫存程式來完成的。叫用這個程式時，各種所需使用的參數規格，可以從下列網頁中取得：

https://alvinalexander.com/programming/printf-format-cheat-sheet

最後面所增加的三個數字：10 , 13 , 0係我們在forth環境中慣用的 LF, CR 及 null三個字元之碼。

3. 測試結果

ching@center:~$ cd nasm64

ching@center:~/nasm64$ nasm -felf64 average.asm && gcc average.o && ./a.out 1 0 0

0.33333333333333331483

ching@center:~/nasm64$ nasm -felf64 average.asm && gcc average.o && ./a.out 1 0 0

0.3333333333333333148296162562473909929395

ching@center:~/nasm64$ nasm -felf64 average.asm && gcc average.o && ./a.out 1 0 0
3.33333333333333314830e-01

測試的結果顯示，我以輸入三個整數 1 , 0 , 0 來求其浮點數輸出的平均數，也就是等同於計算1 / 3 = ?。取小數點後面為20個數字時，只有16位數為精確的結果，隨後的數字都無意義了，取40位數輸出時，狀況更甚。

能用硬體數學計算處理器時，不會僅只有16位數的精確度。使用我所設計之以整數運算為基礎的純軟體浮點系統，也至少還有17位數以上的精確度。

而且，這樣計算出來所顯示的浮點數，只有假數(mantissa)沒有指數(exponent)，想要運用，就得另行處理，會是有點麻煩的用法。在多媒體影像處理方面的需求上，可能可以忽略指數表示部份，我們在設計全套的浮點系統時，就不能忽略必須帶有指數部份的要求。

我已經設計好了純軟體的64位元浮點系統，精確度與便利性比上述測試的結果要好，因此，我自覺這一次是失敗的測試。或許，將來仍會有人完成這方面的研發，目前，我不打算進一步應用。

4. 討論

事實上，我並不精通組合語言，若非使用forth程式語言時必須偶爾接觸低階指令的設計，我就不可能了解相關的事情，這就是為什麼我單選ciforth作為發展系統之基礎工具的主要原因。我非常感謝這個系統的作者，他奉獻過大量的時間與精力，為許多作業系統提供了基本資源。

反觀上述測試顯示，把一些組合語言的浮點四則運算指令，融入ciforth系統並不困難，相反的，設計起來，還更簡單。

上述程式中，呼叫外在功能程式atoi進行輸入整數的工作，在ciforth中根本不必做，因為，所需要輸入的整數，可以簡化成來自堆疊，要幾個就有幾個。

組合語言指令cvtsi2sd在ciforth中應該也可以照用。換句話說，整數轉換成浮點數格式的工作，可以不必自行設計程式。大家都廣泛使用這個指令，也是後來造成大家對浮點數結構之花樣規格不再熟悉的主要原因。這個指令的功能，等同於一般 forth 系統中 s>f 指令。如果我們仍用一般堆疊來放置浮點數字，它執行前後的堆疊變化就是( n -- f )。

指令divsd就是整件事情的核心，我單選這個以除法當範例的資源，講解在ciforth中進行類似發展的可行性，是因為浮點四則運算中，除法比較難設計，加、減、乘法運算，都可以依樣進行，都有類似的現成指令。更有甚者，雙精度的浮點運算，也有指令可以使用。這方面的問題，不是本文想要強調的重點，已有商售forth可以叫用C中的庫存程式來完成設計。從了解指令尾綴 “sd” 之意義，可以看得出來，我們也可能可以直接使用尾綴 “pd” 的其他浮點四則運算指令，來達到雙精度浮點運算的目的。我在forth環境中，發展出許多工具來解決自己的問題，顧及了普及性的要求，並不想透過能辦到雙精度運算的展示，來炫耀自己的能力，所以沒做此事。

末了，那個在C中有無限多輸出格式可以選擇的 printf現成功能程式，絕對不是我們這種forth使用者應該叫用的對象。forth的輸出能力變化無窮，我個人的作法，強調浮點輸出的指令要自己設計，才不會受制於人。而且，歷屆的C系統中，早就發現過許多printf執行輸出時，能力上的限制，使用者無法自行改良，所以我不跟用。在我的 forth 系統中，設計浮點輸出指令時，被操作的浮點數字資源，是來自堆疊，因此，引用divsd指令來設計forth的浮點除法運算時，程式的內容會變成非常簡單，算完後，只須把結果推放在堆疊上便可。一旦有了浮點數的四則運算指令，就能設計出整套的浮點運算系統。

最後，必須強調的是，這樣的浮點運算方式，浮點數字的位元花樣，可能並不遵循任何IEEE的浮點數字標準規格，數字輸入時，未顯示指數方次的處理方法。因此，強行應用，指數方次的處理，就得另行考慮。至於實際內容為何？用forth進行研究，能夠變得非常簡單。

本文貼出後，網上的顯示結果，可能不盡人意，程式的分欄內容，不會自動對齊，需要操作網頁控制程式的內容來調整，這不是我貼文訴求的重點，我不想花時間去整理。想看整齊程式的讀者，請自行下載重編。