# Commits

committed ab7b7f3

shor fix

• Participants
• Parent commits 059fa25

# Shor.java

` 		//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;`