<commit_before>! Copyright (C) 2009 <NAME>.
! See http://factorcode.org/license.txt for BSD license.
USING: kernel kernel.private locals math math.bitwise
math.functions math.order math.private math.ranges sequences
sequences.private ;
IN: math.primes.erato

<PRIVATE

CONSTANT: masks
{ f 128 f f f f f 64 f f f 32 f 16 f f f 8 f 4 f f f 2 f f f f f 1 }

: bit-pos ( n -- byte mask/f )
    { fixnum } declare
    30 /mod masks nth-unsafe
    { maybe{ fixnum } } declare ; inline

:: marked-unsafe? ( n sieve -- ? )
    n bit-pos [
        [ sieve nth-unsafe ] [ mask zero? not ] bi*
    ] [ drop f ] if* ; inline

:: unmark ( n sieve -- )
    n bit-pos [
        swap sieve [ swap unmask ] change-nth-unsafe
    ] [ drop ] if* ; inline

: upper-bound ( sieve -- n ) length 30 * 1 - ; inline

:: unmark-multiples ( i upper sieve -- )
    i sieve marked-unsafe? [
        i 2 fixnum*fast :> step
        i i fixnum*fast
        [ dup upper <= ] [
            [ sieve unmark ] [ step fixnum+fast ] bi
        ] while drop
    ] when ; inline

: init-sieve ( n -- sieve )
    30 /i 1 + [ 255 ] B{ } replicate-as ; inline

PRIVATE>

:: sieve ( n -- sieve )
    n integer>fixnum-strict init-sieve :> sieve
    sieve upper-bound >fixnum :> upper
    3 upper sqrt 2 <range>
    [ upper sieve unmark-multiples ] each
    sieve ;

: marked-prime? ( n sieve -- ? )
    [ integer>fixnum-strict ] dip
    2dup upper-bound 2 swap between? [ bounds-error ] unless
    over { 2 3 5 } member? [ 2drop t ] [ marked-unsafe?  ] if ;<commit_msg>math.primes.erato: add some comments at the top.<commit_after>! Copyright (C) 2009 <NAME>.
! See http://factorcode.org/license.txt for BSD license.
USING: kernel kernel.private locals math math.bitwise
math.functions math.order math.private math.ranges sequences
sequences.private ;
IN: math.primes.erato

<PRIVATE

! This is a compressed Sieve of Eratosthenes that uses the
! 2-3-5 wheel to check groups of 8 candidates starting with
! { 1 7 11 13 17 19 23 29 } allowing us to use a byte-array
! to store each group of booleans in a byte.

CONSTANT: masks
{ f 128 f f f f f 64 f f f 32 f 16 f f f 8 f 4 f f f 2 f f f f f 1 }

: bit-pos ( n -- byte mask/f )
    { fixnum } declare
    30 /mod masks nth-unsafe
    { maybe{ fixnum } } declare ; inline

:: marked-unsafe? ( n sieve -- ? )
    n bit-pos [
        [ sieve nth-unsafe ] [ mask zero? not ] bi*
    ] [ drop f ] if* ; inline

:: unmark ( n sieve -- )
    n bit-pos [
        swap sieve [ swap unmask ] change-nth-unsafe
    ] [ drop ] if* ; inline

: upper-bound ( sieve -- n ) length 30 * 1 - ; inline

:: unmark-multiples ( i upper sieve -- )
    i 2 fixnum*fast :> step
    i i fixnum*fast
    [ dup upper <= ] [
        [ sieve unmark ] [ step fixnum+fast ] bi
    ] while drop ; inline

: init-sieve ( n -- sieve )
    30 /i 1 + [ 255 ] B{ } replicate-as ; inline

PRIVATE>

:: sieve ( n -- sieve )
    n integer>fixnum-strict init-sieve :> sieve
    sieve upper-bound >fixnum :> upper
    3 upper sqrt 2 <range> [| i |
        i sieve marked-unsafe? [
            i upper sieve unmark-multiples
        ] when
    ] each sieve ;

: marked-prime? ( n sieve -- ? )
    [ integer>fixnum-strict ] dip
    2dup upper-bound 2 swap between? [ bounds-error ] unless
    over { 2 3 5 } member? [ 2drop t ] [ marked-unsafe?  ] if ;
{'fraction_non_alphanumeric': 0.11839323467230443, 'fraction_numerical': 0.02778616732105104, 'mean_word_length': 2.224926971762415, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5919579', 'n_tokens_mistral': 1241, 'n_tokens_neox': 1139, 'n_words': 419}