Computer-Implemented Method for Deciding Whether a Random Number is Larger or Smaller Than a Given Threshold

Abstract

A method is provided for that includes representing a random number and a threshold as a sequence of bits and comparing the sequence of bits representing the random number with the sequence of bits representing the threshold on a bit-wise basis. The most significant bit of the sequence of bits representing the random number is compared with the most significant sequence of bits representing the threshold. If the bits are not equal, deciding that the random number is larger or smaller than the threshold. If the bits are equal, comparing the immediately following bit in the sequence of bits representing the random number with the immediately following bit in the sequence of bits representing the threshold, and repeating this until the bit of the random number does not equal that of the threshold is reached or until all bits have been compared and found to be equal.

Claims

1. A method comprising: representing a random number as a first sequence of bits and representing a threshold as a second sequence of bits; and comparing, by a comparator, the first sequence of bits representing the random number with the second sequence of bits representing the threshold on a bit-wise basis, wherein the comparing comprises comparing a most significant bit of the first sequence of bits representing the random number with a most significant sequence of the second sequence of bits representing the threshold, and determining the first sequence of bits and the most significant sequence of the second sequence of bits are not equal, and deciding that the random number is larger or smaller than the threshold, or determining the first sequence of bits and the most significant sequence of the second sequence of bits are equal, repeatedly comparing an immediately following bit in the first sequence of bits representing the random number with an immediately following bit in the second sequence of bits representing the threshold until a first bit that is not equal in the first sequence of bits representing the random number and the second sequence of bits representing the threshold is reached or until all bits have been compared and found to be equal.

2. The method according to claim 1, wherein the first sequence of bits and the second sequence of bits are found to be equal and further comprising determining that the random number and the threshold are identical.

3. The method according to claim 1, wherein the random number is found to be smaller or equal to the threshold, and the random number is discarded and the comparing is repeated with a new random number.

4. The method of claim 1 wherein the random number is found to be larger than or equal to the threshold, the random number is discarded and the comparing is repeated with a new random number.

5. The method of claim 1, further comprising generating the random number using an algorithmic random number generator or a physical random number generator.

6. The method of claim 5, wherein the comparing is performed concurrently with the generating of the random number.

7. The method of claim 5, wherein the random number is generated on a bit-wise basis comprising generating a first bit of the random number and, after that, generating a second bit of the random number, wherein the first bit is more significant than the second bit.

8. The method of claim 7, wherein, after the first bit has been generated and before the second bit is generated, the first bit is compared to a correspondingly significant bit of the threshold.

9. The method of claim 8, wherein it is determined that the random number is smaller than the threshold in response determining that the first bit is smaller than the correspondingly significant bit of the threshold.

10. The method of claim 8 wherein it is it is determined that the random number is larger than the threshold in response to determining that the first bit is larger than the correspondingly significant bit of the threshold.

11. The method of claim 8, wherein the second bit is generated if it is determined that the first bit is larger than or equal to the correspondingly significant bit of the threshold or the second bit is generated if it is determined that the first bit is smaller than or equal to the correspondingly significant bit of the threshold.

12. The method of claim 11: wherein it is determined that the random number will be smaller than or equal to the threshold, and the generation of the random number is aborted and a new random number is generated; or wherein it is determined that the random number will be larger than or equal to the threshold, and the generation of the random number is aborted and a new random number is generated.

13. The method of claim 1, wherein the method further comprises determining the random number is larger than the threshold, and using the random number in at least one of encryption of data, encryption of data transmission, a numerical simulation.

14. A computer-readable storage medium comprising computer-executable instructions that, when executed by one or more processing devices comprising a comparator, cause the one or more processing devices to: represent a random number as a first sequence of bits and represent a threshold as a second sequence of bits; and compare, by the comparator, the first sequence of bits representing the random number with the second sequence of bits representing the threshold on a bit-wise basis, wherein the comparison comprises comparing a most significant bit of the first sequence of bits representing the random number with a most significant sequence of the second sequence of bits representing the threshold, and determine the first sequence of bits and the most significant sequence of the second sequence of bits are not equal, and decide that the random number is larger or smaller than the threshold, or determine the first sequence of bits and the most significant sequence of the second sequence of bits are equal, repeatedly compare an immediately following bit in the first sequence of bits representing the random number with an immediately following bit in the second sequence of bits representing the threshold until a first bit that is not equal in the first sequence of bits representing the random number and a first sequence in the second sequence of bits representing the threshold is reached or until all bits have been compared and found to be equal.

15. The computer readable medium of claim 14, wherein all bits of the first sequence of bits and the second sequence of bits are found to be equal and further comprising instructions that cause the one or more processing devices to determine that the random number and the threshold are identical.

16. The computer readable medium of claim 14, wherein the random number is found to be smaller or equal to the threshold, and the random number is discarded and the comparison is repeated with a new random number.

17. The computer readable medium of claim 14, wherein the random number is found to be larger than or equal to the threshold, the random number is discarded and the comparison is repeated with a new random number.

18. A computing system comprising a processor and a comparator, wherein the processor is configured to: represent a random number as a first sequence of bits and represent a threshold as a second sequence of bits; and compare, by the comparator, the first sequence of bits representing the random number with the second sequence of bits representing the threshold on a bit-wise basis, wherein the comparison comprises comparing a most significant bit of the first sequence of bits representing the random number with a most significant sequence of the second sequence of bits representing the threshold, and determine the first sequence of bits and the most significant sequence of the second sequence of bits are not equal, and deciding that the random number is larger or smaller than the threshold, or determine the first sequence of bits and the most significant sequence of the second sequence of bits are equal, repeatedly comparing an immediately following bit in the first sequence of bits representing the random number with an immediately following bit in the second sequence of bits representing the threshold until a first bit that is not equal in the first sequence of bits representing the random number and a first sequence in the second sequence of bits representing the threshold is reached or until all bits have been compared and found to be equal.

19. The computing system of claim 18, wherein all bits of the first sequence of bits and the second sequence of bits are found to be equal and further comprising instructions that cause the processor to determine that the random number and the threshold are identical.

20. The computing system of claim 18, wherein the computing system further comprises an algorithmic or physical random number generator configured to generate the random number and wherein the processor is configured to provide the first sequence of bits representing the random number to the comparator.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0040] FIG. 1 Shows a schematic flow diagram of a method according to one embodiment of the disclosed techniques.

[0041] FIG. 2 Shows a further flow diagram illustrating the process flow of a method according to a further embodiment of the disclosed techniques.

[0042] FIG. 3 Shows a schematic depiction of a computing system on which the method according to the disclosed techniques may be implemented.

DETAILED DESCRIPTION

[0043] FIG. 1 shows a schematic flow diagram of the steps performed in a method 100 for deciding whether a random number is larger or smaller than a given threshold. This method may be implemented on any suitable computing system and can also be provided in an encoded form on a computer-readable storage media like a CD, a flash drive or any other suitable storage media. An example of a corresponding computing system will be provided in FIG. 3.

[0044] For the method that follows, it is assumed that a threshold value exists. This threshold may be considered a natural or real number greater than 0. It can have any value, but the method is most advantageous in the case of large numbers (in the order of 2.sup.128 in the case of 128 bit precision). The threshold value is available to the computing system applying the method, and it might be provided by a user or a computing program that makes use of the random numbers that might be the outcome of the method according to some embodiments of the disclosed techniques.

[0045] The threshold can be an arbitrary number, for example it can itself be a randomly generated number that is, however, fixed for at least one phase of the processing where at least two random numbers are utilized. It could also be thought of other realizations where the threshold value changes for each random number to be compared to the respective threshold value. The description below, however, assumes a fixed threshold value. The skilled person, can, however, easily apply the respective teachings to changing threshold values as well.

[0046] In any case, as indicated above, it is assumed that the threshold value is already available to the underlying computing system.

[0047] In this regard, the method 100 begins in step 101 with obtaining a random number. The random number can be obtained in any suitable manner. Specifically, for generating or obtaining the random number, a random number generator can be used. On the other hand, it is also possible to provide already purposely generated random numbers to the computing system that is about to perform the respective method 100. For example, previously generated random numbers (for example an amount of 1 GB of random numbers where each random number is a 128-bit long number) can be provided from an external storage medium, via data transfer techniques like wireless or cabled connections, or via the internet to the computing system for performing the method 100. If random number generators are used, the method is not limited to cases where the random number is already fully created or calculated and is then provided on a manner that it can be obtained in step 101. In fact, the method also allows for obtaining the random number in step 101 in a bit-wise manner. This is a consequence of what happens in step 102 where a sequence of bits corresponding to the random number is obtained for further use. In case the random number is provided as a humanly readable random number, i.e., not in the form of binary code, this humanly readable random number can be represented in a sequence of bits using the commonly known techniques for transforming a number into a sequence of bits. In case the random numbers are generated “on the fly” by using a random number generator, it is preferred that this generation is performed in a bit-wise manner, i.e., each bit of the random number is generated separately. In this way, it is possible to provide the random number on a bit-per-bit basis (i.e., the random number is not already fully created) in step 102.

[0048] Irrespective whether the full random number is already obtained and correspondingly a full sequence of bits is already obtained, the next steps of the method use only a single bit of the corresponding sequences of bits of the threshold and of the random number for performing a bit-wise comparison.

[0049] In step 103, the most significant bit of the random number (i.e., its representation in the form of a sequence of bits) and the most significant bit of the threshold (i.e., its representation in the form of a sequence of bits) are compared. This comparison is preferably performed by a one-bit comparator as this is most suitable and most efficient in carrying out this comparison. However, the disclosed techniques not restricted to such a one-bit comparator and any other techniques or devices for performing the comparison can be used as well.

[0050] During this comparison step 103, the comparator determines whether the first most significant bit of the random number and the first most significant bit of the threshold are equal in step 110. If it is determined in step 110 that they are not equal (as indicated in operation 111), it is determined that the random number is larger (or smaller) than the threshold in step 121.

[0051] The case where the most significant bits are not equal (i.e., step 121) can only be obtained by two circumstances. In the first circumstance, the most significant bit of the random number is 1 and the most significant bit of the threshold is 0. In this case, the random number will be, in any case and completely independent from all following bits, larger that the threshold. The other case is where the most significant bit of the random number is 0 and the most significant bit of the threshold is 1. In this case, the random number is definitely smaller than the threshold.

[0052] In the next step 122, which is optional, it can then be determined whether a specific requirement is fulfilled. For example, for the method 100 it can be intended to only process further random numbers that are larger than the threshold. This requirement will thus only be fulfilled for random numbers that are in fact determined to be larger than the threshold. Random numbers that are smaller than or equal to the threshold will not fulfill this requirement. The other way around is, of course, also possible, i.e., it can be required for example that the random numbers must be smaller than the given threshold for further processing. As indicated above, this requirement step, however, is optional and does not need to be implemented such that the method 100 could already end with step 121 where it is determined that the random number is smaller or larger than the threshold.

[0053] If, however, step 122 is provided, two decisions are possible. Either it is determined in step 123 that the requirement is fulfilled. Then the processing of the random number proceeds to step 125. Further processing of this random number can, for example, comprise using the respective number in numerical simulations or in encrypting data transfer or in encrypting data. Other techniques or processes can be implemented via stop 125 as well.

[0054] If it is determined in step 122 that the requirement is not fulfilled (i.e., step 124), the random number can be discarded in step 126 and a new random number can be obtained which will result in the method resuming with step 101. It is also possible that no new random number is obtained (because none are left, or the process is intended to end) and the method will just end.

[0055] The step 126 and also the corresponding step of ending the method can also immediately follow after step 121 without the decision-making in step 122.

[0056] Returning to the comparison in step 110 where it is determined whether the first most significant bits of the random number and the threshold are equal, another option exists. In this step 112 it can be determined for the first significant bits that they are equal. If this is determined in step 112, a decision regarding whether or not the random number is equal or not equal to the threshold cannot be made. This is because two numbers cannot be determined to be equal only based on comparing their first most significant bits. It can only be decided that they are not equal if their respective most significant bits are not equal. In that case, it is determined if there are any bits left for comparison in step 131. When the method 100 begins with the first most significant bit in step 103, this question is most likely to be answered in the affirmative because random numbers constituted by only a single bit will usually not be used with the disclosed method as the advantages become more important the longer the random numbers actually are.

[0057] However, for the sake of discussion it is assumed that this step is also included for the first most significant bits being compared to each other. If it is determined that there are bits left, the next significant bit is taken, and the respective bits of the random number and the threshold are compared to each other in step 132. This means, compared to the previous run of the method that compared the first most significant bit r.sub.1 of the random number with the most significant bit t.sub.1 of the threshold, now bits r.sub.2 and t.sub.2 are compared. Generally, after comparing bits r.sub.i and t.sub.i the next turn will compare bits r.sub.i+1 and t.sub.i+1.

[0058] A determination following step 110 is then made again for these bits. Once again, this can lead to the finding that these bits are equal (step 112), or that they are not equal (step 111). If they are not equal, the process following step 111 is performed. In fact, if the next significant bits are determined to not be equal, it can immediately determine that the random number is different from the threshold.

[0059] If those next significant bits are still equal (step 112) the method needs to resume with step 132 if there are bits left (step 131) and compare those bits in order to determine once again in step 110 whether those bits are equal or not.

[0060] If, in this course of action, it is determined in step 131 that no bits are left, it can be determined in step 133 that the random number is in fact equal to the threshold (if all bits of two numbers are equal, the numbers are equal).

[0061] In that case, it can be proceeded with step 134 and a new random number can be taken where optionally the random number that is considered to be equal to the threshold can be discarded.

[0062] However, depending on, for example, requirements for the further processing of the random numbers, it can also be the case that the random numbers are to be used that are not smaller than the given threshold. In such a case, random numbers that are larger or equal to the threshold would be used further (like in step 125). This branch, however, is not explicitly shown in the flow diagram of FIG. 1. In any case, the further processing after step 133 can be equal to the processing in the steps 125 or 126 if a further step corresponding to step 122 is included.

[0063] As indicated above, one of such requirements could be to use random numbers further that are at least not smaller than the threshold. However, it is also possible to discard any random number that is determined to be equal to the threshold. This can be specifically advantageous in cases where the random number is used for encryption.

[0064] As already indicated above, for the method according to FIG. 1, it is of no relevance whether the full random number is obtained in steps 101 and 102 as the comparison takes place on a bit-wise basis by, for example, the respective one-bit comparator. While this allows for methods where either the whole random number is provided and obtained (and correspondingly the whole sequence of bits), this also allows for methods where the random number or its corresponding sequence of bits is obtained on a bit-per-bit basis starting with the first most significant bit.

[0065] Where the random number is fully available (because it is pre-created for example), there is no advantage in either obtaining the full sequence of bits compared to not obtaining the full sequence of bits and only obtaining the first most significant bit of this sequence. However, in cases where the random number is not yet fully created, the method as explained with respect to FIG. 1 can advantageously be used to control the generation of the random numbers. For example, the method described in FIG. 1 could be used to generate a biased distribution of numbers from an unbiased random number generation source by only choosing those random numbers for further processing that exceed the threshold (or that do not exceed it, for example).

[0066] In the embodiment of FIG. 2, it can be advantageous to provide each bit generated for the random number to the comparator (or other appropriate techniques) to perform the respective comparison and decide, based on the outcome of this comparison, whether or not to obtain a second bit of this random number. This will be explained in further detail with respect to FIG. 2.

[0067] In FIG. 2, the comparison is performed during the creation of the random number.

[0068] The method will ultimately begin with step 201 where the first bit of the random number is created. Once again, it will be assumed that the threshold is already fully available to the computing system carrying out the respective method. Obtaining or creating the threshold value and its respective sequence of bits will thus not be considered further here and can be done in an arbitrary manner.

[0069] The creation of the random number can be performed in any suitable way using, for example, algorithmic random number generators of physical random number generators as already explained above. The disclosed techniques are not limited in this regard. However, the respective random number generators need to be able to create the random number in the form of a sequence of bits such that it is preferably possible to stop the generation of the random number with each bit generated and to wait for the outcome of the respective comparison. This can be achieved by using random number generators that only generate values 0 and 1 in an arbitrary and random manner in sequence.

[0070] Once this first bit of the random number is generated, this first bit is considered to be the most significant bit of the random number and it is compared to the first bit (i.e., the most significant bit) of the threshold in step 202. This comparison is carried out in one of the ways as already described with respect to FIG. 1 as the process described in FIG. 1 performs a bit-wise comparison of bits of the random number and the threshold.

[0071] If it is determined in step 203 and step 205 that the first bit of the random number is not equal to the first bit of the threshold, it is (implicitly) determined that the random number that is about to be generated is different from the threshold. If this is the case, a further step as already explained with respect to FIG. 1 can be included. This step can comprise determining whether a specific requirement is fulfilled in step 251. This requirement can, for example, be that the random number that is to be generated must be larger (or smaller) than the threshold. For the further explanation, it will be assumed that the requirement is that the random number to be generated is larger than the threshold. If it is determined that this is the case (step 252, which will only be the case if the most significant bit of the random number is 1 and the most significant bit of the threshold is 0), processing proceeds with the generation of the random number in step 254. This generation of the random number can take place without using any further comparison step 202 because it is already known that the random number that is generated at the end of the method will be larger than the threshold from the comparison of the first most significant bit.

[0072] If the requirement is not fulfilled (step 253), the random number can be discarded in step 260 which means that the processing will not proceed with creating the full sequence of bits that will constitute the random number, but potentially a new random number could be generated in step 261. Generating this new random number will usually comprise simply generating a further bit with the random number generator and using this further generated bit as “first bit” in step 201 for the “new random number”.

[0073] Returning to the method in step 202 and the determination whether the first bit of the random number is equal to the first bit of the threshold, another option exists. If it is determined in step 204 that those two bits are in fact equal, it is (optionally) determined in step 241 whether there are any bits left for generation. If only one bit has been created so far, it will usually be the case that further bits are to be generated. In any case, this determination in step 241 is made based on the fact that the bit length of the random number to be generated is usually already known to the system. For example, the task can be to generate a sequence of random numbers having a length of 128 bits. If only one bit has already been created, 127 bits are still to be done. If the method is already proceeded to some degree and, for example, 115 bits have already been created for a given random number, less bits will still need to be created. If all bits have been created for the respective random number, it would be determined in step 243 that no further bits are left for generation and, because it is determined in step 204 that also the last bit of the random number that is generated is equal to the threshold, the random number is equal to the threshold and the random number could be discarded. This is in line with step 260 as already explained previously.

[0074] If it is determined in step 241 with decision 242 that there are still bits left to be generated, the next bit is generated in step 244. This then generated “second” bit (or any consecutive bit) is then compared to the corresponding bit of the threshold. This means that if, for example, out of 128 bits, the bit with number 97 is just created for the random number, this bit is compared to the corresponding bit number 97 of the threshold in step 245. This comparison is performed in the way as it is performed in step 202 and correspondingly, it is determined in correspondence with step 203 whether this respective bit is equal to the bit of the threshold. Once again, decisions 204 or 205 can be made and it can thus be determined based on this second bit whether the random number is different from the threshold (for example larger or smaller).

[0075] Based on this decision, the processing either proceeds with creating bits of the random number or this “random number under generation” is discarded and the generation of a new random number can be started if it is determined, for example, that the random number that would be created when proceeding further is smaller than the threshold.

[0076] It is once again noted that this method is specifically advantageous the longer the random numbers to be generated actually are. This is basically because the decision whether or not the generated sequence of random bits represents a random number that is larger or smaller than the threshold can usually be made very fast. Indeed, in many cases this decision can already be made when having generated the first 3, 4 or 5 bits of the random number. Thus, for a 128 bit random number that is to be generated, it can already be determined after less than 5% of the amount of bits generated, whether the random number will exceed the threshold or not, thereby allowing for stopping the generation of the current random number if it does not fulfill the condition of exceeding (or not exceeding) the threshold and starting the generation of a new random number for a new decision.

[0077] FIG. 3 shows a schematic depiction of an underlying computing system 300 with a limited number of components. In this depiction, there is provided schematically a computing system like a personal computer, a server, a server farm, or any other suitable computing devices. This computing system comprises at least one processor 301 or can, of course, also comprise a plurality of processors. Furthermore, a memory 302, like a hard drive, is associated with the processor such that the processor can access data and computing programs stored on the respective memory. Additionally, a comparator 303, preferably a one-bit comparator is provided in the computing system. This can either be implemented as hardware, as software, or both.

[0078] In any case, the respective computing system 300 is adapted to perform the method according at least one embodiment as explained above. For this purpose, the memory 302 includes computer-readable instructions (program code) for performing a method, for example, in line with the embodiment described with respect to FIG. 1 or with the embodiment described with respect to FIG. 2.

[0079] Further elements of the computing system like data transfer device 304 (wireless or cabled) or interfaces 305 for attaching separate data storages can also be provided but are commonly known to the skilled person and will thus not be explained here in further detail.

[0080] As is seen from the above, the disclosed method allows for deciding whether or not a random number exceeds a specific threshold with very few operations. Though, in principle, the process described can be repeated until the last bit is determined (in case all preceding bits are equal) in order to ultimately determine whether the generated random number is equal to, larger than or smaller than the threshold, this process can also be ended or aborted earlier, for example after having generated only the most significant bit or the first 3 significant bits. Thereby, it can be ensured that the generation of full random numbers is only processed further, if it is already determined right or almost at the beginning that the random number that will be generated is definitely larger than the threshold.

[0081] In the description above, it was assumed that a single random number is generated and is to be compared against a single threshold in order to determine whether it exceeds the threshold or does not exceed the threshold. However, the disclosed techniques are not limited in this regard. For example, the disclosed techniques can also be extended to methods where there is more than one threshold against which the random number that is currently created is to be compared. The comparing of the bits of the random number against each of the thresholds can be done according to any of the previously described embodiments.

[0082] For example, there may be provided n (n being an arbitrary natural number greater than 1) thresholds where the thresholds constitute pairwise disjoint numbers. When generating the random number as explained above on a bit-wise basis, each generated bit or the generated sequence of bits constituting the random number can be compared for each bit generated against the corresponding bit or bits in each of the thresholds. By this, for each new bit, a decision (yes or no) can be made for each of the thresholds whether the to be generated random number will exceed the threshold or it will not exceed the threshold.

[0083] This ultimately allows for creating a plurality of one-bit decisions (yes or no) from the respective comparisons by only creating a single random number. For example, considering a random number of the length of 128 bits, a random number can be calculated that can reasonably be compared against billions of thresholds having different values, thereby allowing for creating billions of decision bits from the 128 bit created random number where it is also possible that it is not even necessary to create all the 128 bits of this random number as the respective decisions can usually be made after having only created a subset of those 128 bits.

[0084] Consequently, by generating just a single bit or 2 or 3 bits out of a random number that, in the end when it is finally created, will be a number of a length of 128 bits can be sufficient to already make hundreds or thousands or even more decisions.

[0085] These decisions are, in one embodiment made at least partially in parallel by comparing the bits already generated for the random number against each of the thresholds in parallel, thereby also arriving at a fast decision-making when using parallel calculations.

[0086] It is also noted that with this process of comparing the bits of the to be generated random number against the thresholds, decisions that will not result in further information can be avoided. Considering, for example, three different thresholds of arbitrary (but fixed) length, for example 128 bit, and a random number that is generated having the same length when it is finally completely generated.

[0087] Assuming that after having generated the first 2 bits of this random number, it is arrived at the decision that this random number exceeds the first and the second threshold, generating a further bit will not provide additional information that is useful for making the decision whether or not the first and second thresholds are exceeded by the to be generated random number. The full random number would thus not need to be created as no additional information in terms of whether or not the random number will exceed the first and second threshold can be obtained.

[0088] For the third threshold, it may be that the first 2 bits were not sufficient for the decision making (because the first two bits of the random number and of the third threshold are identical) and this decision can only be made after having created the third bit. Upon also having made this decision, i.e., whether the to be generated random number will exceed the third threshold or will be smaller than the third threshold, creating each successive bit will not add any information to the already made decisions.

[0089] It would thus be reasonable to abort the decision-making or at least the generation of the random number at this point because all relevant decisions (does the to be generated random number exceed the thresholds or not) are already made. This significantly saves computing resources if the further processing does not depend on the actual random number that would finally be created (i.e., its definite value) but it is only intended to make random decisions by truly random numbers.

[0090] It is clear that this process can be extended to any number of thresholds as long as the number of thresholds does not exceed the maximum value of the to be generated random number. For a random number having potentially 128 bits, it would, for example, not be reasonable to make decisions against thresholds ranging from 0 to 2.sup.130 because at least for the values exceeding 2.sup.128, this decision would always yield “no”.

[0091] With the above-described method of comparing a random number against a plurality of thresholds, it is also possible to create biased random number distributions by, for example, only further processing random numbers that are within a specific interval (for example that are larger than a first threshold and smaller than a second threshold).