flat assembler
Message board for the users of flat assembler.

flat assembler > Examples and Tutorials > [Macro] Prime number generator, simple sqrt, bisearch

Author
Thread Post new topic Reply to topic
RIxRIpt



Joined: 18 Apr 2013
Posts: 49
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
Post 24 Oct 2015, 13:26
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >

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


Copyright © 2004-2018, Tomasz Grysztar.

Powered by rwasa.