summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authormbkma <[email protected]>2020-04-08 01:11:48 +0200
committerGitHub <[email protected]>2020-04-08 01:11:48 +0200
commit8bdf0d013359d295e7b26b46d553c9525d7ed0cb (patch)
tree96235fd9d2df5736553ecc884a9f1b0050ae2365 /src
parent2e5b3891e485237a7860a84b141a770b0a867ea1 (diff)
downloadmate-calc-8bdf0d013359d295e7b26b46d553c9525d7ed0cb.tar.bz2
mate-calc-8bdf0d013359d295e7b26b46d553c9525d7ed0cb.tar.xz
Add modular exponentiation ability and add acccording tests
Diffstat (limited to 'src')
-rw-r--r--src/mp.c68
-rw-r--r--src/mp.h3
-rw-r--r--src/parserfunc.c25
-rw-r--r--src/test-mp-equation.c5
4 files changed, 87 insertions, 14 deletions
diff --git a/src/mp.c b/src/mp.c
index c66285e..d7fcc75 100644
--- a/src/mp.c
+++ b/src/mp.c
@@ -383,7 +383,7 @@ void
mp_logarithm(int64_t n, const MPNumber *x, MPNumber *z)
{
/* log(0) undefined */
- if (mp_is_zero(x))
+ if (mp_is_zero(x))
{
/* Translators: Error displayed when attempting to take logarithm of zero */
mperr(_("Logarithm of zero is undefined"));
@@ -525,19 +525,65 @@ mp_modulus_divide(const MPNumber *x, const MPNumber *y, MPNumber *z)
return;
}
- mp_set_from_mp(x, z);
- mp_divide(x, y, z);
- mp_floor(z, z);
- mp_multiply(z, y, z);
- mp_subtract(x, z, z);
-
MPNumber t1 = mp_new();
+ MPNumber t2 = mp_new();
+
+ mp_divide(x, y, &t1);
+ mp_floor(&t1, &t1);
+ mp_multiply(&t1, y, &t2);
+ mp_subtract(x, &t2, z);
+
mp_set_from_integer(0, &t1);
if ((mp_compare(y, &t1) < 0 && mp_compare(z, &t1) > 0) ||
(mp_compare(y, &t1) > 0 && mp_compare(z, &t1) < 0))
mp_add(z, y, z);
mp_clear(&t1);
+ mp_clear(&t2);
+}
+
+
+void
+mp_modular_exponentiation(const MPNumber *x, const MPNumber *y, const MPNumber *p, MPNumber *z)
+{
+ MPNumber base_value = mp_new();
+ MPNumber exp_value = mp_new();
+ MPNumber ans = mp_new();
+ MPNumber two = mp_new();
+ MPNumber tmp = mp_new();
+
+ mp_set_from_integer(1, &ans);
+ mp_set_from_integer(2, &two);
+ mp_abs(y, &exp_value);
+
+ if (mp_is_negative(y))
+ mp_reciprocal(x, &base_value);
+ else
+ mp_set_from_mp(x, &base_value);
+
+ while (!mp_is_zero(&exp_value))
+ {
+ mp_modulus_divide(&exp_value, &two, &tmp);
+
+ bool is_even = mp_is_zero(&tmp);
+ if (!is_even)
+ {
+ mp_multiply(&ans, &base_value, &ans);
+ mp_modulus_divide(&ans, p, &ans);
+ }
+ mp_multiply(&base_value, &base_value, &base_value);
+ mp_modulus_divide(&base_value, p, &base_value);
+ mp_divide_integer(&exp_value, 2, &exp_value);
+ mp_floor(&exp_value, &exp_value);
+ }
+
+ mp_modulus_divide(&ans, p, z);
+
+ mp_clear(&base_value);
+ mp_clear(&exp_value);
+ mp_clear(&ans);
+ mp_clear(&two);
+ mp_clear(&tmp);
}
@@ -694,7 +740,7 @@ mp_factorize(const MPNumber *x)
list = g_list_append(list, factor);
factor = g_slice_alloc0(sizeof(MPNumber));
mpc_init2(factor->num, PRECISION);
- }
+ }
else
{
mp_add_integer(&divisor, 2, &tmp);
@@ -707,8 +753,8 @@ mp_factorize(const MPNumber *x)
{
mp_set_from_mp(&value, factor);
list = g_list_append(list, factor);
- }
- else
+ }
+ else
{
mpc_clear(factor->num);
g_slice_free(MPNumber, factor);
@@ -758,7 +804,7 @@ mp_factorize_unit64(uint64_t n)
mp_set_from_unsigned_integer(n, factor);
list = g_list_append(list, factor);
}
- else
+ else
{
mpc_clear(factor->num);
g_slice_free(MPNumber, factor);
diff --git a/src/mp.h b/src/mp.h
index f57ff16..3e03089 100644
--- a/src/mp.h
+++ b/src/mp.h
@@ -204,6 +204,9 @@ void mp_factorial(const MPNumber *x, MPNumber *z);
/* Sets z = x mod y */
void mp_modulus_divide(const MPNumber *x, const MPNumber *y, MPNumber *z);
+/* Sets z = x ^ y mod p */
+void mp_modular_exponentiation(const MPNumber *x, const MPNumber *y, const MPNumber *p, MPNumber *z);
+
/* Sets z = x^y */
void mp_xpowy(const MPNumber *x, const MPNumber *y, MPNumber *z);
diff --git a/src/parserfunc.c b/src/parserfunc.c
index ff5c6f4..c63ff96 100644
--- a/src/parserfunc.c
+++ b/src/parserfunc.c
@@ -688,10 +688,29 @@ pf_do_mod(ParseNode* self)
mp_free(left);
if(right)
mp_free(right);
- free(ans);
+ mp_free(ans);
return NULL;
}
- mp_modulus_divide(left, right, ans);
+ if (self->left->evaluate == pf_do_x_pow_y)
+ {
+ MPNumber* base_value = (MPNumber*) (*(self->left->left->evaluate))(self->left->left);
+ MPNumber* exponent = (MPNumber*) (*(self->left->right->evaluate))(self->left->right);
+ if(!base_value || !exponent)
+ {
+ if(base_value)
+ mp_free(base_value);
+ if(exponent)
+ mp_free(exponent);
+ mp_free(ans);
+ return NULL;
+ }
+ mp_modular_exponentiation(base_value, exponent, right, ans);
+ mp_free(base_value);
+ mp_free(exponent);
+ }
+ else
+ mp_modulus_divide(left, right, ans);
+
mp_free(left);
mp_free(right);
return ans;
@@ -769,7 +788,7 @@ pf_do_add(ParseNode* self)
return ans;
}
-/*Add (x) Percentage to value. */
+/* Add (x) Percentage to value. */
void*
pf_do_add_percent(ParseNode* self)
{
diff --git a/src/test-mp-equation.c b/src/test-mp-equation.c
index c1c136a..c6ab98c 100644
--- a/src/test-mp-equation.c
+++ b/src/test-mp-equation.c
@@ -482,6 +482,11 @@ test_equations(void)
test("8 mod 7", "1", 0);
test("−1 mod 7", "6", 0);
+ test("123^456 mod 78", "27", 0);
+ test("2^2 mod 2", "0", 0);
+ test("1^0 mod 2", "1", 0);
+ test("2^1 mod 1", "0", 0);
+
test("sgn 0", "0", 0);
test("sgn 3", "1", 0);
test("sgn −3", "−1", 0);