big: Fix internal_int_mod for inputs with opposite signs.

This threw off Frobenius-Underwood.

4 files changed, 37 insertions, 13 deletions

diff --git a/core/math/big/build.bat b/core/math/big/build.bat
index 43ece1054..47e940888 100644
--- a/core/math/big/build.bat
+++ b/core/math/big/build.bat
@@ -1,10 +1,10 @@
 @echo off

-odin run . -vet -define:MATH_BIG_USE_FROBENIUS_TEST=true

+:odin run . -vet -define:MATH_BIG_USE_FROBENIUS_TEST=true

 

 set TEST_ARGS=-fast-tests

-:set TEST_ARGS=

+set TEST_ARGS=

 :odin build . -build-mode:shared -show-timings -o:minimal -no-bounds-check -define:MATH_BIG_EXE=false && python test.py %TEST_ARGS%

-:odin build . -build-mode:shared -show-timings -o:size -no-bounds-check -define:MATH_BIG_EXE=false && python test.py %TEST_ARGS%

+odin build . -build-mode:shared -show-timings -o:size -no-bounds-check -define:MATH_BIG_EXE=false && python test.py %TEST_ARGS%

 :odin build . -build-mode:shared -show-timings -o:size -define:MATH_BIG_EXE=false && python test.py %TEST_ARGS%

 :odin build . -build-mode:shared -show-timings -o:speed -no-bounds-check -define:MATH_BIG_EXE=false && python test.py %TEST_ARGS%

 :odin build . -build-mode:shared -show-timings -o:speed -define:MATH_BIG_EXE=false && python test.py -fast-tests %TEST_ARGS%
\ No newline at end of file
diff --git a/core/math/big/example.odin b/core/math/big/example.odin
index fb1e51053..9c5fd6bc7 100644
--- a/core/math/big/example.odin
+++ b/core/math/big/example.odin
@@ -84,16 +84,20 @@ print :: proc(name: string, a: ^Int, base := i8(10), print_name := true, newline
 	}
 }
 
-printf :: fmt.printf;
+//printf :: fmt.printf;
 
 demo :: proc() {
 	a, b, c, d, e, f, res := &Int{}, &Int{}, &Int{}, &Int{}, &Int{}, &Int{}, &Int{};
 	defer destroy(a, b, c, d, e, f, res);
 
-	err: Error;
+	err:  Error;
+	frob:  bool;
 	prime: bool;
 
-	set(a, "3317044064679887385961981"); // Composite: 1287836182261 × 2575672364521
+	// USE_MILLER_RABIN_ONLY = true;
+
+	// set(a, "3317044064679887385961979"); // Composite: 17 × 1709 × 1366183751 × 83570142193
+	set(a, "359334085968622831041960188598043661065388726959079837"); // 6th Bell prime
 	trials := number_of_rabin_miller_trials(internal_count_bits(a));
 	{
 		SCOPED_TIMING(.is_prime);
@@ -101,7 +105,9 @@ demo :: proc() {
 	}
 	print("Candidate prime: ", a);
 	fmt.printf("%v Miller-Rabin trials needed.\n", trials);
-	fmt.printf("Is prime: %v, Error: %v\n", prime, err);
+
+	frob, err = internal_int_prime_frobenius_underwood(a);
+	fmt.printf("Frobenius-Underwood: %v, Prime: %v, Error: %v\n", frob, prime, err);
 }
 
 main :: proc() {
diff --git a/core/math/big/internal.odin b/core/math/big/internal.odin
index 6ae2f4284..81cb325d7 100644
--- a/core/math/big/internal.odin
+++ b/core/math/big/internal.odin
@@ -854,7 +854,7 @@ internal_int_mod :: proc(remainder, numerator, denominator: ^Int, allocator := c
 
 	if remainder.used == 0 || denominator.sign == remainder.sign { return nil; }
 
-	return #force_inline internal_add(remainder, remainder, numerator, allocator);
+	return #force_inline internal_add(remainder, remainder, denominator, allocator);
 }
 
 internal_int_mod_digit :: proc(numerator: ^Int, denominator: DIGIT, allocator := context.allocator) -> (remainder: DIGIT, err: Error) {
@@ -2747,9 +2747,27 @@ internal_int_count_lsb :: proc(a: ^Int) -> (count: int, err: Error) {
 	x: int;
 	#no_bounds_check for x = 0; x < a.used && a.digit[x] == 0; x += 1 {}
 
-	q := a.digit[x];
-	x *= _DIGIT_BITS;
-	x += internal_count_lsb(q);
+	when true {
+		q := a.digit[x];
+		x *= _DIGIT_BITS;
+		x += internal_count_lsb(q);
+	} else {
+		lnz := []int{
+   			4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+		};
+
+		q := a.digit[x];
+		x *= _DIGIT_BITS;
+		if q & 1 == 0 {
+			p: DIGIT;
+			for {
+				p = q & 15;
+				x += lnz[p];
+				q >>= 4;
+				if p != 0 { break; }
+			}
+		}		
+	}
 	return x, nil;
 }
 
diff --git a/core/math/big/prime.odin b/core/math/big/prime.odin
index 48c72de0d..316a9de29 100644
--- a/core/math/big/prime.odin
+++ b/core/math/big/prime.odin
@@ -185,14 +185,14 @@ internal_int_kronecker :: proc(a, p: ^Int, allocator := context.allocator) -> (k
 				a1.digit[0] + 1 cannot overflow because the MSB
 				of the DIGIT type is not set by definition.
 			 */
-			if a1.digit[0] + 1 & p1.digit[0] & 2 != 0 {
+			if ((a1.digit[0] + 1) & p1.digit[0] & 2) != 0 {
 				k = -k;
 			}
 		} else {
 			/*
 				Compute k = (-1)^((a1-1)*(p1-1)/4) * k.
 			*/
-			if a1.digit[0] & p1.digit[0] & 2 != 0 {
+			if (a1.digit[0] & p1.digit[0] & 2) != 0 {
 				k = -k;
 			}
 		}