(w, base, more_than, *, need_hi=False, show=False)
| 55 | # See code near end of file for a block of code that can be enabled to |
| 56 | # run millions of tests. |
| 57 | def compute_powers(w, base, more_than, *, need_hi=False, show=False): |
| 58 | seen = set() |
| 59 | need = set() |
| 60 | ws = {w} |
| 61 | while ws: |
| 62 | w = ws.pop() # any element is fine to use next |
| 63 | if w in seen or w <= more_than: |
| 64 | continue |
| 65 | seen.add(w) |
| 66 | lo = w >> 1 |
| 67 | hi = w - lo |
| 68 | # only _need_ one here; the other may, or may not, be needed |
| 69 | which = hi if need_hi else lo |
| 70 | need.add(which) |
| 71 | ws.add(which) |
| 72 | if lo != hi: |
| 73 | ws.add(w - which) |
| 74 | |
| 75 | # `need` is the set of exponents needed. To compute them all |
| 76 | # efficiently, possibly add other exponents to `extra`. The goal is |
| 77 | # to ensure that each exponent can be gotten from a smaller one via |
| 78 | # multiplying by the base, squaring it, or squaring and then |
| 79 | # multiplying by the base. |
| 80 | # |
| 81 | # If need_hi is False, this is already the case (w can always be |
| 82 | # gotten from w >> 1 via one of the squaring strategies). But we do |
| 83 | # the work anyway, just in case ;-) |
| 84 | # |
| 85 | # Note that speed is irrelevant. These loops are working on little |
| 86 | # ints (exponents) and go around O(log w) times. The total cost is |
| 87 | # insignificant compared to just one of the bigint multiplies. |
| 88 | cands = need.copy() |
| 89 | extra = set() |
| 90 | while cands: |
| 91 | w = max(cands) |
| 92 | cands.remove(w) |
| 93 | lo = w >> 1 |
| 94 | if lo > more_than and w-1 not in cands and lo not in cands: |
| 95 | extra.add(lo) |
| 96 | cands.add(lo) |
| 97 | assert need_hi or not extra |
| 98 | |
| 99 | d = {} |
| 100 | for n in sorted(need | extra): |
| 101 | lo = n >> 1 |
| 102 | hi = n - lo |
| 103 | if n-1 in d: |
| 104 | if show: |
| 105 | print("* base", end="") |
| 106 | result = d[n-1] * base # cheap! |
| 107 | elif lo in d: |
| 108 | # Multiplying a bigint by itself is about twice as fast |
| 109 | # in CPython provided it's the same object. |
| 110 | if show: |
| 111 | print("square", end="") |
| 112 | result = d[lo] * d[lo] # same object |
| 113 | if hi != lo: |
| 114 | if show: |
no test coverage detected
searching dependent graphs…