spezielle "Faktorzerlegung" < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo zusammen,
Folgende Aufgabe ist selbstgestellt(, und deshalb eventuell ungenau formuliert):
| Aufgabe | Man bestimme mit so wenigen elementaren Operationen wie möglich, ob sich eine Zahl [mm]n\in\mathbb{N}_{\geqslant 4}[/mm] in der Form [mm]n=b^a[/mm] mit [mm]a,b\in\mathbb{N}_{\geqslant 2}[/mm] darstellen lässt.
Mit "elementaren Operationen" meine ich: +, -, *, /, floor(.), ceil(.), mod und div aber so etwas wie sqrt(.) sollte man nicht verwenden. |
Ein naiver Ansatz wäre wohl das hier:
[mm]\begin{array}{l@{\ }l@{\,}l@{\,}l}
\forall&\multicolumn{3}{@{\!}l}{b\in \left[2:\left\lceil\frac{n}{2}\right\rceil\right]:}\\
{}&\forall&\multicolumn{2}{@{\!}l}{a\in \left[2:\left\lceil\frac{n}{2}\right\rceil\right]:}\\
{}&{}&\texttt{if}&b^a = n\texttt{ return ``ist potenz''}\\
\multicolumn{4}{l}{\texttt{return ``keine potenz''}}
\end{array}[/mm]
(Die Potenzierung kann man als wiederholte Multiplikation implementieren, weshalb ich das nicht genauer ausgeführt habe.)
Gibt es Sätze aus der Zahlentheorie mit denen sich so eine Aufgabe schneller lösen lässt?
Gruß V.N.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:20 Mo 25.01.2010 | | Autor: | felixf |
Moin V.N.!
> Folgende Aufgabe ist selbstgestellt(, und deshalb eventuell
> ungenau formuliert):
>
> Man bestimme mit so wenigen elementaren Operationen wie
> möglich, ob sich eine Zahl [mm]n\in\mathbb{N}_{\geqslant 4}[/mm] in
> der Form [mm]n=b^a[/mm] mit [mm]a,b\in\mathbb{N}_{\geqslant 2}[/mm]
> darstellen lässt.
>
> Mit "elementaren Operationen" meine ich: +, -, *, /,
> floor(.), ceil(.), mod und div aber so etwas wie sqrt(.)
> sollte man nicht verwenden.
> Ein naiver Ansatz wäre wohl das hier:
>
> [mm]\begin{array}{l@{\ }l@{\,}l@{\,}l}
\forall&\multicolumn{3}{@{\!}l}{b\in \left[2:\left\lceil\frac{n}{2}\right\rceil\right]:}\\
{}&\forall&\multicolumn{2}{@{\!}l}{a\in \left[2:\left\lceil\frac{n}{2}\right\rceil\right]:}\\
{}&{}&\texttt{if}&b^a = n\texttt{ return ''ist potenz''}\\
\multicolumn{4}{l}{\texttt{return ''keine potenz''}}
\end{array}[/mm]
Ich nehme mal an, dass $b [mm] \in [/mm] [x : y]$ heissen soll, dass $b$ alle ganzen Zahlen im Intervall $[x, y]$ durchlaeuft? Dann geht das so, aber effektiv ist es nicht  Sooo schlimm aber auch wieder nicht.
> (Die Potenzierung kann man als wiederholte Multiplikation
> implementieren, weshalb ich das nicht genauer ausgeführt
> habe.)
>
> Gibt es Sätze aus der Zahlentheorie mit denen sich so eine
> Aufgabe schneller lösen lässt?
Schliessen wir erstmal den trivialen Fall $n = 1$ aus
Wenn $n = [mm] a^b$ [/mm] ist, dann ist $b = [mm] \frac{\log_2 n}{\log_2 a}$. [/mm] Da $a [mm] \ge [/mm] 2$ sein muss, folgt dass $b [mm] \le \log_2 [/mm] n$ ist. Es gibt also schonmal eine bessere Einschraenkung fuer $b$, naemlich $2 [mm] \le [/mm] b [mm] \le \log_2 [/mm] n$.
Ist weiterhin $n = [mm] a^b$ [/mm] mit $b [mm] \ge [/mm] 2$, so gibt es eine Primzahl $p$ (die $b$ teilt) und ein [mm] $\tilde{a} \in \IN$ [/mm] mit $n = [mm] \tilde{a}^p$. [/mm] Es reicht also aus, fuer $b$ nur Primzahlen zu nehmen.
Weiterhin gibt es zu jeder moeglichen Wahl von $b$ hoechstens eine Wahl von $a$; damit reduziert man den Suchraum aus deinem naiven Algorithmus noch weiter. Man kann also auch schreiben:
| 1: | for b from 2 to floor(log2(n))
| | 2: | if nthpower(n, b) then
| | 3: | return "ist potenz"
| | 4: | return "keine potenz" |
Hierbei muss man jetzt noch erklaeren, wie man floor(log2(n)) und nthpower(n, b) schnell ausrechnet.
Den Wert floor(log2(n)) kann man sehr schnell aus der Binaerdarstellung von $n$ ablesen: ist $t [mm] \in \IN$ [/mm] maximal mit [mm] $2^t \le [/mm] n$, so ist [mm] $\lfloor \log_2 [/mm] n [mm] \rfloor [/mm] = t$. Das kann man also sehr schnell ausrechnen :)
Nun zum nthpower-Test. Dies kann man mit reiner Integer-Arithmetik auch relativ schnell ausrechnen. Die Idee ist, dass man ein maximales $a [mm] \in \IN$ [/mm] sucht mit [mm] $a^b \le [/mm] n$; erfuellt dieses $a$ die Gleichung [mm] $a^b [/mm] = n$, so ist $n$ eine $b$-te Potenz, andernfalls nicht.
Dazu schreibt man $a = [mm] \sum_{i=0}^t a_i 2^i$ [/mm] mit [mm] $a_i \in \{ 0, 1 \}$, [/mm] wobei $t = [mm] \lfloor \frac{\log_2 n}{b} \rfloor$ [/mm] ist. Erst setzt man alle [mm] $a_i$ [/mm] auf 0. Dann probiert man von oben durch, einzelnde [mm] $a_i$ [/mm] auf 1 zu setzen, und schaut ob [mm] $a^b \le [/mm] n$ ist. Etwa so:
| 1: | for i from t downto 0
| | 2: | set a_i := 1
| | 3: | if a^b > n then
| | 4: | a_i := 0 |
Hier benoetigt man zwar einige Potenzen von ganzen Zahlen, aber das ganze geht vergleichsweise schnell. Wenn man ne genauere Laufzeitanalyse macht, stellt man fest dass das alles in einer [mm] $\log [/mm] n$ polynomiellen Anzahl von binaeren Rechenoperationen geht.
(Anstelle alle primen $b$ kann man auch einfach alle $b$ nehmen, oder man benutzt jeweils einen schnellen Primzahltest (der evtl. zu viele Primzahlen liefert), oder man benutzt einfach das ![[]](/images/popup.gif) Sieb des Eratosthenes.)
LG Felix
|
|
|
| |
|
Hallo Felix,
Danke für deine Hilfe! Der Algorithmus funktioniert und ich habe deine Herleitung gut nachvollziehen können. :)
Für den Fall, daß jemand von den Mitlesern auch diesen Algorithmus programmieren möchte, mache ich noch eine Bemerkung:
> wobei [mm]t = \lfloor \frac{\log_2 n}{b} \rfloor[/mm] ist.
Hier wußte ich zunächst nicht weiter, aber in der Wikipedia steht:
http://en.wikipedia.org/wiki/Floor_and_ceiling_functions#Quotients
Setzt man dort [mm]m=0\![/mm], ist das Ganze auch leicht und vor allem schnell berechenbar. ;)
Gruß V.N.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:51 Di 26.01.2010 | | Autor: | felixf |
Hallo V.N.!
Genau, [mm] $\lfloor [/mm] x [mm] \rfloor$ [/mm] ist die groesste ganze Zahl $z [mm] \in \IZ$ [/mm] mit $z [mm] \le [/mm] x$. Wenn man eine Integerdivision von zwei positiven ganzen Zahlen $a, b [mm] \in \IN$ [/mm] macht, spuckt der Computer einem uebrigens sowieso immer [mm] $\lfloor \frac{a}{b} \rfloor$ [/mm] raus.
(Ich hatte noch eine Idee, wie man das ganze optimieren kann, aber die stimmte leider nicht... Deswegen habe ich sie hier entfernt.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:20 Fr 28.01.2011 | | Autor: | felixf |
Moin,
> Man bestimme mit so wenigen elementaren Operationen wie
> möglich, ob sich eine Zahl [mm]n\in\mathbb{N}_{\geqslant 4}[/mm] in
> der Form [mm]n=b^a[/mm] mit [mm]a,b\in\mathbb{N}_{\geqslant 2}[/mm]
> darstellen lässt.
der Algorithmus von Dan Bernstein ist wohl die schnellste Methode, das zu ueberpruefen (in quasilinearer Zeit).
LG Felix
|
|
|
|
