square and cubic functions in C++

This is a discussion on square and cubic functions in C++ within the C++ Programming forums, part of the General Programming Boards category; It's maybe stupid question, but I can't find any function in C++ for square and higher orders, like x^2, x^3 ...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    3

    square and cubic functions in C++

    It's maybe stupid question, but I can't find any function in C++ for square and higher orders, like x^2, x^3 ....

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,643
    /*whew*/ ... man, I've spent hours perfecting this code for you!


    Code:
    
    template <typename number>
    number squared( number n ) {
      return (n*n);
     }
    
    template <typename number>
    number cubed( number n ) {
      return (n*n*n);
     }
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,643
    For higher orders, use:


    Code:
    
    template <typename number>
    number exponential( number n, int order ) {
       if( order == 0 ) {
        return 0;
       }
     number value = n;
       while(--order) {
        value *= n;
       }
     return value;
     }
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  4. #4
    Registered User
    Join Date
    Oct 2002
    Posts
    3

    Question

    Thanx! But that the easiest way??? It seems to me very complicated for simple function like that...

  5. #5
    Registered User
    Join Date
    Oct 2002
    Posts
    3

    Smile

    That was what I was looking for! It works with float's too ;o)

  6. #6
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    This should be pretty fast for positive integer exponents.
    You can make it even faster by taking out the recursion.
    It takes advantage of the fact that (a ^ (n/2))^2 = a^n.

    Code:
    int exp(int a, int n)
    {
        int r;
    
        if (n == 0)
        {
            r = 1;
        }
        else
        {
            if (n % 2 == 0)
            {
                r = exp(a, n/2);
                r *= r;
            }
            else
            {
                r = exp(a, n-1) * a;
            }
        }
    
        return r;
    }

  7. #7
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,643
    Hmm, nice code, Nick. And I wasn't aware of that fact either. I spotted a place where you could speed it up even more, though, by shifting n once to the right instead of dividing by two.

    Code:
    int exp(int a, int n)
    {
        int r;
    
        if (n == 0)
        {
            r = 1;
        }
        else
        {
            if (n % 2 == 0)
            {
                r = exp(a, (n >> 1) );
                r *= r;
            }
            else
            {
                r = exp(a, n-1) * a;
            }
        }
    
        return r;
    }

    And I think making this solution non-recursive would slow down the algorithm due to the additional manipulations, not to mention making it far more unreadable (of course, if you were using it for graphics, readability would be a non-issue...).
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  8. #8
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    use pow() -- it will be faster and more versatile than anything you can come up with
    hello, internet!

  9. #9
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    You could also
    take out n % 2 == 0 with !(n & 0x00000001). I think
    most compilers would see these optimizations if I had used
    unsigned int. Another way to speed it up would be
    to store maybe the first 200 or so in a table.

  10. #10
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,643
    You could also take out n % 2 == 0 with !(n & 0x00000001).
    Ha! We're on a roll now! Ok Nick, here's the challenge:

    Let's time the following:

    number exponential( number n, int order );

    int exp(int a, int n); //..v1.0, v2.0, v.3.0, and the table lookup version.

    Sound like fun?
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  11. #11
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,643

    Talking

    The template won!

    I didn't use the table lookup, but you can easily add it:

    printout:


    Looping Template: 8 seconds to run 10, 000, 000 iterations...
    Recursive #1: 12 seconds to run 10, 000, 000 iterations...
    Recursive #2: 9 seconds to run 10, 000, 000 iterations...
    Recursive #3: 10 seconds to run 10, 000, 000 iterations...
    Attached Files Attached Files
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  12. #12
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    I think for mine to be faster than yours I think n would
    have to be pretty large. In which case
    the results would overflow an integer.

    You could try this version that uses long double.
    Code:
    #include <iostream>
    using namespace std;
    
    long double exp(long double a, unsigned int n);
    
    int main(void)
    {
        long double a = 1.5;
        int n = 300;
        cout << a << "^" <<  n << " = " <<  exp(a, n) << endl;
        return 0;
    }
    
    long double exp(long double a, unsigned int n)
    {
        unsigned int mask = 0xffffffff;
        unsigned int t = n;
        long double r = a;
    
        if (n == 0)
            return 1.0;
    
        // this finds mask such
        // that if n = 0x00001010
        // mask     = 0x00000100
        // there's probably a faster way to do
        // it but it shouldn't matter much if n is large
        while(t != 0)
        {
            mask <<= 1;
            t &= mask;
        }
    
        mask = ~mask;
        mask ^= (mask >> 1);
        mask >>= 1;
    
        while(mask != 0)
        {
            r *= r;
            if (n & mask)
            {
                r *= a;
            }
            mask >>= 1;
        }
        return r;
    }

  13. #13
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Originally posted by Sebastiani

    Looping Template: 8 seconds to run 10, 000, 000 iterations...
    Recursive #1: 12 seconds to run 10, 000, 000 iterations...
    Recursive #2: 9 seconds to run 10, 000, 000 iterations...
    Recursive #3: 10 seconds to run 10, 000, 000 iterations...
    These results seem very strange...
    At first glance, I thought the more advanced function would win.
    I decided to test it for myself

    I got the result:
    Looping Template: 0 seconds to run 10,000,000 iterations...
    Recursive #1: 0 seconds to run 10,000,000 iterations...
    Recursive #2: 0 seconds to run 10,000,000 iterations...
    Recursive #3: 0 seconds to run 10,000,000 iterations...


    So I had to increase the iterations:
    Looping Template: 6 seconds to run 100,000,000 iterations...
    Recursive #1: 8 seconds to run 100,000,000 iterations...
    Recursive #2: 8 seconds to run 100,000,000 iterations...
    Recursive #3: 7 seconds to run 100,000,000 iterations...
    Moral: Keep the code simple!
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  14. #14
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,643
    So I had to increase the iterations:
    My computer may be old, but it's reliable, damn it!

    What are you running, anyway - 2 GHZ??

    But yeah, I was surprised by the results too, thinking the last recursive would be faster. I think it's wierd that the ratios were so different on our machines, too. Strange...
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  15. #15
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    I change the test so that it
    works for larger n. This is what
    I get
    1.5^300 = 6.72013e+052
    Looping Template: 46.06 seconds to run 10000000 iterations...
    1.5^300 = 6.72013e+052
    Recursive #1: 8.111 seconds to run 10000000 iterations...
    1.5^300 = 6.72013e+052
    Recursive #2: 8.033 seconds to run 10000000 iterations...
    1.5^300 = 6.72013e+052
    Recursive #3: 11.265 seconds to run 10000000 iterations...
    1.5^300 = 6.72013e+052
    Iterative #4: 4.414 seconds to run 10000000 iterations...
    And the winner is Iterative #4 coming in at 4.414 seconds.
    Attached Files Attached Files

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Cubic equation program not giving me right answers
    By face_master in forum C++ Programming
    Replies: 8
    Last Post: 08-24-2006, 05:42 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21