[algogeeks] Re: Generate random number from 1 to 10.
Thanks for the explanation Don! It looks like I need better math-foo to
completely understand your explanation...
On Tuesday, February 11, 2014 10:07:05 AM UTC-8, Don wrote:
It can be shown mathematically that if you use a multiplier A such that
A*2^15-1 and A*2^16-1 are both prime, you get a sequence with period
A*2^15. With A=63663 you get a sequence of nearly two billion. If A was
larger than 2^16, the multiplication would result in overflow in some
cases, so the value I used was near the limit. The generator uses only the
low 16 bits as output. The high 16 bits, however, are kept as state,
meaning that you can't tell from the current output what the next output
will be. The full cycle contains each possible output value an equal number
of times, so over a large sample, the outputs are all equally likely.
Using mod 1000 is not a perfect way to get a uniform value in the range
0-1000. Because the outputs are in the range 0..65536, there are 65 ways to
generate numbers = 536 and 66 ways to generate numbers 536. A better way
to generate a number in the range 0..n-1 is to divide the output by
65535/n. Then check the result and if it is = n, repeat the process until
you get a valid result.
Don
On Tuesday, February 11, 2014 1:18:26 AM UTC-5, SVIX wrote:
:) true... that was silly of me.. I was too quick to post... anyway, the
point I was trying to understand was why this specific combination of
operations would produce good randomness... Running the original solution
you posted a million times (with the max limit set to 1000), below is the
frequency of the numbers generated (in the format number X frequency )
On Friday, February 7, 2014 11:42:03 AM UTC-8, Don wrote:
Because if you put that in a loop you will get a series like:
3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5...
On Thursday, February 6, 2014 8:27:27 PM UTC-5, SVIX wrote:
Just curious... Why is this more random than
(getSystemTimeInMilliseconds() % 10)
On Thursday, February 6, 2014 1:47:15 PM UTC-8, Don wrote:
Just noticed that you asked for 1-10, and my code will clearly
generate 0-9. Add one for the desired range.
Don
On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:
// Using George Marsaglia's Multiply With Carry generator
int rnd10()
{
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x 65535) % 10;
}
On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:
Generate random number form 1 - 10 with probability of 1/10.You are
not allowed to used rand() function.
any simple way of achieving above with using any complex
implementation of random number generators algorithm .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Generate random number from 1 to 10.
It can be shown mathematically that if you use a multiplier A such that
A*2^15-1 and A*2^16-1 are both prime, you get a sequence with period
A*2^15. With A=63663 you get a sequence of nearly two billion. If A was
larger than 2^16, the multiplication would result in overflow in some
cases, so the value I used was near the limit. The generator uses only the
low 16 bits as output. The high 16 bits, however, are kept as state,
meaning that you can't tell from the current output what the next output
will be. The full cycle contains each possible output value an equal number
of times, so over a large sample, the outputs are all equally likely.
Using mod 1000 is not a perfect way to get a uniform value in the range
0-1000. Because the outputs are in the range 0..65536, there are 65 ways to
generate numbers = 536 and 66 ways to generate numbers 536. A better way
to generate a number in the range 0..n-1 is to divide the output by
65535/n. Then check the result and if it is = n, repeat the process until
you get a valid result.
Don
On Tuesday, February 11, 2014 1:18:26 AM UTC-5, SVIX wrote:
:) true... that was silly of me.. I was too quick to post... anyway, the
point I was trying to understand was why this specific combination of
operations would produce good randomness... Running the original solution
you posted a million times (with the max limit set to 1000), below is the
frequency of the numbers generated (in the format number X frequency )
On Friday, February 7, 2014 11:42:03 AM UTC-8, Don wrote:
Because if you put that in a loop you will get a series like:
3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5...
On Thursday, February 6, 2014 8:27:27 PM UTC-5, SVIX wrote:
Just curious... Why is this more random than
(getSystemTimeInMilliseconds() % 10)
On Thursday, February 6, 2014 1:47:15 PM UTC-8, Don wrote:
Just noticed that you asked for 1-10, and my code will clearly generate
0-9. Add one for the desired range.
Don
On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:
// Using George Marsaglia's Multiply With Carry generator
int rnd10()
{
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x 65535) % 10;
}
On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:
Generate random number form 1 - 10 with probability of 1/10.You are
not allowed to used rand() function.
any simple way of achieving above with using any complex
implementation of random number generators algorithm .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Generate random number from 1 to 10.
https://groups.google.com/forum/#!original/comp.lang.java.programmer/Z8lfFIDhS7k/wbPLDldPSSgJ
The Multiply With Carry generator is ok for some purposes. There are
generators with longer periods and better statistical properties, but they
are more complicated. The link I provided has code for a 64-bit multiply
with carry generator, while what I posted was a 32-bit multiply with carry
generator.
Don
On Saturday, February 8, 2014 2:26:34 AM UTC-5, atul007 wrote:
@don : awesome +1 . I was not aware of George Marsaglia's Multiply
With Carry generator. But it is soo clll . If you have any good link
for its proof or explanation of the idea behind it then please mention it.
I never knew generating random number can be few lines of code :)
Thanks :)
On Sat, Feb 8, 2014 at 1:28 AM, Don dond...@gmail.com javascript:wrote:
A random generator will not always (or even usually) produce a
permutation of the possible values before repeating.
If you call my function 10 million times and tally up the results, you
will get a distribution with about a million of each value, as close as you
would expect for a random sample.
Your question was to randomly generate values in the range 1-10, not to
generate permutations.
Here is a way to generate a permutation without swapping:
unsigned int X = time(0);
int n[10];
n[0] = 10;
for(i = 1; i 10; ++i)
{
X = 63663 * (X65535) + (X16);
int j = (X 65535) % (i+1);
n[i] = n[j];
n[j] = i;
}
// n now contains a permutation of the values 1-10.
On Thursday, February 6, 2014 11:33:53 PM UTC-5, atul007 wrote:
@don: algo look fine..i tested it ,but it did not generate 1-10 with
probabilty of 1/10 everytime.
actually question was asked in an intrview.
question started with displaying all elements in an array randomly
without repetition i.e only once( probabilty 1/10)...which can be done with
fisher yates .
then interviewer said that u are not allowed to swap elements which is
requied in fishr yates.
his hint was: how will you generate randomly number from 1-10 without
use of rand() function.
expected time complexity : O(n)
On 7 Feb 2014 03:17, Don dond...@gmail.com wrote:
Just noticed that you asked for 1-10, and my code will clearly
generate 0-9. Add one for the desired range.
Don
On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:
// Using George Marsaglia's Multiply With Carry generator
int rnd10()
{
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x 65535) % 10;
}
On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:
Generate random number form 1 - 10 with probability of 1/10.You are
not allowed to used rand() function.
any simple way of achieving above with using any complex
implementation of random number generators algorithm .
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+...@googlegroups.com javascript:.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Generate random number from 1 to 10.
:) true... that was silly of me.. I was too quick to post... anyway, the point I was trying to understand was why this specific combination of operations would produce good randomness... Running the original solution you posted a million times (with the max limit set to 1000), below is the frequency of the numbers generated (in the format number X frequency ) Hello World! 502 x 2061, 245 x 644, 396 x 1328, 537 x 1103, 639 x 1419, 621 x 1401, 298 x 1372, 388 x 888, 668 x 519, 108 x 1621, 912 x 1829, 954 x 1077, 393 x 1220, 959 x 788, 5 25 x 1331, 203 x 788, 769 x 1330, 275 x 1162, 425 x 756, 578 x 770, 84 x 698, 761 x 1082, 698 x 1122, 375 x 1230, 805 x 1329, 483 x 1620, 573 x 936, 377 x 1039, 54 x 672, 858 x 523, 662 x 506, 752 x 1083, 430 x 1206, 472 x 1990, 38 x 1674, 417 x 765, 43 x 1280, 787 x 2051, 227 x 1754, 329 x 913, 835 x 1182, 512 x 652, 78 x 1001, 882 x 1467, 559 x 1178, 602 x 1326, 168 x 1358, 845 x 755, 411 x 243, 977 x 1129, 543 x 1844, 745 x 1661, 549 x 2088, 115 x 2151, 554 x 367, 358 x 1359, 162 x 1021, 839 x 391, 406 x 1916, 972 x 1416, 649 x 1009, 453 x 766, 19 x 961, 585 x 1075, 24 x 833, 67 x 900, 395 x 1056, 310 x 1032, 638 x 1435, 788 x 1824, 119 x 629, 924 x 1136, 490 x 774, 167 x 834, 257 x 869, 61 x 1209, 865 x 996, 542 x 385, 109 x 1942, 913 x 1837, 352 x 962, 156 x 780, 722 x 1892, 637 x 641, 144 x 643, 354 x 1353, 209 x 936, 13 x 1072, 579 x 1277, 256 x 1423, 627 x 2101, 431 x 1234, 478 x 1110, 619 x 667, 990 x 1026, 965 x 865, 233 x 1362, 335 x 1336, 774 x 1026, 626 x 974, 14 5 x 1778, 286 x 1292, 656 x 781, 460 x 1057, 899 x 923, 704 x 1167, 270 x 883, 947 x 1036, 751 x 1789, 139 x 824, 994 x 1263, 560 x 915, 365 x 944, 864 x 720, 132 x 2159, 996 x 910, 477 x 815, 44 x 1124, 550 x 1120, 989 x 714, 555 x 1606, 359 x 2573, 36 x 860, 186 x 1602, 407 x 1671, 758 x 995, 842 x 1142, 459 x 1265, 25 x 764, 830 x 824, 269 x 2126, 657 x 683, 461 x 1406, 687 x 1212, 364 x 879, 930 x 1001, 122 x 1437, 561 x 511, 127 x 1195, 932 x 847, 175 x 1161, 633 x 478, 72 x 1760, 443 x 1657, 448 x 1159, 252 x 1454, 929 x 1254, 733 x 894, 501 x 1574, 305 x 1442, 675 x 1698, 114 x 2041, 680 x 1355, 723 x 2015, 400 x 695, 204 x 1332, 770 x 1118, 911 x 1455, 715 x 1302, 281 x 1172, 823 x 962, 768 x 712, 334 x 684, 436 x 1288, 3 x 2315, 246 x 1578, 336 x 1445, 251 x 1334, 55 x 1388, 299 x 1259, 669 x 679, 716 x 1 201, 282 x 940, 526 x 1617, 92 x 1043, 37 x 839, 841 x 718, 341 x 1606, 847 x 1842, 949 x 713, 90 x 1152, 192 x 1264, 137 x 1237, 942 x 1201, 568 x 370, 74 x 718, 79 9 x 801, 169 x 1894, 608 x 1019, 174 x 878, 978 x 528, 655 x 271, 264 x 899, 703 x 1344, 507 x 1001, 73 x 882, 877 x 294, 317 x 1220, 883 x 974, 126 x 936, 496 x 104 2, 697 x 285, 544 x 1044, 983 x 1104, 353 x 1226, 919 x 912, 163 x 1950, 205 x 2031, 14 x 1006, 258 x 1049, 62 x 1027, 157 x 2209, 401 x 1475, 9 x 2093, 56 x 1367, 4 95 x 964, 300 x 1369, 104 x 1105, 151 x 1551, 394 x 825, 289 x 1655, 966 x 1789, 514 x 1260, 953 x 1267, 520 x 1195, 86 x 949, 1 x 1123, 567 x 1450, 371 x 1514, 48 x 1630, 198 x 388, 241 x 1529, 807 x 2055, 50 x 2080, 556 x 970, 651 x 717, 900 x 855, 508 x 1434, 318 x 734, 646 x 1478, 383 x 627, 889 x 2111, 693 x 1925, 936 x 259 5, 741 x 933, 418 x 988, 984 x 1008, 31 x 727, 926 x 823, 603 x 1472, 211 x 919, 888 x 1070, 692 x 1944, 259 x 1751, 68 x 1263, 311 x 1005, 793 x 998, 925 x 753, 491 x 1414, 210 x 1972, 301 x 1917, 306 x 2586, 348 x 1196, 724 x 1596, 967 x 1326, 584 x 692, 686 x 1287, 776 x 1222, 581 x 939, 824 x 982, 866 x 1834, 7 x 624, 51 x 1 719, 234 x 730, 337 x 1166, 848 x 1576, 479 x 1054, 199 x 474, 467 x 1034, 442 x 1172, 8 x 802, 812 x 382, 379 x 825, 562 x 583, 128 x 1608, 133 x 248, 937 x 1322, 1 81 x 393, 747 x 1187, 424 x 1491, 228 x 1040, 794 x 1013, 659 x 532, 800 x 1139, 604 x 1651, 170 x 633, 413 x 719, 455 x 1060, 895 x 839, 521 x 647, 265 x 641, 312 x 1340, 450 x 915, 735 x 1005, 217 x 999, 783 x 939, 26 x 856, 878 x 1151, 121 x 1068, 253 x 1323, 931 x 1169, 63 x 1370, 740 x 1414, 872 x 833, 158 x 1165, 597 x 822 , 57 x 1880, 973 x 1380, 539 x 1034, 105 x 629, 20 x 871, 628 x 515, 634 x 1153, 438 x 538, 681 x 1435, 247 x 1126, 99 x 634, 623 x 1613, 806 x 1417, 372 x 805, 347 x 1659, 616 x 809, 420 x 2190, 859 x 917, 663 x 1401, 229 x 1455, 473 x 1149, 427 x 1228, 342 x 1253, 908 x 1931, 474 x 1197, 718 x 1251, 938 x 998, 615 x 860, 705 x 1043, 795 x 1209, 414 x 1677, 218 x 1094, 27 x 863, 837 x 702, 80 x 1243, 212 x 1005, 694 x 867, 498 x 1659, 545 x 683, 355 x 1006, 32 x 1153, 836 x 1547, 974 x 100 3, 540 x 2549, 825 x 926, 873 x 809, 116 x 1164, 920 x 536, 449 x 1673, 254 x 900, 582 x 1214, 497 x 1668, 629 x 970, 915 x 647, 729 x 924, 771 x 1138, 777 x 633, 81 9 x 1177, 385 x 1430, 586 x 1163, 390 x 1430, 481 x 1044, 962 x 908, 766 x , 813 x 913, 193 x 1609, 235 x 1173, 801 x 1018, 288 x 1014, 914 x 1583, 658 x 1016, 4 62 x 1278, 901 x 1296, 509 x 838, 515 x 537, 319 x 969, 146 x 1026, 950 x 1632, 517 x
[algogeeks] Re: Generate random number from 1 to 10.
Because if you put that in a loop you will get a series like:
3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5...
On Thursday, February 6, 2014 8:27:27 PM UTC-5, SVIX wrote:
Just curious... Why is this more random than
(getSystemTimeInMilliseconds() % 10)
On Thursday, February 6, 2014 1:47:15 PM UTC-8, Don wrote:
Just noticed that you asked for 1-10, and my code will clearly generate
0-9. Add one for the desired range.
Don
On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:
// Using George Marsaglia's Multiply With Carry generator
int rnd10()
{
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x 65535) % 10;
}
On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:
Generate random number form 1 - 10 with probability of 1/10.You are not
allowed to used rand() function.
any simple way of achieving above with using any complex implementation
of random number generators algorithm .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Generate random number from 1 to 10.
A random generator will not always (or even usually) produce a permutation
of the possible values before repeating.
If you call my function 10 million times and tally up the results, you will
get a distribution with about a million of each value, as close as you
would expect for a random sample.
Your question was to randomly generate values in the range 1-10, not to
generate permutations.
Here is a way to generate a permutation without swapping:
unsigned int X = time(0);
int n[10];
n[0] = 10;
for(i = 1; i 10; ++i)
{
X = 63663 * (X65535) + (X16);
int j = (X 65535) % (i+1);
n[i] = n[j];
n[j] = i;
}
// n now contains a permutation of the values 1-10.
On Thursday, February 6, 2014 11:33:53 PM UTC-5, atul007 wrote:
@don: algo look fine..i tested it ,but it did not generate 1-10 with
probabilty of 1/10 everytime.
actually question was asked in an intrview.
question started with displaying all elements in an array randomly without
repetition i.e only once( probabilty 1/10)...which can be done with fisher
yates .
then interviewer said that u are not allowed to swap elements which is
requied in fishr yates.
his hint was: how will you generate randomly number from 1-10 without use
of rand() function.
expected time complexity : O(n)
On 7 Feb 2014 03:17, Don dond...@gmail.com javascript: wrote:
Just noticed that you asked for 1-10, and my code will clearly generate
0-9. Add one for the desired range.
Don
On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:
// Using George Marsaglia's Multiply With Carry generator
int rnd10()
{
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x 65535) % 10;
}
On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:
Generate random number form 1 - 10 with probability of 1/10.You are not
allowed to used rand() function.
any simple way of achieving above with using any complex implementation
of random number generators algorithm .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+...@googlegroups.com javascript:.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Generate random number from 1 to 10.
@don : awesome +1 . I was not aware of George Marsaglia's Multiply
With Carry generator. But it is soo clll . If you have any good link
for its proof or explanation of the idea behind it then please mention it.
I never knew generating random number can be few lines of code :)
Thanks :)
On Sat, Feb 8, 2014 at 1:28 AM, Don dondod...@gmail.com wrote:
A random generator will not always (or even usually) produce a permutation
of the possible values before repeating.
If you call my function 10 million times and tally up the results, you
will get a distribution with about a million of each value, as close as you
would expect for a random sample.
Your question was to randomly generate values in the range 1-10, not to
generate permutations.
Here is a way to generate a permutation without swapping:
unsigned int X = time(0);
int n[10];
n[0] = 10;
for(i = 1; i 10; ++i)
{
X = 63663 * (X65535) + (X16);
int j = (X 65535) % (i+1);
n[i] = n[j];
n[j] = i;
}
// n now contains a permutation of the values 1-10.
On Thursday, February 6, 2014 11:33:53 PM UTC-5, atul007 wrote:
@don: algo look fine..i tested it ,but it did not generate 1-10 with
probabilty of 1/10 everytime.
actually question was asked in an intrview.
question started with displaying all elements in an array randomly
without repetition i.e only once( probabilty 1/10)...which can be done with
fisher yates .
then interviewer said that u are not allowed to swap elements which is
requied in fishr yates.
his hint was: how will you generate randomly number from 1-10 without use
of rand() function.
expected time complexity : O(n)
On 7 Feb 2014 03:17, Don dond...@gmail.com wrote:
Just noticed that you asked for 1-10, and my code will clearly generate
0-9. Add one for the desired range.
Don
On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:
// Using George Marsaglia's Multiply With Carry generator
int rnd10()
{
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x 65535) % 10;
}
On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:
Generate random number form 1 - 10 with probability of 1/10.You are
not allowed to used rand() function.
any simple way of achieving above with using any complex
implementation of random number generators algorithm .
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Generate random number from 1 to 10.
Just noticed that you asked for 1-10, and my code will clearly generate
0-9. Add one for the desired range.
Don
On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:
// Using George Marsaglia's Multiply With Carry generator
int rnd10()
{
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x 65535) % 10;
}
On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:
Generate random number form 1 - 10 with probability of 1/10.You are not
allowed to used rand() function.
any simple way of achieving above with using any complex implementation
of random number generators algorithm .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Generate random number from 1 to 10.
Just curious... Why is this more random than (getSystemTimeInMilliseconds()
% 10)
On Thursday, February 6, 2014 1:47:15 PM UTC-8, Don wrote:
Just noticed that you asked for 1-10, and my code will clearly generate
0-9. Add one for the desired range.
Don
On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:
// Using George Marsaglia's Multiply With Carry generator
int rnd10()
{
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x 65535) % 10;
}
On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:
Generate random number form 1 - 10 with probability of 1/10.You are not
allowed to used rand() function.
any simple way of achieving above with using any complex implementation
of random number generators algorithm .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Generate random number from 1 to 10.
@don: algo look fine..i tested it ,but it did not generate 1-10 with
probabilty of 1/10 everytime.
actually question was asked in an intrview.
question started with displaying all elements in an array randomly without
repetition i.e only once( probabilty 1/10)...which can be done with fisher
yates .
then interviewer said that u are not allowed to swap elements which is
requied in fishr yates.
his hint was: how will you generate randomly number from 1-10 without use
of rand() function.
expected time complexity : O(n)
On 7 Feb 2014 03:17, Don dondod...@gmail.com wrote:
Just noticed that you asked for 1-10, and my code will clearly generate
0-9. Add one for the desired range.
Don
On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:
// Using George Marsaglia's Multiply With Carry generator
int rnd10()
{
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x 65535) % 10;
}
On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:
Generate random number form 1 - 10 with probability of 1/10.You are not
allowed to used rand() function.
any simple way of achieving above with using any complex implementation
of random number generators algorithm .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: generate random number
@Karthikeya: You accept that your for-loop generates a random integer between 0 and 2^d - 1, right? Then take a look at http://en.wikipedia.org/wiki/Rejection_sampling. Basically, you reject any random integer that exceeds b-a. The probability that you reject a number is 1 - (b - a + 1) / (2^d - 1). Call this r. Then the average number of integers rejected is r + r^2 + r^3 + ... = r / (1 - r), so the average number of integers required to produce one [a, b] sample is 1 + r / (1 - r) = 1 / (1 - r) = (2^d - 1) / (b - a + 1). Dave On Feb 26, 12:40 pm, karthikeya s karthikeya.a...@gmail.com wrote: Assuming we have an implementation of RANDOM(0.1), how can we implement RANDOM(a.b) - i.e. given we have a function that returns 0 OR 1 both with a probability of 1/2, how can we implement a function that returns integers from a to b (b a), all with a probability of 1/ n, where n = (b-a+1) my soln: 1.we can run random(0,1) b-a timesand sum up all the values generatedthat is what i thought...but smone told me that it is not correct coz sum follows binomial distribution, thus don't have equally like chance 2.on some site: RANDOM(a,b) range = b - a; d = the number of binary bits %range has do for(i = 1 to d): i th bit of integer res = rand(0,1); while(res range); return (a + res); Each time of while loop need O(log(b-a)) time, and the expectation of that while loop is constant. Therefore, it takes time O(log(b- a))..how does he say that expectation of that while loop is constantm weak with probability.plz enlighten me -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
