nl_tokens: Determine the period of f ( i . e . find r such that f ( x ) = f ( x + r ) .
pl_tokens: 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 ( <mask> / 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' ; }