function findPeriod() {
    let bestSoFar = 1;

    for (let attempts = 0; attempts < 2 * numOutBits; attempts += 1) {
      // NOTE: Here we take advantage of the fact that, for Shor's algorithm,
      // we know that f(x) = f(x+i) ONLY when i is an integer multiple of the rank r.
      if (f(bestSoFar) === f0) {
        dbg(`The period of ${a}^x mod ${n} is ${bestSoFar}`);
        return bestSoFar;
      }

      dbg('Starting quantum computation ...');
      const sample = determineFrequency(f);
      dbg('Done quantum computation, result', { sample });

      // Each "sample" has a high probability of being approximately equal to some
      // integer multiple of (inputRange/r) rounded to the nearest integer.
      // So we use a continued fraction function to find r (or a divisor of r).
      const continuedFraction = qubitsMath.continuedFraction(
        sample / inputRange,
        accuracyRequiredForContinuedFraction,
      );
      // The denominator is a "candidate" for being r or a divisor of r (hence we need to find
      // the least common multiple of several of these).
      const candidateDivisor = continuedFraction.denominator;
      dbg('Candidate divisor of r: ', { candidateDivisor });

      // Reduce the chances of getting the wrong answer by ignoring obviously wrong results!
      if (candidateDivisor > 1 && candidateDivisor <= outputRange) {
        if (f(candidateDivisor) === f0) {
          dbg('This is a multiple of the rank');
          bestSoFar = candidateDivisor;
        } else {
          const lcm = qubitsMath.lcm(candidateDivisor, bestSoFar);
          if (lcm <= outputRange) {
            dbg('This is a good candidate');
            bestSoFar = lcm;
          }
        }
      }
      dbg('Least common multiple so far: ', { bestSoFar, attempts });
    }
    dbg(`Giving up trying to find rank of ${a}`);
    return 'failed';
  }
function findPeriod() {
    let bestSoFar = 1;

    for (let attempts = 0; attempts < 2 * numOutBits; attempts += 1) {
      
      
      if (f(bestSoFar) === f0) {
        dbg(`The period of ${a}^x mod ${n} is ${bestSoFar}`);
        return bestSoFar;
      }

      dbg('Starting quantum computation ...');
      const sample = determineFrequency(f);
      dbg('Done quantum computation, result', { sample });

      
      
      
      const continuedFraction = qubitsMath.continuedFraction(
        sample / inputRange,
        accuracyRequiredForContinuedFraction,
      );
      
      
      const candidateDivisor = continuedFraction.denominator;
      dbg('Candidate divisor of r: ', { candidateDivisor });

      
      if (candidateDivisor > 1 && candidateDivisor <= outputRange) {
        if (f(candidateDivisor) === f0) {
          dbg('This is a multiple of the rank');
          bestSoFar = candidateDivisor;
        } else {
          const lcm = qubitsMath.lcm(candidateDivisor, bestSoFar);
          if (lcm <= outputRange) {
            dbg('This is a good candidate');
            bestSoFar = lcm;
          }
        }
      }
      dbg('Least common multiple so far: ', { bestSoFar, attempts });
    }
    dbg(`Giving up trying to find rank of ${a}`);
    return 'failed';
  }
function findPeriod ( ) { let bestSoFar = 1 ; for ( let attempts = 0 ; attempts < 2 * numOutBits ; attempts += 1 ) { // NOTE: Here we take advantage of the fact that, for Shor's algorithm, // we know that f(x) = f(x+i) ONLY when i is an integer multiple of the rank r. if ( f ( bestSoFar ) === f0 ) { dbg ( ` ${ a } ${ n } ${ bestSoFar } ` ) ; return bestSoFar ; } dbg ( 'Starting quantum computation ...' ) ; const sample = determineFrequency ( f ) ; dbg ( 'Done quantum computation, result' , { sample } ) ; // Each "sample" has a high probability of being approximately equal to some // integer multiple of (inputRange/r) rounded to the nearest integer. // So we use a continued fraction function to find r (or a divisor of r). const continuedFraction = qubitsMath . continuedFraction ( sample / inputRange , accuracyRequiredForContinuedFraction , ) ; // The denominator is a "candidate" for being r or a divisor of r (hence we need to find // the least common multiple of several of these). const candidateDivisor = continuedFraction . denominator ; dbg ( 'Candidate divisor of r: ' , { candidateDivisor } ) ; // Reduce the chances of getting the wrong answer by ignoring obviously wrong results! if ( candidateDivisor > 1 && candidateDivisor <= outputRange ) { if ( f ( candidateDivisor ) === f0 ) { dbg ( 'This is a multiple of the rank' ) ; bestSoFar = candidateDivisor ; } else { const lcm = qubitsMath . lcm ( candidateDivisor , bestSoFar ) ; if ( lcm <= outputRange ) { dbg ( 'This is a good candidate' ) ; bestSoFar = lcm ; } } } dbg ( 'Least common multiple so far: ' , { bestSoFar , attempts } ) ; } dbg ( ` ${ a } ` ) ; return 'failed' ; }
Determine the period of f (i.e. find r such that f(x) = f(x+r).
Determine the period of f ( i . e . find r such that f ( x ) = f ( x + r ) .