Talk:Miller–Rabin primality test: Difference between revisions
→Pseudocode in task description
| (4 intermediate revisions by 4 users not shown) | |||
Line 48:
== Run Basic and PureBasic problems with output ==
Tested in multiple languages all return 31 as a composite.
Line 60:
::: I haven't run the PureBasic code, but it looks like it does the base selection correctly (2 to n-2, albeit the pseudocode is 2 to n-1, so we should test input = 3) and has a continue to skip the test if x=1 or x=n-1. These were the two issues that weren't right with RunBasic. The Liberty Basic example has 200 lines of test cruft but the actual loop is broken in that it runs 11 iterations of Miller-Rabin all with the same base (7). It also looks broken in that it doesn't properly skip the loop if r = n-1. If we remove the optimization of checking small factors at the beginning, I believe it will fail if given 31 and a base of 3. IMO it should be written without this optimization and with far less code. [[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 05:41, 12 March 2016 (UTC)
:::: The PureBasic code returns these primes from 4-100: 5, 7, 11, 13, 17, 19, 23, 29, 37, 41, 73, 97. I'm not sure where it is going wrong. EDIT: it appears PureBasic is overflowing when doing the Pow(). PS- sorry I'm new here I hope you don't mind me editing the heading [[User:Bearded badger|Bearded badger]] ([[User talk:Bearded badger|talk]])
::::: Given n = 31, if we select a base of 22 then it does x = (22^15) % 31 and gets -8 as the result (instead of 30 = n-1). Similar with base 27. The Pow operation overflows very easily, so the program isn't very useful as written. It needs a powmod using a ladder (see the C deterministic code or the Go code, for examples). [[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 07:22, 12 March 2016 (UTC)
==Pseudocode in task description==
The pseudocode includes the line "for r = 1 .. s − 1". Where is r used?--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 17:26, 20 August 2019 (UTC)
: It's not, so I have updated the pseudocode replacing the '''for r''' loop with a '''repeat s-1 times''' loop. -- [[User:Markjreed|Markjreed]] ([[User talk:Markjreed|talk]]) 17:05, 28 November 2021 (UTC)
== Pari/GP ==
An extension of Pari code thru consecutive bases, where sprp is per the article. Allows confirmation of 341550071728321 passing bases 2,3,5,7,11,13,17 as well as 3215031751 with 2,3,5,7 (OEIS A074773) eg MR(3215031751,2,7).
::''MR(n,blo,bhi)={prodd=1;ctr=0;
::forprime(b=blo,bhi,ctr+=1;
::prodd= prodd* sprp(n,b); \\SO, any 0 will clear it ...
::if(prodd==0,break));
::print(prodd, " ",ctr);}''
<br>--[[User:Billymacc|Billymacc]] ([[User talk:Billymacc|talk]]) 16:53, 13 July 2021 (UTC)
| |||