Vergleich großer Basen/Exponenten?

[Guest]

Hallo,

wie kann ich effizient zwei sehr große Basen/Exponenten miteinander vergleichen?

Beispiel:

343443^534543 und 433453^234323

Da man das mit keinem Taschenrechner berechnen kann, hab ichs mit der schnelle Exponentiation versucht:

	public static BigInteger berechne(int b1, int e1){
		BigInteger two = BigInteger.valueOf(2);
		BigInteger x = BigInteger.ONE;
		BigInteger e = BigInteger.valueOf(e1);
		BigInteger b = BigInteger.valueOf(b1);
		while(!(e.compareTo(BigInteger.ZERO) == 0)){
			while(e.mod(two).compareTo(BigInteger.ZERO) == 0){
				e = e.divide(two);
				b = b.pow(2);
			}
			e = e.subtract(BigInteger.ONE);
			x = x.multiply(b);
		}
		return x;
	}

Allerdings dauert das immer noch ewig. Muss ich den Wert überhaupt berechnen oder kann ich auch anders feststellen welche Basen/Exponenten die größere Zahl ergeben?

 

[Joker]

du könntest BigInteger#pow() benutzen:

 public static int compareBigIntegers(int b1, int e1, int b2, int e2) {		 
		  BigInteger zahl = BigInteger.valueOf(b1).pow(e1);
		  BigInteger zahl2 = BigInteger.valueOf(b2).pow(e2);		  
		  return zahl.compareTo(zahl2);
	  }

aber ob das sehr viel schneller ist wage ich zu bezweifeln. Du könntest das ganze nochmal beschleunigen, indem du die beiden Zahlen parallel berechnest, zumindest bei Prozessoren mit >2 Kernen bringt das dann schon was.

Allerdings kann ich mir keinen Anwendungsfall vorstellen, wo sechsstellige Exponenten benötigt würden das geht sogar weit über das was in der Kryptografie benötigt wird hinaus.

 

[Gast]

Es geht viel einfacher:
Math.log(z1_basis) * z1_exponent > Math.log(z2_basis) * z2_exponent

 

[SlaterB]

grummel, immer diese einfachen Lösungen

faszinierendes Problem, habe dazu eine Weile gesessen, da kann ich meine Idee für eine schnelle Bestimmung noch skizzieren:

Abschätzung/ Rundung nutzen!,
die Zahlen werden ja sicherlich um tausende Dezimalstellen und mehr abweichen, was man nur nicht erkennen kann,
da kann man auch ruhig die Zahlen etwas größer oder kleiner wählen,
wenn man die Zahl x kleiner macht und diese sich dann als größer herausstellt als die vergrößerte Zahl y, dann ist x auch garantiert größer als y

was nützt es, die Zahlen größer oder kleiner zu machen?
wenn man geschickt wählt, bekommt man Zahlen, die in einfache Primfaktoren zerfallen, das hilft bei der weiteren Berechnung

343443 ist größer als 327680 = 2^16 * 5
433453 ist kleiner als 466560 = 2^7 * 3^6 * 5

solche Zahlen drumherum kann man recht gut mit einfachen Mittel berechnen, erstmal lauter Zweien wählen,
wenn die gesuchte Zahl grob erreicht ist , dann verfeinern, z.B. 3 Zweien durch 2 Dreien ersetzen

-------

statt 343443^534543 und 433453^234323 werden nun 327680^534543 und 466560^234323 verglichen,
klingt noch nicht viel einfacher, aber als Primzahlen bedeutet das

2^(16*534543) * 5^534543 vs. 2^(7 *234323) * 3^(6*234323) * 5^234323

nun muss man kräftig kürzen, am einfachsten natürlich Zweien gegen Zweien usw.

aber auch unterschiedliche Ziffern sind zu kürzen, wenn man wieder großzügig rundet:
2^8 sind 256, 3^5 sind 243, also kann man jeweils 8 Zweien gegen 5 Dreien kürzen,
wenn man nur immer in die gleiche Richtung rundet
(immer eine Zahl kleiner machen und die andere größer)

am Ende werden höchstwahrscheinlich auf einer Seite Zigtausend Faktoren überbleiben, das ist dann die größere
und wenn das die Zahl war die immer verkleinert wurde, während die andere immer größer wurde, dann ist der Beweis erbracht,
im Negativfall muss man das ganze nochmal umgekehrt machen: nun immer die andere Zahl vergrößern usw.

falls beide Durchgänge nicht das gleiche Resultat bringen, dann liegen die Zahlen sehr dicht zusammen,
dann hilft das Verfahren nicht, aber das wäre wohl fast ein Lottogewinn
falls man nicht aktiv dichte Paare wie 343443^534543 und 343444^534542 vergleicht