Re: Miller Rabin Primality Test Wrong Result
On May 19, 7: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.
[snip of code].
I was going to comment on your code, but it would be easier for you to
start over, at least with the meat of the algorithm.
As you know, the algorithm you wrote is incorrect. If you look at
block labeled "pseudocode" on Wikipedia, you will see that you are
supposed to keep computation of s inside the loop:
http://en.wikipedia.org/wiki/Miller-Rabin_primality_test
I hate to be an old nag, but you really need to try harder. For
example, you wrote:
But y = x * x, so y can never be negative. In any case, this is not
what the pseudo code says, which is written out for you. You should at
least use the same variable names (s, r, d, not tempNumber) to
minimize any confusion.
Also, there is no reason to convert to a string to find a bit, but
that is secondary issue.
If I were you, I would simply code what you see, line for line,
directly from the Wikipedia page, using the exact same variable names.
It should not take you more than 1 hour to get this part right with a
bit of focus/discipline. If you get stuck, come back, and we will help
you, but there is a large difference between the code you wrote and
the algorithm as it is on the page.
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]