Re: Miller Rabin Primality Test Wrong Result
On May 19, 8:43 am, Peter_APIIT <PeterAP...@gmail.com> wrote:
Hello to all, i have developed a miller rabin primality test program
but return me wrong result all the time.
I don't know what wrong with it after few days of debug.
Your code is littered with unnecessary initialisations and variables
which have enormous scope. You are going to have real problems with
debugging your code in the future. You should only declare variables
where you actually use them.
And if your code is really unindented as this sample indicates, nobody
will want to review it.
[code]
#include <iostream>
#include <sstream>
#include <string>
#include <bitset>
#include <vector>
#include <limits>
#include <algorithm>
#include <functional>
#include <utility>
#include <ctime>
Well, for a start, if you need 10 headers, I'd advise splitting this
up into smaller files for sanities sake.
using namespace std;
// =========================================
// =========================================
const unsigned short NITE = 50;
Meaning what? And why is this so global?
typedef unsigned long long ulong;
void Userinput(ulong&);
bool MillerRabinPrimeTest(const ulong&);
ulong ComputeModularExponentiation(const ulong&, const ulong&, const
ulong&);
ulong ComputeExponentiation(const ulong&, const ulong&);
// =========================================
int main()
{
ulong number(0);
Why no indentation. It makes it really really difficult to read.
Excessive scope and unnecessary initialisation. You only use this in
the loop below, where it always gets set.
while (1)
for (;;) by preference
{
cout << "\n";
Userinput(number);
what is wrong with returning a result? Much clearer.
cout << boolalpha << MillerRabinPrimeTest(number);
}
return 0;}
// =========================================
void Userinput(ulong& number)
{
cout << "Enter Number : ";
cin >> number;
while (cin.fail())
{
cin.clear();
cin.ignore(numeric_limits<int>::max(), '\n');
cout << "\nEnter Number : ";
cin >> number;}
}
// =========================================
bool MillerRabinPrimeTest(const ulong& number)
{
ulong a(0), x(0), y(0), tempNumber(0);
Again, excessive scope and unnecessary initialisation
bool IsPrime(false);
Why? You only use it once - right at the end, to return. This is
incredibly confusing.
tempNumber = number - 1;
if (number > 2)
{
// Write them as 2 ^ s * d
Incomprehensible comment. And it certainly doesn't describe the loop
below
while (tempNumber % 2 == 0)
{
// tempNumber is d
tempNumber /= 2;
}
And what on earth is that loop meant to achieve? If tempnumber is d,
call it d. But what about s?
for (int loop = 0;loop < NITE;++loop)
{
srand((unsigned int)time(0));
// rand() % upperBound + startnumber
a = rand() % (number - 2) + 2;
should be interesting when you pass 0, 1 or 2 to this function. And
why not name your variables the same as they are in the algorithm?
// a = primeFactor[loop];
rand() does not return prime numbers.
x = ComputeModularExponentiation(a, tempNumber, number);
y = (x * x) % number;
if (x == 1 || y == -1)
how can y possibly be negative?
{
return true;
}
}
}
return IsPrime;}
And another thing. I wouldn't put the } on the same line as the return
statement. It's not nice ti read.
// =========================================
ulong ComputeModularExponentiation(
const ulong& a, const ulong& d,
const ulong& n)
{
enum {NBITS = numeric_limits<ulong>::digits };
string bitExponent = bitset<NBITS>((unsigned long)d).to_string();
OK, I completely fail to see why you need to convert the bitset to a
string. You can index into a bitset. If you are going to do something
exotic like that, please at least explain why.
Also, as you are casting d down to unsigned long from unsigned long
long, it raises a question in my mind as to why you are using unsigned
long long in the first place.
typedef string::size_type strType;
strType MSSB = bitExponent.find_first_of('1');
ulong result(a % n);
MSSB += 1;
while (MSSB < NBITS)
{
result *= result;
if (bitExponent[MSSB] == '1')
{
result = result * a % n;
}
++MSSB;
}
return result;}
// =========================================
ulong ComputeExponentiation(const ulong& base, const ulong& exponent)
This is almost exactly the same as the above. You need to explain why
you have two almost identical functions that can't be refactored. If
you have a bug in one, chances are you'll need to fix it in both.
{
enum {NBITS = numeric_limits<ulong>::digits };
string bitExponent = bitset<NBITS>((unsigned long)exponent).to_string
();
typedef string::size_type strType;
strType MSSB = bitExponent.find_first_of('1');
ulong result(base);
MSSB += 1;
while (MSSB < NBITS)
{
result *= result;
if (bitExponent[MSSB] == '1')
{
result *= base;
}
++MSSB;
}
return result;}
// =========================================
// =========================================
// =========================================
// =========================================
// =========================================
// =========================================
[/code]
Thanks for any comments.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]