檢查8086程式集中的質數

我正在嘗試使用 Turbo Assembler 在 8086 匯編程式中檢查給定數字是否為素數。但也許我的代碼有問題，因為某些素數（19、23、31、37）顯示它不是素數。其余的素數（2,3,5,7,11,17,29,41,...,71）運行良好。

這是整個代碼：

DATA SEGMENT
NUM DB 37H
PR DB 0H
NPR DB 0H
DATA ENDS

CODE SEGMENT
START: ASSUME CS:CODE, DS:DATA
MOV AX, DATA
MOV DS, AX
MOV AL, NUM
MOV BL, 02H
MOV BH,00H
MOV DX,0000H
MOV AH,00H

UP:DIV BL 
CMP AH,00H
JNE NEXT
INC BH
NEXT: CMP BH, 02H
JE NPRIME
INC BL
MOV AX, 0000H
MOV DX, 0000H
MOV AL, NUM
CMP BL, NUM
JBE UP

PRIME: 
INC PR
JMP EXIT

NPRIME: 
INC NPR

EXIT:
MOV AH, 4CH
INT 21H

CODE ENDS
END START

也許問題一定出在這部分？

UP:DIV BL 
CMP AH,00H
JNE NEXT
INC BH
NEXT: CMP BH, 02H
JE NPRIME
INC BL
MOV AX, 0000H
MOV DX, 0000H
MOV AL, NUM
CMP BL, NUM
JBE UP

請讓我知道我哪里出錯了，在此先感謝！

uj5u.com熱心網友回復：

我試過你的程式，它運行良好，只是你似乎考慮了 0 和 1 素數。這是不正確的。

素數是大于 1 的數，它只能被自身和 1 整除。

快速修復如下：

...
MOV AL, NUM
cmp al, 2           <<<< Add this line
jb  NPRIME          <<<< Add this line
MOV BL, 02H
MOV BH,00H
MOV DX,0000H
MOV AH,00H

UP:DIV BL 
CMP AH,00H
JNE NEXT
INC BH
NEXT: CMP BH, 02H
JE NPRIME
INC BL
MOV AX, 0000H
MOV DX, 0000H
MOV AL, NUM
CMP BL, NUM
JBE UP

PRIME: 
INC PR
JMP EXIT

NPRIME: 
INC NPR

EXIT:
...

如果我將其留在那里，那就沒什么答案了！因此，請允許我進行以下觀察：

• 歸零DX是重復兩次的冗余操作
• 您可以在一次操作中加載BH和BL
• 不要在兩個不同的地方加載號碼
• 變數PR和NPR是互斥的，所以一個變數就足夠了
• 您不需要分支來增加計數器

更好的解決方法如下：

  ...
  cmp  NUM, 2
  jb   NPRIME    ; 0 and 1 are no prime numbers
  mov  bx, 0002h ; BH=0 (counter), BL=2 (divisor)
UP:
  mov  al, NUM
  mov  ah, 0
  div  bl
  cmp  ah, 1     ; Only sets carry flag is remainder is 0
  adc  bh, 0     ; Conditional increment of counter
  cmp  bh, 2
  je   NPRIME
  inc  bl
  cmp  bl, NUM
  jbe  UP
PRIME: 
  inc  PR
NPRIME: 
EXIT:
...

因為您的演算法會嘗試每個除數本身，所以即使上述建議的更改也不會使程式真正高效。
我可以添加一個至少快 10 倍的代碼版本。如果您有興趣，請給我留言，也許我可以在周末添加它...

[編輯]

快速檢查素數

嘗試減少迭代次數，尤其是除法次數（div這是一項昂貴的操作）是我們在這里追求的：

• 首先拆分小數字 [0,3] 是最有效的。這避免了回圈中的額外測驗。
• 接下來我們拆分偶數，因為除了數字 2（我們已經拆分）之外，沒有偶數是素數。
• 因此回圈只需要除奇數。我們可以一次省略所有偶數除數，因為奇數除以偶數永遠不會產生零余數。
• 我們只需要測驗除數直到該數字的整數平方根。幸運的是，我們不需要計算它。只要除法的商仍然大于除數，我們還沒有達到整數平方根。

; IN (dl) OUT (cx) MOD (ax,bl)
TestPrime:
  xor  cx, cx         ; CX=0 means NotPrime
  cmp  dl, 4
  jb   .Less4
  mov  bl, 1
  test dl, bl
  jz   .No            ; Number is EVEN, so not prime
  ; Remaining candidates {5,7,9,11,13,15,...}
.Loop:
  add  bl, 2          ; Division by {3,5,7,9,11,....}
  mov  al, dl
  mov  ah, 0          ; Will divide AX by BL
  div  bl
  test ah, ah         ; Remainder == 0 ?
  jz   .No            ; Yes, found an additional divisor, so not prime
  cmp  al, bl         ; Quotient > divisor ?
  ja   .Loop          ; Yes, continue up to isqrt(number)
.Yes:
  inc  cx             ; CX=1 means Prime
  ret
.Less4:
  cmp  dl, 2
  jae  .Yes           ; 2 and 3 are prime, 0 and 1 are not prime
.No:
  ret

小于 256 的素數

下表顯示DIV了已執行的指令數量以及以納秒為單位的時間。中間的列是問題的改進代碼，右邊的列是今天優化的代碼。隨著數量的增長，收益也在增長。

小于 256 的非素數

下表顯示了數量DIV了已執行的指令數量以及以納秒為單位的時間。中間的列是問題的改進代碼，右邊的列是今天優化的代碼。隨著數量的增長，收益也在增長。

標籤：部件 x86-16 塔斯马 鸸鹋8086

上一篇：如何將Python3代碼轉換為C /Assembly語言？[復制]

下一篇：你怎么能告訴一臺計算機它正在添加而不在Assembly中添加addl