Die Exponentialfunktion über algebraische Zahlen

8

Bei einer algebraischen Zahl α bin ich daran interessiert, eine Annäherung von bis zu einer gegebenen Genauigkeit zu finden, wobei sich auf den Realteil der komplexen Zahl bezieht.( )(eα)()

Formal möchte ich eine rationale Zahl so berechnen, dass | ( e α ) - r | 2 - nr

|(eα)r|2n

α ist durch ein (Standard-) Minimalpolynom gegeben.

Wie schnell können wir dieses Problem lösen?


Wenn als Gleitkomma angegeben wird, wird die folgende Referenz verwendetα

R. Brent. Schnelle Auswertung elementarer Funktionen mit mehrfacher Genauigkeit. JACM, 1976.

scheint eine Antwort zu geben.

Ich bin mir jedoch nicht sicher, ob es für die algebraische Zahl . α

user22166
quelle
1
Sowohl exp als auch log können angenähert werden in der Zeit O ( M ( n ) log n ) n Bits Genauigkeit. Da die numerische Wurzelnäherung nicht wesentlich schneller ist (sie benötigt sicherlich mindestens Ω ( M ( n ) ) Zeit ), entspricht Ihre Frage im Wesentlichen der Komplexität der Approximation von α . Für ein festes Polynom kann letzteres in der Zeit O ( M ( n ) ) erfolgen.nO(M(n)logn)Ω(M(n))αO(M(n))mit der Newton-Methode, aber ich bin mir nicht sicher, was genau passiert, wenn das Polynom (und ein Begrenzungsintervall!) Teil der Eingabe ist.
Emil Jeřábek
(Die asymptotische Zeitkomplexität der Newtonschen Iteration ist mehr oder weniger die Zeit, die benötigt wird, um das Polynom bei einer gegebenen Eingabe mit Genauigkeitsbits auszuwerten .)n
Emil Jeřábek
1
Oh, aber alles, was ich geschrieben habe, gilt, wenn Sie einen Verwandten wollen Fehler , wird in einer Exponenten-Mantisse-Darstellung ausgegeben, und die Fehlergrenze gilt für die Mantisse. So wie die Frage geschrieben ist, können Sie keine bessere Grenze als das triviale 2 O ( n ) erhalten , da die Größe der Ausgabe exponentiell in der Größe der Eingabe ist, bereits wenn α eine ganze Zahl ist und ϵ = 1 . r2O(n)αϵ=1
Emil Jeřábek
2
Um das Problem zu vermeiden, dass Emil sich auf die Komplexität realer Funktionen bezieht, werden diese untersucht, wenn die Domäne eine kompakte Menge wie das Einheitsintervall ist. Wenn Ihr beliebig groß sein kann, kann exp nicht in Polynomzeit berechnet werden. α
Kaveh
PS: Diese Algorithmen funktionieren im Allgemeinen für alle berechenbaren reellen Zahlen, einschließlich algebraischer Zahlen. Wir müssen nur willkürlich gute Näherungen für die Eingaben bereitstellen.
Kaveh

Antworten:

3

Wie geschrieben, benötigt das Problem Zeit , wobei m die Länge der Eingabe ist (die Sie leider verwendet haben2Ω(m)m für etwas anderes verwendet). In der Tatistdie Größe der Ausgabe exponentiell in der Größe der Eingabe, wenn z. B. α eine positive ganze Zahl ist (gegeben durch ihr minimales Polynom x - α ) und n = 0 ist. Diese Grenze ist natürlich optimal, da es eine Reihe von Möglichkeiten gibt, das Ergebnis in der Zeit 2 O ( m ) zu berechnen.nαxαn=02O(m)


Lassen Sie mich versuchen, die Frage so umzuformulieren, dass sie etwas sinnvoller ist. Die Hauptfrage ist, wie die Darstellung der Eingabe und Ausgabe sowie der Begriff der Approximation so gewählt werden, dass die Potenzierung eine kämpfende Chance hat, in der Polynomzeit berechenbar zu sein.

Ein Weg wurde von Kaveh in den Kommentaren erwähnt: Beschränken Sie die Domäne auf ein festes endliches Intervall. Dies funktioniert zwar, ist jedoch unnötig einschränkend. Insbesondere gibt es keine gute Möglichkeit, eine algebraische Zahl in eine begrenzte Zahl umzuwandeln, damit ihre Exponentiale etwas miteinander zu tun haben.

Ein flexiblerer Ansatz besteht darin, die Eingabe als Festkommazahl und die Ausgabe als Gleitkommazahl darzustellen . Um genau zu sein, ist eine Festpunktdarstellung eine Zeichenfolge bezeichnet ± j a

±arar1a0.a1as
, wobei a j{ 0 , 1 } und eine Gleitkommadarstellung ± 2 e × ist±jaj2jaj{0,1} mit einer ähnlichen Interpretation, wobei e eine binäre ganze Zahl ist und a 0 = 1 . (Ausnahmsweise erlauben wir auch, dass 0 sich selbst darstellt.) Eine Annäherung eines reellen x an m Bits mitabsoluterGenauigkeit ist ein reelles x ', so dass | x - x | < 2 - m und eine Annäherung an m BitsrelativerGenauigkeit ist
±2e×a0.a1as
ea0=10xmx|xx|<2mm so dass | 1x . Wir werden die absolute Genauigkeit für Festkomma-Näherungen und die relative Genauigkeit für Gleitkomma-Näherungen verwenden. Daraus folgt, dass wir in beiden Fällen genauso gut s m annehmen können(bis zum Verlust eines Genauigkeitsbits).|1x/x|<2msm

Festpunkt- und Gleitkomma-Darstellungen von dyadischen Gaußschen Rationalen und Approximationen komplexer Zahlen werden auf ähnliche Weise unter Verwendung eines Paares von Real definiert. Überall unten bezeichnet die Gesamtgröße der Eingabe.n

Die (reale oder komplexe) Exponentiation sei nun das folgende Problem: Die Eingabe ist eine Festpunktdarstellung einer Zahl und einer unären natürlichen Zahl m , und die Ausgabe ist eine Gleitkommanäherung von e x anxmex Bits relativer Genauigkeit. DerLogarithmusnimmtzweifacheine Gleitkommazahl x und ein unäres m als Eingabe, und die Ausgabe ist eine Festkomma-Annäherung von log x (z. B. der Hauptzweig im komplexen Fall) an m Bits mit absoluter Genauigkeit.mxmlogxm

Solange wir uns an Laufzeitgrenzen halten, die einige milde Regelmäßigkeitsbedingungen erfüllen, und konstante multiplikative Faktoren ignorieren, haben wir:

  • Die Komplexität der Exponentiation, des Logarithmus oder einer ähnlichen analytischen Funktion ist zumindest die Komplexität der ganzzahligen Multiplikation: z. B. können wir von exp ( a 2 - t ) = a 2 - t + a 2 2 - 2 t ablesen - 1 + O.a2 für ausreichend großes t , linear in der Länge von a .exp(a2t)=a2t+a222t1+O(a323t)ta
  • Potenzierung und Logarithmus sind gleich komplex. Der Grund ist, dass wir die Umkehrung einer schönen Funktion durch Newton-Iteration (oder komplexere Methoden wie in Brent ) unter Verwendung der Auswertung der Funktion selbst berechnen können . Die Iteration beinhaltet typischerweise Multiplikationen oder Divisionen, aber wir können uns diese durch den vorherigen Punkt leisten.

Die algebraischen Zahlen können durch ihr minimales Polynom f (geschrieben als Folge von ganzzahligen Koeffizienten in Binärform) zusammen mit einigen Mitteln zur Unterscheidung zwischen den Wurzeln desselben Polynoms dargestellt werden. Ein natürlicher Weg, dies zu tun, besteht darin, ein Isolationsintervall oder eine Isolationsscheibe zu benötigen: ein Paar von Festpunktnummern c , ρ, so dassαfc,ρ . Wir müssen zumindest verlangen, dass α eine eindeutige Wurzel von f mit dieser Eigenschaft ist, aber etwas Stärkeres kann geeigneter sein. Dazu später mehr.|cα|<ραf

Die algebraische Zahlennäherung sei das folgende Problem: Berechnen Sie bei gegebener algebraischer Zahl in der obigen Darstellung und m in unär eine (komplexe) Festpunktnäherung von α an m Bits mit absoluter Genauigkeit.αmαm

Die ursprüngliche Frage bezog sich auf , aber lassen Sie mich dies zunächst ignorieren und die Potenzierung der algebraischen Zahl als das folgende Problem definieren: Berechnen Sie bei α und m wie oben eine (komplexe) Gleitkommanäherung von e α an m relative Bits Richtigkeit.Reeααmeαm

Fakt: Bis auf lineare Faktoren entspricht die Komplexität der algebraischen Zahlenexponentiation der Komplexität der algebraischen Zahlennäherung plus der Komplexität der komplexen Exponentiation.

Beweisskizze: Einerseits können wir zuerst die Fixpunktnäherung von berechnen und dann potenzieren. Es ist zu beachten, dass m + O ( 1 ) Bits mit absoluter Genauigkeit für α e α bis m Bits mit relativer Genauigkeit bestimmen und umgekehrt.αm+O(1)αeαm

Wenn wir andererseits eine algebraische Zahlenexponentiation durchführen können, können wir auch eine einfache Exponentiation durchführen, da wir eine Festpunktzahl (die als genau angesehen wird) leicht in ihre Darstellung als algebraische Zahl umwandeln können. Durch die obigen Kommentare bedeutet dies, dass wir auch Logarithmen in derselben Zeitgrenze berechnen können. Wir können also eine algebraische Zahl approximieren , indem wir zuerst approximieren und dann einen Logarithmus nehmen. QEDeα

Dies teilt die Frage in zwei völlig unabhängige Probleme auf. Die bekannteste Obergrenze für die Potenzierung ist

Satz ( Brent ): Wenn wir Bit-Ganzzahlen in der Zeit M ( n ) multiplizieren könnennM(n) , können wir die komplexe Exponentiation (und den Logarithmus) in der Zeit berechnen .O(M(n)logn)

Die bekannteste Untergrenze ist Ω(M(n)) oben erwähnte . Die bekannteste Obergrenze für ist n log nM(n) nach Fürers Algorithmus.nlogn2O(logn)

Es ist schwieriger, den Stand der Technik für die algebraische Näherung von Zahlen (dh das Finden von Wurzeln) herauszufinden, da es sich immer noch um ein Gebiet aktiver Forschung handelt und die Formulierungen von Grenzen in der Literatur oft nicht so klar sind, wie man es gerne hätte. Lassen bezeichnen O ( f ( n ) p o l y l o g ( f ( n ) ) ) .O~(f(n))O(f(n)polylog(f(n)))

Für reale Wurzel Annäherung, Pan und Tsigaridas geben:

Satz: Die Näherung der reellen algebraischen Zahl kann in der Zeit , wobei d = deg (O~(d2τ+dm) ist und τ das Maximum der Bitlängen der Koeffizienten von f ist .d=deg(f)τf

In derselben Arbeit erwähnen sie als die bekannteste Grenze für die komplexe Wurzelnäherung. In einem etwas neueren Artikel ( http://arxiv.org/abs/1404.4775 ) scheinen sie für den komplexen Fall die gleichen Grenzen zu beanspruchen wie für den realen Fall, unter der Annahme, dass die angegebene Isolationsplatte ein Isolationsverhältnis aufweist (the Abstand der Plattenmitte zur nächsten anderen Wurzel von f geteilt durch den Radius der Platte) mindestensO~(d3+d2m)f oder so, aber es ist ziemlich chaotisch geschrieben und ich kann es falsch interpretieren.1+1/logd


Nun die letzte Komplikation. Ich habe das Problem als Annäherung an , während die Frage nach Re e α fragt . Dies macht das Problem tatsächlich schwieriger: Wenn Re e αIm e α ist , dann hat eine Annäherung x + i y von e α an m Bits relativer Genauigkeit den Fehler y 2 - m , der durchaus größer als x selbst sein kann, und in Es ist nicht garantiert, dass der Fall durch x 2 - m begrenzt ist .eαReeαReeαImeαx+iyeαmy2mxx2m

Zur Potenzierung exakter Rationalitäten können wir das Problem umgehen:

Satz: Wenn und unäres m gegeben sind , wobei x , y binäre Rationalen (oder exakte Festpunktzahlen) sind, können wir eine Gleitkommanäherung von Re e α an m Bits relativer Genauigkeit innerhalb derselben Zeitgrenze berechnen als komplexe Exponentiation wie oben definiert, bis zum linearen Faktor. (Dh, O ( M.α=x+iymx,yReeαm Verwendung des Brent-Algorithmus.)O(M(n)logn)

Beweisskizze: Wir haben . Wir können e x approximieren und Gleitkommazahlen lassen sich leicht multiplizieren. Das Problem besteht darin, cos y mit dem relativen Fehler 2 - m zu approximieren . Wir können die ganze Zahl berechnen k am nächsten zu 2 y / π , von wo cos y ist ± cos y ' oder ± sin y ' , wobei y ' = y -Reeα=excosyexcosy2mk2y/πcosy±cosy±siny erfüllt| y'| π/4. Das Problem tritt auf, wenn wirsiny'berechnen müssenundy'sehr klein ist, dawirm+log|benötigen, umsiny'zumBits relativer Genauigkeitzu haben y'-1| Bits von absoluter Genauigkeit. Angenommen,y=u/vist klein, so haben wir eine gute rationale Näherung vonπ: y=ykπ2|y|π/4sinyysinymm+log|y1|y=u/v , wobei ganze Zahlen sind, die als Eingabe angegeben werden. Wenn y 'u,vyπ Nunπist bekannteinen finite Unvernünftigkeit Maß habenν(die Stromgrenze ist7.6063vonSalikhov). Dies impliziert | y'| 1

|π2ukv|2|y|k.
πν7.6063 was eine lineare Obergrenze fürlog|ergibt y'-1| in Bezug auf die Länge der Eingabe. Wir können alsoy'mit der gewünschten Genauigkeitberechnen; Die Bewertung vonsiny'ist dann kein Problem (wenny'ausreichend klein ist, können wir einfachsiny'y' nehmen). QED
|y|12kν1vν,
log|y1|ysinyysinyy

Ich weiß nicht, ob das auch für algebraisches . Im obigen Argument kann man eine Bindung an log | erhalten y ' | Nach dem Satz von Baker ist jedoch keine seiner Versionen, die ich gesehen habe, gut genug, um die erforderliche Genauigkeit in der Größe der Eingabe linear zu machen: Insbesondere beinhalten die Grenzen ein (ziemlich unangenehmes) Polynom in Gradαlog|y| . Dies macht den resultierenden Algorithmus polynomisch in der Größe der Eingabe, aber mit einem lächerlichen Exponenten.deg(f)

Emil Jeřábek
quelle
Ich denke, das Hauptproblem ist, dass die Potenzierung über ganze Zahlen nicht mehrzeitberechnbar ist. Eine Möglichkeit, mit der Potenzierung über reelle Zahlen umzugehen, besteht darin, dieses Problem vom Rest zu trennen: 1. Finden Sie eine ganze Zahl so dass 0 b / k < 1 , 2. Berechnen Sie r = ( b / k ) e , 3. return ( r , k , e ) als Antwort. k0b/k<1r=(b/k)e(r,k,e)
Kaveh
k,b,e(r,k,e)2aaeaa/log2exp(aa/log2log2)
be
renb/k1/2r22nkerkkkann variieren, was es schwierig macht, Berechnungen für solche Darstellungen durchzuführen. Was sind die Vorteile?
Emil Jeřábek