Naming
Oh my, what would Mr.Maintainer think if he would inherit the code... single letter variable names, methodnames like fF. He would have a hard time to figure out what is happening.
So let us clean this a little bit
public int fF(int possiblePrime)
{
int baseNumber = 2, v = 0;
while (baseNumber < possiblePrime)
{
int exponent = possiblePrime - 1;
v = operate(baseNumber, exponent, possiblePrime);
if (v != 1)
break;
baseNumber++;
}
return baseNumber;
}
int operate(int baseNumber, int exponent, int divisor)
{
if (exponent == 2)
return (baseNumber * baseNumber) % divisor;
return (exponent % 2 != 0) ? (baseNumber * operate(baseNumber, exponent - 1, divisor)) % divisor : (operate(baseNumber, exponent / 2, divisor) * operate(baseNumber, exponent / 2, divisor)) % divisor;
}
Style
As many will agree, using braces {}
, for single if
statements also, is a have to.So let us use them and also let us remove the tenary expression and add an int result
which we will return
public int fF(int possiblePrime)
{
int baseNumber = 2, v = 0;
while (baseNumber < possiblePrime)
{
int exponent = possiblePrime - 1;
v = operate(baseNumber, exponent, possiblePrime);
if (v != 1)
{
break;
}
baseNumber++;
}
return baseNumber;
}
int operate(int baseNumber, int exponent, int divisor)
{
int result = 0;
if (exponent == 2)
{
result = (baseNumber * baseNumber) % divisor;
}
else if (exponent % 2 != 0)
{
result = (baseNumber * operate(baseNumber, exponent - 1, divisor)) % divisor;
}
else
{
result = (operate(baseNumber, exponent / 2, divisor) * operate(baseNumber, exponent / 2, divisor)) % divisor;
}
return result;
}
Refactoring
Now let us focus on operate()
What you are doing, is always calling number * number % divisor
so let us extract this to a method
private int calculateProductModulo(int firstValue, int secondValue, int moduloNumber)
{
return (firstValue * secondValue) % moduloNumber;
}
The operate()
method now looks
int operate(int baseNumber, int exponent, int divisor)
{
int result = 0;
if (exponent == 2)
{
result = calculateProductModulo(baseNumber, baseNumber, divisor);
}
else if (exponent % 2 != 0)
{
result = calculateProductModulo(baseNumber, operate(baseNumber, exponent - 1, divisor), divisor);
}
else
{
result = calculateProductModulo(operate(baseNumber, exponent / 2, divisor), operate(baseNumber, exponent / 2, divisor), divisor);
}
return result;
}
If we now extract the recursive calls out of the call to calculateProductModulo()
we will see clearly what you have stated in your answer
int operate(int baseNumber, int exponent, int divisor)
{
int result = 0;
if (exponent == 2)
{
result = calculateProductModulo(baseNumber, baseNumber, divisor);
}
else if (exponent % 2 != 0)
{
int recursiveResult = operate(baseNumber, exponent - 1, divisor);
result = calculateProductModulo(baseNumber, recursiveResult, divisor);
}
else
{
int recursiveResult1 = operate(baseNumber, exponent / 2, divisor);
int recursiveResult2 = operate(baseNumber, exponent / 2, divisor);
result = calculateProductModulo(recursiveResult1, recursiveResult2, divisor);
}
return result;
}
The code is calling 2 times the same method with the same arguements.
Let us eleminate the double calling
int operate(int baseNumber, int exponent, int divisor)
{
int result = 0;
int recursiveResult = 0
if (exponent == 2)
{
result = calculateProductModulo(baseNumber, baseNumber, divisor);
}
else if (exponent % 2 != 0)
{
recursiveResult = operate(baseNumber, exponent - 1, divisor);
result = calculateProductModulo(baseNumber, recursiveResult, divisor);
}
else
{
recursiveResult = operate(baseNumber, exponent / 2, divisor);
result = calculateProductModulo(recursiveResult , recursiveResult , divisor);
}
return result;
}
return
statement... \$\endgroup\$ – Quaxton Hale Oct 7 '14 at 8:09