Commits

Duncan McBain committed ab7b7f3

shor fix

  • Participants
  • Parent commits 059fa25

Comments (0)

Files changed (1)

 		//Create an array of complex numbers large enough to represent q in a register
 		entangled = new Complex[(int)Math.pow(2,findRegisterSize(n))];
 
+		// control variables - either we're done or we're taking too long.
 		boolean done = false, fail = false;
+		// Tracking our iterations.
 		int count = 0;
-		x = rng.nextInt(n);
+		// First random x, will be refined in the loop if necessary.
 		while (!done)
 		{
+			x = rng.nextInt(n);
+			while((gcd(x,n) != 1) || (x <= 1))
+				x = rng.nextInt(n);
 			moddedExponents = new int[q];
 			count++;
 			if (count > 20)
 			for(int i = 0; i < entangled.length; ++i)
 				entangled[i] = new Complex(0,0);
 
-			while((gcd(x,n) != 1) || (x <= 1))
-				x = rng.nextInt(n);
-	
-		
-	
 			for(int i = 0; i < q; i++)
 			{
 				value_position = modularPower(x, i, n);
 				moddedExponents[i] = value_position;
 				entangled[value_position].addToMe(constant);
 			}
-	
+
 			outState = new QubitRegister(entangled);
 			outState.normalise();
 
 			
 			// So we get it from this function.
 			int bestDenominator = findDenominator(c,q);
-			// This is the numerator.
-			int p = (int)Math.floor(bestDenominator*c + 0.5);
 			// If the denominator isn't even, it probably won't work. There are ways around this, but...
 			if(bestDenominator % 2 == 0)
-				continue;
+				if(bestDenominator*2 < q)
+					bestDenominator *= 2;
+				else
+					continue;
 			// There are two roots formed from this expression; the GCD of each with n is calculated. Hopefully, we have
 			// some nontrivial ones! OTOH the program can return 1 and n.
 			int expd = modularPower(x, bestDenominator/2, n);
 		return size;
 	}
 
-	/*public static int findDenominator(double value)
-	{
-		double r, y, error = Double.MAX_VALUE;
-		int a;
-		int[] p,q;
-		p = new int[3];
-		q = new int[3];
-		a = (int)Math.floor(value);
-		r = value - (double)a;
-		y = 1/r;
-		p[2] = 0; p[1] = 1;
-		q[2] = 1; q[1] = 0;
-		p[0] = a*p[1] + p[2];
-		q[0] = a*q[1] + q[2];
-		p[2] = p[1]; p[1] = p[0];
-		q[2] = q[1]; q[1] = q[0];
-		error = 1 + (double)p[0]/(double)q[0];
-		System.out.println(p[0]+"/"+q[0]+" "+error);
-		while(error > 0.01)
-		{
-			a = (int)Math.floor(y);
-			r = y - a;
-			y = 1/r;
-			p[0] = a*p[1] + p[2];
-			q[0] = a*q[1] + q[2];
-			p[2] = p[1]; p[1] = p[0];
-			q[2] = q[1]; q[1] = q[0];
-			error = Math.abs((double)p[0]/(double)q[0] - (double)p[1]/(double)q[1]);
-			System.out.println(p[0]+"/"+q[0]+" "+error);
-		}
-		return q[0];
-	}*/
 	public static int findDenominator(double c, int maxQ)
 	{
-		double y = c;
-		double z;
+		double z, y = c;
 		int q0 = 0;
 		int q1 = 1;
 		int q2 = 0;
 		while(true)
 		{
 			z = y - Math.floor(y);
-			if (z < 0.5 / Math.pow(maxQ,2))
+			if (z < 0.5 /(maxQ*maxQ))
 				return q1;
 			if (z != 0)
 				y = 1 / z;
 			else
 				return q1;
-			q2 = (int)Math.floor(y) * q1 + q0;
+			q2 = (int)Math.floor(y)*q1 + q0;
 			if (q2 >= maxQ)
 				return q1;
 			q0 = q1;