<commit_before>USING: combinators combinators.lib io locals kernel math
math.functions math.ranges namespaces random sequences ;
IN: math.miller-rabin

SYMBOL: a
SYMBOL: n
SYMBOL: r
SYMBOL: s
SYMBOL: count
SYMBOL: trials

: >even ( n -- int )
    dup even? [ 1- ] unless ; foldable

: >odd ( n -- int )
    dup even? [ 1+ ] when ; foldable

: next-odd ( m -- n )
    dup even? [ 1+ ] [ 2 + ] if ;

: random-bits ( m -- n ) 2^ random ; foldable

: (factor-2s) ( s n -- s n )
    dup even? [ -1 shift >r 1+ r> (factor-2s) ] when ;

: factor-2s ( n -- r s )
    #! factor an even number into 2 ^ s * m
    dup even? over 0 > and [
        "input must be positive and even" throw
    ] unless 0 swap (factor-2s) ;

:: (miller-rabin) | n prime?! |
    n 1- factor-2s s set r set
    trials get [
        n 1- [1,b] random a set
        a get s get n ^mod 1 = [
            0 count set
            r get [
                2^ s get * a get swap n ^mod n - -1 = [
                    count [ 1+ ] change
                    r get +
                ] when
            ] each<commit_msg>small cleanup in miller-rabin<commit_after>USING: combinators combinators.lib io locals kernel math
math.functions math.ranges namespaces random sequences ;
IN: math.miller-rabin

SYMBOL: a
SYMBOL: n
SYMBOL: r
SYMBOL: s
SYMBOL: count
SYMBOL: trials

: >even ( n -- int )
    dup even? [ 1- ] unless ; foldable

: >odd ( n -- int )
    dup even? [ 1+ ] when ; foldable

: next-odd ( m -- n )
    dup even? [ 1+ ] [ 2 + ] if ;

: random-bits ( m -- n ) 2^ random ; foldable

: factor-2s ( n -- r s )
    #! factor an even number into 2 ^ s * m
    dup even? [ -1 shift >r 1+ r> factor-2s ] when ;

:: (miller-rabin) | n prime?! |
    0 n 1- factor-2s s set r set
    trials get [
        n 1- [1,b] random a set
        a get s get n ^mod 1 = [
            0 count set
            r get [
                2^ s get * a get swap n ^mod n - -1 = [
                    count [ 1+ ] change
                    r get +
                ] when
            ] each
{'fraction_non_alphanumeric': 0.12173484475110892, 'fraction_numerical': 0.021192705766387383, 'mean_word_length': 1.5826972010178118, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2001056', 'n_tokens_mistral': 723, 'n_tokens_neox': 696, 'n_words': 272}