diff options
| author | Jeroen van Rijn <Kelimion@users.noreply.github.com> | 2021-07-26 14:55:03 +0200 |
|---|---|---|
| committer | Jeroen van Rijn <Kelimion@users.noreply.github.com> | 2021-08-11 20:59:51 +0200 |
| commit | 5f7aeb30450cb9ca794ffe45949f77ed67836ecf (patch) | |
| tree | d2e94a7e1d68bc9eb9043126d11b84d11b2941b9 /core/math | |
| parent | 1ebaa9fb3b64cb6f93bad066a2d0c8e2737dbe5b (diff) | |
big: Add `mod` and `addmod`.
Diffstat (limited to 'core/math')
| -rw-r--r-- | core/math/big/basic.odin | 52 | ||||
| -rw-r--r-- | core/math/big/example.odin | 10 |
2 files changed, 54 insertions, 8 deletions
diff --git a/core/math/big/basic.odin b/core/math/big/basic.odin index 0807581b5..fe443db87 100644 --- a/core/math/big/basic.odin +++ b/core/math/big/basic.odin @@ -662,14 +662,60 @@ int_div :: proc(quotient, remainder, numerator, denominator: ^Int) -> (err: Erro */
if quotient == nil && remainder == nil { return .None; }
-
if err = clear_if_uninitialized(numerator); err != .None { return err; }
if err = clear_if_uninitialized(denominator); err != .None { return err; }
- return _int_div_small(quotient, remainder, numerator, denominator);
+ z: bool;
+ if z, err = is_zero(denominator); z { return .Division_by_Zero; }
+
+ /*
+ If numerator < denominator then quotient = 0, remainder = numerator.
+ */
+ c: int;
+ if c, err = cmp_mag(numerator, denominator); c == -1 {
+ if remainder != nil {
+ if err = copy(remainder, numerator); err != .None { return err; }
+ }
+ if quotient != nil {
+ zero(quotient);
+ }
+ return .None;
+ }
+
+ if false && (denominator.used > 2 * _MUL_KARATSUBA_CUTOFF) && (denominator.used <= (numerator.used/3) * 2) {
+ // err = _int_div_recursive(quotient, remainder, numerator, denominator);
+ } else if false {
+ // err = _int_div_school(quotient, remainder, numerator, denominator);
+ } else {
+ err = _int_div_small(quotient, remainder, numerator, denominator);
+ }
+
+ return err;
}
div :: proc{ int_div, };
+/*
+ remainder = numerator % denominator.
+ 0 <= remainder < denominator if denominator > 0
+ denominator < remainder <= 0 if denominator < 0
+*/
+int_mod :: proc(remainder, numerator, denominator: ^Int) -> (err: Error) {
+ if err = div(nil, remainder, numerator, denominator); err != .None { return err; }
+
+ z: bool;
+ if z, err = is_zero(remainder); z || denominator.sign == remainder.sign { return .None; }
+ return add(remainder, remainder, numerator);
+}
+mod :: proc { int_mod, };
+
+/*
+ remainder = (number + addend) % modulus.
+*/
+int_addmod :: proc(remainder, number, addend, modulus: ^Int) -> (err: Error) {
+ if err = add(remainder, number, addend); err != .None { return err; }
+ return mod(remainder, remainder, modulus);
+}
+addmod :: proc { int_addmod, };
/*
==========================
@@ -974,7 +1020,7 @@ _int_sqr :: proc(dest, src: ^Int) -> (err: Error) { }
/*
- Fivide by three (based on routine from MPI and the GMP manual).
+ Divide by three (based on routine from MPI and the GMP manual).
*/
_int_div_3 :: proc(quotient, numerator: ^Int) -> (remainder: int, err: Error) {
/*
diff --git a/core/math/big/example.odin b/core/math/big/example.odin index 6ceeb4d26..5a7976a88 100644 --- a/core/math/big/example.odin +++ b/core/math/big/example.odin @@ -67,16 +67,16 @@ demo :: proc() { destination, source, quotient, remainder, numerator, denominator := &Int{}, &Int{}, &Int{}, &Int{}, &Int{}, &Int{}; defer destroy(destination, source, quotient, remainder, numerator, denominator); - err = set (numerator, 2); - err = set (denominator, 3); - err = zero(quotient); + err = set (numerator, 3); + err = set (denominator, 2); + err = set (quotient, 3); err = zero(remainder); - err = pow(numerator, numerator, 260); + err = addmod(remainder, numerator, denominator, quotient); if err != .None { fmt.printf("Error: %v\n", err); } else { - print("numerator ", numerator, 16); + print("numerator ", numerator, 10); print("denominator", denominator, 10); print("quotient ", quotient, 10); print("remainder ", remainder, 10); |