You are not logged in. Please login at www.codechef.com to post your questions!

×

[closed] Number of Iteration In Robin Miller algo

3
2

My Question is that what will be the effect of number of iteration in Robin miller algo sometimes it produce correct answer after passing 0 or 1 iteration sometimes it need upto 8 iteration whats the reason ?? i got AC using 1 iteration in PON (spoj) while i got AC using 8 iteration in http://www.codechef.com/MAY13/problems/WITMATH(may challenge) here is the algorithm Algorithm

Input :A number N to be tested and a variable iteration-the number of 'a' for which algorithm will test N. Output :0 if N is definitely a composite and 1 if N is probably a prime.

Write N as For each iteration Pick a random a in [1,N-1] x = mod n if x =1 or x = n-1 Next iteration for r = 1 to s-1 x = mod n if x = 1 return false if x = N-1 Next iteration return false return true

asked 25 May '13, 11:45

chandan11111's gravatar image

3★chandan11111
3.6k133555
accept rate: 10%

closed 27 May '13, 12:26

The question has been closed for the following reason "The question is answered, right answer was accepted" by chandan11111 27 May '13, 12:26


It highly depends on the input and also the random numbers generated!!!

you can go through this link!!

link

answered 25 May '13, 12:35

kunal361's gravatar image

4★kunal361
6.0k133272
accept rate: 21%

thnxx @kunal361

(25 May '13, 18:45) chandan111113★

Yes it depends on random numbers. You are lucky if you got AC in minimum iterations.

link

answered 25 May '13, 17:15

simle_coders's gravatar image

1★simle_coders
023
accept rate: 0%

2

ok all depends on luck :P hahah

(25 May '13, 18:46) chandan111113★

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×16
×1

question asked: 25 May '13, 11:45

question was seen: 1,179 times

last updated: 27 May '13, 12:26