Generierung von Ziffern der Wurzel aus 2

Könnten Sie versuchen, mit Hilfe der mapping:

a/b -> (a+2b)/(a+b) ab a= 1, b= 1. Diese konvergiert gegen Wurzel(2) (in der Tat gibt die Fortsetzung Bruchteil Darstellungen).

Nun der entscheidende Punkt: Diese können dargestellt werden als eine matrix-Multiplikation (ähnlich wie fibonacci)

Wenn a_n und b_n sind die N-te Zahl in den Schritten dann

[1 2] [a_n b_n]^T = [a_(n+1) b_(n+1)]^T

[1 1]

welches jetzt gibt uns

[1 2]ⁿ [a_1 b_1]^T = [a_(n+1) b_(n+1)]^T

[1 1]

So, wenn die 2x2-matrix A, die wir brauchen, um zu berechnen Aⁿ, die getan werden kann, durch wiederholtes quadrieren und verwendet nur integer-Arithmetik (so dass Sie nicht haben, um sorgen über die Präzision, Fragen).

Beachten Sie auch, dass die a/b bekommen Sie immer in reduzierter form (als gcd(a,b) = gcd(a+2b, a+b)), also, wenn Sie denken mit einem Bruchteil der Klasse, die zum darstellen der Zwischenergebnisse nicht!

Da die N-te Nenner ist wie (1+sqrt(2))^n, um 3 Millionen stellen, würden Sie wahrscheinlich benötigen, um zu berechnen, bis die 3671656^th Begriff.

Beachten, auch wenn Sie auf der Suche für die ~3.6 Millionstel Begriff, wiederholte Quadratur Ihnen erlauben, um die Berechnung der N-TEN term in O(Log n) Multiplikationen und Additionen.

Außerdem kann dieser einfach parallel, im Gegensatz zu den iterativen diejenigen, die wie Newton-Raphson etc.

Als für beliebig große zahlen haben, könnten Sie einen Blick auf Die GNU Multiple Precision Arithmetic Library (für C/C++).

Schönste Weg ist wohl mit den weiter fraction expansion [1; 2, 2, ...] die Quadratwurzel von zwei.

def root_two_cf_expansion():
    yield 1
    while True:
        yield 2

def z(a,b,c,d, contfrac):
    for x in contfrac:
        while a > 0 and b > 0 and c > 0 and d > 0:
            t = a // c
            t2 = b // d
            if not t == t2:
                break
            yield t
            a = (10 * (a - c*t))
            b = (10 * (b - d*t))
            # continue with same fraction, don't pull new x
        a, b = x*a+b, a
        c, d = x*c+d, c
    for digit in rdigits(a, c):
        yield digit

def rdigits(p, q):
    while p > 0:
        if p > q:
           d = p // q
           p = p - q * d
        else:
           d = (10 * p) // q
           p = 10 * p - q * d
        yield d

def decimal(contfrac):
    return z(1,0,0,1,contfrac)

decimal((root_two_cf_expansion()) gibt einen iterator von allen Dezimalstellen. t1 und t2 im Algorithmus sind die minimalen und maximalen Werte für die nächste Ziffer. Wenn Sie gleich sind, und wir-Ausgang, digit.

Beachten Sie, dass dies nicht mit bestimmten Ausnahmefällen, wie negative zahlen in der Fortsetzung Bruchteil.

(Dieser code ist eine Anpassung der Haskell-code für die Behandlung kettenbrüche, wurde im Umlauf.)

Gut, der folgende code ist der code, den ich geschrieben habe. Es generiert eine Millionen stellen nach dem Dezimalkomma für die Quadratwurzel von 2 in über 60800 Sekunden für mich, aber mein laptop war zu schlafen, wenn es das Programm ist, sollte es schneller. Sie können versuchen, zu generieren 3 Millionen stellen, aber es könnte ein paar Tage, um es zu bekommen.

def sqrt(number,digits_after_decimal=20):
import time
start=time.time()
original_number=number
number=str(number)
list=[]
for a in range(len(number)):
    if number[a]=='.':
        decimal_point_locaiton=a
        break
    if a==len(number)-1:
        number+='.'
        decimal_point_locaiton=a+1
if decimal_point_locaiton/2!=round(decimal_point_locaiton/2):
    number='0'+number
    decimal_point_locaiton+=1
if len(number)/2!=round(len(number)/2):
    number+='0'
number=number[:decimal_point_locaiton]+number[decimal_point_locaiton+1:]
decimal_point_ans=int((decimal_point_locaiton-2)/2)+1
for a in range(0,len(number),2):
    if number[a]!='0':
        list.append(eval(number[a:a+2]))
    else:
        try:
            list.append(eval(number[a+1]))
        except IndexError:
            pass
p=0
c=list[0]
x=0
ans=''
for a in range(len(list)):
    while c>=(20*p+x)*(x):
        x+=1
    y=(20*p+x-1)*(x-1)
    p=p*10+x-1
    ans+=str(x-1)
    c-=y
    try:
        c=c*100+list[a+1]
    except IndexError:
        c=c*100
while c!=0:
    x=0
    while c>=(20*p+x)*(x):
        x+=1
    y=(20*p+x-1)*(x-1)
    p=p*10+x-1
    ans+=str(x-1)
    c-=y
    c=c*100
    if len(ans)-decimal_point_ans>=digits_after_decimal:
            break
ans=ans[:decimal_point_ans]+'.'+ans[decimal_point_ans:]
total=time.time()-start
return ans,total

Hier ist ein effizienter integer-Wurzel-Funktion (in Python 3.x), die beendet werden soll in allen Fällen. Es beginnt mit einem Wert, der wesentlich näher an der Wurzel, so dauert es weniger Schritte. Beachten Sie, dass int.bit_length erfordert Python 3.1+. Fehlerprüfung Links für die Kürze.

def isqrt(n):
    x = (n >> n.bit_length() // 2) + 1
    result = (x + n // x) // 2
    while abs(result - x) > 1:
        x = result
        result = (x + n // x) // 2
    while result * result > n:
        result -= 1
    return result