math.primes: Check for prime before running pollard-rho-brent

rename brent-factors to pollard-rho-brent

diff --git a/basis/math/primes/factors/factors-tests.factor b/basis/math/primes/factors/factors-tests.factor
index 02610e941e2a8544d46b891b26adfd4814915bcf..7a29c7c8df203bcd6392671e037a91ba9c116893 100644 (file)
--- a/basis/math/primes/factors/factors-tests.factor
+++ b/basis/math/primes/factors/factors-tests.factor
@@ -1,4 +1,4 @@
-USING: math.primes.factors sequences tools.test ;
+USING: math math.primes.factors sequences tools.test ;
 
 { { 999983 999983 1000003 } } [ 999969000187000867 factors ] unit-test
 { { } } [ -5 factors ] unit-test
@@ -11,3 +11,38 @@ USING: math.primes.factors sequences tools.test ;
 { { 1 2 3 4 6 8 12 24 } } [ 24 divisors ] unit-test
 { 24 } [ 360 divisors length ] unit-test
 { { 1 } } [ 1 divisors ] unit-test
+
+
+{ { 618970019642690137449562111 } } [
+    618970019642690137449562111 factors ! 89 2^ 1 -, prime
+] unit-test
+
+{
+    { 162259276829213363391578010288127 }
+} [
+    ! Mersenne Prime M107
+    107 2^ 1 - factors
+] unit-test
+
+{
+    { 2316528667279 8168603188573 }
+} [
+    18922803457956001611802867 factors
+] unit-test
+
+{ { 35742549198872617291353508656626642567 } } [
+    35742549198872617291353508656626642567 factors ! bell number prime
+] unit-test
+
+! Too slow
+! {
+!     {
+!         618970019642690137449562111
+!         162259276829213363391578010288127
+!         170141183460469231731687303715884105727
+!     }
+! } [
+!     89 2^ 1 -
+!     107 2^ 1 -
+!     127 2^ 1 - * * factors
+! ] unit-test
\ No newline at end of file

diff --git a/basis/math/primes/factors/factors.factor b/basis/math/primes/factors/factors.factor
index ba0c613e32e20ee5289ffecfe989ef1ebb50533b..aff87c5317da993f1c300dad8095ef21078ab5ac 100644 (file)
--- a/basis/math/primes/factors/factors.factor
+++ b/basis/math/primes/factors/factors.factor
@@ -35,7 +35,7 @@ PRIVATE>
 
 : unique-factors ( n -- seq ) group-factors keys ; flushable
 
-: factors ( n -- seq ) brent-factors ; flushable
+: factors ( n -- seq ) pollard-rho-brent-factors ; flushable
 
 : totient ( n -- t )
     {

diff --git a/basis/math/primes/pollard-rho-brent/pollard-rho-brent-tests.factor b/basis/math/primes/pollard-rho-brent/pollard-rho-brent-tests.factor
index cff46202ed6883b4903876ec062c6c18610f52d4..8fad4e046fdfde28bbbc5b1d4d030de4cb30273c 100644 (file)
--- a/basis/math/primes/pollard-rho-brent/pollard-rho-brent-tests.factor
+++ b/basis/math/primes/pollard-rho-brent/pollard-rho-brent-tests.factor
@@ -3,6 +3,6 @@
 USING: math.primes.pollard-rho-brent sorting tools.test ;
 IN: math.primes.pollard-rho-brent.tests
 
-{ { 2 2 2507191691 1231026625769 } } [ 12345678910111213141516 brent-factors ] unit-test
-{ { 2 2 2 2 3 257 7221391 696389341 } } [ 62036506940903331216 brent-factors ] unit-test
-{ { 13 4253 15823 32472893749823741 } } [ 28408516453955558205925627 brent-factors ] unit-test
+{ { 2 2 2507191691 1231026625769 } } [ 12345678910111213141516 pollard-rho-brent-factors ] unit-test
+{ { 2 2 2 2 3 257 7221391 696389341 } } [ 62036506940903331216 pollard-rho-brent-factors ] unit-test
+{ { 13 4253 15823 32472893749823741 } } [ 28408516453955558205925627 pollard-rho-brent-factors ] unit-test

diff --git a/basis/math/primes/pollard-rho-brent/pollard-rho-brent.factor b/basis/math/primes/pollard-rho-brent/pollard-rho-brent.factor
index 7ea0f673f1ef8baad324aff735e4bf2942c05b49..151cbcf288594ffbd6eaeef64c20a64e2bfa14c9 100644 (file)
--- a/basis/math/primes/pollard-rho-brent/pollard-rho-brent.factor
+++ b/basis/math/primes/pollard-rho-brent/pollard-rho-brent.factor
@@ -1,7 +1,7 @@
 ! Copyright (C) 2021 Doug Coleman.
 ! See http://factorcode.org/license.txt for BSD license.
-USING: kernel make math math.order math.primes math.ranges
-random sorting ;
+USING: arrays kernel make math math.order math.primes
+math.ranges random sorting ;
 IN: math.primes.pollard-rho-brent
 
 ! https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/
@@ -40,29 +40,34 @@ IN: math.primes.pollard-rho-brent
 : brent-factor ( n -- factor )
     dup even? [ drop 2 ] [ (brent-factor) ] if ;
 
-DEFER: brent-factors
+DEFER: pollard-rho-brent-factors
 
+! 0) can hang if given a large prime, so check prime? first
 ! 1) brent-factor can return a composite number
 ! 2) also it can hang if you give it a prime number
 ! 3) factors can be found in random order
 ! therefore we check these conditions
-:: (brent-factors) ( n! -- )
+:: (pollard-rho-brent-factors) ( n! -- )
     n brent-factor :> factor
     ! 1) check for prime
     factor prime? [
         factor ,
     ] [
-        factor brent-factors %
+        factor pollard-rho-brent-factors %
     ] if
     n factor = [
         n factor /i
         ! 2) check for prime
-        dup prime? [ , ] [ (brent-factors) ] if
+        dup prime? [ , ] [ (pollard-rho-brent-factors) ] if
     ] unless ;
 
-: brent-factors ( n! -- factors )
+: pollard-rho-brent-factors ( n! -- factors )
     dup 1 <= [
         drop { }
     ] [
-        [ (brent-factors) ] { } make
+        dup prime? [
+            1array
+        ] [
+            [ (pollard-rho-brent-factors) ] { } make
+        ] if
     ] if natural-sort ;