Suppose I have a function rand() that can generate one integer random
number between 0 and 100. Suppose also rand() is very expensive. What
is the fastest way to generate 10 different random number between 0 and
100? (call rand() only 10 times...)
Thanks,
qq 11 2865
quick...@yahoo.com wrote: Suppose I have a function rand() that can generate one integer random number between 0 and 100. Suppose also rand() is very expensive. What is the fastest way to generate 10 different random number between 0 and 100? (call rand() only 10 times...)
Thanks,
qq
If you're not talking about the standard function std::rand(), then
your post is off topic here since it is not concerned with the C++
language or libraries. See the FAQ for what is on-topic: http://www.parashift.com/c++-faq-lit...t.html#faq-5.9. You
probably want a newsgroup dealing with algorithms in general (e.g.,
comp.programming) or one dealing with random number generation.
Cheers! --M qu******@yahoo.com wrote: Suppose I have a function rand() that can generate one integer random number between 0 and 100. Suppose also rand() is very expensive. What is the fastest way to generate 10 different random number between 0 and 100? (call rand() only 10 times...)
Is there a C++ language question somewhere hiding in all this? For
general programming questions consider 'comp.programming'.
If you're talking about the Standard function 'rand', then it (a) doesn't
generate 0 to 100 numbers, its limits are 0 and RAND_MAX, and (b) is in
fact quite inexpensive.
V qu******@yahoo.com wrote: Suppose I have a function rand() that can generate one integer random number between 0 and 100. Suppose also rand() is very expensive. What is the fastest way to generate 10 different random number between 0 and 100? (call rand() only 10 times...)
Thanks,
qq
I don't think it is possible to solve that problem and guarantee to only
call rand() 10 times. I could be wrong.
john
John Harrison wrote: qu******@yahoo.com wrote: Suppose I have a function rand() that can generate one integer random number between 0 and 100. Suppose also rand() is very expensive. What is the fastest way to generate 10 different random number between 0 and 100? (call rand() only 10 times...)
I don't think it is possible to solve that problem and guarantee to only call rand() 10 times. I could be wrong.
You can, for example, create a list with the numbers from 0 to 100, call
rand, pick the number obtained and remove it from the list, call rand and
pick the number obtained modulus the remaining elements in the list, remove
it from the list, and repeat the times desired.
--
Salu2
John Harrison wrote: qu******@yahoo.com wrote:
Suppose I have a function rand() that can generate one integer random number between 0 and 100. Suppose also rand() is very expensive. What is the fastest way to generate 10 different random number between 0 and 100? (call rand() only 10 times...)
Thanks,
qq
I don't think it is possible to solve that problem and guarantee to only call rand() 10 times. I could be wrong.
I am thinking something in the direction of: make a vector of 100 values,
ten loops, each containing: a calls to 'rand()' to get an index, extract
the value from the vector, amend the value indexed to the value below or
above it, unless it's been already extracted, then keep going in that
direction until reaching the value that hasn't been extracted yet. The
proof of the randomness of the values extracted that way lies on the OP.
V
Julián Albo wrote: John Harrison wrote:
qu******@yahoo.com wrote:
Suppose I have a function rand() that can generate one integer random number between 0 and 100. Suppose also rand() is very expensive. What is the fastest way to generate 10 different random number between 0 and 100? (call rand() only 10 times...)
I don't think it is possible to solve that problem and guarantee to only call rand() 10 times. I could be wrong.
You can, for example, create a list with the numbers from 0 to 100, call rand, pick the number obtained and remove it from the list, call rand and pick the number obtained modulus the remaining elements in the list, remove it from the list, and repeat the times desired.
But after you remove an item for the list you need a random number from
0 to 99, and you haven't got that. By using a modulus you are biasing
the pick, so unless you list is random in the first place (which it
isn't) you are going to get biased results.
john
Julián Albo wrote: John Harrison wrote:
qu******@yahoo.com wrote:
Suppose I have a function rand() that can generate one integer random number between 0 and 100. Suppose also rand() is very expensive. What is the fastest way to generate 10 different random number between 0 and 100? (call rand() only 10 times...)
I don't think it is possible to solve that problem and guarantee to only call rand() 10 times. I could be wrong.
You can, for example, create a list with the numbers from 0 to 100, call rand, pick the number obtained and remove it from the list, call rand and pick the number obtained modulus the remaining elements in the list, remove it from the list, and repeat the times desired.
The OP didn't specify but if the desired distribution is uniformly
random then this will not work (i.e., not all outcomes are equally likely).
Victor Bazarov wrote: John Harrison wrote:
qu******@yahoo.com wrote:
Suppose I have a function rand() that can generate one integer random number between 0 and 100. Suppose also rand() is very expensive. What is the fastest way to generate 10 different random number between 0 and 100? (call rand() only 10 times...)
Thanks,
qq
I don't think it is possible to solve that problem and guarantee to only call rand() 10 times. I could be wrong.
I am thinking something in the direction of: make a vector of 100 values, ten loops, each containing: a calls to 'rand()' to get an index, extract the value from the vector, amend the value indexed to the value below or above it, unless it's been already extracted, then keep going in that direction until reaching the value that hasn't been extracted yet. The proof of the randomness of the values extracted that way lies on the OP.
V
It's clever, but it doesn't sound random to me.
Suppose your initial list is 0 to 100 and the first random number picks
5. So 5 is one of your random numbers, but in the list 5 gets replaced
with the next higher number, i.e. 6. So now you have two sixes in the
list. And if either of those sixes gets hit you'll have three sevens, etc.
I think you'll will get more bunching than you would with a
straightforward random pick.
john
John Harrison wrote: You can, for example, create a list with the numbers from 0 to 100, call rand, pick the number obtained and remove it from the list, call rand and pick the number obtained modulus the remaining elements in the list, remove it from the list, and repeat the times desired.
But after you remove an item for the list you need a random number from 0 to 99, and you haven't got that. By using a modulus you are biasing the pick, so unless you list is random in the first place (which it isn't) you are going to get biased results.
Is a random result. Certainly is not equally distributed as the original
rand function, but the distribution properties of the result were not in
the OP conditions, it just asked for speed and for call rand 10 times.
--
Salu2 qu******@yahoo.com wrote: Suppose I have a function rand() that can generate one integer random number between 0 and 100. Suppose also rand() is very expensive. What is the fastest way to generate 10 different random number between 0 and 100? (call rand() only 10 times...)
Thanks,
qq
This is an instance of a general problem of converting random values
from one set into random values from another set. In your case there
are (100 C 10) possible outcomes and you have random values from a set
of size 100. Since (100 C 10) is not divisible by 100, there is no way
to guarantee the number of required operations.
You can do well on expectation though and a short illustration should
give you the idea. Suppose you want to pick a number between 1 and 5
and you only have a coin. Flip it three times to get a number between 1
and 8. If the number is less than or equal to 5, you're done.
Otherwise you have one of three numbers. Flip once more get another bit
which, combined with the leftover choice among three, gives you one
among 6 values. If the value is 1-5 your done, otherwise repeat the
process.
I'm not sure this is optimal but as you can see, unless rand() truly is
expensive, it's probably not worth the effort.
Mark
On 2005-11-11, John Harrison <jo*************@hotmail.com> wrote: Victor Bazarov wrote: John Harrison wrote: qu******@yahoo.com wrote: Suppose I have a function rand() that can generate one integer random number between 0 and 100. Suppose also rand() is very expensive. What is the fastest way to generate 10 different random number between 0 and 100? (call rand() only 10 times...) I am thinking something in the direction of: make a vector of 100 values, ten loops, each containing: a calls to 'rand()' to get an index, extract the value from the vector, amend the value indexed to the value below or above it, unless it's been already extracted, then keep going in that direction until reaching the value that hasn't been extracted yet. The proof of the randomness of the values extracted that way lies on the OP.
V
It's clever, but it doesn't sound random to me.
Suppose your initial list is 0 to 100 and the first random number picks 5. So 5 is one of your random numbers, but in the list 5 gets replaced with the next higher number, i.e. 6. So now you have two sixes in the list. And if either of those sixes gets hit you'll have three sevens, etc.
I think you'll will get more bunching than you would with a straightforward random pick.
If the OP really gave a crap about randomness he wouldn't be
worried about getting duplicates. ;-)
Anyhow, I took a stab at it, using a rotating translation table.
And, err, rand_expensive needs to be *really* expensive before
adopting this solution.
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstdlib>
#include <ctime>
using namespace std;
int rand_expensive()
{
/* Spend millions of resources somehow doing the following: */
return rand()%101;
}
struct counter
{
int c_;
counter(int c): c_(c) { }
int operator()()
{
return c_++;
}
};
int main()
{
srand(time(0));
vector<int> nums;
vector<int> range(101);
generate_n(range.begin(), 101, counter(0));
for (int i = 0; i < 10; ++i) {
int r = rand_expensive();
while (find(nums.begin(), nums.end(), range[r]) != nums.end())
{
rotate(range.begin(), range.begin()+1, range.end());
}
nums.push_back(range[r]);
}
copy(nums.begin(), nums.end(), ostream_iterator<int>(cout, " "));
cout << endl;
return 0;
}
--
Neil Cerutti This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Zhang Le |
last post by:
Hi,
I did a small benchmark of matrix-vector multiply operation using
Numeric module. I'm a bit suprised to find matrix*col-vector is much
faster than row-vector*matrix. I wonder whether other...
|
by: Virus |
last post by:
Ok well what I am trying to do is have
1.) the background color to change randomly with 5 different colors.(change
on page load)
2,) 10 different quotes randomly fadeing in and out in random...
|
by: Peteroid |
last post by:
I know how to use rand() to generate random POSITIVE-INTEGER numbers.
But, I'd like to generate a random DOUBLE number in the range of 0.0 to 1.0
with resolution of a double (i.e., every possible...
|
by: vips |
last post by:
I have a string
str="10*12*14"
now I want the total of this value
i.e. 10 multiply 12 multiply 14
how do i get it ?
is there any function in vb.net to do that ??
if i put it as query to...
|
by: fatimahtaher |
last post by:
Hi,
I am supposed to create a program that generates a random number and then asks the user to guess the number (1-100). The program tells the user if he guessed too high or too low. If he...
|
by: jjmillertime |
last post by:
I'm new so i apologize if this is in the wrong spot. I'm also new to
programming in C and i've been searching for quite a while on how to
create a program using C that will generate two random...
|
by: Janaka Perera |
last post by:
Hi All,
We have done a object oriented design for a system which will create a
class multiply inherited by around 1000 small and medium sized
classes.
I would be greatful if you can help me...
|
by: Peter Oliphant |
last post by:
I would like to be able to create a random number generator that produces
evenly distributed random numbers up to given number.
For example, I would like to pick a random number less than 100000,...
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
|
by: ryjfgjl |
last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
| |