Stringrechner für grosse Zahlen

Übersicht

BlitzBasic

Codearchiv

	Noobody Betreff: Stringrechner für grosse Zahlen	Sa, Feb 07, 2009 22:20 Antworten mit Zitat
Wie man ja bekanntlich weiss, können Zahlen am Computer normalerweise eine bestimmte Wertgrenze nicht überschreiten, weil sie nur eine begrenzte Anzahl Bits zur Verfügung haben. Bei einem gebräuchlichen Integer liegt die Grenze bei 2^31 - unter normalen Umständen mehr als ausreichend. Jedoch kann es gut mal sein, dass man irgendwann an diese Grenze stösst - sei es bei einer Wahrscheinlichkeitsberechnung oder beim Ausrechnen der Fakultät. Daher habe ich diese kleine Funktionssammlung geschrieben, die statt mit Zahlen mit Strings rechnet. Nicht zu verwechseln mit einem Termberechner, der mathematische Terme zerlegt und ausrechnet, nimmt der Stringrechner Zahlen in Form von Zeichenketten entgegen (z.B. "4628768762") und verrechnet diese miteinander - wie er das macht, kommt natürlich auf die Funktion an. Diese Zahlen können beinahe unbegrenzt gross sein; die einzige Grenze ist hier natürlich der Arbeitsspeicher, aber den sollte man nicht so schnell voll haben Im Moment beherrscht er die vier Grundoperation Addition, Subtraktion, Multiplikation und Division. Vorzeichen sind kein Problem, jedoch kann er im Moment nur Ganzzahlen (wenn ich mich mal dazu aufraffe, erweiter ich ihn irgendwann auf Dezimalzahlen). Ausserdem sind die Vergleichsoperatoren > und < eingebaut, ebenso wie Abs und Sgn. Der Code mit einem kleinen Beispiel: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Graphics 800, 600, 0, 2 SetBuffer BackBuffer() Global N1$ = "11111111111111111111111111149289648276119826647382984797564786538873948765383599567777777587987297" Global N2$ = "-11111111111111111111111111111111113234345768876856427868746567489448537426794666644469538653653321" Print String_Divide$( N1$, N2$ ) Print String_Multiply$( N1$, N2$ ) Print String_Add$( N1$, N2$ ) Print String_Substract( N1$, N2$ ) Print String_Greater( N1$, N2$ ) Print String_Smaller( N1$, M2$ ) Print String_Sgn( N2$ ) Print String_Abs( N2$ ) WaitKey() End ;-------------------------------------------Ende Beispiel Const CHARLIMIT = 1024 ;Den Wert hier ändern für Zahlen mit mehr als 1024 Zeichen Function String_Add$( S1$, S2$ ) Local Char[ CHARLIMIT + 1 ] Sgn1 = String_Sgn( S1$ ) Sgn2 = String_Sgn( S2$ ) If Sgn1 = 1 And Sgn2 = -1 Then Return String_Substract( S1$, String_Abs$( S2$ ) ) If Sgn1 = -1 And Sgn2 = 1 Then Temp$ = String_Substract( String_Abs( S1$ ), S2$ ) If String_Sgn( Temp$ ) = -1 Then Return String_Abs( Temp$ ) Else Return "-" + Temp$ EndIf If Sgn1 = -1 And Sgn2 = -1 Then Return "-" + String_Add( String_Abs( S1$ ), String_Abs( S2$ ) ) If Len( S2$ ) > Len( S1$ ) Then Temp$ = S1$ S1$ = S2$ S2$ = Temp$ EndIf For i = 1 To Len( S1$ ) Char[ CHARLIMIT - Len( S1$ ) + i ] = Asc( Mid( S1$, i, 1 ) ) - 48 Next For i = Len( S2$ ) To 1 Step -1 Char[ CHARLIMIT - i + 1 ] = Char[ CHARLIMIT - i + 1 ] + ( Asc( Mid( S2$, Len( S2$ ) - i + 1, 1 ) ) - 48 ) Next Local Border = 0 For i = CHARLIMIT To 0 Step -1 If Char[ i ] <> 0 Then Border = i If Char[ i ] > 9 Then Char[ i - 1 ] = Char[ i - 1 ] + Floor( Char[ i ]/10. ) Char[ i ] = Char[ i ] Mod 10 EndIf Next Local Outstring$ = "" For i = CHARLIMIT To Border Step -1 Outstring$ = Chr( Char[ i ] + 48 ) + Outstring$ Next Return Outstring$ End Function Function String_Substract$( S1$, S2$ ) Local Char[ CHARLIMIT + 1 ] If S1$ = S2$ Then Return "0" Sgn1 = String_Sgn( S1$ ) Sgn2 = String_Sgn( S2$ ) If Sgn1 = 1 And Sgn2 = -1 Then Return String_Add( S1$, String_Abs$( S2$ ) ) If Sgn1 = -1 And Sgn2 = 1 Then Return "-" + String_Add( String_Abs( S1$ ), S2$ ) If Sgn1 = -1 And Sgn2 = -1 Then Temp$ = String_Substract( String_Abs( S1$ ), String_Abs( S2$ ) ) If String_Sgn( Temp$ ) = -1 Then Return String_Abs( Temp$ ) Else Return "-" + Temp$ EndIf For i = 1 To Len( S1$ ) Char[ CHARLIMIT - Len( S1$ ) + i ] = Asc( Mid( S1$, i, 1 ) ) - 48 Next For i = Len( S2$ ) To 1 Step -1 Char[ CHARLIMIT - i + 1 ] = Char[ CHARLIMIT - i + 1 ] - ( Asc( Mid( S2$, Len( S2$ ) - i + 1, 1 ) ) - 48 ) Next Local Border = 0 For i = CHARLIMIT To CHARLIMIT - Len( S1$ ) - Len( S2$ ) Step -1 If Char[ i ] < 0 Then Char[ i - 1 ] = Char[ i - 1 ] - Abs( Floor( Char[ i ]/10. ) ) Char[ i ] = ( 10 - ( Abs( Char[ i ] ) Mod 10 ) ) Mod 10 EndIf If Char[ i ] <> 0 Then Border = i Next Local Outstring$ = "" For i = CHARLIMIT To Border Step -1 Outstring$ = Chr( Char[ i ] + 48 ) + Outstring$ Next Return Outstring$ End Function Function String_Multiply$( S1$, S2$ ) Local Outstring$ = "0", Sign$ Sgn1 = String_Sgn( S1$ ) Sgn2 = String_Sgn( S2$ ) If Sgn1 = -1 Or Sgn2 = -1 Then If Sgn1 <> Sgn2 Then Sign$ = "-" S1$ = String_Abs( S1$ ) S2$ = String_Abs( S2$ ) EndIf If Len( S1$ ) < Len( S2$ ) Then Temp$ = S1$ S1$ = S2$ S2$ = Temp$ EndIf For i = Len( S2$ ) To 1 Step -1 Local PartString$ = "", Factor = Asc( Mid( S2$, i, 1 ) ) - 48 For t = 1 To Len( S1$ ) PartString$ = PartString$ + Chr( ( Asc( Mid( S1$, t, 1 ) ) - 48 )*Factor + 48 ) Next PartString$ = PartString$ + String( "0", Len( S2$ ) - i ) Outstring$ = String_Add( Outstring$, PartString$ ) Next Return Sign$ + Outstring$ End Function Function String_Divide$( S1$, S2$ ) Local PartString$, OutString$, Sign$ Sgn1 = String_Sgn( S1$ ) Sgn2 = String_Sgn( S2$ ) If Sgn1 = -1 Or Sgn2 = -1 Then If Sgn1 <> Sgn2 Then Sign$ = "-" S1$ = String_Abs( S1$ ) S2$ = String_Abs( S2$ ) EndIf PartString$ = Left( S1$, Len( S2$ ) ) S1$ = Right( S1$, Len( S1$ ) - Len( S2$ ) ) While Not String_Greater( S2$, PartString$ + S1$ ) Local Counter = 0 While Not String_Greater( S2$, PartString$ ) PartString$ = String_Substract( PartString$, S2$ ) Counter = Counter + 1 Wend If Counter > 0 Or OutString$ <> "" Then OutString$ = OutString$ + Counter If PartString$ = "0" Then PartString$ = "" PartString$ = PartString$ + Left( S1$, 1 ) If Len( S1$ ) > 1 Then S1$ = Right( S1$, Len( S1$ ) - 1 ) Else S1$ = "" Wend Return Sign$ + Outstring$ End Function Function String_Greater( S1$, S2$ ) Sgn1 = String_Sgn( S1$ ) Sgn2 = String_Sgn( S2$ ) If Sgn1 = -1 And Sgn2 = 1 Then Return False If Sgn1 = 1 And Sgn2 = -1 Then Return True If Sgn1 = -1 And Sgn2 = -1 Then Return String_Smaller( String_Abs( S1$ ), String_Abs( S2$ ) ) If Len( S1$ ) > Len( S2$ ) Then Return True If Len( S2$ ) > Len( S1$ ) Then Return False For i = 1 To Len( S1$ ) If Asc( Mid( S1$, i, 1 ) ) < Asc( Mid( S2$, i, 1 ) ) Then Return False If Asc( Mid( S1$, i, 1 ) ) > Asc( Mid( S2$, i, 1 ) ) Then Return True Next Return False End Function Function String_Smaller( S1$, S2$ ) Sgn1 = String_Sgn( S1$ ) Sgn2 = String_Sgn( S2$ ) If Sgn1 = -1 And Sgn2 = 1 Then Return True If Sgn1 = 1 And Sgn2 = -1 Then Return False If Sgn1 = -1 And Sgn2 = -1 Then Return String_Greater( String_Abs( S1$ ), String_Abs( S2$ ) ) If Len( S1$ ) < Len( S2$ ) Then Return True If Len( S2$ ) < Len( S1$ ) Then Return False For i = 1 To Len( S1$ ) If Asc( Mid( S1$, i, 1 ) ) > Asc( Mid( S2$, i, 1 ) ) Then Return False If Asc( Mid( S1$, i, 1 ) ) < Asc( Mid( S2$, i, 1 ) ) Then Return True Next Return False End Function Function String_Sgn( SourceString$ ) Select Left( SourceString$, 1 ) Case "-" Return -1 Case "0" Return 0 Default Return 1 End Select End Function Function String_Abs$( SourceString$ ) If Left( SourceString$, 1 ) = "-" Then Return Mid( SourceString$, 2 ) Else Return SourceString$ End Function Function String_Negate$( SourceString$ ) If String_Sgn( SourceString$ ) = -1 Then Return String_Abs( SourceString$ ) Return "-" + SourceString$ End Function Bei Bugs und Anregungen bitte melden

Noobody

Betreff: Stringrechner für grosse Zahlen

Sa, Feb 07, 2009 22:20
Antworten mit Zitat

Wie man ja bekanntlich weiss, können Zahlen am Computer normalerweise eine bestimmte Wertgrenze nicht überschreiten, weil sie nur eine begrenzte Anzahl Bits zur Verfügung haben.
Bei einem gebräuchlichen Integer liegt die Grenze bei 2^31 - unter normalen Umständen mehr als ausreichend.
Jedoch kann es gut mal sein, dass man irgendwann an diese Grenze stösst - sei es bei einer Wahrscheinlichkeitsberechnung oder beim Ausrechnen der Fakultät.

Daher habe ich diese kleine Funktionssammlung geschrieben, die statt mit Zahlen mit Strings rechnet.
Nicht zu verwechseln mit einem Termberechner, der mathematische Terme zerlegt und ausrechnet, nimmt der Stringrechner Zahlen in Form von Zeichenketten entgegen (z.B. "4628768762") und verrechnet diese miteinander - wie er das macht, kommt natürlich auf die Funktion an. Diese Zahlen können beinahe unbegrenzt gross sein; die einzige Grenze ist hier natürlich der Arbeitsspeicher, aber den sollte man nicht so schnell voll haben Razz

Im Moment beherrscht er die vier Grundoperation Addition, Subtraktion, Multiplikation und Division. Vorzeichen sind kein Problem, jedoch kann er im Moment nur Ganzzahlen (wenn ich mich mal dazu aufraffe, erweiter ich ihn irgendwann auf Dezimalzahlen).
Ausserdem sind die Vergleichsoperatoren > und < eingebaut, ebenso wie Abs und Sgn.

Der Code mit einem kleinen Beispiel: BlitzBasic: [AUSKLAPPEN]

Graphics 800, 600, 0, 2
SetBuffer BackBuffer()

Global N1$ = "11111111111111111111111111149289648276119826647382984797564786538873948765383599567777777587987297"
Global N2$ = "-11111111111111111111111111111111113234345768876856427868746567489448537426794666644469538653653321"

Print String_Divide$( N1$, N2$ )
Print String_Multiply$( N1$, N2$ )
Print String_Add$( N1$, N2$ )
Print String_Substract( N1$, N2$ )
Print String_Greater( N1$, N2$ )
Print String_Smaller( N1$, M2$ )
Print String_Sgn( N2$ )
Print String_Abs( N2$ )
WaitKey()
End


;-------------------------------------------Ende Beispiel

Const CHARLIMIT = 1024 ;Den Wert hier ändern für Zahlen mit mehr als 1024 Zeichen

Function String_Add$( S1$, S2$ )
	Local Char[ CHARLIMIT + 1 ]
	
	Sgn1 = String_Sgn( S1$ )
	Sgn2 = String_Sgn( S2$ )
	
	If Sgn1 = 1 And Sgn2 = -1 Then Return String_Substract( S1$, String_Abs$( S2$ ) )
	If Sgn1 = -1 And Sgn2 = 1 Then
		Temp$ = String_Substract( String_Abs( S1$ ), S2$ )
		If String_Sgn( Temp$ ) = -1 Then Return String_Abs( Temp$ ) Else Return "-" + Temp$
	EndIf
	If Sgn1 = -1 And Sgn2 = -1 Then Return "-" + String_Add( String_Abs( S1$ ), String_Abs( S2$ ) )
	
	If Len( S2$ ) > Len( S1$ ) Then
		Temp$ = S1$
		S1$ = S2$
		S2$ = Temp$
	EndIf
	
	For i = 1 To Len( S1$ )
		Char[ CHARLIMIT - Len( S1$ ) + i ] = Asc( Mid( S1$, i, 1 ) ) - 48
	Next
	
	For i = Len( S2$ ) To 1 Step -1
		Char[ CHARLIMIT - i + 1 ] = Char[ CHARLIMIT - i + 1 ] + ( Asc( Mid( S2$, Len( S2$ ) - i + 1, 1 ) ) - 48 )
	Next
	
	Local Border = 0
	For i = CHARLIMIT To 0 Step -1
		If Char[ i ] <> 0 Then Border = i
		
		If Char[ i ] > 9 Then
			Char[ i - 1 ] = Char[ i - 1 ] + Floor( Char[ i ]/10. )
			Char[ i ] = Char[ i ] Mod 10
		EndIf
	Next
	
	Local Outstring$ = ""
	For i = CHARLIMIT To Border Step -1
		Outstring$ = Chr( Char[ i ] + 48 ) + Outstring$
	Next
	
	Return Outstring$
End Function

Function String_Substract$( S1$, S2$ )
	Local Char[ CHARLIMIT + 1 ]
	
	If S1$ = S2$ Then Return "0"
	
	Sgn1 = String_Sgn( S1$ )
	Sgn2 = String_Sgn( S2$ )
	
	If Sgn1 = 1 And Sgn2 = -1 Then Return String_Add( S1$, String_Abs$( S2$ ) )
	If Sgn1 = -1 And Sgn2 = 1 Then Return "-" + String_Add( String_Abs( S1$ ), S2$ )
	If Sgn1 = -1 And Sgn2 = -1 Then
		Temp$ = String_Substract( String_Abs( S1$ ), String_Abs( S2$ ) )
		If String_Sgn( Temp$ ) = -1 Then Return String_Abs( Temp$ ) Else Return "-" + Temp$
	EndIf
		
	For i = 1 To Len( S1$ )
		Char[ CHARLIMIT - Len( S1$ ) + i ] = Asc( Mid( S1$, i, 1 ) ) - 48
	Next
	
	For i = Len( S2$ ) To 1 Step -1
		Char[ CHARLIMIT - i + 1 ] = Char[ CHARLIMIT - i + 1 ] - ( Asc( Mid( S2$, Len( S2$ ) - i + 1, 1 ) ) - 48 )
	Next
	
	Local Border = 0
	For i = CHARLIMIT To CHARLIMIT - Len( S1$ ) - Len( S2$ ) Step -1
		If Char[ i ] < 0 Then
			Char[ i - 1 ] = Char[ i - 1 ] - Abs( Floor( Char[ i ]/10. ) )
			Char[ i ] = ( 10 - ( Abs( Char[ i ] ) Mod 10 ) ) Mod 10
		EndIf
		
		If Char[ i ] <> 0 Then Border = i
	Next
	
	Local Outstring$ = ""
	For i = CHARLIMIT To Border Step -1
		Outstring$ = Chr( Char[ i ] + 48 ) + Outstring$
	Next
	
	Return Outstring$
End Function

Function String_Multiply$( S1$, S2$ )
	Local Outstring$ = "0", Sign$
	
	Sgn1 = String_Sgn( S1$ )
	Sgn2 = String_Sgn( S2$ )
	
	If Sgn1 = -1 Or Sgn2 = -1 Then
		If Sgn1 <> Sgn2 Then Sign$ = "-"
		
		S1$ = String_Abs( S1$ )
		S2$ = String_Abs( S2$ )
	EndIf
	
	If Len( S1$ ) < Len( S2$ ) Then
		Temp$ = S1$
		S1$ = S2$
		S2$ = Temp$
	EndIf
	
	For i = Len( S2$ ) To 1 Step -1
		Local PartString$ = "", Factor = Asc( Mid( S2$, i, 1 ) ) - 48
		
		For t = 1 To Len( S1$ )
			PartString$ = PartString$ + Chr( ( Asc( Mid( S1$, t, 1 ) ) - 48 )*Factor + 48 )
		Next
		
		PartString$ = PartString$ + String( "0", Len( S2$ ) - i )
		
		Outstring$ = String_Add( Outstring$, PartString$ )
	Next
	
	Return Sign$ + Outstring$
End Function

Function String_Divide$( S1$, S2$ )
	Local PartString$, OutString$, Sign$
	
	Sgn1 = String_Sgn( S1$ )
	Sgn2 = String_Sgn( S2$ )
	
	If Sgn1 = -1 Or Sgn2 = -1 Then
		If Sgn1 <> Sgn2 Then Sign$ = "-"
		
		S1$ = String_Abs( S1$ )
		S2$ = String_Abs( S2$ )
	EndIf
	
	PartString$ = Left( S1$, Len( S2$ ) )
	S1$ = Right( S1$, Len( S1$ ) - Len( S2$ ) )
	
	While Not String_Greater( S2$, PartString$ + S1$ )
		Local Counter = 0
		While Not String_Greater( S2$, PartString$ )
			PartString$ = String_Substract( PartString$, S2$ )
			Counter = Counter + 1
		Wend
		
		If Counter > 0 Or OutString$ <> "" Then OutString$ = OutString$ + Counter
		
		If PartString$ = "0" Then PartString$ = ""
		
		PartString$ = PartString$ + Left( S1$, 1 )
		If Len( S1$ ) > 1 Then S1$ = Right( S1$, Len( S1$ ) - 1 ) Else S1$ = ""
	Wend
	
	Return Sign$ + Outstring$
End Function

Function String_Greater( S1$, S2$ )
	Sgn1 = String_Sgn( S1$ )
	Sgn2 = String_Sgn( S2$ )
	
	If Sgn1 = -1 And Sgn2 = 1 Then Return False
	If Sgn1 = 1 And Sgn2 = -1 Then Return True
	If Sgn1 = -1 And Sgn2 = -1 Then Return String_Smaller( String_Abs( S1$ ), String_Abs( S2$ ) )
	
	If Len( S1$ ) > Len( S2$ ) Then Return True
	If Len( S2$ ) > Len( S1$ ) Then Return False
	
	For i = 1 To Len( S1$ )
		If Asc( Mid( S1$, i, 1 ) ) < Asc( Mid( S2$, i, 1 ) ) Then Return False
		If Asc( Mid( S1$, i, 1 ) ) > Asc( Mid( S2$, i, 1 ) ) Then Return True
	Next
	
	Return False
End Function

Function String_Smaller( S1$, S2$ )
	Sgn1 = String_Sgn( S1$ )
	Sgn2 = String_Sgn( S2$ )
	
	If Sgn1 = -1 And Sgn2 = 1 Then Return True
	If Sgn1 = 1 And Sgn2 = -1 Then Return False
	If Sgn1 = -1 And Sgn2 = -1 Then Return String_Greater( String_Abs( S1$ ), String_Abs( S2$ ) )
	
	If Len( S1$ ) < Len( S2$ ) Then Return True
	If Len( S2$ ) < Len( S1$ ) Then Return False
	
	For i = 1 To Len( S1$ )
		If Asc( Mid( S1$, i, 1 ) ) > Asc( Mid( S2$, i, 1 ) ) Then Return False
		If Asc( Mid( S1$, i, 1 ) ) < Asc( Mid( S2$, i, 1 ) ) Then Return True
	Next
	
	Return False
End Function

Function String_Sgn( SourceString$ )
	Select Left( SourceString$, 1 )
		Case "-"
			Return -1
		Case "0"
			Return 0
		Default
			Return 1
	End Select
End Function

Function String_Abs$( SourceString$ )
	If Left( SourceString$, 1 ) = "-" Then Return Mid( SourceString$, 2 ) Else Return SourceString$
End Function

Function String_Negate$( SourceString$ )
	If String_Sgn( SourceString$ ) = -1 Then Return String_Abs( SourceString$ )
	Return "-" + SourceString$
End Function

Bei Bugs und Anregungen bitte melden Razz

Zuletzt bearbeitet von Noobody am So, Apr 19, 2009 19:16, insgesamt 3-mal bearbeitet

	Starwar	Sa, Feb 07, 2009 22:56 Antworten mit Zitat
Super. Jetzt brauche ich nur noch einen Weg um die 64Bit Integer der API-Funktionen in den String zu bekommen. Dann werd ich endlich eine Anzeige für den freien Festplattenpeicher haben und FilseSize für große Dateien. Danke.

Starwar

Sa, Feb 07, 2009 22:56
Antworten mit Zitat

Super. Jetzt brauche ich nur noch einen Weg um die 64Bit Integer der API-Funktionen in den String zu bekommen. Dann werd ich endlich eine Anzeige für den freien Festplattenpeicher haben und FilseSize für große Dateien. Danke.

	Silver_Knee	So, Feb 08, 2009 8:38 Antworten mit Zitat
weiß net ob das geht aber übergib mal ne 8 Byte bank mit ner userlib ...(Int64*,...) und dann haste vllt 2 Integer in der Bank... und der eine kannste via dieser stringfunktionen mal 2 ^ 32 nehmen (shl wäre jetzt cool) und dann die beiden zahlen addieren.

Silver_Knee

So, Feb 08, 2009 8:38
Antworten mit Zitat

weiß net ob das geht aber übergib mal ne 8 Byte bank mit ner userlib ...(Int64*,...) und dann haste vllt 2 Integer in der Bank... und der eine kannste via dieser stringfunktionen mal 2 ^ 32 nehmen (shl wäre jetzt cool) und dann die beiden zahlen addieren.

	Coffee	So, Feb 08, 2009 13:05 Antworten mit Zitat
Hi! Sieht ja schonmal ganz gut aus und geht soweit sogar recht schnell, aber versuch's mal mit: Code: [AUSKLAPPEN] [EINKLAPPEN] Global N1$ = "11111111111111111111111111149289648276119826647382984797564786538873948765383599567777777587987297" Global N2$ = "-11111111111111111111111111111111113234345768876856427868746567489448537426794666644469538653653321" Da gibts noch kleine Schönheitsfehler, die es zu beseitigen gilt lg
Mjam

Coffee

So, Feb 08, 2009 13:05
Antworten mit Zitat

Hi!

Sieht ja schonmal ganz gut aus und geht soweit sogar recht schnell, aber versuch's mal mit:
Code: [AUSKLAPPEN]

Global N1$ = "11111111111111111111111111149289648276119826647382984797564786538873948765383599567777777587987297"
Global N2$ = "-11111111111111111111111111111111113234345768876856427868746567489448537426794666644469538653653321"

Da gibts noch kleine Schönheitsfehler, die es zu beseitigen gilt Smile

*Mjam*

	Noobody	So, Feb 08, 2009 13:57 Antworten mit Zitat
Ja, der Fehler steckte in einer veralteten Zeile in String_Substract und den Funktionen String_Greater und String_Smaller, die noch nicht auf Vorzeichen reagiert haben. Vielen Dank für den Hinweis! Sollte jetzt fehlerfrei funktionieren.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Noobody

So, Feb 08, 2009 13:57
Antworten mit Zitat

Ja, der Fehler steckte in einer veralteten Zeile in String_Substract und den Funktionen String_Greater und String_Smaller, die noch nicht auf Vorzeichen reagiert haben.
Vielen Dank für den Hinweis!
Sollte jetzt fehlerfrei funktionieren.

Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

	Coffee	So, Feb 08, 2009 16:07 Antworten mit Zitat
Wieso gibt die Division bei den Zahlen im Beispiel eigentlich -1 aus?
Mjam

Coffee

So, Feb 08, 2009 16:07
Antworten mit Zitat

Wieso gibt die Division bei den Zahlen im Beispiel eigentlich -1 aus?

*Mjam*

	Noobody	So, Feb 08, 2009 16:31 Antworten mit Zitat
Weil es eine Ganzzahl - Division ist (Dezimalzahlen sind ja (noch) nicht eingebaut). Wenn man es in einen genauen Rechner eingibt, erhält man etwas mit -1.0000418295628....., das wird natürlich abgerundet und die Funktion liefert -1 zurück.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Noobody

So, Feb 08, 2009 16:31
Antworten mit Zitat

Weil es eine Ganzzahl - Division ist (Dezimalzahlen sind ja (noch) nicht eingebaut).
Wenn man es in einen genauen Rechner eingibt, erhält man etwas mit -1.0000418295628....., das wird natürlich abgerundet und die Funktion liefert -1 zurück.

Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

	Triton	So, Apr 05, 2009 1:14 Antworten mit Zitat
Ich beschäftige mich ja auch schon geraume Zeit mit dem Thema. Und daher habe ich deine Bibliothek einigen Tests unterzogen. Dabei musste sie gegen Rallimens und gegen meine eigene (derzeit noch nicht veröffentlichte) Bibliothek antreten. Wie erklären sich einige Werte? Addition: da kann man einiges Optimieren: Rallimens ist etwa 50% schneller, meins etwa 100% schneller als deins. Zudem funktioniert deins nicht mehr bei größeren Zahlen. Multiplikation: Rallimen legt vor. Und du bist auch nicht schlecht dabei, wenn man von den Fehlern absieht, die bei dir wieder bei größeren Zahlen auftreten. Warum meins so unglaublich langsam bei größeren Zahlen wird, weiß ich nicht. Muss ich noch dran arbeiten.. Division: Da sehen meine Zeiten ganz schön kacke aus, gegen eure, wa? Allerdings ist deins Fehlerhaft. Rechne z.B. mal 1234567980/987! Somit sind auch deine Zeiten mit Vorsicht zu genießen. Rallimens ist da schon besser. Aber auch da konnte ich ein Beispiel finden, für Zahlen die falsch berechnet werden. Leider habe ich mir das nirgends notiert. Vielleicht finde ich es nochmal. Meins ist zwar ganz schön lahm verglichen mit eurem, aber dafür absolut fehlerfrei. Potenzen: da ist bei dir irgendwie total der Wurm drin. Keine einzige Potenz mit einer anderen Basis als 2 funktioniert. Ich habe eine relativ einfache ahochb-Funktion dafür genutzt, an der kanns kaum liegen. Ansonsten liege ich da vorne, weil ich viele Potenzen auf Addition zurückführe, was ja bei mir schneller ist. Viel Spaß beim verbessern und optimieren Vielleicht helfen dir diese Werte ja.
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

So, Apr 05, 2009 1:14
Antworten mit Zitat

Ich beschäftige mich ja auch schon geraume Zeit mit dem Thema. Und daher habe ich
deine Bibliothek einigen Tests unterzogen. Dabei musste
sie gegen Rallimens und gegen meine eigene (derzeit noch nicht veröffentlichte)
Bibliothek antreten.

user posted image

Wie erklären sich einige Werte?
Addition: da kann man einiges Optimieren: Rallimens ist etwa 50% schneller, meins
etwa 100% schneller als deins. Zudem funktioniert deins nicht mehr bei größeren Zahlen.

Multiplikation: Rallimen legt vor. Und du bist auch nicht schlecht dabei, wenn man von
den Fehlern absieht, die bei dir wieder bei größeren Zahlen auftreten. Warum meins so
unglaublich langsam bei größeren Zahlen wird, weiß ich nicht. Muss ich noch dran arbeiten..

Division: Da sehen meine Zeiten ganz schön kacke aus, gegen eure, wa? Allerdings ist
deins Fehlerhaft. Rechne z.B. mal 1234567980/987! Somit sind auch deine Zeiten mit
Vorsicht zu genießen.
Rallimens ist da schon besser. Aber auch da konnte ich ein Beispiel finden, für Zahlen
die falsch berechnet werden. Leider habe ich mir das nirgends notiert. Vielleicht finde
ich es nochmal.
Meins ist zwar ganz schön lahm verglichen mit eurem, aber dafür absolut fehlerfrei.

Potenzen: da ist bei dir irgendwie total der Wurm drin. Keine einzige Potenz mit einer
anderen Basis als 2 funktioniert. Ich habe eine relativ einfache ahochb-Funktion dafür
genutzt, an der kanns kaum liegen. Ansonsten liege ich da vorne, weil ich viele Potenzen
auf Addition zurückführe, was ja bei mir schneller ist.

Viel Spaß beim verbessern und optimieren Wink

Vielleicht helfen dir diese Werte ja.

Coding: silizium-net.de | Portfolio: Triton.ch.vu

	Noobody	So, Apr 05, 2009 1:40 Antworten mit Zitat
Kann es sein, dass du mit Fehler eine Fehlermeldung meinst? Dann würde ich dir raten, den Code nochmals anzuschauen, besonders die erste Zeile der eigentlichen Lib: Code: [AUSKLAPPEN] [EINKLAPPEN] Const CHARLIMIT = 1024 ;Den Wert hier ändern für Zahlen mit mehr als 1024 Zeichen Wenn du nämlich mit sehr sehr grossen Zahlen rechnest, sprengt das natürlich das Blitzarray, daher habe ich diesen Wert eingebaut, um die Grösse des Arrays zu bestimmen. Dass die Division fehlerhaft ist, war mir eigentlich klar, seit neuem weiss ich sogar, woran es liegt, wird daher bald gefixt
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Noobody

So, Apr 05, 2009 1:40
Antworten mit Zitat

Kann es sein, dass du mit Fehler eine Fehlermeldung meinst? Dann würde ich dir raten, den Code nochmals anzuschauen, besonders die erste Zeile der eigentlichen Lib: Code: [AUSKLAPPEN]

Const CHARLIMIT = 1024 ;Den Wert hier ändern für Zahlen mit mehr als 1024 Zeichen

Wenn du nämlich mit sehr sehr grossen Zahlen rechnest, sprengt das natürlich das Blitzarray, daher habe ich diesen Wert eingebaut, um die Grösse des Arrays zu bestimmen.

Dass die Division fehlerhaft ist, war mir eigentlich klar, seit neuem weiss ich sogar, woran es liegt, wird daher bald gefixt Wink

Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

	Triton	So, Apr 05, 2009 2:03 Antworten mit Zitat
Ach du hast es begrenzt - das erklärt dann einige der Fehler. Nicht aber bei den Potenzen. Dafür habe ich mal meine Funktionen bischen umgeschrieben, damit sie bei dir passen: Code: [AUSKLAPPEN] [EINKLAPPEN] Graphics 1000,600,32,2 Include "noobody-stringr.bb" font = LoadFont("lucida console",12) SetFont font SeedRnd MilliSecs() t1=MilliSecs() p$=ahochb("6","216") Print p Text 10,280,"Dauer: "+Str(MilliSecs()-t1)+" ms" WaitKey End Function vergleich(a$,b$) ; a;b element Z ; Rückgabewerte: ; 1 - a > b, b < a ; 2 - b > a; a < b ; 0 - a = b ; betrag = 1 -> behandelt a$ und b$ als natürliche Zahlen If betrag=1 Then If Left$(a$,1)="-" Then a$ = Mid$(a$,2) If Left$(b$,1)="-" Then b$ = Mid$(b$,2) End If If a$ = b$ Then Return 0 If Left$(a$,1) = "-" And Left$(b$,1) <> "-" Then Return 2 If Left$(b$,1) = "-" And Left$(a$,1) <> "-" Then Return 1 l1=Len(a$) l2=Len(b$) If l1 > l2 Then Return 1 If l1 < l2 Then Return 2 If l1 < 10 Then If l2 < 10 Then If Int(a$) > Int(b$) Then Return 1 If Int(a$) < Int(b$) Then Return 2 End If End If While Int(za$) = Int(zb$) pos=pos+1 za$=Mid(a$,pos,1) zb$=Mid(b$,pos,1) If Int(za$) > Int(zb$) Then Return 1 If Int(za$) < Int(zb$) Then Return 2 Wend End Function Function ahochb$(a$,b$) ;a;b element Z c$="1" d$=a$ If vergleich(a$,"2") = 1 Then While vergleich(c$,b$) = 2 c$ = String_Add$(c$,"1") a$ = String_Multiply$(a$,d$) Wend End If If a$ = "2" Then While vergleich(c$,b$) = 2 c$ = String_Add$(c$,"1") a$ = String_Add$(a$,a$) Wend End If Return a$ End Function
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

So, Apr 05, 2009 2:03
Antworten mit Zitat

Ach du hast es begrenzt - das erklärt dann einige der Fehler. Nicht aber bei den Potenzen.

Dafür habe ich mal meine Funktionen bischen umgeschrieben, damit sie bei dir passen:

Code: [AUSKLAPPEN]

Graphics 1000,600,32,2
Include "noobody-stringr.bb"

font = LoadFont("lucida console",12)
SetFont font

SeedRnd MilliSecs()

t1=MilliSecs()
p$=ahochb("6","216")
Print p
Text 10,280,"Dauer: "+Str(MilliSecs()-t1)+" ms"
WaitKey
End

Function vergleich(a$,b$)
; a;b element Z
; Rückgabewerte:
; 1 - a > b, b < a
; 2 - b > a; a < b
; 0 - a = b
; betrag = 1 -> behandelt a$ und b$ als natürliche Zahlen
If betrag=1 Then
If Left$(a$,1)="-" Then a$ = Mid$(a$,2)
If Left$(b$,1)="-" Then b$ = Mid$(b$,2)
End If
If a$ = b$ Then Return 0

If Left$(a$,1) = "-" And Left$(b$,1) <> "-" Then Return 2
If Left$(b$,1) = "-" And Left$(a$,1) <> "-" Then Return 1

l1=Len(a$)
l2=Len(b$)
If l1 > l2 Then Return 1
If l1 < l2 Then Return 2
If l1 < 10 Then
If l2 < 10 Then
   If Int(a$) > Int(b$) Then Return 1
   If Int(a$) < Int(b$) Then Return 2
End If
End If

While Int(za$) = Int(zb$)
pos=pos+1
za$=Mid(a$,pos,1)
zb$=Mid(b$,pos,1)
If Int(za$) > Int(zb$) Then Return 1
If Int(za$) < Int(zb$) Then Return 2
Wend
End Function

Function ahochb$(a$,b$)
;a;b element Z
c$="1"
d$=a$
If vergleich(a$,"2") = 1 Then
While vergleich(c$,b$) = 2
   c$ = String_Add$(c$,"1")
   a$ = String_Multiply$(a$,d$)
Wend
End If
If a$ = "2" Then
While vergleich(c$,b$) = 2
   c$ = String_Add$(c$,"1")
   a$ = String_Add$(a$,a$)
Wend
End If
Return a$
End Function

Coding: silizium-net.de | Portfolio: Triton.ch.vu

	Noobody	So, Apr 05, 2009 2:18 Antworten mit Zitat
Hm, irgendwas scheint bei String_Multiply nicht zu stimmen - er spuckt komischerweise irgendwelche ASCII - Buchstaben aus, wenn einer der beiden Zahlen einstellig ist. Dem muss ich noch nachgehen - danke für den Tipp.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Noobody

So, Apr 05, 2009 2:18
Antworten mit Zitat

Hm, irgendwas scheint bei String_Multiply nicht zu stimmen - er spuckt komischerweise irgendwelche ASCII - Buchstaben aus, wenn einer der beiden Zahlen einstellig ist.
Dem muss ich noch nachgehen - danke für den Tipp.

Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

	Noobody	So, Apr 05, 2009 12:25 Antworten mit Zitat
Okay, ich habe jetzt mal alle Fehler gefixt, die bisher aufgetreten sind (in String_Substract steckte ein kleiner Fehler, der aber nur in sehr seltenen Fällen auftrat, sowie in String_Add - weil ich aber Division und Multiplikation auf Addition und Substraktion zurückführe, hatte das automatisch Auswirkungen auf die beiden Funktionen). Sollte jetzt alles so funktionieren, wie man es erwarten würde. Leider habe ich während den Tests eine unangenehmere Eigenschaft der Blitzarrays festgestellt - je grösser sie sind, desto grösser wird die Zugriffszeit. Wenn man also CHARLIMIT höherschraubt, um grössere Zahlen zu ermöglichen, wird dadurch automatisch die Berechnungszeit grösser. Ich habe da erst einen Fehler in meinem Code vermutet, der irgendeine Schleife bei grösserem Charlimit länger laufen lässt, aber wenn ich CHARLIMIT gleichbleiben lasse und dafür nur das Blitzarray vergrössere, steigt die Berechnungszeit automatisch mit. Ich hatte ursprünglich die Blitzarrays gewählt, um die Berechnungszeit zu drücken, aber scheinbar war das keine so gute Wahl Naja, ich werde die Funktionen eventuell mal neu schreiben, aber ich glaube sowieso kaum, dass hier jemand grosses Interesse hat (wer braucht schon Stringrechner in der Spieleprogrammierung?). Mit der neuen Version habe ich übrigens bei den Potenzen mit einer Basis ungleich 2 die Nase vorn - beispielsweise bei 987654^123 brauche ich hier nur 675ms (alle Angaben ohne Debugger). Scheinbar ist meine Addition zwar langsamer, dafür die Multiplikation schneller. Korrigierter Code ist im Erstpost zu finden.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Noobody

So, Apr 05, 2009 12:25
Antworten mit Zitat

Okay, ich habe jetzt mal alle Fehler gefixt, die bisher aufgetreten sind (in String_Substract steckte ein kleiner Fehler, der aber nur in sehr seltenen Fällen auftrat, sowie in String_Add - weil ich aber Division und Multiplikation auf Addition und Substraktion zurückführe, hatte das automatisch Auswirkungen auf die beiden Funktionen).
Sollte jetzt alles so funktionieren, wie man es erwarten würde.
Leider habe ich während den Tests eine unangenehmere Eigenschaft der Blitzarrays festgestellt - je grösser sie sind, desto grösser wird die Zugriffszeit. Wenn man also CHARLIMIT höherschraubt, um grössere Zahlen zu ermöglichen, wird dadurch automatisch die Berechnungszeit grösser.
Ich habe da erst einen Fehler in meinem Code vermutet, der irgendeine Schleife bei grösserem Charlimit länger laufen lässt, aber wenn ich CHARLIMIT gleichbleiben lasse und dafür nur das Blitzarray vergrössere, steigt die Berechnungszeit automatisch mit.

Ich hatte ursprünglich die Blitzarrays gewählt, um die Berechnungszeit zu drücken, aber scheinbar war das keine so gute Wahl Confused

Naja, ich werde die Funktionen eventuell mal neu schreiben, aber ich glaube sowieso kaum, dass hier jemand grosses Interesse hat (wer braucht schon Stringrechner in der Spieleprogrammierung?).

Mit der neuen Version habe ich übrigens bei den Potenzen mit einer Basis ungleich 2 die Nase vorn - beispielsweise bei 987654^123 brauche ich hier nur 675ms (alle Angaben ohne Debugger).
Scheinbar ist meine Addition zwar langsamer, dafür die Multiplikation schneller.

Korrigierter Code ist im Erstpost zu finden.

Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

	Triton	Mi, Apr 08, 2009 1:07 Antworten mit Zitat
Noobody hat Folgendes geschrieben: Mit der neuen Version habe ich übrigens bei den Potenzen mit einer Basis ungleich 2 die Nase vorn - beispielsweise bei 987654^123 brauche ich hier nur 675ms (alle Angaben ohne Debugger). Scheinbar ist meine Addition zwar langsamer, dafür die Multiplikation schneller. Hat mich ganz schön geschockt, diese 675 ms. Nicht schlecht. Aber ich habe mich auch nochmal an meine Multiplkation gesetzt und diese verbessert: 6^216 dauert 47 ms 6^1296 dauert 1580 ms 987654^123 dauert 260 ms 987654321012^123 dauert 943 ms Auch die reine Multiplikation ist jetzt wesentlich schneller, abgesehen von 100 mal 1000-Stellig. Das ist zwar auch 4x schneller, verglichen mit vorher, aber immernoch langsamer als euers. Seltsam.
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Mi, Apr 08, 2009 1:07
Antworten mit Zitat

Noobody hat Folgendes geschrieben:

Mit der neuen Version habe ich übrigens bei den Potenzen mit einer Basis ungleich 2 die Nase vorn - beispielsweise bei 987654^123 brauche ich hier nur 675ms (alle Angaben ohne Debugger).
Scheinbar ist meine Addition zwar langsamer, dafür die Multiplikation schneller.

Hat mich ganz schön geschockt, diese 675 ms. Nicht schlecht. Aber ich habe mich auch nochmal an meine Multiplkation gesetzt und diese verbessert:

6^216 dauert 47 ms
6^1296 dauert 1580 ms
987654^123 dauert 260 ms
987654321012^123 dauert 943 ms

Auch die reine Multiplikation ist jetzt wesentlich schneller, abgesehen von 100 mal 1000-Stellig. Das ist zwar auch 4x schneller, verglichen mit vorher, aber immernoch langsamer als euers. Seltsam.

Coding: silizium-net.de | Portfolio: Triton.ch.vu

Übersicht

BlitzBasic

Codearchiv

Nach Oben

BlitzBasic Portal

Stringrechner für grosse Zahlen

Betreff: Stringrechner für grosse Zahlen