2018年11月15日 星期四

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


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


Ching-Tang Tseng
Hamilton, New Zealand
16 November 2018

國際論壇網站曾於今年九月三日公開貼出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 ;


執行結果:
















2018年11月1日 星期四

來自第三方的資源


來自第三方的資源


Ching-Tang Tseng
Hamilton, New Zealand
2 November 2018

1. 前言


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

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

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

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

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

參考網頁如下:



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庫存程式來完成的。叫用這個程式時,各種所需使用的參數規格,可以從下列網頁中取得:


最後面所增加的三個數字: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中根本不必做,因為,所需要輸入的整數,可以簡化成來自堆疊,要幾個就有幾個。

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

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

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

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


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