Difference between revisions of "Verify the bounded discrepancy of an input sequence"
From Polymath1Wiki
Yangofzeal (Talk | contribs) (New page: <pre> #!/usr/bin/env python """Erdos Discrepancy Problem sequence verification. Verifies that discrepancy is bounded for 1124-length sequence of +/-1. file 1124_min.txt should contain: +...) |
Yangofzeal (Talk | contribs) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | [http://michaelnielsen.org/polymath1/index.php?title=Experimental_results back to the main experimental results page]. | ||
| + | |||
<pre> | <pre> | ||
#!/usr/bin/env python | #!/usr/bin/env python | ||
| Line 14: | Line 16: | ||
from __future__ import with_statement | from __future__ import with_statement | ||
from numpy import zeros, int8 | from numpy import zeros, int8 | ||
| − | + | SEQUENCE_LENGTH = 1124 | |
fileInput = '1124_min.txt' | fileInput = '1124_min.txt' | ||
| Line 20: | Line 22: | ||
pass | pass | ||
| − | def verifySequence(x, | + | def verifySequence(x, C=2, verbose=False): |
| − | """verify discrepancy <= | + | """verify discrepancy <= C |
""" | """ | ||
| − | for i in range( | + | for i in range(SEQUENCE_LENGTH): |
| − | inds = range(i, | + | inds = range(i,SEQUENCE_LENGTH,i+1) |
s = x[inds].sum() # discrepancy | s = x[inds].sum() # discrepancy | ||
| − | if abs(s) > | + | if abs(s) > C: |
| − | msg = ' | + | msg = 'd = %d has discrepancy %s' |
msg %= (i+1, s) | msg %= (i+1, s) | ||
raise DiscrepancyError(msg) | raise DiscrepancyError(msg) | ||
| Line 37: | Line 39: | ||
if __name__=='__main__': | if __name__=='__main__': | ||
# load +/- sequence | # load +/- sequence | ||
| − | x = zeros( | + | x = zeros(SEQUENCE_LENGTH, dtype = int8) |
with open(fileInput, 'r') as f: | with open(fileInput, 'r') as f: | ||
a = f.read() | a = f.read() | ||
| Line 45: | Line 47: | ||
elif side == '+': | elif side == '+': | ||
x[i] = 1 | x[i] = 1 | ||
| − | assert i == | + | assert i == SEQUENCE_LENGTH - 1 |
isGood = verifySequence(x) | isGood = verifySequence(x) | ||
</pre> | </pre> | ||
Latest revision as of 18:43, 11 January 2010
back to the main experimental results page.
#!/usr/bin/env python
"""Erdos Discrepancy Problem sequence verification.
Verifies that discrepancy is bounded
for 1124-length sequence of +/-1.
file 1124_min.txt should contain:
+ - + + - - - - ...
by Michael Yang, 2010
"""
from __future__ import with_statement
from numpy import zeros, int8
SEQUENCE_LENGTH = 1124
fileInput = '1124_min.txt'
class DiscrepancyError(Exception):
pass
def verifySequence(x, C=2, verbose=False):
"""verify discrepancy <= C
"""
for i in range(SEQUENCE_LENGTH):
inds = range(i,SEQUENCE_LENGTH,i+1)
s = x[inds].sum() # discrepancy
if abs(s) > C:
msg = 'd = %d has discrepancy %s'
msg %= (i+1, s)
raise DiscrepancyError(msg)
if verbose: print i+1, s
if verbose: print 'verified'
return True
if __name__=='__main__':
# load +/- sequence
x = zeros(SEQUENCE_LENGTH, dtype = int8)
with open(fileInput, 'r') as f:
a = f.read()
for i, side in enumerate(a.strip().split()):
if side == '-':
x[i] = -1
elif side == '+':
x[i] = 1
assert i == SEQUENCE_LENGTH - 1
isGood = verifySequence(x)
