Categories
Uncategorized

Kvantti testaa: π:n rationaaliset likiarvot

Toimituksen harrastajamatemaatikkosektio päätyi osaksi mielenkiintoista keskustelua luvun π rationaalilikiarvoista. Keskustelussa pohdittiin sitä, onko olemassa muita rationaalilukuja kuin 355 / 113 = 710 / 226 = 3,1415929… ≈  3,1415926… = π, joiden desimaaliesitys sisältää enemmän oikeita piin desimaaleja kuin numeroiden lukumäärien summa kyseisen rationaaliluvun osoittajassa ja nimittäjässä. Valtaosa keskustelijoista uskoi, että muita tämänkaltaisia rationaalilukuja ei ole olemassa; näin sanottiin myös Wikipediassa. Useampi keskustelun osapuoli oli jopa toteuttanut tietokoneohjelman etsimään tämänkaltaisia lukuja, ja yhtään tämän ehdon toteuttavaa rationaalilukua p/q, jossa q < 109 ei ollut löytynyt. Tämä oli se kohta, jossa ensimmäinen Kvantin toimittaja liittyi mukaan keskusteluun.

Käytännöllisempi, ja usein riittävä arvio on π = 3.

Keskustelussa esitetty ohjelmat perustuivat seuraavaan algoritmiin:

  • Aseta p1 ← 3, q1 ← 1.
  • Kullakin i, laske desimaaliesitys luvulle pi / qi, muunna se merkkijonoksi ja laske oikeiden piin desimaalien määrä.
    • Jos pi / qi > π, niin pi + 1 ← 4 + pi ja qi + 1 ← 1 + qi, muuten pi + 1pi + 3 ja qi + 1 ← 1 + qi.

Tämä algoritmi oli kuitenkin huomattavan tehoton, koska se edellytti mielivaltaisen laskentatarkkuuden desimaaliluvun laskemista kullakin nimittäjän positiivisella kokonaislukuarvolla, vaikka suurimmalla osalla näistä saatiin verrattain huono rationaalilukuarvio piille. Toimittaja päätti tehostaa algoritmia muotoon:

  • Määrittele alaraja(n) ← ⌊10n π⌋ / 10n, yläraja(n) ←  ⌈10n π⌉ / 10n.
  • Aseta pi ← 3, qi ← 1, n ← 1.
  • Kullakin i, kasvata n kunnes ei enää alaraja(n) < pi / qi < yläraja(n).
    • Jos pi / qi > π, niin pi + 1 ← 22 + pi ja qi + 1 ← 7 + qi, muuten pi + 1 ← 3 + pi ja qi + 1 ← 1 + qi.

Tämä algoritmi huomioi pienen osan hyvien rationaaliarvioiden sijannin säännöllisyydestä, ja oli siten noin kertaluokan verran aikaisempaa nopeampi. Tämä mahdollisti tarkasteluvälin kasvattamisen nimittäjän arvoille q < 1010 ilman laskentajan kymmenkertaistumista.

Tässä kohtaa joku pidemmän linjan koodari saattaa arvata, mitä ensimmäisellä ajokerralla meni pieleen. 1010 > 232, ja kuten tunnettua GNU-kääntäjä ei varoita tämänkaltaisesta ikuisen silmukan luovasta virheestä. Siis se samainen GNU-kääntäjä, joka tunnistaa vakiona esimerkiksi ohjelmakoodiin kirjoitetun komennon ”pow(x,-1.5)” ja uudelleenkirjoittaa sen automaattisesti monta kertaa nopeammaksi laskutoimitukseksi ”1/(x*sqrt(x))”.

Kun kaikki tarvittavat kokonaislukumuuttujat oli päivitetty 64-bittisiksi, niin ohjelma löysi melkein heti 32-bittisten lukujen ulkopuolelta rationaaliluvun 21053343141 / 6701487259. Tämä 21 numerosta koostuva rationaaliluku tuottaa 22 oikeaa piin desimaalia, ja on siten ensimmäinen rationaaliluku luvun 355 / 113 jälkeen, joka tuottaa enemmän oikeita piin desimaaleja kuin luvun numeroiden määrä. Erinomaista. (Tässä välissä on oikea hetki korjatapäivittää Wikipediaa.)

Tämä luku ei kuitenkaan vielä tyydyttänyt toimittajafyysikon matemaattista silmää. Toimittajan mielestä nimittäin myös luvusta löytyvät jakomerkki on merkki, joten yhteensä 21 + 1 = 22 merkillä saadaan 22 oikeaa desimaalia.

Kvantti testaa: Stern–Brocot-puu

Piin rationaalisten likiarvojen takana on yllättävän paljon yllättävän huonosti tunnettua matematiikkaa. Se tiedetään, että paikallisesti optimaaliset rationaalilikiarvot liittyvät luvun katkaistuun ketjumurtolukuesitykseen (kuva Wikipediasta):

Ketjumurtoluku, katkaistu.

Poikkeuksellisen hyvät rationaaliapproksimaatiot löytyvät kohdista, jossa katkaisukohtaa seuraava termi an + 1 on suuri. Esimerkiksi 23 numeron mittainen rationaaliluku 60499999499 / 490050000000 tuottaa 187 ensimmäistä oikeaa desimaalia Champernownen vakiosta, koska tämän vakion ketjumurtolukuesityksen 18. alkio on noin 10166.

Seuraa omituista matematiikkaa:

  • Thue–Siegel–Roth teoreeman (Roth, 1955) mukaan millään ei-rationaalisella algebrallisella luvulla ei voi olla olemassa tietyssä mielessä hyvää rationaalista likiarvoa. Kuitenkaan, tämän teoreeman vakiokertoimelle C > 0 ei tunneta mitään alarajaa. Toisaalta, ei ole pystytty osoittamaan että vähintään astelukua kolme olevien algebrallisten numeroiden ketjumurtolukuesityksen termit olisivat rajoitettuja – toisaalta, yhtään tällaista lukua ei tunneta.
  • Liouvillen luku, ja tapa osoittaa luvun transsendenttisuus (eli ei-algebrallisuus), perustuu tietyssä mielessä liian hyvien rationaalilikiarvojen olemassaoloon. Liouvillen luvuille tiedetään, että ketjumurtolukuesitys on rajoittamaton ja epäjaksollinen. Toisaalta, joukkojen mahtavuuteen perustuvan todistuksen perusteella täytyy olla olemassa ääretön määrä rajoitetun ketjumurtolukuesityksen transsendenttilukuja – toisaalta, yhtään tämänkaltaista lukua ei tunneta.
  • Transsendenttisen Neperin luvun e ketjumurtolukuesitys on lähes jaksollinen {2, 1, 1, 2n/3}, kun taas transsendenttisen luvun π ketjumurtolukuesitys näyttää kaikin puolin satunnaiselta.
  • Hurwitzin teoreeman mukaan kaikille fyysikoille tuttu luku φ on kaikista säännöllisin olemassa oleva irrationaaliluku, eli sen rationaalilikiarvot ovat itseisarvoltaan kaikkein kauimpana itse luvusta vakiosuuruisella nimittäjän arvolla.

Seuraa vielä omituisempaa matematiikkaa: Stern–Brocot-puu, joka on ääretön, täydellinen binäärinen puu, ja joka sisältää kaikki positiiviset rationaaliluvut. 19. vuosisadan matematiikkaa, jonka kehittivät toisistaan riippumatta saksalainen matemaatikko Stern vuonna 1858 ja ranskalainen kelloseppä Brocot vuonna 1861. Näistä jälkimmäinen käytti tätä menetelmää muun muassa mekaanisten kellojen rakenteen optimointiin. Tämä puu binäärinen hakupuu, josta etsittäessä mitä tahansa (positiivista) lukua x käydään järjestyksessä läpi kaikki tämän luvun paikallisesti optimaaliset rationaalilikiarvot.

Toteutettiin Stern–Brocot-haku käyttäen Python 3 -ohjelmointikieltä (Liite 1). Muutama kymmentä millisekuntia myöhemmin löytyikin 433 numeron ja yhden jakomerkin mittainen rationaaliluku 19018707285669230760901439447147703396215907683135463371925261155627043396809635
64320007808107929370299752345187688835741387003036853361285671158059867702399073
227994426905220194699766118756059055619036488502928002591 / 60538425514642032610236102321594053171639147815034502073923125317213474068823247
69460000587137745497965614474682677464128740227175441009465871441487396268034351
33473281606663121381125761746030151344353855924025288111, joka antaa 436 oikeaa piin desimaalia. Tämä luku on ainakin jossain määrin uusi, koska sitä ei löydy esimerkiksi Google-haulla. Tehtiin vielä hieman lisätutkimuksia. Seuraava vähintään yhtä hyvä likiarvo löytyy vasta 8928+1 merkin kohdalta, antaen 8931 oikeaa desimaalia.

Liiteet

Liite 1, Python 3 -ohjelmakoodi

#!/usr/bin/env python3
import fractions
# Määritellään pii, yksi, haluttu tarkkuus, ja laskuri tarkkuudelle.
pii = 31415926535897932384626433
one = 10**25
trg = one
des = 0
# Alustetaan halutun tarkkuuden mukaiset ala- ja ylärajat.
pi = fractions.Fraction(pii,one)
pia = fractions.Fraction((pii//trg)*trg,one)
piy = fractions.Fraction((pii//trg+1)*trg,one)
# Määritetään jokin piitä pienempi ja suurempi luku.
L = fractions.Fraction(3,1)
H = fractions.Fraction(4,1)
# Lasketaan 1. iteraatio.
M = fractions.Fraction(L.numerator+H.numerator,L.denominator+H.denominator)

while M != pi:
    if M > pi:
        H = M
    else:
        L = M
    M = fractions.Fraction(L.numerator+H.numerator,L.denominator+H.denominator)
    # Lasketaan oikeiden desimaalien määrä.
    while M >= pia and M < piy:
        trg //= 10
        des += 1
        pia = fractions.Fraction((pii//trg)*trg,one)
        piy = fractions.Fraction((pii//trg+1)*trg,one)
        if M >= pia and M < piy: continue
        # Tulostetaan välitulos
        pen = len(str(M.numerator))+len(str(M.denominator))
        print(des,pen,M)
    if trg < 10:
        break

Viitteet

Brocot, Achille. ”Calcul des rouages par approximation, nouvelle méthode.” Revue Chronométrique 3:186–94, 1861.
Hurwitz, Adolf. ”Über die angenäherte Darstellung der Irrationalzahlen durch rationale Brüche.” Mathematische Annalen 39(2):279–84, 1891.
Roth, Klaus F. ”Rational approximations to algebraic numbers.” Mathematika 2, 168:1–20, 1955.
Stern, Moritz A. ”Ueber eine zahlentheoretische Funktion.” Journal für die reine und angewandte Mathematik 55:193–220, 1858.