Welcome, guest | Sign In | My Account | Store | Cart

Power Of Two (Python recipe) by Thomas Lehmann
ActiveState Code (http://code.activestate.com/recipes/577475/)

  • 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
Download
 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 = [1]

        # 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.
Tags: power_of_two