Vergleich zweier Produkte von Ganzzahllisten?

10

Angenommen, ich habe zwei Listen positiver Ganzzahlen mit begrenzter Männlichkeit und nehme das Produkt aller Elemente jeder Liste. Wie lässt sich am besten feststellen, welches Produkt größer ist?

Natürlich kann ich einfach jedes Produkt berechnen, aber ich hoffe, dass es einen effizienteren Ansatz gibt, da die Anzahl der Ziffern in den Produkten linear mit der Anzahl der Terme zunimmt, so dass die gesamte Berechnung quadratisch ist.

Wenn ich addieren statt multiplizieren würde, könnte ich eine "Zippering-Strategie" verwenden, bei der Einträge aus der ersten Liste schrittweise hinzugefügt und von der zweiten subtrahiert werden, um die Notwendigkeit zu umgehen, die (großen) Gesamtsummen zu berechnen. Die analogen Techniken für Produkte würden darin bestehen, die Logarithmen der Einträge zu summieren, aber das Problem besteht nun darin, dass für die Berechnung der Protokolle eine ungenaue Arithmetik erforderlich ist. Es sei denn, es gibt eine Möglichkeit zu beweisen, dass der numerische Fehler irrelevant ist?

user168715
quelle
Wenn wir den maximalen ganzzahligen Wert kennen und dieser unabhängig von n ist (dh eine Konstante k), können wir eine Nachschlagetabelle der Faktoren aller Zahlen von 1 bis k erstellen. Nun denke ich, wenn Sie alles in die Basis [Produkt der Faktoren] schreiben, wird es linear, da Sie die Produkte in linearer Zeit mit dieser Basis berechnen können und dann jede Ziffer (beginnend mit der Ziffer höchster Ordnung) der Reihe nach vergleichen, bis eine größer als die andere ist. Die Details dort sind etwas knifflig, aber ich denke, das sollte funktionieren, wenn k eine Konstante ist.
Phylliida
Ich würde eher sagen, dass die analoge Technik für Produkte darin besteht, eine rationale Zahl gleich den ersten Elementen der ersten Liste geteilt durch die ersten Elemente der zweiten (plus Behandlung von s) zu halten. Aber das ist nicht wirklich hilfreich, denn wenn alle Zahlen Coprime sind, werden beide Produkte berechnet. | Ich bin mir auch nicht sicher, ob der naive Algorithmus quadratisch ist. Die Berechnung eines Produkts aus n ganzen Zahlen der Größe m kann bis zu C ( m , m ) + C ( m , 2 m ) + dauern . . . + C ( m , ( n0nm wobei C ( x , y ) die Kosten für die Multiplikation einer x- Bit-Ganzzahl mit einer y- Bit-Ganzzahl sind. Es sei denn, Sie berücksichtigen, dass die Produkte auch in das Format passenC(m,m)+C(m,2m)+...+C(m,(n1)m)C(x,y)xy
xavierm02
1
Es kann eine Möglichkeit geben, die Methode in math.stackexchange.com/a/1081989/10385
xavierm02
Eine Verbesserung des naiven Ansatzes: Zählen Sie die Anzahl der Vorkommen jedes Faktors (in linearer Zeit) und berechnen Sie das Produkt erst am Ende mithilfe eines effizienten Stromversorgungsalgorithmus. Dies funktioniert in der Zeit , die O ( n) istO(M(n)) Verwendung der derzeit asymptotisch schnellsten Methode. O(nlogn2O(logn))
Emil Jeřábek
2
Ich werde über die erforderliche Genauigkeit für Protokolle nachdenken. Es kann tatsächlich effizienter sein.
Emil Jeřábek

Antworten:

6

(Ich verstehe die Beschreibung des Problems so, dass die Eingabenummern durch eine Konstante begrenzt sind, sodass ich die Abhängigkeit von der Grenze nicht verfolgen kann.)

Das Problem ist in linearer Zeit und logarithmischem Raum unter Verwendung von Summen von Logarithmen lösbar. Im Detail ist der Algorithmus wie folgt:

  1. Zählen Sie mithilfe von Binärzählern die Anzahl der Vorkommen jeder möglichen Eingangsnummer in beiden Listen.

Dies dauert einige Zeit , und die Zähler verwenden den Raum O ( log n ) , da jeder Zähler im Wert durch n begrenzt ist.O(n)O(logn)n

p1,,pkO(1)aaO(logn)

  1. β1,,βkO(logn)Λ:=i=1kβilogpi

  2. β1==βk=0

Λ0

|Λ|>2Clogn
CΛ
  1. Geben Sie das Vorzeichen von i=1kβiπiπilogpim:=Clogn+k+1

M(m)m , aber hier würde es keinen großen Unterschied machen, selbst wenn wir den trivialen O ( m 2 ) -Multiplikationsalgorithmus verwenden. Wir können rechnenM(m)=O(mlogm2O(logm))O(m2)logpimO(M(m)logm)iβiπiO(M(m))O(M(m)logm)O(lognpoly(loglogn))

O(n)

Emil Jeřábek
quelle
Vielen Dank! Ich muss die Details später durcharbeiten, aber das scheint sehr vielversprechend!
user168715