埃拉托色尼筛 x86 组装
Sieve of Eratosthenes x86 Assembly
我是汇编新手，正在尝试实现 Erathothenes 筛法，我有代码，但它只能在 1 到 600 之间工作，出于某种原因，当我输入 n=1000 时它会失控，这是完整的代码，任何帮助都可以。
Include Irvine32.inc
n=1000
.data
prime DWORD n DUP(?)
.code
main PROC
mov ecx,n ;initialize ecx to 1000
mov esi, OFFSET prime
;--------------------------------------------------------
; Initialize Array with 1's
;--------------------------------------------------------
FillArray: mov eax,1
mov [esi],eax
mov eax,[esi]
add esi,TYPE DWORD ;4 to jump to the next index
loop FillArray
mov ebx,8
mov edx,0
mov ecx,n
mov ebp,2
mov esi,0
;----------------------------------------------------------------
; Sieve
;----------------------------------------------------------------
SIEVE: mov eax,prime[ebx]
mov edx,ebx
mov edi,ebx
add edx,edi ;j=i+i
mov esi,ebp
mov ecx,n
sub ecx,ebp
add ecx,2
add ebx,TYPE DWORD
cmp eax,1
je FLIP
inc ebp
loop SIEVE
jmp K
FLIP: mov eax,0
mov prime[edx],eax
add edx,edi
cmp esi,n
jg SIEVE
add esi,ebp
loop FLIP
K:
mov esi, OFFSET prime
mov ecx,n
sub ecx,2
mov ebx,1
mov edx,8 ;Start checking from index of second element
PRINT: mov eax,prime[edx] ;
add edx,TYPE DWORD
inc ebx
cmp eax,1
jne H
mov eax,ebx
call WriteDec
call Crlf
loop PRINT
jmp D
H: loop PRINT
D:
exit
main ENDP
END main
你对 "going haywire" 的含义不够具体，你可能没有调试你的代码，也没有对它进行足够的评论以使其易于理解，所以在看了几分钟后我跟着我的直觉告诉我从头开始并以常规方式编写它。
这是否对您有帮助 - 我不知道，可能不会，至少在不付出巨大 "analyse this" 努力的情况下不会。
但我相信这个是标题为"Sieve of Eratosthenes x86 Assembly"和[=的问题的有效答案55=].
所以你开始吧，尝试完全理解外国来源并尝试掌握所使用的思想；在某种程度上，它会在您编写自己的代码时开始为您提供帮助。祝你好运。 :)
首先，在写一些代码之前，您应该首先清理数学方面的任务。
如果你愿意，你会知道没有必要 "sieve" 进一步超出 sqrt(n) 值。
因为如果 sqrt(n) 是素数，那么它乘以 2*sqrt(n), 3*sqrt(n), ..., previous_prime *sqrt(n) 已经 "sieved" 来自循环中较早筛选的那些较小的素数。
第一个 "yet unsieved" 数字是 sqrt(n) * sqrt(n)，即 n 本身，并且超出了数组边界。所以在达到 number >= sqrt(n) 之后你可以结束你的算法主循环（我正在使用尖锐的 number > sqrt(n) 测试，因为 sqrt(n) 被截断为整数，所以对于特殊 "n"（整数 sqrt(n)）我会尝试 "sieve" n 本身一次，但是 flip_loop 内的测试会检测到并终止。
Include Irvine32.inc
n=1000
n_terminal=31
; terminal compare value is min(sqrt(n), 0FFFFh) (last value to process)
; no point to sieve beyond sqrt(n), because first unset multiply is
; sqrt(n)*sqrt(n) = n => beyond array
; and no point to sieve 10000h, because 10000h*10000h is out of 32b
.data
prime BYTE n DUP(?)
.code
main PROC
; fill array with "1" (from number 2 to n)
mov edi,OFFSET prime+2
mov ecx,n-2
mov eax,1 ; eax=1 will be used also later (also ah=0)
rep stosb
; set "0" and "1" as non-prime too
mov WORD PTR [prime],cx ; (cx == 0 after "rep stosb")
; set "0" to all other non-primes by sieving
mov esi,eax ; esi=1, start the loop as if "1" was handled last
sieve_loop:
inc esi ; next number to test
; sqrt(n) is enough to process, beyond that n <= number*number => out of array
cmp esi,n_terminal
ja sieve_end ; out of table, end sieving
cmp prime[esi],al ; compare with "1"
jne sieve_loop ; not a prime, don't flip the rest of sieve
; esi is prime, flip the other multiplies of it, starting from esi*esi (!)
mov edi,esi ; esi*esi as smaller multiples are already covered by
imul edi,edi ; smaller prime numbers sieving the array before
flip_loop:
cmp edi,n ; check if the multiply points beyond table
jae sieve_loop ; if yes, continue main loop with next "prime"
mov prime[edi],ah ; set this number to "0" (not prime)
add edi,esi ; edi = next multiply of esi prime
jmp flip_loop
sieve_end:
; print all primes starting from 2
mov esi,eax ; esi = 1, as if "1" was handled last
print_loop:
inc esi ; while (++number < n)
cmp esi,n
jae end_print_loop
cmp BYTE PTR prime[esi],1 ; eax/al is modified from "WriteDec"
jne print_loop ; not a prime number, loop
; esi is prime number, print it
mov eax,esi
call WriteDec ; these two calls must preserve esi
call Crlf
jmp print_loop
end_print_loop:
exit
main ENDP
END main
我确实在 linux 和 NASM 下测试过它，所以我不得不稍微更改语法来编译它，然后将语法改回 MASM/TASM + irvine，所以可能在转换过程中出现了一些小错误，如果它不起作用请告诉我。
对于仍然有此问题的任何人，我已经从 python 到汇编实现了以下代码。
from math import sqrt
def FindPrimes(limit):
isPrime = {}
isPrime[1] = False
for i in range(2, limit + 1):
isPrime[i] = True
checkLimit = int(sqrt(limit)) + 1
for i in range(2, checkLimit):
if isPrime[i]:
for factor in range(2, limit + 1):
j = i * factor
if (j > limit): break
isPrime[j] = False
primes = []
for i in range(1, limit + 1):
if isPrime[i]:
primes.append(i)
return primes
请注意，以下程序集实现是在 MASM 中，它需要您手动输入平方根加 1，因为我们将第一个 DWORD 处理为 "isPrime[1]"，当然还有极限 "FindPrimes(limit)".
.386
.model flat,stdcall
.stack 4096
ExitProcess proto,dwExitCode:dword
n=1000
sqrt=32
.data
sieveArray DWORD n DUP(0)
primeNumbers DWORD n DUP(0)
limit DWORD 0
varInnerLoop DWORD 0 ;variable j
falseValue DWORD 0
primerHelper DWORD 1
.code
main PROC
mov ecx,LENGTHOF sieveArray-1
mov edi,OFFSET sieveArray+TYPE DWORD*2
mov eax,1
fillUp:
mov [edi],eax
add edi,TYPE DWORD
loop fillUp
checkForPrime:
mov edi,OFFSET sieveArray+TYPE DWORD*2 ;reset for iteration
mov esi,[edi] ;pointer helper
mov eax,TYPE DWORD ;offset helper
mov ebx,1 ;counter for loopOverNumbers reference
mov ecx,sqrt-1 ;sqrt(limit)+1 `limit`¨, -1 because index 0 = index 1, counter
mov edx,1 ;outer loop variable helper for inner loop
loopOverNumbers:
cmp ebx,ecx
je iterateOverPrimes ;take me out of the loop because I have iterated over range(1,edx)
cmp esi,1
pushad ;save my flags for outer loop, specially ebx and ecx
je iterateOverFactorsSetUp
continueIteration:
popad
add edi,eax
mov esi,[edi]
inc edx
loop loopOverNumbers
iterateOverFactorsSetUp:
mov eax,1 ;factor for inner loop
mov ecx,n+1
iterateOverFactors:
cmp ebx,ecx
je continueIteration
push edx
push eax
inc eax ;pointer must increment to reflect real value
inc edx ;pointer must increment to reflect real value
imul edx,eax
mov varInnerLoop,edx ;j = i * factor
cmp varInnerLoop,n ;if (j > limit): break
jg continueIterationHelper
imul edx,TYPE DWORD
mov edi,OFFSET sieveArray
add edi,edx
mov eax,0
mov [edi],eax ;reset to old value before pointer
pop eax
pop edx
inc eax
loop iterateOverFactors
continueIterationHelper: ;have to pop eax and edx in order to get original values when returning to
pop eax
pop edx
jmp continueIteration
iterateOverPrimes:
mov eax,TYPE DWORD
mov ecx,n+1 ;limit helper
mov ebx,0
mov edi,OFFSET sieveArray+TYPE DWORD
checkifPrime:
mov esi,[edi]
cmp esi,1
pushad
je appendToPrimeArray
continueSearch:
popad
add edi,eax
inc ebx
loop checkifPrime
jmp searchDone
appendToPrimeArray:
mov eax,TYPE DWORD
mov edi,OFFSET primeNumbers
imul eax,primerHelper ;pointer for primeNumbers helper
add edi,eax
inc ebx
mov [edi],ebx
inc primerHelper
jmp continueSearch
searchDone:
INVOKE ExitProcess,0
main ENDP
END main
为了检查您的结果，您可以检查 primeNumbers，它将连续包含每个素数作为 DWORD。
如果您有任何疑虑，请告诉我:)
我是汇编新手，正在尝试实现 Erathothenes 筛法，我有代码，但它只能在 1 到 600 之间工作，出于某种原因，当我输入 n=1000 时它会失控，这是完整的代码，任何帮助都可以。
Include Irvine32.inc
n=1000
.data
prime DWORD n DUP(?)
.code
main PROC
mov ecx,n ;initialize ecx to 1000
mov esi, OFFSET prime
;--------------------------------------------------------
; Initialize Array with 1's
;--------------------------------------------------------
FillArray: mov eax,1
mov [esi],eax
mov eax,[esi]
add esi,TYPE DWORD ;4 to jump to the next index
loop FillArray
mov ebx,8
mov edx,0
mov ecx,n
mov ebp,2
mov esi,0
;----------------------------------------------------------------
; Sieve
;----------------------------------------------------------------
SIEVE: mov eax,prime[ebx]
mov edx,ebx
mov edi,ebx
add edx,edi ;j=i+i
mov esi,ebp
mov ecx,n
sub ecx,ebp
add ecx,2
add ebx,TYPE DWORD
cmp eax,1
je FLIP
inc ebp
loop SIEVE
jmp K
FLIP: mov eax,0
mov prime[edx],eax
add edx,edi
cmp esi,n
jg SIEVE
add esi,ebp
loop FLIP
K:
mov esi, OFFSET prime
mov ecx,n
sub ecx,2
mov ebx,1
mov edx,8 ;Start checking from index of second element
PRINT: mov eax,prime[edx] ;
add edx,TYPE DWORD
inc ebx
cmp eax,1
jne H
mov eax,ebx
call WriteDec
call Crlf
loop PRINT
jmp D
H: loop PRINT
D:
exit
main ENDP
END main
你对 "going haywire" 的含义不够具体，你可能没有调试你的代码，也没有对它进行足够的评论以使其易于理解，所以在看了几分钟后我跟着我的直觉告诉我从头开始并以常规方式编写它。
这是否对您有帮助 - 我不知道，可能不会，至少在不付出巨大 "analyse this" 努力的情况下不会。
但我相信这个是标题为"Sieve of Eratosthenes x86 Assembly"和[=的问题的有效答案55=].
所以你开始吧，尝试完全理解外国来源并尝试掌握所使用的思想；在某种程度上，它会在您编写自己的代码时开始为您提供帮助。祝你好运。 :)
首先，在写一些代码之前，您应该首先清理数学方面的任务。
如果你愿意，你会知道没有必要 "sieve" 进一步超出 sqrt(n) 值。
因为如果 sqrt(n) 是素数，那么它乘以 2*sqrt(n), 3*sqrt(n), ..., previous_prime *sqrt(n) 已经 "sieved" 来自循环中较早筛选的那些较小的素数。
第一个 "yet unsieved" 数字是 sqrt(n) * sqrt(n)，即 n 本身，并且超出了数组边界。所以在达到 number >= sqrt(n) 之后你可以结束你的算法主循环（我正在使用尖锐的 number > sqrt(n) 测试，因为 sqrt(n) 被截断为整数，所以对于特殊 "n"（整数 sqrt(n)）我会尝试 "sieve" n 本身一次，但是 flip_loop 内的测试会检测到并终止。
Include Irvine32.inc
n=1000
n_terminal=31
; terminal compare value is min(sqrt(n), 0FFFFh) (last value to process)
; no point to sieve beyond sqrt(n), because first unset multiply is
; sqrt(n)*sqrt(n) = n => beyond array
; and no point to sieve 10000h, because 10000h*10000h is out of 32b
.data
prime BYTE n DUP(?)
.code
main PROC
; fill array with "1" (from number 2 to n)
mov edi,OFFSET prime+2
mov ecx,n-2
mov eax,1 ; eax=1 will be used also later (also ah=0)
rep stosb
; set "0" and "1" as non-prime too
mov WORD PTR [prime],cx ; (cx == 0 after "rep stosb")
; set "0" to all other non-primes by sieving
mov esi,eax ; esi=1, start the loop as if "1" was handled last
sieve_loop:
inc esi ; next number to test
; sqrt(n) is enough to process, beyond that n <= number*number => out of array
cmp esi,n_terminal
ja sieve_end ; out of table, end sieving
cmp prime[esi],al ; compare with "1"
jne sieve_loop ; not a prime, don't flip the rest of sieve
; esi is prime, flip the other multiplies of it, starting from esi*esi (!)
mov edi,esi ; esi*esi as smaller multiples are already covered by
imul edi,edi ; smaller prime numbers sieving the array before
flip_loop:
cmp edi,n ; check if the multiply points beyond table
jae sieve_loop ; if yes, continue main loop with next "prime"
mov prime[edi],ah ; set this number to "0" (not prime)
add edi,esi ; edi = next multiply of esi prime
jmp flip_loop
sieve_end:
; print all primes starting from 2
mov esi,eax ; esi = 1, as if "1" was handled last
print_loop:
inc esi ; while (++number < n)
cmp esi,n
jae end_print_loop
cmp BYTE PTR prime[esi],1 ; eax/al is modified from "WriteDec"
jne print_loop ; not a prime number, loop
; esi is prime number, print it
mov eax,esi
call WriteDec ; these two calls must preserve esi
call Crlf
jmp print_loop
end_print_loop:
exit
main ENDP
END main
我确实在 linux 和 NASM 下测试过它，所以我不得不稍微更改语法来编译它，然后将语法改回 MASM/TASM + irvine，所以可能在转换过程中出现了一些小错误，如果它不起作用请告诉我。
对于仍然有此问题的任何人，我已经从 python 到汇编实现了以下代码。
from math import sqrt
def FindPrimes(limit):
isPrime = {}
isPrime[1] = False
for i in range(2, limit + 1):
isPrime[i] = True
checkLimit = int(sqrt(limit)) + 1
for i in range(2, checkLimit):
if isPrime[i]:
for factor in range(2, limit + 1):
j = i * factor
if (j > limit): break
isPrime[j] = False
primes = []
for i in range(1, limit + 1):
if isPrime[i]:
primes.append(i)
return primes
请注意，以下程序集实现是在 MASM 中，它需要您手动输入平方根加 1，因为我们将第一个 DWORD 处理为 "isPrime[1]"，当然还有极限 "FindPrimes(limit)".
.386
.model flat,stdcall
.stack 4096
ExitProcess proto,dwExitCode:dword
n=1000
sqrt=32
.data
sieveArray DWORD n DUP(0)
primeNumbers DWORD n DUP(0)
limit DWORD 0
varInnerLoop DWORD 0 ;variable j
falseValue DWORD 0
primerHelper DWORD 1
.code
main PROC
mov ecx,LENGTHOF sieveArray-1
mov edi,OFFSET sieveArray+TYPE DWORD*2
mov eax,1
fillUp:
mov [edi],eax
add edi,TYPE DWORD
loop fillUp
checkForPrime:
mov edi,OFFSET sieveArray+TYPE DWORD*2 ;reset for iteration
mov esi,[edi] ;pointer helper
mov eax,TYPE DWORD ;offset helper
mov ebx,1 ;counter for loopOverNumbers reference
mov ecx,sqrt-1 ;sqrt(limit)+1 `limit`¨, -1 because index 0 = index 1, counter
mov edx,1 ;outer loop variable helper for inner loop
loopOverNumbers:
cmp ebx,ecx
je iterateOverPrimes ;take me out of the loop because I have iterated over range(1,edx)
cmp esi,1
pushad ;save my flags for outer loop, specially ebx and ecx
je iterateOverFactorsSetUp
continueIteration:
popad
add edi,eax
mov esi,[edi]
inc edx
loop loopOverNumbers
iterateOverFactorsSetUp:
mov eax,1 ;factor for inner loop
mov ecx,n+1
iterateOverFactors:
cmp ebx,ecx
je continueIteration
push edx
push eax
inc eax ;pointer must increment to reflect real value
inc edx ;pointer must increment to reflect real value
imul edx,eax
mov varInnerLoop,edx ;j = i * factor
cmp varInnerLoop,n ;if (j > limit): break
jg continueIterationHelper
imul edx,TYPE DWORD
mov edi,OFFSET sieveArray
add edi,edx
mov eax,0
mov [edi],eax ;reset to old value before pointer
pop eax
pop edx
inc eax
loop iterateOverFactors
continueIterationHelper: ;have to pop eax and edx in order to get original values when returning to
pop eax
pop edx
jmp continueIteration
iterateOverPrimes:
mov eax,TYPE DWORD
mov ecx,n+1 ;limit helper
mov ebx,0
mov edi,OFFSET sieveArray+TYPE DWORD
checkifPrime:
mov esi,[edi]
cmp esi,1
pushad
je appendToPrimeArray
continueSearch:
popad
add edi,eax
inc ebx
loop checkifPrime
jmp searchDone
appendToPrimeArray:
mov eax,TYPE DWORD
mov edi,OFFSET primeNumbers
imul eax,primerHelper ;pointer for primeNumbers helper
add edi,eax
inc ebx
mov [edi],ebx
inc primerHelper
jmp continueSearch
searchDone:
INVOKE ExitProcess,0
main ENDP
END main
为了检查您的结果，您可以检查 primeNumbers，它将连续包含每个素数作为 DWORD。
如果您有任何疑虑，请告诉我:)