|
Post by mayhew61 on Mar 13, 2021 20:48:43 GMT -5
I'm trying to translate the Miller-Rabin primality test as a learning exercise, and it's crashing after about 11 loops of running normally.
It looks functionally identical to the one in Rosetta Code, but I'm clearly doing something wrong. I'll post the code soon. Until then, what does this error mean? The log is no help.
|
|
|
Post by Brandon Parker on Mar 13, 2021 21:09:43 GMT -5
Basically, you have attempted to access something that is not there. If you can post the code, we can help you out pretty easily most likely. The one posted for Liberty BASIC on Rosetta Code works fine on my machine. {:0) Brandon Parker
|
|
|
Post by mayhew61 on Mar 13, 2021 23:24:41 GMT -5
It works on Rosetta Code, I'm just working through it to brush up on both my programming and number theory. I'll post the code when my laptop is charged up again.
|
|
|
Post by metro on Mar 13, 2021 23:25:46 GMT -5
|
|
|
Post by Rod on Mar 14, 2021 4:59:56 GMT -5
11 is smart thinking. But to save us guessing run the program with the debugger. Click on the ladybug icon then >>> You will then see the program run and it should stop with the offending line highlighted. Be sure you have the foot of the IDE in view as it has error reporting messages. Sometimes that can be off screen.
You can also post the error.log which will give us a clue as well.
|
|
|
Post by mayhew61 on Mar 14, 2021 22:11:43 GMT -5
Thank you for looking into this! I haven't uploaded the code yet, because I did turn on debugger, found part of the problem.
I had cut/pasted code from another program that never passed an even number to the function. Little things! Anyway, I'm dead tired and it's still not behaving. I'll get back bright and early. Thanks again! Mark
|
|
|
Post by mayhew61 on Mar 15, 2021 12:52:32 GMT -5
Making progress. It calculates correctly, but the code is a mess, because LB doesn't have CONTINUE for loops. Can't complain though. This is the only language I know that can use arbitrarily large integers without a DLL or external library.
|
|
|
Post by tsh73 on Mar 15, 2021 14:39:10 GMT -5
GOTO is poor man CONTINUE
for i = 1 to N ...some stuff if someCondition then [CONT] ...some more stuff [CONT] next
|
|
|
Post by mayhew61 on Mar 16, 2021 13:23:55 GMT -5
It really is the poor man's continue, I'm just just surprised it's not included (suggestion for next version?). Strangely though I had to use it as a substitute for a regular loop structure. I'm about to try posting this from my phone. It gave me an error with every combination of do/while/until and while/wend.
Still, I'm confident it's the smallest implementation of Miller-Rabin you can get in Liberty Basic.
|
|
|
Post by mayhew61 on Mar 16, 2021 13:24:40 GMT -5
Edit: This was adapted from pseudocode on hackerearth, the Euler function I had written for another program and cut/pasted it. This took just under two hours to find two 512-bit primes in 460 tries.
Function MillerRabin(n,k) d=(n-1): c =d: s= 0: pp= 1 while (d AND 1)= 0 s=s+1:d= d/2 wend
[OuterLoop] k= k-1 a=int(rnd(1)*(n-4))+2 x= Euler(a,d,n) if (x=1) or (x=c) then goto [NxLoop]
for r=1 to (s-1) x= (x*x) MOD n if x= 1 then exit for if x= c then goto [NxLoop] next pp= 0 ' composite if for loop completes [NxLoop] if (k>0) AND (pp=1) then goto [OuterLoop] MillerRabin= pp end Function
Function Euler(a,b,n) total=1:rq=a do if (b AND 1)=1 then total=((total*rq) MOD n) b= b-1 end if b= b/2 rq=((rq*rq) mod n) loop until b = 0 Euler=total end function
|
|
|
Post by tsh73 on Mar 16, 2021 14:51:47 GMT -5
How it could be checked / supposed to work?
I loaded program from Rosetta code, pasted your function instead of MillerRabin it had. Got all tests said to be composite " Composite, found in 0 milliseconds ... Composite, found in 2109 milliseconds "
Initial program said "7 Probably Prime. Tested in 0 milliseconds ... 170141183460469231731687303715884105727 Probably Prime. Tested in 1516 milliseconds ")
This part of code bothers me
if x= c then goto [NxLoop] next pp= 0 ' composite if for loop completes [NxLoop] I remember LB being not safe about jumping out of the loop (EXIT FOR is OK).
|
|
|
Post by mayhew61 on Mar 16, 2021 16:14:53 GMT -5
Figured out the discrepancy. The OP returns a 1 for a composite number, mine returns a 1 for prime. You're right about about the janky use of GOTO. Ain't pretty. It's a work in progress.
|
|
|
Post by Brandon Parker on Mar 17, 2021 9:56:43 GMT -5
Try this as a replacement for your MillerRabin() function. It should be functionally equivalent, but prettier. Jumping out of loops is NEVER a good idea. That is a sure-fire way to corrupt the stack and cause the program to eventually crash with strange and unpredictable behavior.
Function MillerRabin(n, k) d = (n-1) : c = d : s = 0 : pp = 1 While (d And 1) = 0 s = (s + 1) : d = (d/ 2) Wend
While (k > 0) And (pp = 1) k = (k - 1) a = (Int(rnd(1) * (n - 4)) + 2) x = Euler(a, d, n) If (x <> 1) And (x <> c) Then For r = 1 To (s - 1) x = ((x * x) Mod n) If (x = 1) Then Exit For If (x = c) Then Exit For Next r If (r = (s - 1)) And (x <> c) Then pp = 0 'composite if for loop completes End If Wend MillerRabin = pp End Function
Please run the code and make sure it checks out with what is expected since I could have made a mistake changing the looping structure. I did test it against the Rosetta Code version and it checks out against the results. The speed is slightly faster for a couple, but overall I think it will be slower than the posted code. Optimization is most likely possible ...
{:0)
Brandon Parker
|
|
|
Post by Carl Gundel on Mar 17, 2021 11:28:03 GMT -5
Making progress. It calculates correctly, but the code is a mess, because LB doesn't have CONTINUE for loops. Can't complain though. This is the only language I know that can use arbitrarily large integers without a DLL or external library. You solved the isEmpty not understood problem? What was the cause? -Carl
|
|
|
Post by mayhew61 on Mar 17, 2021 21:54:51 GMT -5
@brandon: I found another work-around.
if (x=1) then pp= 2: exit for
And after the 'next':
pp= pp-1
This admittedly bizarre approach leaves a possible prime at 1, a composite set to 0, leaving the loop correctly with 'exit'
@carl: I never figured out the source of the problem. Every possible use of while/wend or do/until created the error. So I gave up and just used GOTO.
|
|