diff options
| author | Jeroen van Rijn <Kelimion@users.noreply.github.com> | 2021-07-22 18:12:19 +0200 |
|---|---|---|
| committer | Jeroen van Rijn <Kelimion@users.noreply.github.com> | 2021-08-11 20:59:51 +0200 |
| commit | d4d863c4db6fcc893ff3a04ff3ef4ca1ef757f4c (patch) | |
| tree | 8838608941394ad2256372c3d7254b6a759e260b /core/math | |
| parent | 78c0877994427d1c215c00a0623ce4d9a0bfb542 (diff) | |
big: Add `mod_power_of_two`.
Diffstat (limited to 'core/math')
| -rw-r--r-- | core/math/big/basic.odin | 59 | ||||
| -rw-r--r-- | core/math/big/example.odin | 8 |
2 files changed, 55 insertions, 12 deletions
diff --git a/core/math/big/basic.odin b/core/math/big/basic.odin index 7a3bbf751..42db8b88e 100644 --- a/core/math/big/basic.odin +++ b/core/math/big/basic.odin @@ -322,7 +322,7 @@ int_sub_digit :: proc(dest, a: ^Int, digit: DIGIT) -> (err: Error) { carry := dest.digit[i] >> ((size_of(DIGIT) * 8) - 1);
dest.digit[i] &= _MASK;
}
- }
+ }
zero_count := old_used - dest.used;
/*
@@ -374,13 +374,13 @@ int_halve :: proc(dest, src: ^Int) -> (err: Error) { Shift the current digit, add in carry and store.
*/
dest.digit[x] = (src_digit >> 1) | (fwd_carry << (_DIGIT_BITS - 1));
- /*
- Forward carry to next iteration.
- */
- fwd_carry = carry;
- }
+ /*
+ Forward carry to next iteration.
+ */
+ fwd_carry = carry;
+ }
- zero_count := old_used - dest.used;
+ zero_count := old_used - dest.used;
/*
Zero remainder.
*/
@@ -447,7 +447,7 @@ int_double :: proc(dest, src: ^Int) -> (err: Error) { */
dest.digit[dest.used] = 1;
}
- zero_count := old_used - dest.used;
+ zero_count := old_used - dest.used;
/*
Zero remainder.
*/
@@ -463,6 +463,49 @@ int_double :: proc(dest, src: ^Int) -> (err: Error) { double :: proc { int_double, };
shl1 :: double;
+
+/*
+ dest = src % (2^power);
+*/
+int_mod_power_of_two :: proc(dest, src: ^Int, power: int) -> (err: Error) {
+ dest := dest; src := src;
+ if err = clear_if_uninitialized(dest); err != .None {
+ return err;
+ }
+ if err = clear_if_uninitialized(src); err != .None {
+ return err;
+ }
+
+ if power < 0 { return .Invalid_Argument; }
+ if power == 0 { return zero(dest); }
+
+ /*
+ If the modulus is larger than the value, return the value.
+ */
+ err = copy(dest, src);
+ if power >= (src.used * _DIGIT_BITS) || err != .None {
+ return;
+ }
+
+ /*
+ Zero digits above the last digit of the modulus.
+ */
+ zero_count := (power / _DIGIT_BITS) + 0 if (power % _DIGIT_BITS == 0) else 1;
+ /*
+ Zero remainder.
+ */
+ if zero_count > 0 {
+ mem.zero_slice(dest.digit[zero_count:]);
+ }
+
+ /*
+ Clear the digit that is not completely outside/inside the modulus.
+ */
+ dest.digit[power / _DIGIT_BITS] &= DIGIT(1 << DIGIT(power % _DIGIT_BITS)) - DIGIT(1);
+ return clamp(dest);
+}
+mod_power_of_two :: proc { int_mod_power_of_two, };
+
/*
==========================
Low-level routines
diff --git a/core/math/big/example.odin b/core/math/big/example.odin index 014e19af6..1b8503233 100644 --- a/core/math/big/example.odin +++ b/core/math/big/example.odin @@ -57,16 +57,16 @@ demo :: proc() { a, b, c := &Int{}, &Int{}, &Int{}; defer destroy(a, b, c); - err = set(a, 0); - a.used = 2; - a.digit[1] = 1; + err = set(a, -512); err = set(b, 1); err = set(c, -4); + + err = mod_power_of_two(a, a, 10); fmt.printf("%v (%v)\n", int_get_float(a)); - print("a", a, 16); + print("a", a, 10); print("b", b, 10); print("c", c, 10); |