[HaBo]

lone.wolf

Abstrakt:
Prüfe, ob dass Produkt zweier beliebigen Zahlen kleiner ist als eine
weitere Zahl - OHNE das Produkt zu berechnen

x * y <= z ?

Beispiel: RSA
P*Q soll kleiner als 2^64 sein.

Folgendes noch: Auf Overflow prüfen ist nicht erlaubt!

MfG

D31~$0u1

Also, warum man das Produkt nicht ausrechnen soll, versteh ich zwar nicht, aber so müsste es im Prinzip gehen:

Lg, D31~$0u1

detrexer

ähm ... teilen?

X*Y < Z |/X
y < Z/X

__________________
Mein Blog: http://keinwegraus.wordpress.com/

ChiefWiggum

x * y <= z

"Eine Division ist eine Multiplikation mit dem Kehrwert"
Also:
x / (1/y)

__________________
Be the source always with you.

sw33tlull4by

Wie wäre es mit umformung?
x*y <= z
y <=z/x bzw. x<=z/y

//edit
bevor das unklar wird:
es müssen beide Bedingungen erfüllt sein damit x*y <= z wirklich stimmt

__________________
Nur die Schwachen klammern sich an die Moral.

Kill my daemons and my angels will follow them.

ChiefWiggum

Da bin ich aber anderer Meinung.
Wenn die eine [Bedingung] Zutrifft, dann WIRD die andere auch zutreffen.
Es kann nicht nur eine Zutreffen

x*y <= z
x <= z/y
Allerdings muss y > 0, sonst kehrt sich doch das <= um^^

__________________
Be the source always with you.

0wnZ

Für welchen Definitionsbereich ? Reelle Zahlen ?
Zunächst würde ich ich prüfen, ob eine der Zahlen größer ist als z (es sei denn es werden auch negative Zahlen zugelassen, dann müssen zusätzlich auch Vorzeichen geprüft werden). Sonst würde ich iwi "schummeln", dass man indirekt die Produkte erfährt. (=> Alles ohne Informatik bisher)

sw33tlull4by

AlterHacker:
Beide müssen ja nicht zutreffen, denn wer sagt das x*y<z gilt?
das soll ja gerade rausgefunden werden.
und ob x,y positiv oder negativ sind ist bei der betrachtungsweise egal.
@Ownz:
Das müssen die reellen zahlen sein, denn die operationen < und > sind nicht auf komplexen Zahlen definiert,der Betrag aber schon,und das ist eine reelle Zahl.
@threadstarter:
wie Ownz schon sagte ein paar infos mehr wären super

__________________
Nur die Schwachen klammern sich an die Moral.

Kill my daemons and my angels will follow them.

ChiefWiggum

Ich sag nur dass entweder beide zutreffen oder keins

__________________
Be the source always with you.

sw33tlull4by

stimmt hast recht.
Denkfehler meinerseits, da war ich wohl etwas zu "unfaul".

__________________
Nur die Schwachen klammern sich an die Moral.

Kill my daemons and my angels will follow them.

Thunderb0lt

Steh ich dann jetzt auf dem Schlauch?

Wenn ich x*y <= z habe, kann ich durch x oder y dividieren. Dabei muss ich aber eine Fallunterscheidung machen. Wenn sich durch die Division das Vorzeichen nur einer Seite ändert, muss ich die Beziehung umdrehen. Ändern sich die Vorzeichen auf beiden Seiten, bleibt alles wie gehabt.

Man erhält also für

- x>0, y>0 und ein beliebiges z
- x<0 y<0 und ein beliebiges z
- x<0 y>0 und z>0
- x>0 y<0 und z>0

x <= z/y bzw. y<= z/x

- x<0 y>0 und z>0

x <= z/y bzw. y >= z/x

- x>0 y<0 und z<0

x >= z/y bzw. y <= z/x

Das zeigt aber doch, dass jeweils beide Bedingungen zutreffen müssen und zusätzlich die Grundannahmen im Bezug auf die Vorzeichen, oder irre ich?

lone.wolf

@Ownz:
D = R^+

Die Umformung ist schonmal ein guter Ansatz:

x * y <= z = x > z/y

Setzt man Werte ein, so sieht man schön, dass es passt.

Hat jemand noch andere Vorschläge?

MfG

sw33tlull4by

Hi Thunderbolt.
- x>0, y>0 und ein beliebiges z
-Nein für müsste dann gelten z>0 damit die oben genannten Bedingungen
müssten erfüllt werden
- x<0 y<0 und ein beliebiges z
-gleicher fall wie oben
- x<0 y>0 und z>0
- x>0 y<0 und z>0
-in beiden Fällen kann z <0 sein,und solange die oben genannte
Bedingungen erfüllt sind ist die vorraussetzung dann wahr.
-sollte z sogar echt kleiner 0 sein, so sieht man leicht ein, das
bei richtiger Umstellung das Vorzeichen wegdividiert wird.
Weswegen die Unterscheidung nach Vorzeichen hier nicht von
belangen ist

mfg

sw33t

__________________
Nur die Schwachen klammern sich an die Moral.

Kill my daemons and my angels will follow them.

CDW

Es gilt doch
log(xy)==log(x)+log(y)

Für negative Zahlen sollte eine Vorabgfrage und ggf. Normalisierung genügen (falls z negativ: x<0,y>0 oder y<0,x>0, falls z positiv: x,y<0 oder x,y>0). Technisch gesehen kann man darauf pfeifen - positiv oder negativ ist nur eine Sache der Interpretation der binären Darstellung *g*.

Btw:
Der "logarithmus" zur Basis 2 lässt sich trivial berechnen (bits zählen, Rest bilden - zuerst Anzahl der Bits (und damit die Potenzen) vergleichen und bei Bedarf noch die Reste). D.h man könnte auch ohne Logfunktion auskommen - alleine mit Potenzzerlegung und Addition.

Bsp zu der "Potenzzerlegung"
10*17<171
Zerlege in 2er Potenzen:

10=2^3 +2^1 (wie gesagt, einfaches Bitzählen/Bitabfragen zur Zerlegung genügt, man braucht keine Division oder Ähnliches)
17=2^4 +2^0
und
171=2^7 + 2^5+2^3+2^1+2^0

Ich schreibe mal weiter mit 2^, weil es die gewohnte Notation ist, allerdings sind die Basen gleich - daher reichen Exponenten schon für alle Operationen aus.

Die ganzen Multiplikationen werden bei Potenzen als Addition aufgefasst:
also "Kreuzmultiplikation" 17*10 = 2^4*2^3 + 2^4*2^1 + 2^1*2^0 + 2^3*2^0=
=2^(4+3)+2^(4+1)+2^(2+1)+2^(1+0) = 2^7+2^5+2^3+2^1
nun vergleiche die einzelnen Potenzstellen:
2^7+2^5+2^3+2^1 (+0*2^0)=170=10*17
||___||___||___| |
2^7+2^5+2^3+2^1+2^0 = 171
d.h 2^7=2^7 -> 7=7
2^5=2^5 -> 5=5 usw.

alle gleich, allerdings hat 171 noch 2^0 - das ist "mehr".
bei 170 wären
2^7+2^5+2^3+2^1 ==
2^7+2^5+2^3+2^1 (also gleich)
bei 10*17<169 hätte man
2^7+2^5+2^3+2^0=169
verglichen mit
2^7+2^5+2^3+2^1=170
=>falsch, da 2^1>1^0 -> 1>0

bei 192 =2^7+2^6 wäre man schon nach dem zweiten Vergelich fertig (da 2^6>2^5)

PS: es ist spät. kann sein, dass das Verfahren auch absoluter Humbug ist

__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.

sw33tlull4by

Das ist echt clever.
Kleiner Verbesserungsvorschlag:
erhöhe die Stelle an welcher die Potenz steht um 1,
dh:
2^0 wird zu 1
2^5 wird zu 6
so vermeidest du das bei 2^0 das additive neutrale Element einbezogen wird.
und da du die erhöhung auf beiden seiten machst,solltest du auch vergleichbare werte bekommen, Bsp:
(170)10 = (10101010)2
(171)10 = (10101011)2

wenn du das nun erhöhst steht dort,wenn man nur die exponenten betrachtet und addiert:
1+3+6+7 = 17 für 170, das gleiche gilt auch für 171(0+1+3+6+7),
da bei 2^0 die 0 addiert wird.

jetzt erhöhen wir mal das alles um 1:
2+4+7+8 = 21 für 170
1+2+4+7+8 = 22 für 171
voilá.

mfg

sw33t

__________________
Nur die Schwachen klammern sich an die Moral.

Kill my daemons and my angels will follow them.