annotate CodonSwitchTool/fastdivmod.py @ 2:aad5e435e4dc draft default tip

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