Difference between revisions of "Verify the bounded discrepancy of an input sequence"

From Polymath1Wiki
Jump to: navigation, search
(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: +...)
 
m (Changed variable names to be more in harmony with theory page)
Line 14: Line 14:
 
from __future__ import with_statement
 
from __future__ import with_statement
 
from numpy import zeros, int8
 
from numpy import zeros, int8
N = 1124
+
SEQUENCE_LENGTH = 1124
 
fileInput = '1124_min.txt'
 
fileInput = '1124_min.txt'
  
Line 20: Line 20:
 
     pass
 
     pass
  
def verifySequence(x, maxDiscrepancy=2, verbose=False):
+
def verifySequence(x, C=2, verbose=False):
     """verify discrepancy <= MAX_DISCREPANCY
+
     """verify discrepancy <= MAX_DISCREPASEQUENCE_LENGTHCY
  
 
"""
 
"""
     for i in range(N):
+
     for i in range(SEQUENCE_LENGTH):
         inds = range(i,N,i+1)
+
         inds = range(i,SEQUENCE_LENGTH,i+1)
 
         s = x[inds].sum()  # discrepancy
 
         s = x[inds].sum()  # discrepancy
         if abs(s) > maxDiscrepancy:
+
         if abs(s) > C:
             msg = 'n = %d has discrepancy %s'
+
             msg = 'd = %d has discrepancy %s'
 
             msg %= (i+1, s)
 
             msg %= (i+1, s)
 
             raise DiscrepancyError(msg)
 
             raise DiscrepancyError(msg)
Line 37: Line 37:
 
if __name__=='__main__':
 
if __name__=='__main__':
 
     # load +/- sequence
 
     # load +/- sequence
     x = zeros(N, dtype = int8)
+
     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 45:
 
         elif side == '+':
 
         elif side == '+':
 
             x[i] = 1
 
             x[i] = 1
     assert i == N - 1
+
     assert i == SEQUENCE_LENGTH - 1
 
     isGood = verifySequence(x)
 
     isGood = verifySequence(x)
 
</pre>
 
</pre>

Revision as of 18:29, 11 January 2010

#!/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 <= MAX_DISCREPASEQUENCE_LENGTHCY

"""
    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)