Created
June 2, 2020 13:58
-
-
Save galatolofederico/b4cad6299e3cfebf38e0c25405c26636 to your computer and use it in GitHub Desktop.
Search a text in pi (or other continued fractions) in Python
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import sys | |
| import time | |
| import argparse | |
| import string | |
| chars = string.ascii_lowercase | |
| parser = argparse.ArgumentParser() | |
| parser.add_argument("--constant", type=str, choices=["pi", "phi"], default="pi") | |
| parser.add_argument("--mode", type=str, choices=["print", "search"], default="search") | |
| parser.add_argument("--log-intervall", type=int, default=1000) | |
| parser.add_argument("--text", type=str, default="") | |
| args = parser.parse_args() | |
| if args.mode == "search" and args.text == "": | |
| print("You have to specify a text to search.\n") | |
| parser.print_help() | |
| sys.exit(1) | |
| if not all([c in chars for c in args.text]): | |
| print("Your search string must use only these caracters:\n") | |
| print(chars) | |
| print() | |
| sys.exit(1) | |
| constants = dict( | |
| pi=dict( | |
| a=lambda k: 0 if k == 0 else 2 * k - 1, | |
| b=lambda k: 4 if k == 1 else (k - 1)**2 | |
| ), | |
| phi=dict( | |
| a=lambda k: 1, | |
| b=lambda k: 1 | |
| ) | |
| ) | |
| def continued_fraction(a, b, base=10): | |
| (p0, q0), (p1, q1) = (a(0), 1), (a(1) * a(0) + b(1), a(1)) | |
| k = 1 | |
| while True: | |
| (d0, r0), (d1, r1) = divmod(p0, q0), divmod(p1, q1) | |
| if d0 == d1: | |
| yield d1 | |
| p0, p1 = base * r0, base * r1 | |
| else: | |
| k = k + 1 | |
| x, y = a(k), b(k) | |
| (p0, q0), (p1, q1) = (p1, q1), (x * p1 + y * p0, x * q1 + y * q0) | |
| def text_stream(digits, chars): | |
| it = iter(digits) | |
| N = 0 | |
| while True: | |
| d1 = next(it) | |
| d2 = next(it) | |
| N += d1*10 | |
| N += d2 | |
| yield chars[N % len(chars)], (d1, d2) | |
| N = 0 | |
| digits_stream = continued_fraction( | |
| constants[args.constant]["a"], | |
| constants[args.constant]["b"], | |
| ) | |
| t_start = time.time() | |
| str_found_i = 0 | |
| found_digits = [] | |
| prob_success_trial = (1/len(chars))**len(args.text) | |
| for i, (char, digits) in enumerate(text_stream(digits_stream, chars)): | |
| if char == args.text[str_found_i]: | |
| str_found_i += 1 | |
| found_digits.append(str(digits[0])) | |
| found_digits.append(str(digits[1])) | |
| else: | |
| str_found_i = 0 | |
| found_digits = [] | |
| if str_found_i == len(args.text): | |
| print("=== SUCCESS ===") | |
| print("'%s' found starting from digit number: %d" % (args.text, i*2)) | |
| print("digits: ...%s... " % "".join(found_digits)) | |
| print("===============") | |
| sys.exit(0) | |
| if i != 0 and i % args.log_intervall == 0: | |
| speed = 2*args.log_intervall/(time.time()-t_start) | |
| prob = (1 - (1 - prob_success_trial)**i) | |
| print("digits/s: %.2f\tsuccess probability: %.2f%%" % (speed, prob*100)) | |
| t_start = time.time() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment