BigNum2 v0.2.1.20080517

Flamefire · Verfasst: Mo 07.12.09 17:44

ggt(-a,b)=ggt(a,b)
und ggt(a,b)=ggt(b,a)

-->ggt>=0 (wobei ich auch bei der 0 noch was hatte...glaube ich)

und kgv(a,b)=|a*b|/ggt(a,b)

-->auch immer >=0

und ja bei 0^-y gibts ne exception ;-)

und (-x)^y macht er auch korrekt

wurzeln hab ich generell nur von x>=0 definiert (zwecks (-

^(1/3)=-2 wenn man so rechnen könnte, lt. wiki aber n.d.)

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Hier noch ein paar schnelle Bugs und Features aus dem Gammatest (bevor der neue Source rausgeht):

1. (-10)^5 = 100000 statt richtig -100000

2. log(x,1) sollte exception werfen, gibt stackoverflow

3. Standard: gcd(0,0)=0, gibt exception

4. Standard: lcm(0,0)=0, gibt accces violation

5. Wie ist xroot(a,-b) definiert? = 1/xroot(a,b) ? Dann wäre xroot(2,-3) = 1/xroot(2,3) = 1/1 = 1!
Also entweder nicht zulassen oder =1 aber nicht = 0

6. sqr sollte sqrt heißen, bzw wirklich als sqr(a) = a*a implementiert werden

Gruß Gammatester

Flamefire · Verfasst: Mo 07.12.09 23:17

Danke fürs Testen.
1) War ein Tippfehler...Hab die Zahl auf ungerade geprüft, nicht den Exponent ^^
2) Ok ist mir entfallen. Stand nicht auf Wiki ;-)

3) Lt. Wiki ist ggt(0,0) nicht definiert. Hier
Weil:
c=ggt(a,b)
dann gilt u.a.:
a mod c=0 und b mod c=0
wenn ggt(0,0)=0 dann wäre 0/0=0 Rest 0
Aber x/0 ist nicht definiert.
4) Hab dort einfach an BenBEs funktion weitergegeben. Berechne es jetzt selbst. Sollte funktionieren.
5) root(2,-3)=0.7937...-->Auf Integer ist das 0
Aber ok...eigendlich müsste man es ja aufrunden und dürfte immer auf was >=0,5 kommen
6) Ist geändert und eine sqr funktion mit eingebaut.

Einloggen, um Attachments anzusehen!

BenBE · Verfasst: Mo 07.12.09 23:58

@4. Was spricht gegen ggT(0,0)=1 ??? Aber gut, wenn Wiki n.d. sagt, passt's so.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Alle ernstzunehmenden mathematischen Quellen setzen gcd(0,a) = abs(a).
Leider ist Wiki (speziell das deutsche) oft genug keine solche ernstzunehmende Quelle.
ZB sagt es gcd(a,b) = gcd(b,a) und gcd(a,0)=|a|, weigert sich aber dann auch gcd(0,a)=|a| und gcd(0,0)=0 aufzulisten!
Das englische Wiki behauptet nicht, daß gcd(0,0) undefiniert sei, im Gegenteil: "It is useful to define gcd(0,0)=0"

Im übrigen rechnet auch bignum2 zB gcd(0,a)=abs(a), also sollte doch im Spezialfall a=0 dann auch gcd(0,0)=0 herauskommen.

Schönen Abend
Gammatester

BenBE · Verfasst: Di 08.12.09 00:58

gcd(0,0) kann man streiten, weil 1 ein Teiler von 0 ist (ich weiß, klingt doof, ist aber so) ... Aber ich kann mit der Definition der englischen Wiki (bzw. ernstzunehmender Literatur) durchaus leben. Zumal ich eh immer Source ohne Ausnahmeregeln bevorzuge (wenn's möglich ist).

Bei Mathe weiß man eh immer nicht, ob die unvollständig oder falsch ist

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Flamefire · Verfasst: Di 08.12.09 11:55

ähm...
du sagst

Zitat:

gcd(a,b) = gcd(b,a) und gcd(a,0)=|a|

aber gcd(0,a)=|a| sei nicht aufgeführt?

ist es aber:
gcd(0,a)=gcd(a,0)=|a|

und in der wiki steht eindeutig das gcd(0,0) nicht definiert ist.

das problem ist das gleiche wie log zur basis 1:

Eine natürliche Zahl a teilt b wenn es ein c gibt mit: b=a*c
demzufolge würde gelten, dass für jedes x gilt: x|0. weil 0=x*0

da die natürlichen Zahlen unendlich sind, gibt es kein größtes x.

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Flamefire hat folgendes geschrieben :

ähm...
du sagst

Zitat:

gcd(a,b) = gcd(b,a) und gcd(a,0)=|a|

aber gcd(0,a)=|a| sei nicht aufgeführt?

ist es aber:
gcd(0,a)=gcd(a,0)=|a|

Wer lesen kann ist klar im Vorteil: auf der deutschen Wikiseite steht nur gcd(a,0)=|a|! Leider weigert sich der Autor unter Berücksichtigung der Symmetrie gcd(0,a) abzuleiten und dann den Speziallfall a=0!

Zitat:

und in der wiki steht eindeutig das gcd(0,0) nicht definiert ist.

Das ist ja genau das Problem.

Zitat:

das problem ist das gleiche wie log zur basis 1:

Nein! Ist es ganz und gar nicht: log(x,a) = ln(x)/ln(a) bedeutet log(x,1) = ln(x)/ln(1) = ln(x)/0 und das ist nun wirklich durch keine Definition zu retten!

Zitat:

Eine natürliche Zahl a teilt b wenn es ein c gibt mit: b=a*c
demzufolge würde gelten, dass für jedes x gilt: x|0. weil 0=x*0

da die natürlichen Zahlen unendlich sind, gibt es kein größtes x.

Es gibt viele Möglichkeiten den gcd zu definieren. Hier die mM sinnvollste für ganze Zahhlen: "gcd(a,b) ist der eindeutige nicht-negative Generator der von a und b erzeugten Untergruppe von Z", und die von a=b=0 erzeugte Untergruppe ist nun mal {0}, und wer erzeugt das? Analog läuft die idealtheoretische Definition (siehe u.a. engl. Wiki).

Wenn Du nicht glaubst, daß gcd(0,0)=0 ist, schau nach bei Knuth oder bei Maple, Pari usw, oder tippe gcd(0,0) bei Wolfram Alpha ein.

Wie gesagt, Wiki ist oft nicht zuverlässig und sollte durch andere Quellen bestätigt werden.

Flamefire · Verfasst: Di 08.12.09 17:08

Gammatester hat folgendes geschrieben :

Wer lesen kann ist klar im Vorteil: auf der deutschen Wikiseite steht nur gcd(a,0)=|a|! Leider weigert sich der Autor unter Berücksichtigung der Symmetrie gcd(0,a) abzuleiten und dann den Speziallfall a=0!

ich wollte damit nur darauf aufmerksam machen, dass es aus den gegebenen regeln ableitbar ist.
sonst müsste z.b. auch gcd(-a,-b)=gcd(a,b) u.a. da stehen.
das zusätzlich aufzuschreiben ist wegen der Kommutativität nicht nötig.

Hab nochmal nachgeguckt: Mathematisch gesehen ist der ggt(0,0) nicht definiert, aufgrund meiner obigen Beweisführung
algebraisch (also z.b. nach deiner Defintion) sieht es anders aus. Steht so auch auf wiki.
Ehrlich gesagt weiß ich absolut nicht, wie man das Problem hier lösen soll.
Denn eigendlich rechnet man hier ja nur mathematisch, andrerseits gibt es auch algebraische Anwendungen.

Und nur als Anmerkung zum log:
log(1,1)=ln(1)/ln(1)=0/0=0?

Aber insgesammt, werde ich es jz im Code so notieren, dass gcd(0,0)=0 ist. Schient zumindest besser, als ein Fehler.
Lade den Code aber nicht neu hoch, da es nur eine Änderung ist. Solltest du noch merh finden, was nicht korrekt ist, fasse ich das dann zusammen, und lade das dann hoch.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

procedure TSJBigNumber.GCD(Num2: TSJBigNumber);
begin
  if(self.fSign=0) and (Num2.Sign=0) then begin
    //raise EMathError.Create('GCD of (0,0) is not defined');
    exit;//gcd(0,0):=0 (per algebraischer Definition)
  end;
  if(Num2.fSign<>0) then begin
    if(self.fSign=0) then self.Assign(Num2) //gcd(0,a)=|a|
    else self.fNumber:=BM_GCD(self.fNumber,Num2.Number);
  end;
  //else ggt(a,0)=|a|
  self.fSign:=1;
end;

Gammatester · Beiträge: 328 Erhaltene Danke: 101

1 Bug, 2 Featurerequests:

Bug: IsOne(-1)=true

Featurerequests:
- IsZero public machen wie IsOne
- Self.Assign(int64(1)) oder cardinal(1) in XRoot und Power damit's auch Delphi6 kompatibel ist. Eine nackte 1 bringt den Fehler "Ambiguous overloaded call to 'Assign'"

Gruß Gammatester

Flamefire · Verfasst: Di 08.12.09 18:33

Geht klar.
IsOne sollte sich um den Absolutbetrag kümmern. Ist umbenannt und entsprechend Funktionen hinzugefügt.
IsZero war nicht vorgesehn, da stattdessen Num.Sign=0 geprüft werden kann.
Aber das ist jetzt auch mit drin.
Die Assigns sind gefixt.

Einloggen, um Attachments anzusehen!

Horst_H · Verfasst: Di 08.12.09 23:41

Hallo,

was sind das alles für schreckliche Sachen ;-)

Warum wird nicht mit wenigstens Word statt byte gearbeitet.
Oder dies hier:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

Function BM_Add(Num1, Num2: TBigNumber): TBigNumber;
Var
    X: Integer;
    O: Integer;
Begin
    SetLength(Result, Max(Length(Num1), Length(Num2)) + 1);
    FillChar(Result[0], Length(Result), 0);

    O := 0;
    For X := 0 To High(Result) Do
    Begin
        If X < Length(Num1) Then
            O := O + Num1[X];
        If X < Length(Num2) Then
            O := O + Num2[X];

        Result[X] := O And $FF;
        O := O And $FF00 Shr 8;
    End;
    BM_Optimize(Result);
End;

Wäre es nicht sinniger, Result erst mit mit der längeren der beiden Zahlen zu füllen, um eine Stelle verlängern, dann eine Schleife mit Übertragsrechnung und Summation der kürzeren Zahl mit result und anschliessend nur noch solange es einen Übertrag gibt?

Gruß Horst

Flamefire · Verfasst: Di 08.12.09 23:54

Dass das ganze nicht optimal ist, hatte BenBE schon geschrieben, da seine Unit eher aus Spaß entstanden ist.
Man kann sie benutzen und mit der Wrapper Klasse nun auch für alle x€Z (einzige Beschränkung ist freier Speicher)

Wenn die jemand optimieren möchte, dann gerne ;-)

dagri · Hält's aus hier Beiträge: 4

Um das Niveau mal zu senken: Kann mir einer mal sagen, wie ich eine Integer Zahl in eine BigNum Zahl umwandele? Ich habe BigNum in der Schule leider noch nicht durchgenommen und daher keine Ahnung davon

BenBE · Verfasst: Sa 18.12.10 08:31

markieren

Delphi-Quelltext

1:	Function BMD_StrToBigNum(Str: String; HexInput: Boolean): TBigNumber;

Die Parameter sollten eigentlich eindeutig sein.

Ansonsten auf von Jaenicke die OOP-Erweiterung angucken; insbesondere TSJBigNum.Assign.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Bei einer solchen Unit mit so grossem Echo wären ein paar Duzend Unit-Tests sicher gut. Ich gehe mal davon aus, dass du die Unit irgendwie mit ein paar Beispielzahlen getestet hast, wieso nicht gleich richtige Unit-Tests und die gleich mitliefern?

Übrigens: Delphi unterstützt auch Operator Overloading. Operator Overloading braucht man fast nie, ausser in genau diesem Fall

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

var
  A, B: TBigInt;
begin
  A := '4000000000000000000001'; // Implicit string conversion
  B := 5; // Implicit integer conversion

  // Arbitrary math expression
  ShowMessage(IntToStr(A mod B + 2)); // 3

Die Stringkonvertierung sieht ein bisschen nach Magic aus, daher muss es über den Compilerswitch implicitstringconversion aktiviert werden.

// Edit: Da BigNum2 keine negativen Zahlen unterstützt, tut es das hier natürlich auch nicht.

Einloggen, um Attachments anzusehen!

BenBE · Verfasst: Mo 20.12.10 11:39

Die Unit ist zu Delphi-4-Zeiten entstanden, wo es das noch nicht gab. Bin auch nicht unbedingt erfreut, wenn die Nutzung neuer Features alten Code bricht, also bitte den Patch mit bedingte Compilierung vorschlagen.

Und die fehlenden Unit Tests: Hatte noch nicht einen Fall, wo sich dieser Aufwand gelohnt hätte.

Die Unit ist noch zu Gymnasialzeiten entstanden, daher auch kein Fokus auf Security oder Performance. Für Spielerin reicht das vielleicht, für richtige Anwendungen muss man sich den Kram eh für seinen Zweck anpassen.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Hab erst nach dem Post gemerkt, dass der Thread uralt ist

Alten Code bricht dieser Code nicht. Es handelt sich hier um eine zusätzliche Unit, die deine verwendet und einfach eine vereinfachte API bietet (Anwendung äquivalent zu "Integer").

Ich hatte schon angefangen Unit-Tests zu schreiben, als ich merkte, dass vieles failed. Erst dann ist mir klar geworden, dass negative Zahlen nicht unterstützt werden und ich dafür die neue Klasse von Jaenicke verwenden müsste. Das funktioniert aber schlecht mit meinem Record-Typ zusammen (da der Record-Typ nicht instanziert werden muss), daher hab ich es jetzt einfach sein lassen :\

Flamefire · Verfasst: Mo 20.12.10 14:38

unit-tests hätten hiefür schon mal was. weil sowas brauch man doch häufiger und das hier ist die einzige wirklich gute unit, die ich kenne/gefunden habe (damals als ich das brauchte

)
Ich hatte dafür auch die Erweiterung in die Klasse geschrieben, das negative Zahlen unterstützt werden. Ist aber eben nur in der Klasse enthalten. Operator-Überladen geht nur mit records? Oder doch auch mit Klassen? Wäre ja schon ziemlich cool, wenn man vl die Klasse als Record umschreiben und so wie normale Integer verwenden kann. Hatte ich ja damals das Problem:
Integer --> wurden zu klein, int64 auch zu klein, float typen wurden ungenau. also viel code umschreiben um die klasse zu verwenden, obwohls auch nur ne zahlendarstellung ist...
also sinnvoll wäre es.

vl mal ein statement von BenBE dazu (ist ja hauptsächlich seins)

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Ich wär bereit, das umzuschreiben, aber nur, wenn die Lizenz dahingehend geändert wird, dass man die Library auch für kommerzielle Zwecke einsetzen darf (auch ohne separate Bewilligung), vorzugsweise eine bekannte Open-Source Lizenz. Meinetwegen mit entsprechendem Verweis in den Credits oder Doku. Ansonsten macht's für mich nicht viel Sinn, hier Arbeit reinzustecken.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme