Mercurial > repos > gianmarco_piccinno > cs_tool_project_rm

comparison fastdivmod.py @ 0:5397da1ef896 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author gianmarco_piccinno
date Tue, 21 May 2019 05:05:15 -0400
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:5397da1ef896
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