Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/df/d72/modular__division_8cpp.html below:

TheAlgorithms/C++: math/modular_division.cpp File Reference

Loading...

Searching...

No Matches

An algorithm to divide two numbers under modulo p Modular Division More...

#include <cassert>
#include <cstdint>
#include <iostream>

Go to the source code of this file.

An algorithm to divide two numbers under modulo p Modular Division

To calculate division of two numbers under modulo p Modulo operator is not distributive under division, therefore we first have to calculate the inverse of divisor using Fermat's little theorem Now, we can multiply the dividend with the inverse of divisor and modulo is distributive over multiplication operation. Let, We have 3 numbers a, b, p To compute (a/b)p (a/b)p ≡ (a*(inverse(b)))p ≡ ((ap)*inverse(b)p)p NOTE: For the existence of inverse of 'b', 'b' and 'p' must be coprime For simplicity we take p as prime Time Complexity: O(log(b)) Example: ( 24 / 3 ) % 5 => 8 % 5 = 3 — (i) Now the inverse of 3 is 2 (24 * 2) % 5 = (24 % 5) * (2 % 5) = (4 * 2) % 5 = 3 — (ii) (i) and (ii) are equal hence the answer is correct.

See also

modular_inverse_fermat_little_theorem.cpp, modular_exponentiation.cpp

Definition in file modular_division.cpp.

This function calculates modular division.

Parameters

a integer dividend b integer divisor p integer modulo

Returns

a/b modulo c

Calculate the inverse of b

Calculate the final result

Definition at line 75 of file modular_division.cpp.

75 {

uint64_t inverse =

(b, p - 2, p) % p;

77 uint64_t result =

78 ((a % p) * (inverse % p)) % p;

79 return result;

80}

uint64_t power(uint64_t a, uint64_t b, uint64_t c)

This function calculates a raised to exponent b under modulo c using modular exponentiation.

This function calculates a raised to exponent b under modulo c using modular exponentiation.

Parameters

a integer base b unsigned integer exponent c integer modulo

Returns

a raised to power b modulo c

Initialize the answer to be returned

Update a if it is more than or equal to c

In case a is divisible by c;

If b is odd, multiply a with answer

b must be even now

b = b/2

Definition at line 50 of file modular_division.cpp.

50 {

51 uint64_t ans = 1;

52 a = a % c;

53 if (a == 0) {

54 return 0;

55 }

56 while (b > 0) {

58 if (b & 1) {

59 ans = ((ans % c) * (a % c)) % c;

60 }

62 b = b >> 1;

63 a = ((a % c) * (a % c)) % c;

64 }

65 return ans;

66}

Function for testing power function. test cases and assert statement.

Returns

void

Definition at line 89 of file modular_division.cpp.

89 {

91 assert(test_case_1 == 0);

92 std::cout << "Test 1 Passed!" << std::endl;

94 assert(test_case_2 == 5);

95 std::cout << "Test 2 Passed!" << std::endl;

97 assert(test_case_3 == 0);

98 std::cout << "Test 3 Passed!" << std::endl;

100 assert(test_case_4 == 2);

101 std::cout << "Test 4 Passed!" << std::endl;

103 assert(test_case_5 == 2);

104 std::cout << "Test 5 Passed!" << std::endl;

105}

uint64_t mod_division(uint64_t a, uint64_t b, uint64_t p)

This function calculates modular division.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4