467,166 Members | 1,039 Online

# Random Number Generators....

 I have a problem that I really don't understand at all. In my previous post I could get started on my projects I just had a few problems with syntax errors. This problem is something that I don't conceptually understand very well. Here it is: Î* â the ratio of the circumference of a circle to its diameter â is one of the most common and important constants in mathematics. It is an irrational number (a real number that cannot be expressed as the ratio of two integers), but its value has been calculated to more than a million decimal places using different formulas. (See, for example, Petr Beckmann's A History of Î*, St. Martin's Press: New York, 1971) In this assignment you will estimate the value of Î* by simulating randomly throwing darts at a target. The figure at the left is a quarter circle of radius 1.0 inscribed in a square of side 1.0 on the Cartesian plane. It can be show that area of the dark blue quarter circle is Î*/4. If we were to randomly throw d darts at the square, and c of them landed in the circle, we could estimate the value of Î*/4 as c / d, so an approximation of Î* is 4* ( c / d ). Your program should "throw" darts at the target by generating a random coordinate pair (x, y) where x and y are floating point values in the range [0.0, 1.0], which will represent the point the dart hit the target. (You can generate numbers in this range with the expression (double)rand()/RAND_MAX) .) This point will be inside the quarter circle if: sqrt( x2 + y2) <= 1.0 By maintaining counters for the number of darts landing in the quarter circle and the the total number of darts thrown, the value of Î* can be approximated. The larger the number of darts thrown, the better the approximation will be. Your program should use a function that, each time it is called, generates a new random coordinate pair, determines if this pair represents a point inside the quarter circle, and returns a 1 if it is, and a 0 if it is not. Your program should run a simulation for a user-specified number of dart throws, and then display the estimated value of Î* and the percentage difference (percent error) between your estimated value and the true value of Î*; if your estimated value is p, then the percent error is (( p - Î*) / Î* ) * 100. (The actual value of Î* to 15 significant figures is 3.14159265358979.) __________________________________________________ _________________________ I do have some ideas about the variables that I need but I'm not sure how to really implement the rand()/ RAND_MAX function... could someone give a start in the right direction? Feb 26 '06 #1
• viewed: 2428
Share:
40 Replies
 RadiationX wrote: [...] Your program should "throw" darts at the target by generating a random coordinate pair (x, y) where x and y are floating point values in the range [0.0, 1.0], which will represent the point the dart hit the target. (You can generate numbers in this range with the expression (double)rand()/RAND_MAX) [...] I do have some ideas about the variables that I need but I'm not sure how to really implement the rand()/ RAND_MAX function... could someone give a start in the right direction? You do not need to implement the rand() function nor define RAND_MAX; they are part of the Standard C library. Just #include and start using them. -- Eric Sosman es*****@acm-dot-org.invalid Feb 26 '06 #2
 RadiationX wrote: I do have some ideas about the variables that I need but I'm not sure how to really implement the rand()/ RAND_MAX function... could someone give a start in the right direction? Both rand() and the associated constant RAND_MAX are part of the builtin C API. Uli Feb 26 '06 #3
 In article <11*********************@u72g2000cwu.googlegroups. com>, RadiationX wrote: Your program should use a function that, each time it is called,generates a new random coordinate pair, determines if this pairrepresents a point inside the quarter circle, and returns a 1 if it is,and a 0 if it is not. Be careful with that. A -lot- of implementations use linear congruential random number generators for rand(), and there is a well known problem with those that if you use consequative samples from the stream as (x,y) pairs and graph the results, instead of filling a square evenly, you will get a number of noticably seperated diagnonal lines. There are various corrections that one can use to reduce this problem, but the best correction is to use a much better random number generator. One that is said to be fast and very good is the Mersenne Twister, http://www.math.sci.hiroshima-u.ac.j...at/MT/emt.html -- All is vanity. -- Ecclesiastes Feb 26 '06 #4
 On 2006-02-26, RadiationX wrote: __________________________________________________ _________________________ I do have some ideas about the variables that I need but I'm not sure how to really implement the rand()/ RAND_MAX function... could someone give a start in the right direction? rand() and RAND_MAX return integers. so rand()/RAND_MAX either 0 or 1. Think for a moment about why that must be true. So there must be a techinque you can do to ensure that you get a floating point answer from that calculation. I suppose I could tell you it's a FAQ..... You might want to print the value of RAND_MAX. Random number generators start to show predictability when the number of numbers generated gets "close to" the period of the pRNG. RAND_MAX isn't the period, but it will give you a general idea how long the period is. If RAND_MAX is 65535, you probably don't want to use more than 6000 or so values from it in any simulation. There are MANY things to learn about RNGs. Googling the topic will give you more links than you might care to know. Know that there is no software method that can produce "random numbers", only a subset of an arbitrary, albeit ABSOLUTELY predictable sequence of numbers. For MOST applications, the difference doesn't matter all that much. When it DOES matter, it becomes a hardware problem involving things like mason or gamma ray detectors. Feb 26 '06 #5
 In article <-r********************@comcast.com>, Charles Krug wrote:Know that there is no software method that can produce "random numbers",only a subset of an arbitrary, albeit ABSOLUTELY predictable sequence ofnumbers. For MOST applications, the difference doesn't matter all thatmuch. When it DOES matter, it becomes a hardware problem involving things likemason or gamma ray detectors. Or Lava Lamps. -- All is vanity. -- Ecclesiastes Feb 26 '06 #6
 Charles Krug wrote: Know that there is no software method that can produce "random numbers", only a subset of an arbitrary, albeit ABSOLUTELY predictable sequence of numbers. That is true, but some generators (by the way, that should be called pseudo-random generators, because, indeed, we have no means of expressing true randomness algorithmically, or that would be a giant step forward!) are pretty good. One of the best I have used came from one of the D. Knuth books. Simple enough, yet incredibly efficient. You can also try this: http://www.random.org/ It can help either generating random sequences for direct use, or for comparing your own generator with good random sequences, using a statistical tool such as: http://www.fourmilab.ch/random/ At any rate, I strongly suggest implementing the one Knuth suggests. IIRC, it memorizes 55 past numbers to generate a new one (so that should help you find the algorithm in question in "The Art of Computer Programming". Feb 26 '06 #7
 ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) writes: In article <11*********************@u72g2000cwu.googlegroups. com>, RadiationX wrote: Your program should use a function that, each time it is called,generates a new random coordinate pair, determines if this pairrepresents a point inside the quarter circle, and returns a 1 if it is,and a 0 if it is not. Be careful with that. A -lot- of implementations use linear congruential random number generators for rand(), and there is a well known problem with those that if you use consequative samples from the stream as (x,y) pairs and graph the results, instead of filling a square evenly, you will get a number of noticably seperated diagnonal lines. There are various corrections that one can use to reduce this problem, but the best correction is to use a much better random number generator. One that is said to be fast and very good is the Mersenne Twister, http://www.math.sci.hiroshima-u.ac.j...at/MT/emt.html This is good advice for anyone doing real work with random numbers, but I don't think it's something the OP should be worrying about. He has a homework assignment to write a fairly elementary program that uses random sampling to estimate the value of pi. For his purposes, it's reasonable to assume that rand(), when used properly, yields sufficiently random numbers. I suspect that any problems with whatever random number generator he's using aren't going to show up in the number of iterations he's going to be able to use (the method converges very slowly). The OP's major problem is how to write the program, not how to use a random number generator, much less how to implement a high-quality one. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Feb 26 '06 #8
 Thanks for all the help from everyone. I'm working on the solution now Feb 26 '06 #10
 I have not written any code yet, I'm still trying to get my head around this problem. Here are my ideas so far: My only input from the user will be how many darts they choose to throw. This will be an int. Once I get this value I need to generate coordinate pairs from their value of darts. Say they choose 500 darts. What I need then is two variables to hold the coordinate pairs. Say x and y. So, x will get 500 and y will get 500. So I will loop 500 times. Now I need to count the number of 'hits' in the range of sqrt(x^2 + y^2)<= 1.00 I can use a simple IF statement for this counter. I think this is the right track Feb 27 '06 #11
 Ok, I have a question. How do I generate a specific number of random numbers? For instance if I needed 500 random numbers how do I 'put' these 500 numbers into the Random Number Generator? Feb 27 '06 #12
 RadiationX wrote: Ok, I have a question. How do I generate a specific number of random numbers? For instance if I needed 500 random numbers how do I 'put' these 500 numbers into the Random Number Generator? Uh, you don't put numbers INTO the generator, you take them out. Call the rand() function 1000 times (for each of the 500 x & y values you need) and save the returned values. Each time you call it, you'll get back a new random number. Feb 27 '06 #13
 could you give me an example of some sample code ? Feb 27 '06 #14
 "RadiationX" writes: Ok, I have a question. How do I generate a specific number of random numbers? For instance if I needed 500 random numbers how do I 'put' these 500 numbers into the Random Number Generator? Please read . (This doesn't answer your question, but it will greatly help you get answers to any future questions.) -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Feb 27 '06 #15
 RadiationX wrote: could you give me an example of some sample code ? /* randtest.c */ #include #include #include int main() { float r; int i; srand((unsigned int)time((time_t *)NULL)); for (i=0; i<500; ++i) { r[i] = rand() / (RAND_MAX + 1.); r[i] = rand() / (RAND_MAX + 1.); } printf("\n\n"); for (i=0; i<500; ++i) { printf("%f %f\n", r[i],r[i]); } return 0; } Feb 27 '06 #16
 "me********@aol.com" writes: RadiationX wrote: could you give me an example of some sample code ? /* randtest.c */ #include #include #include int main() { float r; int i; srand((unsigned int)time((time_t *)NULL)); [snip] Both casts are unnecessary. As long as the prototypes for srand() and time() are visible (which they are since you have the proper #include directives), the conversions will be done implicitly. Just use: srand(time(NULL)); (You do sometimes need an explicit cast when you're calling a function with a variable number of parameters, such as printf.) -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Feb 27 '06 #17
 ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote: In article <-r********************@comcast.com>, Charles Krug wrote:Know that there is no software method that can produce "random numbers",only a subset of an arbitrary, albeit ABSOLUTELY predictable sequence ofnumbers. For MOST applications, the difference doesn't matter all thatmuch.When it DOES matter, it becomes a hardware problem involving things likemason or gamma ray detectors. Or Lava Lamps. Or tea. Or even ATS; it is the only known purpose for which that substance is useful. Richard Feb 27 '06 #18
 RadiationX wrote: I have not written any code yet, I'm still trying to get my head around this problem. Here are my ideas so far: My only input from the user will be how many darts they choose to throw. This will be an int. Make this a function. Once I get this value I need to generate coordinate pairs from their value of darts. Say they choose 500 darts. What I need then is two variables to hold the coordinate pairs. Say x and y. So, x will get 500 and y will get 500. Hmmm? You already have the 500 from the previous function. No need to save it again (twice) in x or y. So I will loop 500 times. Now I need to count the number of 'hits' in the range of sqrt(x^2 + y^2)<= 1.00 I can use a simple IF statement for this counter. I think this is the right track Define the functions used in main() below and, hopefully, you'll have a working program. Don't forget to #include other necessary headers; maybe test if the user requested 0 (zero) throws. #include int main(void) { int i, inside = 0; int throws = get_user_number(); for (i = 0; i < throws; ++i) { double x = get_random_double(0, 1); double y = get_random_double(0, 1); if (distance_to_origin(x, y) <= 1) { ++inside; } } printf("Out of %d throws, %d were inside the quarter circle.\n", throws, inside); return 0; } -- If you're posting through Google read Feb 27 '06 #19
 Keith Thompson wrote: "me********@aol.com" writes: RadiationX wrote: could you give me an example of some sample code ? /* randtest.c */ #include #include #include int main() { float r; int i; srand((unsigned int)time((time_t *)NULL)); [snip] Both casts are unnecessary. As long as the prototypes for srand() and time() are visible (which they are since you have the proper #include directives), the conversions will be done implicitly. Just use: srand(time(NULL)); (You do sometimes need an explicit cast when you're calling a function with a variable number of parameters, such as printf.) Ok, thanks for pointing that out. BTW, I copied it from the FAQ (some of us _do_ actually look at the FAQ first). -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Feb 27 '06 #20
 "me********@aol.com" writes: Keith Thompson wrote: "me********@aol.com" writes: [...] > srand((unsigned int)time((time_t *)NULL)); [snip] Both casts are unnecessary. As long as the prototypes for srand() and time() are visible (which they are since you have the proper #include directives), the conversions will be done implicitly. Just use: srand(time(NULL)); (You do sometimes need an explicit cast when you're calling a function with a variable number of parameters, such as printf.) Ok, thanks for pointing that out. BTW, I copied it from the FAQ (some of us _do_ actually look at the FAQ first). I've just sent a note to Steve Summit. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Feb 27 '06 #21
 Keith Thompson wrote: "me********@aol.com" writes: RadiationX wrote: could you give me an example of some sample code ? /* randtest.c */ #include #include #include int main() { float r; int i; srand((unsigned int)time((time_t *)NULL)); [snip] Both casts are unnecessary. As long as the prototypes for srand() and time() are visible (which they are since you have the proper #include directives), the conversions will be done implicitly. Just use: srand(time(NULL)); (You do sometimes need an explicit cast when you're calling a function with a variable number of parameters, such as printf.) -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Here is the code that I've written thus far #include #include #include int randG(); int main() { int numDarts; int hits=0; int k; srand(time(NULL)); printf("Enter The number of darts"); scanf("%d", numDarts); for(k=0;k<=numDarts;++k); { randG(); } system("pause"); return 0; } randG() { double x; double y; x = (double)rand()/RAND_MAX; y = (double)rand()/RAND_MAX; if((sqrt(x*x + y*y)<=1.0)) return 1; else return 0; } Feb 27 '06 #22
 RadiationX wrote: Here is the code that I've written thus far Your code gave me a lot of warnings when I tried to compile it. I suggest you turn up your compiler warning level and deal with warnings as if they were errors (and therefore the code doesn't compile) for my compiler (gcc) I do "gcc -W -Wall -Werror -std=c89 -pedantic source.c" #include #include #include #include /* for time() */ int randG(); int main() { int numDarts; int hits=0; int k; srand(time(NULL)); printf("Enter The number of darts"); fflush(stdout); /* make sure printf output is done before reaching the scanf() call */ scanf("%d", numDarts); scanf("%d", &numDarts); ^ for(k=0;k<=numDarts;++k); { randG(); } No matter what the value of numDarts is, randG() will execute exactly once. I think you don't want the last semicolon on the for() line. Also randG() by itself will execute the function, return 0 or 1, and promptly ignore that 0 or 1. You may want to do something with the return value of randG() (maybe adding it to `hits'). Are you going to print something to let you know the number of hits your program achieved? system("pause"); return 0; } randG() int randG() { [snip randG() implementation] -- If you're posting through Google read Feb 28 '06 #23
 "RadiationX" wrote in message news:11********************@i39g2000cwa.googlegrou ps.com... Here is the code that I've written thus far #include #include #include Don't you need to include ? int randG(); int main() { int numDarts; int hits=0; int k; srand(time(NULL)); printf("Enter The number of darts"); scanf("%d", numDarts); You mean: scanf("%d", &numDarts); Maybe you should check for invalid user input later on and handle it appropriately. for(k=0;k<=numDarts;++k); That semicolon is very harmful. You are throwing numDarts+1 here, that will not make any difference, remember that later though. { randG(); More stuff will be here in the future, maybe: if (randG()) hits++; } system("pause"); That is a pretty system specific. return 0; } randG() Why not: int randG()? { double x; double y; x = (double)rand()/RAND_MAX; y = (double)rand()/RAND_MAX; if((sqrt(x*x + y*y)<=1.0)) That sqrt() is not absolutely needed there, if you choose to discard it you can get rid of too. return 1; else return 0; } Feb 28 '06 #24
 stathis gotsis wrote: "RadiationX" wrote in message news:11********************@i39g2000cwa.googlegrou ps.com... Here is the code that I've written thus far #include #include #include Don't you need to include ? int randG(); int main() { int numDarts; int hits=0; int k; srand(time(NULL)); printf("Enter The number of darts"); scanf("%d", numDarts); You mean: scanf("%d", &numDarts); Maybe you should check for invalid user input later on and handle it appropriately. for(k=0;k<=numDarts;++k); That semicolon is very harmful. You are throwing numDarts+1 here, that will not make any difference, remember that later though. { randG(); More stuff will be here in the future, maybe: if (randG()) hits++; } system("pause"); That is a pretty system specific. return 0; } randG() Why not: int randG()? { double x; double y; x = (double)rand()/RAND_MAX; y = (double)rand()/RAND_MAX; if((sqrt(x*x + y*y)<=1.0)) That sqrt() is not absolutely needed there, if you choose to discard it you can get rid of too. How? return 1; else return 0; } Feb 28 '06 #25
 On 2006-02-27, Richard Bos wrote: ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote: In article <-r********************@comcast.com>, Charles Krug wrote: >Know that there is no software method that can produce "random numbers", >only a subset of an arbitrary, albeit ABSOLUTELY predictable sequence of >numbers. For MOST applications, the difference doesn't matter all that >much. >When it DOES matter, it becomes a hardware problem involving things like >mason or gamma ray detectors. Or Lava Lamps. Or tea. Or even ATS; it is the only known purpose for which that substance is useful. Or a device that extracts the whole of the Universe from a piece of fairycake and then tells you "You are HERE"... Feb 28 '06 #26
 stathis gotsis wrote: "RadiationX" wrote in message news:11********************@i39g2000cwa.googlegrou ps.com... Here is the code that I've written thus far #include #include #include Don't you need to include ? int randG(); int main() { int numDarts; int hits=0; int k; srand(time(NULL)); printf("Enter The number of darts"); scanf("%d", numDarts); You mean: scanf("%d", &numDarts); Maybe you should check for invalid user input later on and handle it appropriately. for(k=0;k<=numDarts;++k); That semicolon is very harmful. You are throwing numDarts+1 here, that will not make any difference, remember that later though. { randG(); More stuff will be here in the future, maybe: if (randG()) hits++; } system("pause"); That is a pretty system specific. return 0; } randG() Why not: int randG()? { double x; double y; x = (double)rand()/RAND_MAX; y = (double)rand()/RAND_MAX; if((sqrt(x*x + y*y)<=1.0)) That sqrt() is not absolutely needed there, if you choose to discard it you can get rid of too. return 1; else return 0; }Here is my updated code. I'm not trying to get any quck answers, I really want to learn this stuff. There are some things that I just don't have enough experiece with, and this is one of them #include #include #include #include int randG(); int main() { int numDarts; int hits=0; int k; double pi; srand(time(NULL)); printf("Enter The number of darts"); scanf("%d", &numDarts); for(k=0;k<=numDarts;++k); { hits = randG(); printf("%d\n",hits); } system("pause"); return 0; } randG() { double x; double y; x = (double)rand()/RAND_MAX; y = (double)rand()/RAND_MAX; if((sqrt(x*x + y*y)<=1.0)) return 1; else return 0; } Feb 28 '06 #27
 "me********@aol.com" wrote: stathis gotsis wrote: "RadiationX" wrote in message news:11********************@i39g2000cwa.googlegrou ps.com... { double x; double y; x = (double)rand()/RAND_MAX; y = (double)rand()/RAND_MAX; if((sqrt(x*x + y*y)<=1.0)) That sqrt() is not absolutely needed there, if you choose to discard it you can get rid of too. How? If a non-negative real number is smaller than or equal to 1.0, how large must the square of that number be? Richard Feb 28 '06 #28
 "RadiationX" wrote in message news:11********************@j33g2000cwa.googlegrou ps.com...Here is my updated code. I'm not trying to get any quck answers, I really want to learn this stuff. There are some things that I just don't have enough experiece with, and this is one of them #include #include #include #include int randG(); int main() { int numDarts; int hits=0; int k; double pi; srand(time(NULL)); printf("Enter The number of darts"); scanf("%d", &numDarts); for(k=0;k<=numDarts;++k); { hits = randG(); If you do it this way, hits will be set to 0 or 1. You need to count the number of hits, maybe this way: if (randG()) hits++; printf("%d\n",hits); That prints 0 or 1. It would be a nicer test if you printed the number of hits after the above loop has ended. } system("pause"); return 0; } randG() { double x; double y; x = (double)rand()/RAND_MAX; y = (double)rand()/RAND_MAX; if((sqrt(x*x + y*y)<=1.0)) For a real number a>=0, a<=b <=> a^2<=b^2. You can use that to omit the sqrt(). return 1; else return 0; } Maybe you should consider the comments made in previous posts as well. Feb 28 '06 #29
 Richard Bos wrote: "me********@aol.com" wrote: stathis gotsis wrote: "RadiationX" wrote in message news:11********************@i39g2000cwa.googlegrou ps.com... > { > double x; > double y; > > x = (double)rand()/RAND_MAX; > y = (double)rand()/RAND_MAX; > > if((sqrt(x*x + y*y)<=1.0)) > That sqrt() is not absolutely needed there, if you choose to discard it you can get rid of too. How? If a non-negative real number is smaller than or equal to 1.0, how large must the square of that number be? Oh, I get it. x = 0.9 If the x coordinate is less than 1, its square is less than 1. y = 0.9 And if the y coordinate is less than 1, its square is less than 1. So if the squares of both are less than 1, then the distance from the origin is less than 1. print math.sqrt(x**2 + y**2) 1.27279220614 Uh, what went wrong? Richard Feb 28 '06 #30
 On 2006-02-28, me********@aol.com wrote: Richard Bos wrote: "me********@aol.com" wrote: > stathis gotsis wrote: > > "RadiationX" wrote in message > > news:11********************@i39g2000cwa.googlegrou ps.com... > > > { > > > double x; > > > double y; > > > > > > x = (double)rand()/RAND_MAX; > > > y = (double)rand()/RAND_MAX; > > > > > > if((sqrt(x*x + y*y)<=1.0)) > > > > > > > That sqrt() is not absolutely needed there, if you choose to discard it you > > can get rid of too. > > How? If a non-negative real number is smaller than or equal to 1.0, how large must the square of that number be? Oh, I get it. x = 0.9 If the x coordinate is less than 1, its square is less than 1. True. y = 0.9 And if the y coordinate is less than 1, its square is less than 1. True. So if the squares of both are less than 1, then the distance from the origin is less than 1. False. print math.sqrt(x**2 + y**2) 1.27279220614 Uh, what went wrong? The distance from the origin is 1.27. Hint: the distance from the origin being less than one is determined by being inside the unit _circle_, not the unit square. Feb 28 '06 #31
 Jordan Abel wrote: On 2006-02-28, me********@aol.com wrote: Richard Bos wrote: "me********@aol.com" wrote: > stathis gotsis wrote: > > "RadiationX" wrote in message > > news:11********************@i39g2000cwa.googlegrou ps.com... > > > { > > > double x; > > > double y; > > > > > > x = (double)rand()/RAND_MAX; > > > y = (double)rand()/RAND_MAX; > > > > > > if((sqrt(x*x + y*y)<=1.0)) > > > > > > > That sqrt() is not absolutely needed there, if you choose to discard it you > > can get rid of too. > > How? If a non-negative real number is smaller than or equal to 1.0, how large must the square of that number be? Oh, I get it.> x = 0.9 If the x coordinate is less than 1, its square is less than 1. True.> y = 0.9 And if the y coordinate is less than 1, its square is less than 1. True. So if the squares of both are less than 1, then the distance from the origin is less than 1. False.> print math.sqrt(x**2 + y**2) 1.27279220614 Uh, what went wrong? The distance from the origin is 1.27. Hint: the distance from the origin being less than one is determined by being inside the unit _circle_, not the unit square. Yeah, _I_ know that. I'm waiting to hear Richards Bos' explanation of how to determine distance without using sqrt. The stuff about how big the square of a number <1 must be doesn't cut it. Feb 28 '06 #32
 In article <11*********************@t39g2000cwt.googlegroups. com>, me********@aol.com wrote: > Richard Bos wrote: >> > > > if((sqrt(x*x + y*y)<=1.0)) >> > > That sqrt() is not absolutely needed there, if you choose to discard it you >> > > can get rid of too. Yeah, _I_ know that. I'm waiting to hear Richards Bos' explanationof how to determine distance without using sqrt. The stuff abouthow big the square of a number <1 must be doesn't cut it. He didn't say that you could determine distances without using sqrt(). He said "that sqrt() is not absolutely needed there". If sqrt(x*x+y*y) < c then by squaring both sides, sqrt(x*x+y*y)*sqrt(x*x+y*y) < c*c so x*x+y*y < c*c but when c is 1.0 then c*c is also 1.0 so the test in the code in question could be: if ((x*x + y*y) <= 1.0) Thus the sqrt() was indeed not absolutely needed there and could be discarded in that particular code. Richard made no claim about other code. -- Programming is what happens while you're busy making other plans. Feb 28 '06 #33
 me********@aol.com wrote: stathis gotsis wrote: "RadiationX" wrote in message news:11********************@i39g2000cwa.googlegrou ps.com... > > if((sqrt(x*x + y*y)<=1.0)) That sqrt() is not absolutely needed there, if you choose to discard it you can get rid of too. How? sqrt(FOOBAR) <= 1.0 but 1.0 == sqrt(1.0), so that can written that as sqrt(FOOBAR) <= sqrt(1.0) and, as all the numbers are positive, the "sqrt()" can be safely removed FOOBAR <= 1.0 to get an equivalent condition. -- If you're posting through Google read Feb 28 '06 #34
 On 2006-02-28, me********@aol.com wrote: Jordan Abel wrote: On 2006-02-28, me********@aol.com wrote: > > Richard Bos wrote: >> "me********@aol.com" wrote: >> >> > stathis gotsis wrote: >> > > "RadiationX" wrote in message >> > > news:11********************@i39g2000cwa.googlegrou ps.com... >> > > > { >> > > > double x; >> > > > double y; >> > > > >> > > > x = (double)rand()/RAND_MAX; >> > > > y = (double)rand()/RAND_MAX; >> > > > >> > > > if((sqrt(x*x + y*y)<=1.0)) >> > > > >> > > >> > > That sqrt() is not absolutely needed there, if you choose to discard it you >> > > can get rid of too. >> > >> > How? >> >> If a non-negative real number is smaller than or equal to 1.0, how large >> must the square of that number be? > > Oh, I get it. > >>>> x = 0.9 > > If the x coordinate is less than 1, its square is less than 1. True. >>>> y = 0.9 > > And if the y coordinate is less than 1, its square is less than 1. True. > So if the squares of both are less than 1, then the distance > from the origin is less than 1. False. > >>>> print math.sqrt(x**2 + y**2) > 1.27279220614 > > Uh, what went wrong? The distance from the origin is 1.27. Hint: the distance from the origin being less than one is determined by being inside the unit _circle_, not the unit square. Yeah, _I_ know that. I'm waiting to hear Richards Bos' explanation of how to determine distance without using sqrt. The stuff about how big the square of a number <1 must be doesn't cut it. But you're not looking at the square of X and the square of Y - you're looking at the square of the distance, which is the sum of those two squares. Feb 28 '06 #35
 Walter Roberson wrote: In article <11*********************@t39g2000cwt.googlegroups. com>, me********@aol.com wrote: > Richard Bos wrote: >> > > > if((sqrt(x*x + y*y)<=1.0))> > > That sqrt() is not absolutely needed there, if you choose to discard it you >> > > can get rid of too.Yeah, _I_ know that. I'm waiting to hear Richards Bos' explanationof how to determine distance without using sqrt. The stuff abouthow big the square of a number <1 must be doesn't cut it. He didn't say that you could determine distances without using sqrt(). He said "that sqrt() is not absolutely needed there". If sqrt(x*x+y*y) < c then by squaring both sides, sqrt(x*x+y*y)*sqrt(x*x+y*y) < c*c so x*x+y*y < c*c but when c is 1.0 then c*c is also 1.0 so the test in the code in question could be: if ((x*x + y*y) <= 1.0) Thus the sqrt() was indeed not absolutely needed there and could be discarded in that particular code. Richard made no claim about other code. Ok, I see it. Another fine example of the kind of thinking that makes space shuttles explode. -- Programming is what happens while you're busy making other plans. Feb 28 '06 #36
 "me********@aol.com" writes: Walter Roberson wrote: [...] He didn't say that you could determine distances without using sqrt(). He said "that sqrt() is not absolutely needed there". If sqrt(x*x+y*y) < c then by squaring both sides, sqrt(x*x+y*y)*sqrt(x*x+y*y) < c*c so x*x+y*y < c*c but when c is 1.0 then c*c is also 1.0 so the test in the code in question could be: if ((x*x + y*y) <= 1.0) Thus the sqrt() was indeed not absolutely needed there and could be discarded in that particular code. Richard made no claim about other code. Ok, I see it. Another fine example of the kind of thinking that makes space shuttles explode. Huh??? The test if (x*x + y*y <= 1.0) is mathematically and practically equivalent to if (sqrt(x*x + y*y) <= 1.0) and likely to be substantially more efficient. We don't need to compute the distance; we only care whether the distance is less than or equal to 1.0, and we can easily determine that from the square of the distance, which is easier to compute. Are you implying that there's something dangerous about this simple optimization? If so, what? -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Feb 28 '06 #37
 Keith Thompson wrote: "me********@aol.com" writes: Walter Roberson wrote: [...] He didn't say that you could determine distances without using sqrt(). He said "that sqrt() is not absolutely needed there". If sqrt(x*x+y*y) < c then by squaring both sides, sqrt(x*x+y*y)*sqrt(x*x+y*y) < c*c so x*x+y*y < c*c but when c is 1.0 then c*c is also 1.0 so the test in the code in question could be: if ((x*x + y*y) <= 1.0) Thus the sqrt() was indeed not absolutely needed there and could be discarded in that particular code. Richard made no claim about other code. Ok, I see it. Another fine example of the kind of thinking that makes space shuttles explode. Huh??? The test if (x*x + y*y <= 1.0) is mathematically and practically equivalent to if (sqrt(x*x + y*y) <= 1.0) and likely to be substantially more efficient. We don't need to compute the distance; we only care whether the distance is less than or equal to 1.0, and we can easily determine that from the square of the distance, which is easier to compute. Are you implying that there's something dangerous about this simple optimization? If so, what? Never mind. I've re-thought it. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Mar 1 '06 #38
 ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote: In article <11*********************@t39g2000cwt.googlegroups. com>, me********@aol.com wrote: > Richard Bos wrote: >> > > > if((sqrt(x*x + y*y)<=1.0))> > > That sqrt() is not absolutely needed there, if you choose to discard it you >> > > can get rid of too.Yeah, _I_ know that. I'm waiting to hear Richards Bos' explanationof how to determine distance without using sqrt. You're not determining the exact distance, you're only trying to discover whether it's smaller than a certain number. And since the square root function is strictly ascending... The stuff about how big the square of a number <1 must be doesn't cut it. Do the actual math on the actual functions, not on an incoherent jumble of words. He didn't say that you could determine distances without using sqrt(). He said "that sqrt() is not absolutely needed there". Actually, I didn't. stathis gotsis wrote that. All I did was agree, and point out why. Richard Mar 2 '06 #39
 Richard Bos wrote: ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote: In article <11*********************@t39g2000cwt.googlegroups. com>, me********@aol.com wrote:> > Richard Bos wrote:> >> > > > if((sqrt(x*x + y*y)<=1.0))> >> > > That sqrt() is not absolutely needed there, if you choose to discard it you> >> > > can get rid of too.Yeah, _I_ know that. I'm waiting to hear Richards Bos' explanationof how to determine distance without using sqrt. You're not determining the exact distance, you're only trying to discover whether it's smaller than a certain number. Yeah, it's already been cleared up. And since the square root function is strictly ascending...The stuff about how big the square of a number <1 must be doesn't cut it. Do the actual math on the actual functions, not on an incoherent jumble of words. I DID do the actual math. But because you were not clear, I went down the wrong path and got nonsensical results. And since I believed that I understood what I think you said, it did not occur to me that what I heard was not what you meant. He didn't say that you could determine distances without using sqrt(). He said "that sqrt() is not absolutely needed there". Actually, I didn't. stathis gotsis wrote that. All I did was agree, and point out why. The issue is settled as far as I'm concerned. Richard Mar 2 '06 #40
 "Richard Bos" wrote in message news:44****************@news.xs4all.nl... ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote: In article <11*********************@t39g2000cwt.googlegroups. com>, me********@aol.com wrote:> > Richard Bos wrote:> >> > > > if((sqrt(x*x + y*y)<=1.0))> >> > > That sqrt() is not absolutely needed there, if you choose to discard it you> >> > > can get rid of too.Yeah, _I_ know that. I'm waiting to hear Richards Bos' explanationof how to determine distance without using sqrt. You're not determining the exact distance, you're only trying to discover whether it's smaller than a certain number. And since the square root function is strictly ascending... Or that since both root and 1 are non-negative numbers... But this way we implicitly use the fact that x^2 is strictly ascending for x>=0. Mar 3 '06 #41

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

 1 post views Thread by Brandon Michael Moore | last post: by 7 posts views Thread by Ioannis Vranos | last post: by 23 posts views Thread by MConly | last post: by 5 posts views Thread by Peteroid | last post: by 15 posts views Thread by felixnielsen@hotmail.com | last post: by 11 posts views Thread by TreatmentPlant | last post: by reply views Thread by urkel | last post: by 7 posts views Thread by BillG | last post: by 16 posts views Thread by jason.cipriani@gmail.com | last post: by 6 posts views Thread by Otekpo Emmanuel | last post: by reply views Thread by SwissProgrammer | last post: by 1 post views Thread by SwissProgrammer | last post: by 3 posts views Thread by SwissProgrammer | last post: by 1 post views Thread by AccessUser22 | last post: by 1 post views Thread by vinayak1209 | last post: by reply views Thread by isladogs | last post: by reply views Thread by jobsrod | last post: by reply views Thread by nearlyhub | last post: by