flat assembler
Message board for the users of flat assembler. flat assembler > Examples and Tutorials > [Macro] Prime number generator, simple sqrt, bisearch
Author
 Thread  RIxRIpt

Joined: 18 Apr 2013
Posts: 50
Code:
```;l_inc's print macro, can be found on the forum
include 'exmacro/print.inc'

;Taken from http://www.codecodex.com/wiki/Calculate_an_integer_square_root
fasm_sqrt_result = 0
macro fasm_sqrt n {
local root, rem, place
root = 0
rem = n
place = 0x4000000000000000
while place > rem
place = place shr 2
end while
while place
if rem >= root + place
rem = rem - root - place
root = root + place shl 1
end if
root = root shr 1
place = place shr 2
end while
fasm_sqrt_result = root
display 'ISQRT of ', d=n, ' is ', d=root, 13, 10
}

;Generating prime numbers up to `N`, using Sieve of Eratosthenes
;https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
;Thanks to l_inc [ http://board.flatassembler.net/topic.php?p=184093#184093 ]
macro generate_primes n {
local x, y, i, j, p, slimit, sbase, virtual_prime_bits
display 'Primes, up to: ', d=n, 13, 10
virtual at 0
virtual_prime_bits::
; 0, 1 - not primes
; 2, .. - probrably primes
db 1111'1100b
db 1 + (n - 1) / 8 dup 1111'1111b
repeat (n + 1) / 8 + 1
i = % - 1
load x byte from i
repeat 8
j = % - 1
p = i * 8 + j
if p > n
break
end if
if x and (1 shl j)
sbase = p * p
slimit = 1 + (n - sbase) / p
if slimit > 0
repeat slimit
j = sbase + p * (% - 1)
load y byte from j / 8
y = y and (not (1 shl (j and 7)))
store byte y at j / 8
end repeat
end if
end if
end repeat
end repeat
end virtual
repeat (n + 1) / 8 + 1
i = % - 1
load x byte from virtual_prime_bits:i
repeat 8
j = % - 1
if x and (1 shl j)
p = i * 8 + j
if p > n
break
end if
dq p
display d=p, 13, 10
end if
end repeat
end repeat
}

;Binary search of value with specific type in a specific region [left; right) - right bound not included
;Searches for the left most value, which is equal to `value`
;Returns (sets bisearch_result) address of first value, which is greater or equal to `value`
macro bisearch value, type, left, right {
local x, l, m, r, base
display 'Binary search:', 13, 10
display 'l', 9, 'm', 9, 'r', 9, 'x', 13, 10
if type eq byte
size = 1
else if type eq word
size = 2
else if type eq dword
size = 4
else if type eq qword
size = 8
else
display 'Invalid type: `', `type, 13, 10
err
end if
l = 0
r = (right - left - 1) / size
while l <= r
m = (l + r) shr 1
load x type from left + m * size
display d=l, 9, d=m, 9, d=r, 9, d=x, 13, 10
if value <= x
r = m - 1
else
l = m + 1
end if
end while
bisearch_result = left + l * size
}

;Usage
Primes:
fasm_sqrt 1 shl 20
generate_primes fasm_sqrt_result
EndPrimes:

x = 444
bisearch_result = -1
bisearch x, qword, Primes, EndPrimes

load p qword from bisearch_result
display 'First prime, which is >= ', d=x, ': ', d=p, 13, 10
``` 24 Oct 2015, 13:26    Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First  Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum

Copyright © 1999-2019, Tomasz Grysztar.

Powered by rwasa.