| |
| Autor |
 Wie findet man schnell aus einer sehr großen Zahl einen bestimmten Teiler? |
|
hyperG
Senior 
Dabei seit: 03.02.2017
Mitteilungen: 1994
 |  Themenstart: 2023-02-01
|
Hallo zusammen,
gegeben sei eine sehr große Zahl: z=1333^46-1333^2
gesucht:
\sourceon gesucht
Teiler > 371589506172169684820792380487023574727989967093214168534795930157231838
Teiler < 371589506172169684876530806412849043187994525658140101859623884373371844
\sourceoff
Universeller Weg mit bekannten Funktionen wie "Divisors":
\sourceon Mathematica
divis = Divisors[z];Length[divis]
Select[divis, Untergrenze < # < Obergrenze &]
(* liefert hier im Idealfall nur 1 Teiler statt 17694720*2 Stück!!
(bis zu 10 mögliche Teiler ist auch kein Problem)
*)
\sourceoff
Ist jedoch sehr langsam, da selbst mit dem 1. Optimierungs-Trick:
"z=z/(größterPrimteilerVon(z))"
noch 17694720 Teiler über bleiben!!
Primteiler > Obergrenze müssen eh nicht betrachtet werden!
Frage: Ich kenne ja die Faktorisierung von z (ohne den größten Primfaktor):
2^4 · 3^2 · 5 · 23 · 29 · 31^2 · 37 · 43^2 · 89 · 137 · 199 · 1297 · 15907 · 16699 · 438989 · 1461637 · 560096021 · 925274476589 · 6052230764119 · 18561034430599 · 2679949944233566577
Wie kann man die relevanten Teiler bereits vorab herausfiltern, ohne alle 17 Mio. Teiler betrachten zu müssen?
Ich hatte schon überlegt, mit einem eigenen Code wie
https://www.geeksforgeeks.org/generating-all-divisors-of-a-number-using-its-prime-factorization/
mir selbst die Funktion zur Ermittlung aller Teiler zu schreiben und schon bei der Generierung diejenigen herauszufiltern, die außerhalb der Grenzen liegen. So entfällt auch die Sortierung, die ja beim Befehl "Divisors"
auch zwangsweise mit dran hängt & auch Zeit frisst.
Da hier viele schlaue Denker dabei sind, gibt es doch bestimmt auch noch andere Optimierungswege...
Es hat auch nichts mit Mathematica zu tun, da es hier um einen universellen Optimierungs-Algorithmus geht.
In SAGE lautet der Befehl übrigens divisors(z).
Leider habe ich noch keine Sprache/Algorithmus gefunden, wo man Unter- & Obergrenze mit eingeben kann, um die Ergebnis-Anzahl zu verkleinern
und Geschwindigkeit zu vergrößern...
Grüße Gerd
Beispiel:
Divisors[2^9 * 438989 *1000003, min=10^5,max=5*10^5]
muss man nicht alle 40 Teiler betrachten, sortieren und vergleichen,
sondern man sieht ohne zu rechnen, dass nur der mittlere Primfaktor allein die Einschränkung erfüllt!
|
 Profil
|
hyperG
Senior 
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.1, vom Themenstarter, eingetragen 2023-02-02
|
Optimierung des Beispiels mit der bekannten c-Funktion aus
geeksforgeeks.org/generating-all-d...prime-factorization/
bei der Erstellung nur nach OBEN begrenzt
ergibt schon mal 11 statt 40 Werte:
1 438989 2 4 8 16 32 64 128 256 512
Die restlichen 10 "zu kleinen" kann man erst bei der letzten Ausgabe
herausfiltern, da sie ja durch "noch anstehende Multiplikationen"
gültig sein könnten - oder?
|
Profil
|
DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 3262
 | Beitrag No.2, eingetragen 2023-02-02
|
Falls die Faktorisierung unbekannt ist, wird es keine effiziente Lösung geben.
Falls die Faktorisierung bekannt ist, ist es äquivalent zum Problem, aus einer Menge von Summanden alle Summen in einem bestimmten Intervall zu berechnen.
Falls man so wenige Summanden hat wie hier, kann man dazu die Menge halbieren, für jede Hälfte per Brute-Force alle Summen bestimmen und dann die Summenmengen der zwei Hälften in Linearzeit "mergen".
Damit hat man die Laufzeit des naiven Brute-Force-Ansatzes immerhin auf etwa die Quadratwurzel reduziert. Exponentiell ist sie nach wie vor in der Anzahl der Faktoren/Summanden.
Edit: Denkfehler: Das Mergen funktioniert nur dann in annähernder Linearzeit, wenn das Intervall (wie hier) sehr klein ist.
|
Profil
|
Ixx
Aktiv
Dabei seit: 05.04.2020
Mitteilungen: 343
 | Beitrag No.3, eingetragen 2023-02-02
|
Bei bekannter Faktorisierung sollte Dynamische Programmierung gut funktionieren.
|
Profil
|
Fabi
Senior
Dabei seit: 03.03.2002
Mitteilungen: 4586
 | Beitrag No.4, eingetragen 2023-02-02
|
Hallo,
Welche Geschwindigkeit wäre denn akzeptabel bzw. wielange braucht dein Mathematica-Code?
vG,
Fabi
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.5, vom Themenstarter, eingetragen 2023-02-02
|
\sourceon Mathematica
t1=AbsoluteTime[];divis=Divisors[1333^46-1333^2];(* dauert 84 s *)
Select[divis,371589506172169684820792380487023574727989967093214168534795930157231838<#<371589506172169684876530806412849043187994525658140101859623884373371844&]
AbsoluteTime[]-t1
Length[divis]
Out:
{371589506172169684825466647758074245946272352812525824261090539212864452,371589506172169684825466647758074245946272352812525824261090539212865785}
Out[3]= 101.9603469 s (* V12 sogar 105 s *)
Out[4]= 35389440 Teiler
\sourceoff
\sourceon SAGE
for t in divisors(1333**46-1333**2):
if (371589506172169684820792380487023574727989967093214168534795930157231838 < t) & (t < 371589506172169684876530806412849043187994525658140101859623884373371844):
print(f'(t)={(t)}\n')
Out: nach 56 s beide Ergebnisse da:
(t)=371589506172169684825466647758074245946272352812525824261090539212864452
(t)=371589506172169684825466647758074245946272352812525824261090539212865785
\sourceoff
Mein Versuch der Optimierung:
\sourceon Mathematica
primzerlegung = FactorInteger[1333^46 - 1333^2, Automatic]; (* Automatic bedeutet, dass nach 2.7 s abgebrochen wird, da der letzte Faktor
560196326334932122996877071071998993786115796675946741 zu lange dauert
... dann Rekursionsfunktion mit Break/Exit, sobald zu groß
aus https://www.geeksforgeeks.org/generating-all-d...prime-factorization/
*)
Out1:
{371589506172169684825466647758074245946272352812525824261090539212865785,371589506172169684825466647758074245946272352812525824261090539212864452}
Out2: 160 s (* V12 170 s *)
\sourceoff
Es kommt zwar das selbe Ergebnis heraus & die Primfaktorzerlegung ist mit 2.7 s schnell genug,
ABER trotz Herausfilterung ganzer Bäume, die schon mitten im Ast die Grenze überschreiten,
ist die Summenzeit sehr viel langsamer!
Vermutlich ist der Interpreter für rekursive Funktionen mit sehr großen Listen (35389440 Einträge) einfach ungeeignet.
c++ & GMP & Pointer auf Listen müsste da sehr viel schneller werden...
|
Profil
|
DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 3262
| Beitrag No.6, eingetragen 2023-02-02
|
Quick&Dirty in Python:
\sourceon Python
\numberson
D = [2, 2, 2, 2, 3, 3, 5, 23, 29, 31, 31, 37, 43, 43, 89, 137, 199, 1297, 15907, 16699,
438989, 1461637, 560096021, 925274476589, 6052230764119, 18561034430599,
2679949944233566577, 209032384183258142429336555562696133]
def product(divisors):
P = 1
for d in divisors:
P *= d
return P
print(f"{product(D) == 1333**46 - 1333**2}")
def partial_sums(S, op=lambda x, y: x+y, zero=0):
stack = [(0, zero)]
sums = set()
N = len(S)
while stack:
idx, value = stack.pop()
if idx >= N:
sums.add(value)
else:
stack.append((idx+1, op(value, S[idx])))
stack.append((idx+1, value))
return sums
def merge_sums(S1, S2, lo, hi, op=lambda x, y: x+y):
s1 = sorted(S1)
s2 = sorted(S2, reverse=True)
i = 0
j = 0
sums = set()
while i < len(s1) and j < len(s2):
s = op(s1[i], s2[j])
if s <= lo:
i += 1
elif s >= hi:
j += 1
else:
k = j
while s > lo:
sums.add(s)
k += 1
if k >= len(s2):
break
s = op(s1[i],s2[k])
i += 1
return sums
from time import time_ns
T0 = time_ns()
even = D[::2]
odd = D[1::2]
print(f"{len(D)=} {len(even)=} {len(odd)=}")
even_products = partial_sums(even, op=lambda x, y: x*y, zero=1)
odd_products = partial_sums(odd, op=lambda x, y: x*y, zero=1)
print(len(even_products))
print(len(odd_products))
LO = 371589506172169684820792380487023574727989967093214168534795930157231838
HI = 371589506172169684876530806412849043187994525658140101859623884373371844
M = merge_sums(even_products, odd_products, LO, HI, op=lambda x, y: x*y)
print(f"gefundene Lösungen: {len(M)}")
print(f"Lösungen: {M}")
print(f"time elapsed: {(time_ns() - T0)/10**6:.1f}ms")
"""
True
len(D)=28 len(even)=14 len(odd)=14
12288
12288
gefundene Lösungen: 2
Lösungen: {371589506172169684825466647758074245946272352812525824261090539212864452, 371589506172169684825466647758074245946272352812525824261090539212865785}
time elapsed: 84.0ms
"""
\sourceoff
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.7, vom Themenstarter, eingetragen 2023-02-02
|
Hallo DerEinfaeltige,
ganz großen Dank!!
Nach Entfernen des Sonderzeichens "ö" hat py es bei mir in
\sourceon py
True
len(D)=28 len(even)=14 len(odd)=14
12288
12288
gefundene Loesungen: 2
Loesungen: {371589506172169684825466647758074245946272352812525824261090539212864452, 371589506172169684825466647758074245946272352812525824261090539212865785}
time elapsed: 15.6ms
\sourceoff
erledigt!!! Wow. Steigerung um den Faktor 6538 !!!!
Genau das hatte ich vermutet, dass hier was mächtig uneffektiv läuft.
Grüße Gerd
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.8, vom Themenstarter, eingetragen 2023-02-02
|
Gegenprobe mit unfertiger Primfaktorzerlegung:
\sourceon Python
D = [2, 2, 2, 2, 3, 3, 5, 23, 29, 31, 31, 37, 43, 43, 89, 137, 199, 1297, 15907, 16699,
438989, 1461637, 560096021, 925274476589, 6052230764119, 18561034430599,
560196326334932122996877071071998993786115796675946741]
...
Ausgabe:
True
len(D)=27 len(even)=14 len(odd)=13
12288
6144
gefundene Loesungen: 2
Loesungen: {371589506172169684825466647758074245946272352812525824261090539212864452, 371589506172169684825466647758074245946272352812525824261090539212865785}
time elapsed: 15.6ms
\sourceoff
Funktioniert!
Hintergrund:
Mit Näherungsformeln kann ich mir den Suchbereich einschränken.
Da die gegebenen Zahlen meist sehr große Primteiler (größer als Obergrenze) enthalten, haben sie für das Endergebnis keinen Einfluss.
Erst wenn KEIN Teiler mit dieser "Abkürzung" gefunden wurde, muss man sich die Primfaktorzerlegung genauer anschauen.
Sollten z.B. RSA-Zahlen mit über 160 Stellen über bleiben, ist dieser Weg versperrt.
Dann müsste man anders nach Teilern suchen.
|
Profil
|
| hyperG hat die Antworten auf ihre/seine Frage gesehen. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
