Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

computational efficiency

by thelycaeum (Initiate)
on Oct 04, 2011 at 17:55 UTC ( [id://929619]=perlquestion: print w/replies, xml ) Need Help??

thelycaeum has asked for the wisdom of the Perl Monks concerning the following question:

I want to program a subroutine that randomizes an angle and rotates some coordinates in 3D by that angle. The rotation matrices are already working, so the mathematics are not the problem. I'll have to do that a couple of hundred times to a couple of hundred thousand times, so right now I'm thinking of how to optimize the code. On the one hand I could randomize the sine of the angle and calculate the cosine (both needed for rotation matrices) using the following relation:
$sine=rand(2)-1; $cosine=sqrt(1-$sine**2);
On the other hand I could randomize the angle and calculate both sine and cosine from the angle.
$angle=rand(2*3.14159); $sine=sin($angle); $cosine=cos($angle);
How can I find out which option is more efficient?

Replies are listed 'Best First'.
Re: computational efficiency
by BrowserUk (Patriarch) on Oct 04, 2011 at 18:12 UTC

    Use Benchmark:

    cmpthese -1, { a=>q[ $sine = rand( 2 ) - 1; $cosine = sqrt( 1 - $sine**2 ); ], b=>q[ $angle = rand( 2 *3.14159 ); $sine = sin( $angle ); $cosine = cos( $angle ); ], };; Rate a b a 1614300/s -- -28% b 2246655/s 39% --

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re: computational efficiency
by Lotus1 (Vicar) on Oct 04, 2011 at 18:51 UTC

    What is the application? Do you need a uniform distribution of angles? of points on a circle? of points on a sphere?

    Picking random sine values won't give you a uniform distribution of values for the angles. So for example, if you plot the points on a circle for the randomly chosen sine values then you end up with a higher density of points at certain points along the circumference.

    Probably overkill for your application but I did something similar years ago for picking points on the surface of a sphere and this article was helpful. http://mathworld.wolfram.com/SpherePointPicking.html

      I've read the article a couple of times by now. Let me comment on that.

      I've been planning to randomize my rotation subroutine by doing three subsequent arbitrary rotations about each axis in cartesian space, i.e. arbitrary rotation with independent randomization for each axis x, y and z. These however have to be randomized by two randomization processes each, as the sign of the cosine corresponding to the randomized sine has to randomized, too (if I'm not mistaken here, cf. my reply to moritz comment on correctness). Hence, my (thanks to your comments) improved idea would involve six randomizations for each arbitrary rotation, while the method posted on wolfram would involve only two (cf. equations 9 to 11 in the article), correct?

      What I'm asking myself right now is the following: Moritz is absolutely correct, as a single rotation about one axis (which was my original question) results in omitting half of the angles, consequently incompleteness and bias towards rotation angles below 180°. Would this still be true, if the routine is applied about each axis xyz? So, if Marsaglia (1972) uses two randomizations to produce an arbitrary point in three dimensional space in the polar coordinate system, would three randomizations in cartesian space still result in incompleteness? I think so, because equations 13 to 15 imply, that at least four randomizations are needed in cartesian space... ?

      P.S.: MidLifeXis: Thank you, I found  use Benchmark qw(:all) ;on http://perldoc.perl.org/Benchmark.html

        The approach I like for this problem is what Perlbotics suggested. Make a table. I suggest a hash of arrays where the keys are angles and each value is an array of sin and cos values. Then you choose a random angle (0-360) and get both sin and cos from a fast hash with the negative signs included. This takes care of all four quadrands.

        Do this for each axis of rotation as you proposed. The article I posted was about picking uniformly distributed points on the surface of a sphere which I believe is more difficult than your problem. The only point I was making with my previous post is that if you pick random sine values the corresponding angles are not uniformly distributed. I'm not sure about proving this approach of three rotations but it seems good to me. I'll think about it more and maybe I'll come up with a proof.

        use warnings; use strict; my $ref_trig = make_trigtable(); print "\nangle sine cosine\n"; foreach (1..15) { my $angle = sprintf "%.1f", rand(3600)/10; printf "%5.1f %8.5f %8.5f\n", $angle, $ref_trig->{$angle}[0], $ref +_trig->{$angle}[0]; } sub make_trigtable { use constant PI => 4 * atan2(1, 1); use constant DEG_TO_RAD => PI / 180; my %trig; foreach (0..3600) { my $angle = sprintf "%.1f", $_/10; $trig{$angle}=[sin $angle * DEG_TO_RAD, cos $angle * DEG_TO_RA +D]; } return \%trig; } __END__ C:\perlmonks>perl sinhash.pl angle sine cosine 216.2 -0.59061 -0.59061 268.6 -0.99970 -0.99970 166.8 0.22835 0.22835 276.8 -0.99297 -0.99297 81.6 0.98927 0.98927 355.4 -0.08020 -0.08020 11.9 0.20620 0.20620 82.3 0.99098 0.99098 70.1 0.94029 0.94029 173.1 0.12014 0.12014 14.5 0.25038 0.25038 251.3 -0.94721 -0.94721 161.6 0.31565 0.31565 117.7 0.88539 0.88539 319.7 -0.64679 -0.64679
Re: computational efficiency
by MidLifeXis (Monsignor) on Oct 04, 2011 at 18:09 UTC
Re: computational efficiency
by Perlbotics (Bishop) on Oct 04, 2011 at 18:15 UTC

    If you have got a limited set of angles - or it is allowed to quantise them - I would suggest to cache the computed values or use a pre-computed table of all sines/cosines. E.g. 0.00-359.99 results in a table holding 72000 values - quite feasible.

Re: computational efficiency
by moritz (Cardinal) on Oct 05, 2011 at 10:01 UTC
    First focus on which one is correct. $cosine = sqrt(1 - $sine**2) will only give you non-negative $cosine values, so that solution will only cover 2 of four possible quandrants.

    In cases involving random numbers, it helps to know the theory of how probability density functions are transformed; if you don't want to learn the theory, at least create a few hundred or thousand random points with each method you consider, and plot them in some way -- either in a histogram, or in a density plot or so. That way you have a chance to see if the resulting distribution is what you want.

    MJD #11963, It's easy to get the *wrong* answer in O(1) time.

Re: computational efficiency
by zentara (Archbishop) on Oct 05, 2011 at 09:52 UTC
    I'll have to do that a couple of hundred times to a couple of hundred thousand times, so right now I'm thinking of how to optimize the code.

    You might want to look at PDL, or make a custom Inline::C program to do the calculations. PDL uses very fast Fortran routines to do it's math. Plain Perl's math is slowed down by the overhead it uses on maintaining variable type, so it is not best for computational efficiency.


    I'm not really a human, but I play one on earth.
    Old Perl Programmer Haiku ................... flash japh
      Plain PDL uses C, not Fortran, routines for its calculations (except in PDL::Slatec and PDL::Minuit, which are bindings to supplied Fortran routines, if the system has a Fortran compiler). However PDL::LinearAlgebra is a binding to LAPACK. That was originally in Fortran, but increasingly parts of the implementations you'll find installed or packaged are written in C and/or C++.
Re: computational efficiency
by roboticus (Chancellor) on Oct 05, 2011 at 11:04 UTC

    thelycaeum:

    Are you even sure it's a problem? You're talking about a couple hundred thousand times, but BrowserUk's benchmark shows that even the slower one is capable of well over a million per second. I'd suggest that if your code is running too slowly, profile it and see which parts take enough time to be worth optimizing. After all, if you can generate a million random sin/cos pairs in a second with the slow method, and need only a few hundred thousand per run, you can't even shave a second off your runtime even if your new version takes *no time at all*.

    ...roboticus

    When your only tool is a hammer, all problems look like your thumb.

Re: computational efficiency
by Old_Gray_Bear (Bishop) on Oct 05, 2011 at 14:37 UTC
    The three steps to writing Good Code:
    1. Make it run
    2. Make it run right
    3. Make it run fast
    Keep your notes about optimization around for when you get to the third step. (No, I don't remember who said it; probably Kernigan.)

    Update -- fixed typo

    ----
    I Go Back to Sleep, Now.

    OGB

      First of all, thanks for all of your replies.

      BrowserUK: I'll try that one, I think it's exactly the benchmark code I was looking for.

      Perlbotics: Quantizing the angles seems to be a good idea. At first glance, the following problem arises in my mind: To achieve random 3D rotation, I have to apply rotations around the x,y and z axis. Do you think I could achieve a random probability distribution by simply randomizing the rotation axis and walking through the quantized angles with a foreach loop?

      Lotus1 & moritz: Thanks moritz, I thought about that shortly after the post. I could get rid of that problem by randomizing the sign of the cosine... shouldn't I? I'll think about that and read the article lotus posted, I don't understand it yet.

      zentara: Actually, I intend to learn how to use PDL by writing that program. However, I wanted to get started by writing a backbone in Perl and only solve the more sophisticated problems with PDL. I was having some problems with the notation of complex values in the PDL:FFTW package before, therefore I was wondering what I could program in Perl efficiently and what not.

      roboticus: Very good point, I'll do some analysis on the probability distribution for both methods using BrowserUK's code and I'll work on the point moritz made about the two vs. four quadrants.

      hardburn: I've messing around with POGL a bit, but I think it's too much for me... yet ;)

      Old_Gray_Bear: Thanks, I don't have much programming experience and so I was looking for some hints on how to plan this project.

      Thanks again for all of these great comments :)
Re: computational efficiency
by hardburn (Abbot) on Oct 05, 2011 at 12:57 UTC

    Do you have 3D acceleration hardware available? Rotating coordinates are something GPUs will be very good at. Just a matter of making the right OpenGL incantations.


    "There is no shame in being self-taught, only in not trying to learn in the first place." -- Atrus, Myst: The Book of D'ni.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://929619]
Approved by BrowserUk
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others pondering the Monastery: (5)
As of 2024-03-19 09:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found