|
42
|
1 #!/usr/bin/env python2
|
|
|
2 #
|
|
|
3 # Copyright 2011-2016 Google Inc.
|
|
|
4 #
|
|
|
5 # Licensed under the Apache License, Version 2.0 (the "License");
|
|
|
6 # you may not use this file except in compliance with the License.
|
|
|
7 # You may obtain a copy of the License at
|
|
|
8 #
|
|
|
9 # http://www.apache.org/licenses/LICENSE-2.0
|
|
|
10 #
|
|
|
11 # Unless required by applicable law or agreed to in writing, software
|
|
|
12 # distributed under the License is distributed on an "AS IS" BASIS,
|
|
|
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
|
14 # See the License for the specific language governing permissions and
|
|
|
15 # limitations under the License.
|
|
|
16 #
|
|
|
17 # vim: sw=2 sts=2 et
|
|
|
18
|
|
|
19 from math import log, ceil
|
|
|
20 import sys
|
|
|
21
|
|
|
22
|
|
|
23 def find_largest_power(less_than, base):
|
|
|
24 power = int(log(less_than) / log(base))
|
|
|
25 return base ** power
|
|
|
26
|
|
|
27
|
|
|
28 def divmod_iter(x, by, chunk=None):
|
|
|
29 if x < by:
|
|
|
30 return [x]
|
|
|
31
|
|
|
32 if hasattr(x, 'bit_length'):
|
|
|
33 # crude log(2, x)
|
|
|
34 divisions = x.bit_length() // by.bit_length()
|
|
|
35 else:
|
|
|
36 divisions = log(x) / log(by)
|
|
|
37
|
|
|
38 if divisions < 1024:
|
|
|
39 return divmod_iter_basic(x, by, chunk)
|
|
|
40 else:
|
|
|
41 return divmod_iter_chunking(x, by, chunk)
|
|
|
42
|
|
|
43
|
|
|
44 def divmod_iter_chunking(x, by, chunk=None):
|
|
|
45 """Generate successive (x % by); x /= by, but faster.
|
|
|
46
|
|
|
47 If provided, |chunk| must be a power of |by| (otherwise it is determined
|
|
|
48 automatically for 1024 per inner loop, based on analysis of bench_genmod.py)
|
|
|
49 """
|
|
|
50
|
|
|
51 if by == 1:
|
|
|
52 assert x == 0, x
|
|
|
53 yield 0
|
|
|
54 return
|
|
|
55
|
|
|
56 if chunk is None:
|
|
|
57 digits_per_chunk = 1024
|
|
|
58 chunk = by ** digits_per_chunk
|
|
|
59 else:
|
|
|
60 digits_per_chunk = int(round(log(chunk) / log(by)))
|
|
|
61 if (by ** digits_per_chunk) != chunk:
|
|
|
62 raise ValueError("Chunk=%d must be a power of by=%d" % (chunk, by))
|
|
|
63
|
|
|
64 assert digits_per_chunk > 0
|
|
|
65
|
|
|
66 while x:
|
|
|
67 x, this_chunk = divmod(x, chunk)
|
|
|
68 #this_chunk = int(this_chunk)
|
|
|
69 for _ in range(digits_per_chunk):
|
|
|
70 this_chunk, m = divmod(this_chunk, by)
|
|
|
71 yield m
|
|
|
72
|
|
|
73 if this_chunk == 0 and x == 0:
|
|
|
74 break
|
|
|
75
|
|
|
76
|
|
|
77 def divmod_iter_basic(x, by, chunk=None):
|
|
|
78 """Generate successive (x % by); x /= by, the obvious way.
|
|
|
79
|
|
|
80 Chunk is ignored.
|
|
|
81 """
|
|
|
82 while x:
|
|
|
83 x, m = divmod(x, by)
|
|
|
84 yield m
|
|
|
85
|
|
|
86 def powersum(x, low, high):
|
|
|
87 # http://mikestoolbox.com/powersum.html
|
|
|
88 xm1 = x - 1
|
|
|
89 if xm1 == 0:
|
|
|
90 return high - low + 1
|
|
|
91 a = x ** (high + 1)
|
|
|
92 b = x ** low
|
|
|
93 return (a - b) // xm1
|
