flat assembler
Message board for the users of flat assembler. Index > Examples and Tutorials > [Macro] Prime number generator, simple sqrt, bisearch
Author
 Thread  RIxRIpt Joined: 18 Apr 2013 Posts: 50 RIxRIpt 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