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 © 1999-2018, Tomasz Grysztar.

Powered by rwasa.