Mapping pseudo-random numbers to predefined number ranges

• US 20050050121A1
• Filed: 09/02/2003
• Published: 03/03/2005
• Est. Priority Date: 09/02/2003
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Klein, Udo, Januschke, Peter
• Granted Patent: US 7,328,228 B2
• Time in Patent Office: Days
• US Class Current: 708/250
• CPC Class Codes: G06F 7/582 Pseudo-random number generators

Abstract

Pseudo-random numbers (PRNs) generated by a PRN generator are mapped to predefined number ranges or target ranges. The target range may be smaller or larger than the range of the PRN generator. Mapping to a smaller target range may include generating PRNs (e.g., integers) from a particular bit-input stream (e.g., 32-bit) having a uniform distribution across the range of numbers; selecting an optimal subset of the generated PRNs to map; and mapping the selected PRNs to a corresponding number in a target range such that the mapped numbers are uniformly distributed across the target range. Mapping to a larger target range may include generating uniformly distributed PRNs; applying a generation function to the PRNs to generate uniformly distributed packed numbers; and applying a mapping function to map selected packed numbers to the target range such that the mapped numbers are uniformly distributed.

Claims

1. A method for generating pseudo-random numbers in a target range, the method comprising:

generating a plurality of pseudo-random numbers having a uniform distribution in a source range;

selecting an optimal subset of the plurality of pseudo-random numbers to map; and

mapping the selected pseudo-random numbers to a corresponding number in the target range such that the mapped numbers are uniformly distributed across the target range.

2. The method of claim 1 wherein the source range is from 0 . . . R, the target range has a size B, and selecting the optimal subset of pseudo random numbers comprises identifying those pseudo random numbers that fall between 0 and L, where L is derived from R and B and provides an optimal match to the target range.

3. The method of claim 1, wherein the pseudo random numbers comprise integers.

4. The method of claim 1, wherein generating a plurality of pseudo-random numbers having a uniform distribution comprises using a pseudo-random number generator.

5. The method of claim 2, wherein R is determined according to the following equation 2^b−

1, where b is the number of input bits.

6. The method of claim 2, wherein the source range has a size R+1, and B is numerically smaller than R+1.

7. The method of claim 5, wherein b is 32.

8. The method of claim 5 further comprising minimizing the number of input bits b needed to generate pseudo-random numbers that fall within the desired output range.

9. The method of claim 8 wherein minimizing the number of input bits b comprises minimizing the following equation

$\frac{b}{1-\frac{2^b}{}}$

 

⁢

mod ⁢

 

⁢

B 2 b .

10. The method of claim 1, wherein selecting an optimal subset of the plurality of pseudo-random numbers comprises:

calculating L, where L provides an optimal match to the target range of min, . . . , max and is derived from the following equation L=S*B, where B is max−

min+1 and S is (R+1) div B;

receiving the plurality of pseudo-random numbers having a uniform distribution; and

identifying those pseudo-random numbers r that fall within the range 0, . . . , L.

11. The method of claim 9, wherein the mapped numbers satisfy the following equation (r div S)+min.

12. A method for generating uniformly distributed pseudo-random numbers in an arbitrary target range, the method comprising:

generating a plurality of pseudo-random numbers F having a uniform distribution in a range 0 to R;

mapping the plurality of pseudo-random integer numbers F to an arbitrary target range of size B by (i) obtaining those pseudo-random numbers F that fall in a range 0 to L, where L is derived from R and B and provides an optimal match to the desired range, and (ii) mapping each pseudo-random number F falling in a range 0 to L to a corresponding number in the target range so that the mapped number in the target range is uniformly distributed relative to other mapped numbers.

13. A method for mapping pseudo-random numbers to a target range, the method comprising:

generating in a source range a plurality of pseudo-random numbers having a uniform distribution; and

mapping the pseudo-random numbers to the target range while maintaining the degree of pseudo-randomness of the pseudo random numbers.

14. A method for generating uniformly distributed pseudo-random packed numbers in an arbitrary desired range, the method comprising:

generating uniformly distributed pseudo-random numbers;

applying a generation function to the pseudo-random numbers to generate uniformly distributed packed numbers; and

applying a mapping function to the uniformly distributed packed numbers to map selected packed numbers to corresponding numbers in the arbitrary desired range such that the mapped numbers are uniformly distributed.

15. The method of claim 14, wherein applying a generation function to the pseudo-random numbers to generate uniformly distributed packed numbers comprises:

generating one or more unsigned component packed numbers and a signed component packed number; and

forming the packed numbers with the component packed numbers by concatenating the unsigned component packed numbers to the signed component packed number.

16. The method of claim 14, wherein applying a mapping function to the uniformly distributed packed number to map selected packed numbers comprises:

computing the size of the desired output range;

obtaining those uniformly distributed packed numbers having absolute values that fall in the range 0 . . . L, where L provides an optimal match to the desired output range; and

mapping each obtained packed number to a corresponding number in the desired output range so that the mapped packed number in the desired range is uniformly distributed relative to other mapped packed numbers.

17. A computer system configured to perform operations comprising:

generating a plurality of pseudo-random numbers having a uniform distribution in a source range;

selecting an optimal subset of the plurality of pseudo-random numbers to map; and

mapping the selected pseudo-random numbers to a corresponding number in the target range such that the mapped numbers are uniformly distributed across the target range.

18. The computer system of claim 17, wherein the source range is from 0 . . . R, the target range has a size B, and selecting the optimal subset of pseudo random numbers comprises identifying those pseudo random numbers that fall between 0 and L, where L is derived from R and B and provides an optimal match to the target range

19. The computer system of claim 18, wherein R is determined according to the following equation 2^b−

1, where b is the number of input bits.

20. The computer system of claim 19 further comprising minimizing the number of input bits b needed to generate pseudo-random numbers that fall within the desired output range.

21. The computer system of claim 20 wherein minimizing the number of input bits b comprises minimizing the following equation

$\frac{b}{1-\frac{2^b}{}}$

 

⁢

mod ⁢

 

⁢

B 2 b .

22. A computer system configured to perform operations comprising:

generating uniformly distributed pseudo-random numbers;

applying a generation function to the pseudo-random numbers to generate uniformly distributed packed numbers; and

applying a mapping function to the uniformly distributed packed numbers to map selected packed numbers to corresponding numbers in the arbitrary desired range such that the mapped numbers are uniformly distributed.

23. The computer system of claim 22, wherein applying a generation function to the pseudo-random numbers to generate uniformly distributed packed numbers comprises:

generating one or more unsigned component packed numbers and a signed component packed number; and

forming the packed numbers with the component packed numbers by concatenating the unsigned component packed numbers to the signed component packed number.

24. The computer system of claim 22, wherein applying a mapping function to the uniformly distributed packed number to map selected packed numbers comprises:

computing the size of the desired output range;

obtaining those uniformly distributed packed numbers having absolute values that fall in the range 0 . . . L, where L provides an optimal match to the desired output range; and

mapping each obtained packed number to a corresponding number in the desired output range so that the mapped packed number in the desired range is uniformly distributed relative to other mapped packed numbers.

25. A computer-readable medium having stored therein one or more sequences of instruction for mapping pseudo-random numbers to a target range, wherein execution of the one or more sequences of instructions by one ore more processors causes the one ore more processors to perform operations comprising:

generating a plurality of pseudo-random numbers having a uniform distribution in a source range;

selecting an optimal subset of the plurality of pseudo-random numbers to map; and

mapping the selected pseudo-random numbers to a corresponding number in the target range such that the mapped numbers are uniformly distributed across the target range.

26. The computer-readable medium of claim 25, wherein the source range is from 0 . . . R, the target range has a size B, and selecting the optimal subset of pseudo random numbers comprises identifying those pseudo random numbers that fall between 0 and L, where L is derived from R and B and provides an optimal match to the target range

27. The computer-readable medium of claim 26, wherein R is determined according to the following equation 2^b−

1, where b is the number of input bits.

28. The computer-readable medium of claim 27 further comprising minimizing the number of input bits b needed to generate pseudo-random numbers that fall within the desired output range.