אלגוריתמי "ברז ספרות" לטאו

פוסט לכבוד יום הקירוב של $\tau = 2 \pi$, ה-19/3, או "יום פאי למאחרים".

ביום פאי האחרון קראתי איך מחשבים ייצוג עשרוני וייצוג שבר משולב של קבועים מתמטיים. אם מדובר במספרים רציונליים אז חילוק ארוך מאפשר למצוא את הספרות שלהם. אבל אם הם לא רציונליים צריך למצוא נוסחא שתאפשר לחשב אותם באופן אפקטיבי. זה בדרך כלל אומר סכום אינסופי או שבר משולב אינסופי שהמרכיבים שלהם רציונליים. פה אני אתן דוגמא לאיך זה עובד עם $\tau \approx 6.28$, כמות הרדיוסים של מעגל שנכנסת בהיקף שלו.

כדי למצוא נוסחא לטאו צריך להתחיל בתכונה יחסית קרובה להגדרה שלו. נזכיר ש-$\tau$ זו הזווית שהיא הקפה של מעגל שלם ולכן $\sin(30^\circ) = \sin(\tau/12) = 1/2$. כלומר

$$ .\tau = 12 \sin^{-1}(1/2) $$

את הפונקציה $\sin^{-1}$ אפשר לחשב ישירות. נתחיל מהנגזרת שלה:

$$ \sin^{-1}(x)' = \frac{1}{\sin'(\sin^{-1} x)} = \frac{1}{\cos(\sin^{-1} x)} = (1 – x^2)^{-1/2} $$

את זה אפשר לפתוח בעזרת נוסחת הבינום

$$ \begin{align} & (a+b)^x = \sum_{k=0}^\infty \binom{x}{k}a^{x-k}b^k \\ & \qquad = a^x + x \, a^{x-1}b + \tfrac{x(x-1)}{2!} a^{x-2}b^2 + \tfrac{x(x-1)(x-2)}{3!} a^{x-3}b^3 + \ldots \end{align} $$

ולקבל

$$ (1 – x^2)^{-1/2} = 1 + \frac{1}{2}x^2 + \frac{1\cdot 3}{2\cdot 4}x^4 + \frac{1\cdot 3\cdot 5}{2 \cdot 4 \cdot 6} x^6 + \ldots $$

זו היתה הנגזרת $\sin^{-1}(x)' = (1-x^2)^{-1/2}$ ולכן אפשר לרשום את $\sin^{-1}$ ככה

$$ \sin^{-1}(x) = x + \frac{1}{2}\frac{x^3}{3} + \frac{1\cdot 3}{2\cdot 4}\frac{x^5}{5} + \frac{1\cdot 3\cdot 5}{2\cdot 4\cdot 6}\frac{x^7}{7} + \ldots $$

האיברים בסדרה זו הם בערך ביחס של $x^2$ זה מזה, ועבור $x=1/2$ זה אומר שהם קטנים פי 4 בכל פעם ולכן הסכום מתכנס. זה כבר בצורה שאפשר לחשב: מחליטים על כמות ספרות, עושים כל חילוק בחילוק ארוך, וסוכמים. צריך לשים לב שהספרות האחרונות עלולות להיות לא מדויקות כי החיבור מתחתיהן יכול להעביר שארית. טיפה יותר טריקי להוציא מהטור הזה שבר משולב.

אפשרות אחרת היא שהתוכנה תוציא ספרה אחת בכל פעם (או מקדם אחד של השבר המשולב בכל פעם), ותגדיל אוטומטית את הייצוג הפנימי בהתאם לכמה איברים היא סכמה. בשביל זה צריך לכתוב קצת אחרת את הטור:

$$ \sin^{-1}(x) = x \bigg( 1 + \frac{1}{2 \cdot 3}x^2 \bigg( 1 + \frac{3^2}{4 \cdot 5}x^2 \bigg( 1 + \frac{5^2}{6 \cdot 7}x^2 \bigg( 1 + \ldots \bigg) \bigg) \bigg) \bigg) $$

או

$$ . \tau = 12\cdot \frac{1}{2} \cdot \left( 1 + \frac{1}{4}\frac{1}{2 \cdot 3} \times \right) \left( 1 + \frac{1}{4}\frac{3^2}{4 \cdot 5} \times \right) \left( 1 + \frac{1}{4}\frac{5^2}{6 \cdot 7} \times \right) \cdots $$

המובן שבו יש שיוויון, כלומר שבו הביטוי הזה מייצג מספר ממשי, הוא שההרכבה של כל ההעתקות האלה מתכנסת: ההעתקות מעבירות את הקטע $[1,2]$ לתתי-קטעים מתכנסים של עצמו. ככל שמרכיבים יותר העתקות זו על זו מקבלים טווח יותר מצומצם. הטווחים האלה שואפים להצטמצם למספר אחד וזה בדיוק $\tau$.

איך עוברים מהייצוג הזה לייצוג עשרוני? שומרים מצב פנימי שהוא העתקה מהצורה $x \mapsto \frac{ax+b}{c}$, ומרכיבים מימין את ההעתקות לפי הסדר. אם בתמונה של הקטע $[1,2]$ כל המספרים הם עם אותה ספרת יחידות $n$ אז רושמים אותה ומרכיבים משמאל עם $x \mapsto 10(x-n)$. בקוד זה יכול להיראות ככה:

a, b, c = 6, 0, 1  # x -> 6x = (6x + 0) / 1
n = 1
while True:
    if (digit := (a+b)//c) == (a*2+b)//c:
        print(digit, end='')
        # 10(x - digit)   ∘   (ax + b) / c
        a, b, c = a * 10, (b - digit*c) * 10, c
    else:
        r, s = (2*n-1)**2, 4*(2*n)*(2*n+1)
        n += 1
        # (ax + b) / c   ∘   1 + x * r/s
        a, b, c = a*r, (a+b)*s, c*s

כדי למצוא ייצוג כשבר משולב צריך להפוך את הביטוי. בשביל זה נעבוד עם משפחת פונקציות יותר רחבה, העתקות מביוס מהצורה $x \mapsto \frac{ax+b}{cx+d}$. הקוד יוצא מאוד דומה:

a, b, c, d = 6, 0, 0, 1  # x -> 6x = (6x + 0) / (0x + 1)
n = 1
while True:
    if (term := (a+b)//(c+d)) == (a*2+b)//(c*2+d):
        print(term, end=', ')  # or end=' + 1 / ('
        # 1/(x - term)   ∘   (ax + b) / (cx + d)
        a, b, c, d = c, d, a - term*c, b - term*d
    else:
        r, s = (2*n-1)**2, 4*(2*n)*(2*n+1)
        n += 1
        # (ax + b) / (cx + d)   ∘   1 + x * r/s
        a, b, c, d = a*r, (a+b)*s, c*r, (c+d)*s

לשם ההמחשה נראה את תחילת החישוב

• בהתחלה ההעתקה היא $6x$. זה נותן טווח 6-12 שלא מאפשר להוציא איבר בשבר המשולב
• מרכיבים עם $1+x/24$ ומקבלים $6+x/4$, שנותן את האיבר הראשון 6
• נחסר 6 ונהפוך, ונקבל $4/x$. זה נותן טווח 2-4 שלא מאפשר להוציא איבר
• מרכיבים עם $1+9x/80$ ומקבלים $320/(9x+80)$, שנותן את האיבר השני 3
• ולכן $6+1/3=19/3$ הוא אחד הקירובים הטובים ביותר של $\tau$.