Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Power of 2 in C

  1. Oct 19, 2007 #1
    I'm trying to write a program that raises 2 to the specified power... and I need help.
    And I don't mean an ordinary 2*2*2, n times and such.

    The method used is slightly strange(kinda backwards).
    For ex. take 256, what the program should do is
    1. Take 2, check if the next digit is greater than 4. As it is there is an overflow which gets added to the product ot the first digit*2
    2. Put the result in a string that is built piece by piece with concatenation.
    3. Repeat for the next digit until the end. Then do the same for the next power, up to the desired one.

    Issues I'm not sure of. Say you reach 512 - there is no zero digit to add the overflow of the first one. My guess is - artificially add one, right?

    Then I have some questions - which will be faster?
    1. Arrays or concatenation and substrings(a function which btw I did not find in the standart libraries).
    2. This method or the usual mathematical ones.
  2. jcsd
  3. Oct 19, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    Yes, unless you're trying to calculate mod some power of 10.

    I'm not sure what you mean by each of these:
    * Most if not all methods for working with large numbers involve arrays on some level.
    * Concatenation methods will be very slow in C, since you'll generally be forced to copy the string many times.
    * Your method is slow, since it doesn't take advantage of the form of the problem or the fast machine instructions.
    * There are many mathematical methods for calculating this, some of which are faster than others.

    Since you're working on a binary computer, I'd expect the bit shift operator to be far faster than your method. "1ULL << 60" calculates 2^60 pretty quickly, around a nanosecond. Your method would take around a microsecond unless the cache slowed it down, in which case it might take 5-10 times as long.

    Of course if you want to do this for really large numbers (ones that won't fit into a double word) you'll have to do some programming, but even then an array of integers would surely be much faster than a series of string arrays, right?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook