[Mono-bugs] [Bug 54750][Min] New - BigInteger.isProbablePrime() method is inefficient

bugzilla-daemon@bugzilla.ximian.com bugzilla-daemon@bugzilla.ximian.com
Mon, 23 Feb 2004 04:44:56 -0500 (EST)


Please do not reply to this email- if you want to comment on the bug, go to the
URL shown below and enter your comments there.

Changed by pieter@mentalis.org.

http://bugzilla.ximian.com/show_bug.cgi?id=54750

--- shadow/54750	2004-02-23 04:44:56.000000000 -0500
+++ shadow/54750.tmp.15277	2004-02-23 04:44:56.000000000 -0500
@@ -0,0 +1,38 @@
+Bug#: 54750
+Product: Mono/Class Libraries
+Version: unspecified
+OS: All
+OS Details: 
+Status: NEW   
+Resolution: 
+Severity: 
+Priority: Minor
+Component: CORLIB
+AssignedTo: mono-bugs@ximian.com                            
+ReportedBy: pieter@mentalis.org               
+QAContact: mono-bugs@ximian.com
+TargetMilestone: ---
+URL: 
+Cc: 
+Summary: BigInteger.isProbablePrime() method is inefficient
+
+The method BigInteger.isProbablePrime() is inefficient because it performs 
+the same loop twice.
+This is the current method body:
+
+public bool isProbablePrime () {
+	for (int p = 0; p < smallPrimes.Length; p++) {
+		if (this % smallPrimes [p] == 0)
+			return this == smallPrimes [p];
+	}
+	for (int p = 0; p < smallPrimes.Length; p++) {
+		if (this == smallPrimes [p])
+			return true;
+		if (this % smallPrimes [p] == 0)
+			return false;
+	}
+	...
+}
+
+As you can see, both loops do exactly the same so the second loop can and 
+should be removed.