Welcome, guest | Sign In | My Account | Store | Cart
• It's a simple algorithm doing nearly the same what you can do when calculating a multiplication on a piece on paper.
• In python you don't need this. You simply say 2**n and you have it; so see it as prototyping for a final C/C++ program where you are limited by the given datatypes ... as long you don't write a 'BigNumber' class.
Python, 79 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79``` ```import time import cProfile class Timer: # on Windows this is more precise than 'time.time'. function = time.clock # is providing a start time @staticmethod def value(): return Timer.function() # calculating delta between current time and start time. @staticmethod def delta(start): return Timer.function() - start # background information: http://en.wikipedia.org/wiki/Power_of_two class PowerOfTwo: # main calculation @staticmethod def calculateDigits(digits, n, f): maxk = len(digits)-1 while n > 0: rest = 0 k = 0 while k <= maxk: digits[k] = digits[k] * f + rest rest = digits[k] // 10 digits[k] %= 10 k += 1 if rest > 0: digits.append(rest) maxk += 1 n -= 1 # calculating the power of two @staticmethod def calculate(n): digits =  # little performance improvement for k in [3, 2]: if n > 2**k: PowerOfTwo.calculateDigits(digits, n // k, 2**k) n %= k if n > 0: PowerOfTwo.calculateDigits(digits, n, 2) digits.reverse() return digits @staticmethod def dump(digits, digitsPerRow = 50): count = 0 text = "" for digit in digits: if count % digitsPerRow == 0: text += "\n" text += "%d" % (digit) count += 1 print(text) def main(): n = 4000 start = Timer.value() digits = PowerOfTwo.calculate(n) print("2^%d:" % (n)) print("...%d digits calculated" % (len(digits))) print("...took %f seconds" % (Timer.delta(start))) PowerOfTwo.dump(digits) if __name__ == "__main__": main() #cProfile.run("main()") ```
• You can switch the comment in the last two lines to have the profiling output.
• You can change the timer function; I've heard that on Linux the 'time.time' would be the right function.
• A small performance improvement I've made: when 2^8 or 2^4 is possible that I adjust the multiplication to that to have less loop steps.
• I'm currently using a small and not so fast dell notepad and 2^4000 requires usually less than 2 seconds. Created by Thomas Lehmann on Sun, 28 Nov 2010 (MIT)