flat assembler
Message board for the users of flat assembler.
 Home   FAQ   Search   Register 
 Profile   Log in to check your private messages   Log in 
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

[Macro] Prime number generator, simple sqrt, bisearch


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 rootremplace
    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=root1310
}

;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 xyijpslimitsbasevirtual_prime_bits
    display 'Primes, up to: 'd=n1310
    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=p1310
            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 valuetypeleftright {
    local xlmrbase
    display 'Binary search:'1310
    display 'l'9'm'9'r'9'x'1310
    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: `', `type1310
        err
    end if
    l = 0
    r = (right - left - 1) / size
    while l <= r
        m = (l + rshr 1
        load x type from left + m * size
        display d=l9d=m9d=r9d=x1310
        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 xqwordPrimesEndPrimes

load p qword from bisearch_result
display 'First prime, which is >= 'd=x': 'd=p1310


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


Powered by phpBB © 2001-2005 phpBB Group.

Main index   Download   Documentation   Examples   Message board
Copyright © 2004-2017, Tomasz Grysztar.