#!/usr/bin/python """Attempt to find the rational numbers with 8-bit numerators and denominators that best approximate X/65535 for all X <= 65535. This code has some bug in it that I haven't found yet. """ import contfrac def main(): denom = 65535 for ii in range(1, denom): quotients = contfrac.contfrac_list(ii, denom) found = False for approxnum, approxdenom in contfrac.approximations(quotients): if approxnum> 255 or approxdenom> 255: break lastnum, lastdenom = approxnum, approxdenom found = True if found: print "%d/%d is close to %d/%d (%.2g relative error)" % ( ii, denom, lastnum, lastdenom, (1.0*lastnum/lastdenom)/(1.0*ii/denom)-1) else: print "%d/%d has no good approximations! %s" % ( ii, denom, contfrac.py_contfrac(quotients)) # brute force! _, bestnum, bestdenom = min( (abs(1.0*aa/bb - 1.0*ii/denom) if bb else 1, aa, bb) for aa, bb in ((aa, round(aa * denom / ii)) for aa in range(256)) if bb < 256) print "%d/%d is best approximated by %d/%d (%.2g relative error)" % ( ii, denom, bestnum, bestdenom, (1.0*bestnum/bestdenom)/(1.0*ii/denom)-1 if bestdenom else 0) if __name__ == '__main__': main()