Suche (schnelle) Funktion zum Umrechnen ins Dual- oder Hexadezimalsystem

**Mars**

Probiere ich auch grade.
Bin an folgendem Gescheitert:

Beispiel:
Zahl = 10
Binärdarstellung = 1010
Zahl 11 -> 1011
Zahl 12 -> 1100
Die 2te Zahl kann bis auf die erste Stelle noch alle anderen Werte verändern, da hilft auch der Teilerrest der ersten nicht.

auch doof ist, dass es keinen ggt gibt.
z.B kann man sagen 4 Bin -> 1 Hex.
Für Dezimalzahlen gilt das aber leider nicht. Es gibt keine 2^n Zahl die auf 0 endet, man kann den großen String also nicht in kleine Teile zerlegen und diese einzeln behandeln...

Edit:
Allerdings können die Ergebnisse der ersten Zahl die weiter hinten gelegenen nicht mehr beeinflussen. Dafür werden sie von den Überschlagen der vorherigen Zahlen beeinflusst...

Edit2: http://www.php.net/manual/en/function.base-convert.php
Mal schauen ob das was hilft. Da wird jedenfalls mit Strings hantiert.

Yjuq

Hmn,...
Vielleicht muss man ein wenig anders denken...
Ich weiß nicht ob das hier irgendwie hilft, aber man kann jede Dualzahl (oder auch Blöcke davon) mit Potenzen in Dezimaler Form schreiben. Vielleicht kann man die Dezimalzahl ja vorerst so aufteilen und dann Blockweise die Dualzahl erstellen. Bis 64/32 Bit schafft das der Computer ja mit Integers statt Strings zu rechnen wodurch bereits vorgestellte Funktionen brauchbar werden.

1234567890 (Dec) <=> (Dual) 01001001100101100000001011010010

01001001 10010110 00000010 11010010
73*256^3 + 150*256^2 + 2*256^1 + 210*256^0

**Mars**

Ich dachte an sowas:

[autoit]

Local $t = DllStructCreate('int64')
DllStructSetData($t, 1, 1234567890123456789)
Local $p = DllStructCreate('byte a[8]', DllStructGetPtr($t)), $s
For $i = 9 To 1 Step -1
$s &= Hex($p.a(($i)),2)
Next
ConsoleWrite($s & @CRLF)
$s = StringRegExpReplace($s, "^0+([^0]|0$)", "\1", 1)
ConsoleWrite(Int('0x' & $s) & @CRLF)

[/autoit]

Man kann per Struct den Kram schön ins Hexformat bringen (was ja dem Dualsystem nur noch ein Katzensprung entfernt ist).
Man müsste nur die komplette Dezimalzahl da reinstecken können...

Yjuq

Naja, wie ich ja einen Post vorher gezeigt habe, kann man eine > 64 Bit Zahl in mehrere Blöcke aufteilen. Damit würdest du dann die gesamte Zahl in ein Strukturen Array (oder wie auch immer) unterbringen. Das Problem ist halt, dass man vorab die Zahlen dividieren und subtrahieren muss. Was anderes fällt mir derzeitig leider nicht ein. Ich könnte mir vorstellen wenn man das in FreeBASIC so machen würde (mit Multithreading), dass es ab einer bestimmten Zahl tatsächlich einen Geschwindigkeit Schub anstelle von anderen Algorithmen bringen würde.

Das ist aber auch verzwickt

**Andy**

hehe, nützt alles nix....habe jetzt die Transformation IntToBin in 40 Takten hinbekommen...bringt aber garnix, weil der Overhead des DllCallAddress() und DllCall() viel zu hoch ist

Habe den ASM-Code 1:1 in meine im Assemblertut gezeigte Vorlage für eine Dll kopiert, Ctrl-F9 in FASMW, fertig.
Dllcall ist etwa 20% langsamer als DllCallAddress()

Ich benutze eine 2048 Byte lange Lookup-Tabelle LUT, welche aufeinanderfolgend die 8-Byte-Strings von 00000000 bis 11111111 (0x00 bis 0xFF) enthält.
Hat man den Integer, bspw. 0x3B, dann ist die Adresse = Startadresse_LUT + ( 8 * 0x3B ) und man kann dann von dort den String "00111011" ins Ergebnis kopieren.
Ich habe, um Speichertransfers soweit wie möglich einzusparen, die 4 Strings (a 64 Bit) in 2 SSE-Register kopiert.
Mit bissl Code Verschachteln und Alignment kommt man auf ca. 30 Takte, fürs inlinen in einer Compilersprache sicher keine schlechte Sache^^

Spoiler anzeigen

[autoit]

#AutoIt3Wrapper_UseX64=n ;wg AssembleIt, in der vorliegenden Version kann auch der 64-Bit-Modus verwendet werden
;#include "AssembleIt2.au3"

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

;Assemblercode wandelt Integerzahl in Binärdarstellung

[/autoit] [autoit][/autoit] [autoit]

#cs int2dec
use32 ;32-Bitmode

[/autoit] [autoit][/autoit] [autoit]

mov edi,[esp+4] ;integer
mov edx,[esp+8] ;pointer auf Rückgabestring
mov esi,[esp+12] ;pointer auf LUT

[/autoit] [autoit][/autoit] [autoit]

start:
mov ebx,edi ;integer
and ebx,0x000000FF ;bl maskieren 0xEF, leider kann man nicht [ESI+8*bl] schreiben
movhpd xmm0,qword[esi+8*ebx] ;adressinhalt der 8 bytes "11101111" aus LUT ins register

[/autoit] [autoit][/autoit] [autoit]

mov ebx,edi ;integer
shr ebx,8 ;nach bl schieben
and ebx,0x000000FF ;bl maskieren
movlpd xmm0,qword[esi+8*ebx] ;adressinhalt der 8 bytes aus LUT ins register

[/autoit] [autoit][/autoit] [autoit]

mov ebx,edi ;edi
shr ebx,16 ;nach bl schieben
and ebx,0x000000FF ;bl maskieren
movhpd xmm1,qword[esi+8*ebx] ;adressinhalt der 8 bytes aus LUT ins register

[/autoit] [autoit][/autoit] [autoit]

mov ebx,edi ;edi
shr ebx,24 ;nach bl schieben
movlpd xmm1,qword[esi+8*ebx] ;adressinhalt der 8 bytes aus LUT ins register

[/autoit] [autoit][/autoit] [autoit]

movdqu dqword[edx],xmm1 ;erste 16 bytes ins ergebnis
movdqu dqword[edx+16],xmm0 ;zweite 16 bytes ins ergebnis

[/autoit] [autoit][/autoit] [autoit]

;ab hier stehen die 32 Bytes nullen und einsen im String

[/autoit] [autoit][/autoit] [autoit]

mov ecx,-1 ;erst ab der ersten 1 ausgeben
schleife:
add ecx,1 ;von byte 0 bis 31
cmp ecx,31 ;31 bytes erreicht?
je raus ;dann ist ecx+edx der pointer
cmp byte [edx+ecx],'1' ;ist byte im Rückgabestring eine '1'?
jne schleife ;wenn keine 1, dann nächstes byte im string

[/autoit] [autoit][/autoit] [autoit]

raus:
add edx,ecx ;pointer auf erste 1 im string, ab dort darstellen
mov eax,edx ;pointer auf rückgabestring zurückgeben

[/autoit] [autoit][/autoit] [autoit]

ret

[/autoit] [autoit][/autoit] [autoit]

#ce

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

;assemblercode in den Speicher schreiben, die folgenden Zeilen wurden von AssembleIt() erstellt
$ret_asm = "0x8B7C24048B5424088B74240C89FB81E3FF000000660F1604DE89FBC1EB0881E3FF000000660F1204DE89FBC1EB1081E3FF000000660F160CDE89FBC1EB18660F120CDEF30F7F0AF30F7F4210B9FFFFFFFF83C10183F91F7406803C0A3175F201CA89D0C3"

[/autoit] [autoit][/autoit] [autoit]

$struct_asm = DllStructCreate("byte[" & StringLen($ret_asm) / 2 - 1 & "]") ;platz für asmcode im speicher
$ptr_asm = DllStructGetPtr($struct_asm) ;pointer asmcode
DllStructSetData($struct_asm, 1, $ret_asm) ;asmcode in struct schreiben

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Global $struct_LUT = DllStructCreate("char[2048]") ;für asm
Global $ptr_LUT = DllStructGetPtr($struct_LUT)
_LUT_fuellen() ;für asm

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

$int = 0xDEADBEEF ;integer

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

;rückgabe
$struct = DllStructCreate("char [32];int") ;32 Byte string plus Nullbyte als Stringende
DllStructSetData($struct, 1, "00000000000000000000000000000000") ;string mit Nullen erstellen
$addr = DllStructGetPtr($struct)

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

;~ $ret = _AssembleIt2("str*", "int2dec", "int", $int, "ptr", $addr, "ptr", $ptr_LUT)
;~ ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $ret = ' & $ret & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

;DllCallAddress()
$ret = DllCallAddress("str*:cdecl", $ptr_asm, "int", $int, "ptr", $addr, "ptr", $ptr_LUT) ;int nach bin
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $ret = ' & $ret[0] & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

;Dllcall()
$dll = DllOpen("IntToBin.dll")
$ret = DllCall($dll, "str*", "IntToBin", "int", $int, "ptr", $addr, "ptr", $ptr_LUT)
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $ret = ' & $ret[0] & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func _LUT_fuellen() ;2048 Bytes LUT füllen
$LUT = ""
For $i = 0 To 255
$bin = ''
$value = $i
Do
$bin = Mod($value, 2) & $bin
$value = Floor($value / 2)
Until $value = 0
$LUT &= StringLeft("00000000", 8 - StringLen($bin)) & $bin
Next
DllStructSetData($struct_LUT, 1, $LUT)
EndFunc ;==>_LUT_fuellen

[/autoit] [autoit][/autoit] [autoit][/autoit]

autoit.de/wcf/attachment/24147/ die IntToBin.dll und auch AssembleIt2(), nur noch mit einem Overhead von 1 ms!

Dllcode für FASMW.EXE

Spoiler anzeigen

[autoit]

; DLL creation example für WIN7 64
;
;1) Funktion erstellen in der section .text
; proc Funktionsname
; AssemblerCode....wie er in AutoIt lauffähig ist... hierhinkopieren
; endp
;
;2) In die section .edata den Funktionsnamen eintragen:
;export 'DLLNAME.DLL',\ ;Name der DLL-Datei
;Funktionsname1,'Funktionsname1',\ ;Funktionsnamen
;Funktionsname2,'Funktionsname2'
;
;3) *.asm-datei mit wfasm.exe oder fasm.exe compilieren (in FASMW.EXE laden und CTRL+F9 drücken)
;
;Aufruf aus AutoIt mit
;$ret=dllcall("dllname.dll","RückgabeTYP","Funktionsname","TYP",$parameter1)

[/autoit] [autoit][/autoit] [autoit]

format PE GUI 4.0 DLL
entry DllEntryPoint

[/autoit] [autoit][/autoit] [autoit]

include 'win32a.inc' ;includes

[/autoit] [autoit][/autoit] [autoit]

;einzubindende Librarys
section '.idata' import data readable
library kernel,'KERNEL32.DLL',\
user,'USER32.DLL'

[/autoit] [autoit][/autoit] [autoit]

;************Hier die in der DLL verwendeten Funktionen für den Export eintragen
section '.edata' export data readable
export 'IntToBin.DLL',\ ;Dateiname, Zeilentrenner ist ,\
IntToBin,'IntToBin' ;letzte Funktion ohne das ,\

[/autoit] [autoit][/autoit] [autoit]

;weitere Sektionen je nach Anforderung der Funktionen
;section '.data' data readable writeable

[/autoit] [autoit][/autoit] [autoit]

;section für die Funktionen
section '.code' code readable executable

[/autoit] [autoit][/autoit] [autoit]

;DllEntryPoint wird beim Laden der DLL aufgerufen
;um "bombensicheres" Errorhandling zu haben, Funktion anpassen!
proc DllEntryPoint hinstDLL,fdwReason,lpvReserved
mov eax,TRUE ;hart aber herzlich^^
ret
endp

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

;******************Ab hier fangen die Benutzer-Funktionen an **********

[/autoit] [autoit][/autoit] [autoit]

proc IntToBin

[/autoit] [autoit][/autoit] [autoit]

use32 ;32-Bitmode

[/autoit] [autoit][/autoit] [autoit]

mov edi,[esp+4] ;integer
mov edx,[esp+8] ;pointer auf Rückgabestring
mov esi,[esp+12] ;pointer auf LUT

[/autoit] [autoit][/autoit] [autoit]

start:
mov ebx,edi ;integer
and ebx,0x000000FF ;bl maskieren 0xEF
movhpd xmm0,qword[esi+8*ebx] ;adressinhalt der 4 bytes "1110" in LUT ins register

[/autoit] [autoit][/autoit] [autoit]

mov ebx,edi ;integer
shr ebx,8 ;nach bl schieben
and ebx,0x000000FF ;bl maskieren
movlpd xmm0,qword[esi+8*ebx] ;adressinhalt der 4 bytes in LUT ins register

[/autoit] [autoit][/autoit] [autoit]

mov ebx,edi ;edi
shr ebx,16 ;nach bl schieben
and ebx,0x000000FF ;bl maskieren 0
movhpd xmm1,qword[esi+8*ebx] ;adressinhalt der 4 bytes in LUT ins register

[/autoit] [autoit][/autoit] [autoit]

mov ebx,edi ;edi
shr ebx,24 ;nach bl schieben
movlpd xmm1,qword[esi+8*ebx] ;adressinhalt der 4 bytes in LUT ins register

[/autoit] [autoit][/autoit] [autoit]

movdqu dqword[edx],xmm1 ;erste 16 bytes ins ergebnis
movdqu dqword[edx+16],xmm0 ;zweite 16 bytes ins ergebnis

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

mov ecx,-1 ;erst ab der ersten 1 ausgeben
schleife:
add ecx,1
cmp ecx,31 ;31 bytes erreicht?
je raus ;dann ist ecx+edx der pointer
cmp byte [edx+ecx],'1' ;ist byte im Rückgabestring eine '1'?
jne schleife ;wenn keine 1, dann nächstes byte im string

[/autoit] [autoit][/autoit] [autoit]

raus:
add edx,ecx ;pointer auf erste 1 im string, ab dort darstellen
mov eax,edx ;pointer auf rückgabestring zurückgeben

[/autoit] [autoit][/autoit] [autoit]

ret 12

[/autoit] [autoit][/autoit] [autoit]

endp

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

section '.reloc' data discardable

[/autoit] [autoit][/autoit] [autoit]

data fixups
if ~ $-$$
dd 0,8 ;empty fixups section iff no other fixups
end if
end data

[/autoit]

**Mars**

Läuft wirklich flott. Ein Ranking gibts Morgen, erstmal muss dieser Stringkram aus meinem Kopf.
Irgendwie glaube ich, dass du dich damit auf Platz 1 Rangierst. Dann gibts nur noch Dll Overhead vs Array Overhead

Zum Langen Dec String:
Habe eine selbstverständlich unzufriedenstellende (aber extrem schnelle) Lösung gefunden.
Der Dezimalstring wird einfach in 3er Ketten gespalten und dann umgewandelt.
ddd -> 10 Bit (da 999 < 1024 geht das in jedem Fall).
Allerdings werden dabei 0.34% + x der Bitlänge verbraten. (da die Werte 1000-1023 niemals genutzt werden).
Jetzt stellt sich die Frage: Ist man mit einer falschen, aber schnellen Rechnung zufrieden ? (Die angehängten Nullen kann man durch eine Längenangabe wieder rausschmeißen)

Skript

[autoit]

Global $a_[256], $b_[256], $c_[11111112]

[/autoit] [autoit][/autoit] [autoit]

_DecToBin_Startup()

[/autoit] [autoit][/autoit] [autoit]

Global $DEC = '234950770365524664314635516700700126668787223320782810776196842343923622379715841889813674902718039418167617401497873060561000272'

[/autoit] [autoit][/autoit] [autoit]

Global $BIN = __MComp_DecToBin($DEC)
Global $x = __MComp_BinToDec($BIN)

[/autoit] [autoit][/autoit] [autoit]

ConsoleWrite('Original: ' & $DEC & @CRLF & 'Binär: ' & $BIN & @CRLF & 'Zurück: ' & $x & @CRLF & 'Verlust: ' & StringLen($BIN) - Int(StringLen($DEC)*Log(10)/Log(2)) & ' Bit (Anzahl unnötig verbrauchter Bits)' & @CRLF)

[/autoit] [autoit][/autoit] [autoit]

; nicht Optimal !
; Ersetzen von ddd -> 10 Bit (Verlust: 0.34%)
; Am Ende ggf bis zu 7 Bit Verlust !
Func __MComp_DecToBin($sDec)
While Not IsInt(StringLen($sDec)/3)
$sDec &= 0
WEnd
Local $sRet
For $i = 1 To StringLen($sDec) Step 3
$sRet &= StringRight('0000000000' & _DecToBin(StringMid($sDec, $i, 3)), 10)
Next
Return $sRet
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func __MComp_BinToDec($sBin)
Local $sRet
For $i = 1 To StringLen($sBin) Step 10
$sRet &= StringRight('000' & _BinToDec(StringMid($sBin, $i, 10)), 3)
Next
Return $sRet
EndFunc

[/autoit] [autoit][/autoit] [autoit]

; <Func>--------------------------------------------------|
; Wandelt eine Dualzahl in eine Dezimalzahl um |
; --------------------------------------------------------|
Func _BinToDec($s)
Local $l = StringLen($s)
Return $l<9?$c_[$s]:$l<17?$c_[StringTrimRight($s,8)]*256+$c_[StringRight($s,8)]:$l<25?$c_[StringTrimRight($s,16)]*65536+$c_[StringRight(StringTrimRight($s,8),8)]*256+ $c_[StringRight($s,8)]:BitShift($c_[StringTrimRight($s,24)],-24)+$c_[StringRight(StringTrimRight($s,16),8)]*65536+$c_[StringRight(StringTrimRight($s,8),8)]*256+$c_[StringRight($s,8)]
EndFunc

[/autoit] [autoit][/autoit] [autoit]

; <Func>--------------------------------------------------|
; Ermittelt eine Dualzahl (0101) aus einer Dezimalzahl |
; Die Dezimalzahl muss kleiner als 2^31 sein |
; --------------------------------------------------------|
Func _DecToBin($d)
Return $d<256?$a_[$d]:$d<65536?$a_[$d/256]&$b_[BitAND($d,255)]:$d<16777216?$a_[$d/65536]&$b_[BitAND($d/256,255)]&$b_[BitAND($d,255)]:$a_[BitShift($d,24)]&$b_[BitAND($d/65536,255)]&$b_[BitAND($d/256,255)]&$b_[BitAND($d,255)]
EndFunc

[/autoit] [autoit][/autoit] [autoit]

; <Func>--------------------------------------------------|
; Initialisiert die DecToBin UDF |
; --------------------------------------------------------|
Func _DecToBin_Startup()
Local $t = DllStructCreate('char[64]'), $p = _
DllStructGetPtr($t), $hDll = DllOpen('msvcrt.dll')
For $i = 0 To 255 Step 1
DllCall($hDll, 'ptr:cdecl', '_i64toa', 'int64', _
$i, 'ptr', $p, 'int', 2)
$a_[$i] = DllStructGetData($t, 1)
$b_[$i] = StringRight('0000000' & $a_[$i],
$c_[$a_[$i]] = $i
Next
DllClose($hDll)
EndFunc

[/autoit]

**Andy**

Also wenn du das auf lange Strings anwenden willst, dann kannst du dich warm anziehen
DIE Challenge nehme ich an.
Wird dann aber auch eine Funktion in einer Dll geben, so kann man sie auch in anderen Programmiersprachen nutzen.
Nett wäre, wenn ein Interessierter die Funktion in C oder Compiler-Basic schreiben würde zum Vergleich.

**Mars**

Make hat schon eine Funktion in Basic gefunden die scheinbar keine n² Komplexität besitzt.
Es kann natürlich auch eine DLL sein.

Das Problem ist dabei, dass man ja normalerweise immer die komplette Zahl durch 2 Teilen muss. Bei großen Strings braucht man dann die BugNum UDF (die ja ansich ziemlich flott ist), da man aber für jede 0 oder 1 eine Division durch 2 braucht ist das trotzdem schnarchlangsam...

hier ist mal der Code von Make:

Spoiler anzeigen

Code

Constructor bigint (ByRef a As String)
        Dim As Integer p, i, j, ch, blocks, sign
        If InStr(a, "-") <> 0 Then sign = -1
        '------------------------------------------------------------
        ' extract numerics from input string
        j = 0   '  in-place write pointer
        For i = 0 To Len(a) - 1
            ch = a[i]
            If (ch >= Asc("0")) And (ch <= Asc("9")) Then
                a[j] = ch
                j += 1
            End If
        Next i
        a = Left(a, j)  ' j is one ahead from string index = length of a
        '------------------------------------------------------------
        ' extend to next multiple of 9 digits
        i = Len(a)
        blocks = Int(0.99 + i / 9)  ' number of 9 digit blocks needed
        p = 9 * blocks
        a = String(p - i, "0") + a  ' pad to next multiple of 9 digits
        '------------------------------------------------------------
        ' decimal to binary conversion
        i = ( 8 + Len(a) * 3.32192809488) \ 8   ' bytes needed for binary
        blocks = 1 + (i \ 4)                    ' adjust to multiple of 4
        this.s = String(blocks * 4, Chr(0) ) ' binary destination string
        '------------------------------------------------------------
        Dim As UInteger<32> Ptr bp, bpz, bpcarry, bpdata
        bpz = Cast(UInteger<32> Ptr, StrPtr(this.s)) ' binary output string[0]
        Dim As ULongInt product, carry, multiplier = 1e9
        bpdata = Cast(UInteger<32> Ptr, @product) ' bottom half of product
        bpcarry = bpdata + 1                ' top half of product
        '------------------------------------------------------------
        blocks = 1  ' blocks will be advanced as required by carry
        For i = 1 To Len(a)-8 Step 9   ' msd to lsd in blocks of 9
            bp = bpz    ' point back to the start
            carry = ValULng(Mid(a, i, 9))  ' take the next 9 digit block
            For j = 1 To blocks
                product = CLngInt(*bp) * multiplier + carry
                *bp = CUInt<32>(*bpdata)
                carry = CULngInt(*bpcarry)
                bp += 1
            Next j
            ' advancing blocks only as needed doubles the speed of conversion
            If Carry Then
                *bp = carry
                blocks += 1 ' an exact count of the blocks used
            End If
        Next i
        this.s = Left(this.s, blocks * 4) ' keep only used blocks
        '-------------------------------------------------------------
        If this.s[Len(this.s)-1] And 128 Then this.s = this.s + bigint_0.s ' MSB must be 0
        If sign Then This = bigint_negate(This)
    End Constructor

Alles anzeigen

Und hier eine Version mit BigNum UDF

Spoiler anzeigen

[autoit]

#include <BigNum.au3>
#include <Array.au3>

[/autoit] [autoit][/autoit] [autoit]

Global $a_[256], $b_[256], $c_[11111112]

[/autoit] [autoit][/autoit] [autoit]

_DecToBin_Startup()

[/autoit] [autoit][/autoit] [autoit]

Global $x = '123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890', $t
$t = TimerInit()
Global $b = _Big_DecToBin($x)
$t = TimerDiff($t)

[/autoit] [autoit][/autoit] [autoit]

ConsoleWrite('Time: ' & Round($t, 2) & ' ms' & @CRLF & $b & @CRLF)

[/autoit] [autoit][/autoit] [autoit]

Func _Big_DecToBin($sDec)
Local $iLen = StringLen($sDec), $aBlocks[Ceiling(Log(10)/Log(2)*$iLen/8)]
Local $sTmp = $sDec, $i = 0, $sRet
While Not ($sTmp = '0')
$sRet = StringRight('00000000' & _DecToBin(_BigNum_Div256($sTmp)), & $sRet
$i += 1
WEnd
While StringLeft($sRet, 1) = '0'
$sRet = StringTrimLeft($sRet, 1)
WEnd
Return $sRet
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func _BigNum_Div256(ByRef $sX) ; Input: sX, Output: Modulo, sX /= 256
Local $sM = "0"
Local $bRed = False
Local $sRet = "", $sRem = StringLeft($sX, 3), $sTmp = "", $sTm2 = "", $iCnt, $iLen = 1
$sX = StringTrimLeft($sX, 3)
Do
If __BigNum_DivComp($sRem, 256) = -1 Then
$sTmp = StringLeft($sX, 1)
$sRem &= $sTmp
$sX = StringTrimLeft($sX, 1)
If StringLen($sTmp) > 0 Then $iLen += 1
EndIf
$sTmp = 256
$sTm2 = "0"
If __BigNum_DivComp($sRem, 256) >= 0 Then
For $iCnt = 1 To 9
$sTm2 = $sTmp
$sTmp = __BigNum_DivAdd($sTmp, 256)
If __BigNum_DivComp($sRem, $sTmp) < 0 Then ExitLoop
Next
Else
$iCnt = 0
EndIf
If StringLen($sX) = 0 Then $bRed = True
$sM = $sRem
$sRem = __BigNum_DivSub($sRem, $sTm2)
If $iCnt > 0 Then $sM = $sRem
$sRet &= StringFormat("%0" & String($iLen) & "u", $iCnt)
$iTrm = 3 - StringLen($sRem)
$sTmp = StringLeft($sX, $iTrm)
$sX = StringTrimLeft($sX, $iTrm)
$iLen = StringLen($sTmp)
$sRem &= $sTmp
Until $bRed
$sX = StringRegExpReplace($sRet, "^0+([^0]|0$)", "\1", 1)
Return StringRegExpReplace($sM, "^0+([^0]|0$)", "\1", 1)
EndFunc ;==>__BigNum_Div_DivisorGreater14

[/autoit] [autoit][/autoit] [autoit]

; <Func>--------------------------------------------------|
; Wandelt eine Dualzahl in eine Dezimalzahl um |
; --------------------------------------------------------|
Func _BinToDec($s)
Local $l = StringLen($s)
Return $l<9?$c_[$s]:$l<17?$c_[StringTrimRight($s,8)]*256+$c_[StringRight($s,8)]:$l<25?$c_[StringTrimRight($s,16)]*65536+$c_[StringRight(StringTrimRight($s,8),8)]*256+ $c_[StringRight($s,8)]:BitShift($c_[StringTrimRight($s,24)],-24)+$c_[StringRight(StringTrimRight($s,16),8)]*65536+$c_[StringRight(StringTrimRight($s,8),8)]*256+$c_[StringRight($s,8)]
EndFunc

[/autoit] [autoit][/autoit] [autoit]

; <Func>--------------------------------------------------|
; Ermittelt eine Dualzahl (0101) aus einer Dezimalzahl |
; Die Dezimalzahl muss kleiner als 2^31 sein |
; --------------------------------------------------------|
Func _DecToBin($d)
Return $d<256?$a_[$d]:$d<65536?$a_[$d/256]&$b_[BitAND($d,255)]:$d<16777216?$a_[$d/65536]&$b_[BitAND($d/256,255)]&$b_[BitAND($d,255)]:$a_[BitShift($d,24)]&$b_[BitAND($d/65536,255)]&$b_[BitAND($d/256,255)]&$b_[BitAND($d,255)]
EndFunc

[/autoit] [autoit][/autoit] [autoit]

; <Func>--------------------------------------------------|
; Initialisiert die DecToBin UDF |
; --------------------------------------------------------|
Func _DecToBin_Startup()
Local $t = DllStructCreate('char[64]'), $p = _
DllStructGetPtr($t), $hDll = DllOpen('msvcrt.dll')
For $i = 0 To 255 Step 1
DllCall($hDll, 'ptr:cdecl', '_i64toa', 'int64', _
$i, 'ptr', $p, 'int', 2)
$a_[$i] = DllStructGetData($t, 1)
$b_[$i] = StringRight('0000000' & $a_[$i],
$c_[$a_[$i]] = $i
Next
DllClose($hDll)
EndFunc

[/autoit]

Edit: Er wird natürlich auch eine BigBin -> BigDec benötigt

Yjuq

Soa, es hat ein wenig gedauert bis ich den Algorithmus (den Mars bereits gepostet hat) verstanden habe. Ich möchte diesen an dieser Stelle einmal erklären damit andere das nachvollziehen können.

Erst einmal der Code:

Spoiler anzeigen

[autoit]

#include <Array.au3>
#include <String.au3>

[/autoit] [autoit][/autoit] [autoit]

; Der Algorithmus hat irgendwo einen Fehler!
; Diesen finde ich leider nicht
; Setzt z.B. als $sNumber "1234567890" ein...

[/autoit] [autoit][/autoit] [autoit]

Global $sNumber = '123456789'
Global $aiNumber = StringSplit($sNumber, '')
Global $i, $bp, $carry, $n, $aiBitBlocks[1], $product, $sBitString

[/autoit] [autoit][/autoit] [autoit]

For $i = 1 To $aiNumber[0]
$bp = 0
$carry = $aiNumber[$i]
For $n = 0 To UBound($aiBitBlocks) -1
$product = $aiBitBlocks[$n] * 10 + $carry
$aiBitBlocks[$bp] = BitAND($product, 0x00FF)
$carry = BitAND($product, 0xFF00) / 256
$bp += 1
Next
If $carry Then
_ArrayAdd($aiBitBlocks, 0)
$aiBitBlocks[$bp] = $carry
EndIf
Next

[/autoit] [autoit][/autoit] [autoit]

$sBitString = StringFromASCIIArray($aiBitBlocks)
$sBitString = StringReverse($sBitString)
ConsoleWrite('0x' & Hex(Int($sNumber)) & @CRLF)
ConsoleWrite(StringToBinary($sBitString) & @CRLF)

[/autoit]

Was macht der Algorithmus nun genau?
Er liest jedes Zeichen einzeln aus und verarbeitet diesen in Bit Ebene. Später wird ein String zurück gegeben, welcher intern nun die richtige Bit Reihenfolge für die eingegebene Dezimalzahl besitz. Die einzelnen Bits können somit durch bereits vorgestellte Funktionen in 4 Byte Blöcken (Beispielsweise) ausgegeben werden. Die Zahl 65 ist Beispielsweise als String ein „A“ und intern ist die 65 als 01000001. Und genauso konvertiert der Algorithmus die gesamte Dezimalzahl im String.

Wir wissen ja, dass ein Byte 265 Zustände speichern kann. Wenn wir Werte darüber nutzen wollen, müssen wir ein weiteres Byte hinzunehmen. Bei größeren Werten brauchen wir noch mehr Bytes usw. Dies kann man sich nun zu nutzen machen und die Dezimalzahl Ziffer für Ziffer bearbeiten. Das hat den Vorteil dass man auf die nativen Rechenbefehle von AutoIt zugreifen kann (+, -, *, /).

Nehmen wir einmal an, wir hätten die Zahl „12345“ die wir nun in Binärer Form ausgegeben haben wollten. Zuerst bearbeiten wir logischerweise die Ziffer „1“. Im Dualsystem handelt es sich dabei um die Zahl „00000001“. Wir brauchen also ein Byte um diese 1 zu speichern. Also speichern wir beispielsweise in einem Array im Index [0] nun die Zahl 1. (Wir nehmen einfach mal an, jedes Array Element kann nur 1 Byte speichern.) Nun kommt die nächste Ziffer „2“ heran. Was machen wir nun damit? Im Dezimalsystem würden wir (um 2 hinter die 1 zu hängen) zuerst die 1 mit 10 multiplizieren und danach mit 2 addieren. So kommen wir schon bereits auf die 12. Im Array [0] kann man nun die 1 mit der 12 ersetzen. Das gleiche gilt ebenso für die 3. Wir haben im Element [0] nun die Zahl 123 stehen.

Nun kommt der eigentliche Trick bei diesem Algorithmus. Da wir nur auf 256 Zustände beschränkt sind, müssen wir das ein wenig aufteilen damit die Zahl „1234“ gespeichert werden kann. Dazu brauchen wir erst einmal ein weiteres Element in unseren Array. Wir haben also nun folgenden Arrayaufbau: ([0] = 123; [1] = 0)

Die Zahl „1234“ entspricht im Dualsystem die Zahl „0000 0100 1101 0010“. Wenn wir nun die beiden Bytes aufteilen, enthält unser Array nun die Zahlen ([0] = 210; [1] = 4). Aber wie kommt es dazu? Da wir pro Byte 256 Zustände speichern können, wird nun die Zahl „1234“ durch „256“ dividiert. Wir erhalten nun abgerundet (!) „4“. Damit wäre eine Zahl geklärt. Was ist aber nun mit der anderen Zahl „210“? Dieser erhalten wir wenn wir eine Module Rechnung mit 256 durchführen. Oder anders gesagt: 1234 - 256 * 4 = 210

Nun kommt die letzte Ziffer hinzu. Allerdings ist es hier ein wenig anders. Da das Element [0] jetzt 210 enthält, wird nun diese Zahl verwendet. Also: 210 * 10 + 5 = 2105

Weil diese Zahl auch wieder zu groß ist, erhalten wir folgende 2 Bytes: „0000 1000“ und „0011 1001“. In Element [0] wird nun die der LowByte gespeichert. Dieser beträgt [0] = 57. Das andere Byte wird nun mit zum nächsten Element [1] mitgenommen. Hier wieder die gleiche Rechnung: 4 * 10 + 8 = 48.

Unser Array enthält nun die Elemente ([0] = 57; [1] = 48) und intern sind nun folgende Dualzahlen gespeichert:
[0] = 0011 1001
[1] = 0011 0000

Rückwerts gelesen ergibt dies „0011000000111001“ und entspricht der Zahl „12345“ im Dualsystem.

Ich habe zur Vereinfachung immer mit einem Byte gerechnet. Um den Algorithmus effektiver zu machen sollten 4 Zeichen jeweils extrahiert werden. Jeder moderne PC kann locker 32 Bit gleichzeitig bearbeiten. Man muss nur ein wenig umdenken.

Ich hoffe es war einigermaßen verständlich.

**Mars**

Hab noch was schönes gefunden, und leider keinen Compiler zur Hand.
Der Code soll in C# sein, so wie er aussieht läuft er aber auch mit C++.
Wenn jemand das kompilieren könnte wäre ich ihm sehr verbunden, wenn die dabei entstehende Dll dann auch noch schnell ist, ist alles super

Spoiler anzeigen

Code

//---------------------------------------------------------------------------
AnsiString str_hex2dec(const AnsiString &hex)
    {
    char c;
    AnsiString dec="",s;
    int i,j,l,ll,cy,val;
    int  i0,i1,i2,i3,sig;
    sig=+1; l=hex.Length();
    if (l) { c=hex[l]; if (c=='h') l--; if (c=='H') l--; }
    i0=0; i1=l; i2=0; i3=l;
    for (i=1;i<=l;i++)      // scan for parts of number
        {
        char c=hex[i];
        if (c=='-') sig=-sig;
        if ((c=='.')||(c==',')) i1=i-1;
        if ((c>='0')&&(c<='9')) { if (!i0) i0=i; if ((!i2)&&(i>i1)) i2=i; }
        if ((c>='A')&&(c<='F')) { if (!i0) i0=i; if ((!i2)&&(i>i1)) i2=i; }
        if ((c>='a')&&(c<='f')) { if (!i0) i0=i; if ((!i2)&&(i>i1)) i2=i; }
        }


    l=0; s=""; if (i0) for (i=i0;i<=i1;i++)
        {
        c=hex[i];
             if ((c>='0')&&(c<='9')) c-='0';
        else if ((c>='A')&&(c<='F')) c-='A'-10;
        else if ((c>='a')&&(c<='f')) c-='A'-10;
        for (cy=c,j=1;j<=l;j++)
            {
            val=(s[j]<<4)+cy;
            s[j]=val%10;
            cy  =val/10;
            }
        while (cy>0)
            {
            l++;
            s+=char(cy%10);
            cy/=10;
            }
        }
    if (s!="")
        {
        for (j=1;j<=l;j++) { c=s[j]; if (c<10) c+='0'; else c+='A'-10; s[j]=c; }
        for (i=l,j=1;j<i;j++,i--) { c=s[i]; s[i]=s[j]; s[j]=c; }
        dec+=s;
        }
    if (dec=="") dec="0";
    if (sig<0) dec="-"+dec;


    if (i2)
        {
        dec+='.';
        s=hex.SubString(i2,i3-i2+1);
        l=s.Length();
        for (i=1;i<=l;i++)
            {
            c=s[i];
                 if ((c>='0')&&(c<='9')) c-='0';
            else if ((c>='A')&&(c<='F')) c-='A'-10;
            else if ((c>='a')&&(c<='f')) c-='A'-10;
            s[i]=c;
            }
        ll=((l*1234)>>10);  // num of decimals to compute
        for (cy=0,i=1;i<=ll;i++)
            {
            for (cy=0,j=l;j>=1;j--)
                {
                val=s[j];
                val*=10;
                val+=cy;
                s[j]=val&15;
                cy=val>>4;
                }
            dec+=char(cy+'0');
            for (;;)
                {
                if (!l) break;;
                if (s[l]) break;
                l--;
                }
            if (!l) break;;
            }
        }


    return dec;
    }
//---------------------------------------------------------------------------
AnsiString str_dec2hex(AnsiString dec)
    {
    AnsiString hex=""; BYTE a,b;
    int  i,j,i0,i1,i2,i3,l,sig;
    sig=+1; l=dec.Length();
    i0=0; i1=l; i2=0; i3=l;
    for (i=1;i<=l;i++)      // scan for parts of number
        {
        char c=dec[i];
        if (c=='-') sig=-sig;
        if ((c=='.')||(c==',')) i1=i-1;
        if ((c>='0')&&(c<='9')) { if (!i0) i0=i; if ((!i2)&&(i>i1)) i2=i; }
        }
    if (i0) for (;i1>=i0;i1=j-1)// process integer part /16
        {
        for (a=0,j=i0,i=i0;i<=i1;i++)
            {
            a*=10; a+=dec[i]-'0';
            if (a<16) { if (j>i0){ dec[j]='0'; j++; } continue; }
            b=a>>4; a=a&15;
            if (b>10) { dec[j]='1'; j++; b-=10; }
            dec[j]=b+'0'; j++;
            }
        if ((!a)&&(hex=="")) continue;
        if (a<10) a+='0'; else a+='A'-10;
        hex=AnsiString(char(a))+hex;
        }
    if (hex=="") hex="0";


    if ((i2)&&(i2<=i3))     // process fractional part *16
     for (hex+=".",j=i3-i2+2;j;j--)
        {
        for (a=0,b=0,i=i3;i>=i2;i--)
            {
            a=dec[i]-'0';
            b+=a<<4; dec[i]=(b%10)+'0'; b/=10;
            }
        if (b<10) b+='0'; else b+='A'-10;
        hex+=char(b);
        }
    if (sig<0) hex="-"+hex; hex+="h";
    return hex;
    }
//---------------------------------------------------------------------------

Alles anzeigen

Edit: So wie da mit der for Schleife umgesprungen wird... der Urheber muss Spanier sein...
@Make:
Irgendwie läuft das für große Zahlen aber immernoch nicht.
Die ganze Aufspalterei macht ja nur Sinn, wenn man damit beliebig große Zahlen verarbeiten kann.
Leider finde ich den Fehler nicht

lg
M

**Andy**

Wenn man unterstellt, dass die schnellste Methode darin besteht, mit Hilfe einer LUT aus der HEX-Darstellung die Binärdarstellung zu bekommen, sollte man ggf., um einfach die Anzahl zu berechnender "Binärziffern" zu reduzieren, die Dezimalzahl erst in HEX umwandeln. Beziehungsweise in ein Zahlenformat, welches "gerade so" in 32/64 Bit passt, also Basis 16^n.

Habe mir hier das kaskadierte Hornerschema angeschaut, prinzipiell funktioniert das ja mit allen Basen (heisst das so? )

Das "Problem" der Verwendung von Division und MOD würde ich ebenfalls in einer LUT abhandeln. Diese wäre dann abhängig von der Größe der Basis.
Die Anzahl der Elemente innerhalb der LUT ergibt sich bei Basis 0xF mit 15 Einträgen, bei Basis 0xFF sind es schon 1599 Elemente , bei 0xFFFF 159999 Einträge usw.
Somit hätte man bspw. bei Basis 16 um die Dezimalzahl 19912 in 0x4DC8 bzw. b100110111001000 "umzuwandeln" insgesamt nur 6 Zugriffe auf die LUT! Ohne bis auf eine Multiplikation pro Zugriff aufwändige Berechnungen!
Bisher habe ich das mit Zettel und Bleistift durchgespielt, inwieweit der Aufwand mit sehr langen Strings skaliert, kann ich nicht abschätzen. Werde das mal in ein Script gießen

**Mars**

Umwandlung von Hex in Bin ist "unendlich" schnell
Selbst die AutoIt Version (mit LUT und Ternärem gedöns) braucht für 2 Byte nur 46µs, auf meinem Intel Atom.
(Schätze ich mal, da 46µs im Schnitt gebraucht wurden, während die Zahlenlänge von 0 bis 31Bit erhöht wurde)
Für 1KB = 1024 Byte sind das ca. 24ms
In der Annahme, dass ASM ca. 500x schneller ist sind wie wieder bei unseren 46µs.
Diese Zeit ist vernachlässigbar, wichtig ist die Umrechnung von Dec -> Base 8/16/24, was halt am besten läuft...

**eukalyptus**

Hi

Ich hab hier noch eine ganz flotte BigNum-Version:

Spoiler anzeigen

[autoit]

$sDec = "123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890"

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

#cs
$sDec = ""
For $i = 1 To 10000
$sDec &= Random(0, 9, 1)
Next
#ce

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

$iTimer = TimerInit()
$sBin = _BigNum_DecToBin($sDec)
ConsoleWrite("! Time Decimal To Binary: " & StringFormat("%.2f", TimerDiff($iTimer)) & @CRLF)

[/autoit] [autoit][/autoit] [autoit]

$iTimer = TimerInit()
$sDec2 = _BigNum_BinToDec($sBin)
ConsoleWrite("! Time Binary To Decimal: " & StringFormat("%.2f", TimerDiff($iTimer)) & @CRLF & @CRLF)

[/autoit] [autoit][/autoit] [autoit]

If $sDec2 = $sDec Then
ConsoleWrite("+ Richtig:" & @CRLF & "+ " & $sDec & @CRLF & "+ " & $sDec2 & @CRLF & "+ " & $sBin & @CRLF & @CRLF)
Else
ConsoleWrite("! Falsch:" & @CRLF & "! " & $sDec & @CRLF & "! " & $sDec2 & @CRLF & "! " & $sBin & @CRLF & @CRLF)
_Compare($sDec, $sDec2)
EndIf

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func _Compare($sX, $sY)
Local $aX = StringSplit($sX, "")
Local $aY = StringSplit($sY, "")

[/autoit] [autoit][/autoit] [autoit]

ConsoleWrite("! ")
For $i = 1 To $aX[0]
If $aX[$i] = $aY[$i] Then
ConsoleWrite("_")
Else
ConsoleWrite("|")
ExitLoop
EndIf
Next

[/autoit] [autoit][/autoit] [autoit]

ConsoleWrite(@CRLF)
EndFunc ;==>_Compare

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func _BigNum_DecToBin($sDec)
Local $tChr = DllStructCreate("char[65];")
Local $sRet = ""
While Not ($sDec = "0")
DllCall("msvcrt.dll", "ptr:cdecl", "_i64toa", "int64", __BigNum_DecToBinDiv($sDec), "struct*", $tChr, "int", 2)
$sRet = StringRight("0000000000000000000000000000000000000000000" & DllStructGetData($tChr, 1), 43) & $sRet
WEnd
Return StringRegExpReplace($sRet, "^0+([^0]|0$)", "\1", 1)
EndFunc ;==>_BigNum_DecToBin

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func _BigNum_BinToDec($sBin)
Local Const $cPOT = 32
Local Const $cDVS = Int(2 ^ $cPOT)
Local $aBin = StringRegExp($sBin, '\A.{' & $cPOT - (Ceiling(StringLen($sBin) / $cPOT) * $cPOT - StringLen($sBin)) & '}|.{' & $cPOT & '}+', 3)
Local $aResult, $sTmp, $sPot = "1", $sDec = "0"
For $i = UBound($aBin) - 1 To 0 Step -1
$sTmp = $sPot
$aResult = DllCall("msvcrt.dll", "uint64:cdecl", "_strtoui64", "str", $aBin[$i], "ptr", 0, "int", 2)
__BigNum_BinToDecMul($sTmp, $aResult[0])
__BigNum_BinToDecAdd($sDec, $sTmp)
__BigNum_BinToDecMul($sPot, $cDVS)
Next
Return StringRegExpReplace($sDec, "^0+([^0]|0$)", "\1", 1)
EndFunc ;==>_BigNum_BinToDec

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func __BigNum_BinToDecAdd(ByRef $sX, $sY)
Local $iTmp = StringLen($sX), $iLen = StringLen($sY), $iCar = 0, $sRet = ""
If $iLen < $iTmp Then $iLen = $iTmp
For $i = 1 To $iLen Step 18
$iTmp = Int(StringRight($sX, 18)) + Int(StringRight($sY, 18)) + $iCar
$sX = StringTrimRight($sX, 18)
$sY = StringTrimRight($sY, 18)
If ($iTmp > 999999999999999999) Then
$iTmp = StringRight($iTmp, 18)
$sRet = $iTmp & $sRet
$iCar = 1
Else
$iTmp = StringRight("000000000000000000" & $iTmp, 18)
$sRet = $iTmp & $sRet
$iCar = 0
EndIf
Next
$sX = StringRegExpReplace($iCar & $sRet, "^0+([^0]|0$)", "\1", 1)
EndFunc ;==>__BigNum_BinToDecAdd

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func __BigNum_BinToDecMul(ByRef $sX, $iY)
Local $aX = StringRegExp($sX, '\A.{' & 6 - (Ceiling(StringLen($sX) / 6) * 6 - StringLen($sX)) & '}|.{6}+', 3)
For $i = 0 To UBound($aX) - 1
$aX[$i] = Int($aX[$i]) * $iY
Next
Local $iCar = 0, $iTmp
$sX = ""
For $i = UBound($aX) - 1 To 0 Step -1
$aX[$i] += $iCar
$iCar = Floor($aX[$i] / 1000000)
$iTmp = Mod($aX[$i], 1000000)
If $iTmp <= 1000000 Then $iTmp = StringRight("000000" & $iTmp, 6)
$sX = $iTmp & $sX
Next
If $iCar > 0 Then $sX = $iCar & $sX
$sX = StringRegExpReplace($sX, "^0+([^0]|0$)", "\1", 1)
EndFunc ;==>__BigNum_BinToDecMul

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func __BigNum_DecToBinDiv(ByRef $sX)
Local Const $cDVS = 8796093022208
Local $sRet = "", $iRem = StringLeft($sX, 15), $iTmp = 0, $iTrm = 6, $iLen
$sX = StringTrimLeft($sX, 15)
$iTmp = Floor($iRem / $cDVS)
$sRet &= $iTmp
$iRem -= $iTmp * $cDVS
While StringLen($sX) > 0
$iTrm = 15 - StringLen($iRem)
$iTmp = StringLeft($sX, $iTrm)
$iLen = StringLen($iTmp)
$iRem &= $iTmp
$sX = StringTrimLeft($sX, $iTrm)
$iTmp = Floor($iRem / $cDVS)
$iTmp = StringRight("000000000000000" & $iTmp, $iLen)
$sRet &= $iTmp
$iRem -= $iTmp * $cDVS
WEnd
$sX = StringRegExpReplace($sRet, "^0+([^0]|0$)", "\1", 1)
Return $iRem
EndFunc ;==>__BigNum_DecToBinDiv

[/autoit]

lgE

**Andy**

Hi,
habe das Hornerschema vom Papier nach AutoIt umgesetzt.
Für die HEX-Darstellung (Basis 16) ist das Verfahren sogar recht fix, allerdings wird es bei Binär (Basis 2) recht zäh...kein Wunder, für jedes einzelne Bit muss der gesamte String durchgerechnet werden.
Die HEX-"Umrechnung" kann man natürlich dahingehend optimieren, die Zahlen nicht zu dividieren und den Rest zu bestimmen, sondern direkt per LUT anzusprechen! Das werde ich in ASM umsetzen!

Für die Berechnung könnte man eine Basis von bspw. 256 oder 1024 heranziehen,dann geht die Rechnerei noch schneller, allerdings kann man dann Aufgrund der Größe der benötigten LUT diese nicht mehr einsetzen...
Dann bliebe die Berechnung, ich vermute stark, das ist immer noch langsamer als die Methode mit der LUT.
Schaumamal...

Spoiler anzeigen

[autoit]

;umrechnung dezimalstring in hex und binär
$dez = "123456789"

[/autoit] [autoit][/autoit] [autoit]

For $i = 1 To 5 ;bissl stringlänge aufbauen^^
$dez &= $dez
Next

[/autoit] [autoit][/autoit] [autoit]

$len = StringLen($dez)
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $len = ' & $len & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

$t = TimerInit()
$hex = _DecToHex_16($dez)
$m = TimerDiff($t)
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $hex = ' & $hex & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $m = ' & $m & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

$t = TimerInit()
$bin = _DecToBin($dez)
$m = TimerDiff($t)
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $bin = ' & $bin & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $m = ' & $m & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func _DecToHex_16($dez)
;by Andy nach Hornerschema
$basis = 16
$len = StringLen($dez)
If Mod($len, 2) Then ;wenn stringlänge nicht durch 2 teilbar
$dez = "0" & $dez ;"0" vorne dranhängen
$len += 1 ;länge anpassen
EndIf

[/autoit] [autoit][/autoit] [autoit]

$erg = "" ;ergebnis als Hex-string

[/autoit] [autoit][/autoit] [autoit]

While StringLen($dez) > 2 ;so lange, bis letzte Ziffer erreicht
$rest = 0 ;rest der division
$dez2 = "" ;neuer zahlenstring im zwischenspeicher
$len = StringLen($dez) ;stringlänge
If Mod($len, 2) Then ;wenn stringlänge nicht durch 2 teilbar
$dez = "0" & $dez ;"0" vorne dranhängen
$len += 1 ;länge anpassen
EndIf

[/autoit] [autoit][/autoit] [autoit]

For $i = 1 To $len Step 2 ;den gesamten string durchlaufen
$n = 100 * $rest + Number(StringMid($dez, $i, 2));zahl, die geteilt und geMODed werden muss
$zahl = Int($n / $basis);DIV
$u = "" ;zahl auffüllen auf 2 stellen
If $zahl < 10 And $zahl > 0 Then $u = "0"
$dez2 &= $u & String($zahl);neuer zahlenstring in zwischenspeicher
$rest = Mod($n, $basis) ;rest der division
Next
$erg = Hex($rest, 1) & $erg ;ergebnis-hexstring
$dez = $dez2 ;Zahlenstring aus zwischenspeicher
WEnd

[/autoit] [autoit][/autoit] [autoit]

Return "0x" & $erg

[/autoit] [autoit][/autoit] [autoit]

EndFunc ;==>_DecToHex_16

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func _DecToBin($dez) ;string
;by Andy nach Hornerschema
While StringLeft($dez, 1) = "0"
$dez = StringTrimLeft($dez, 1)
WEnd
$basis = 2
$len = StringLen($dez)
$erg = "" ;ergebnis als Hex-string
While StringLen($dez) > 0 ;so lange, bis letzte Ziffer erreicht
$rest = 0 ;rest der division
$dez2 = "" ;neuer zahlenstring im zwischenspeicher
$len = StringLen($dez) ;stringlänge
For $i = 1 To $len ;den gesamten string durchlaufen
$n = 10 * $rest + Number(StringMid($dez, $i, 1));zahl, die geteilt und geMODed werden muss
$zahl = Int($n / $basis);DIV
$rest = Mod($n, $basis) ;rest der division
$dez2 &= String($zahl) ;neuer zahlenstring in zwischenspeicher
Next
$erg = Hex($rest, 1) & $erg ;ergebnis-hexstring
$dez = $dez2 ;Zahlenstring aus zwischenspeicher
While StringLeft($dez, 1) = "0"
$dez = StringTrimLeft($dez, 1)
WEnd
WEnd
Return $erg

[/autoit] [autoit][/autoit] [autoit]

EndFunc ;==>_DecToBin

[/autoit] [autoit][/autoit] [autoit][/autoit]

**Mars**

Wenn ich das richtig sehe ist die Methode von Make ziemlich ähnlich.
Habe diese mal so umgebaut, dass keine Stringoperationen mehr vorkommen (nur noch Arrays), das Redim rausgenommen, die Ubounds und Pointer vereinfacht usw. Im Endeffekt gab das aber kaum einen Tempovorteil zur Stringversion. Allerdings lässt sich die Arrayversion nahezu 1 zu 1 in ASM übersetzen.

Skript

[autoit]

Global $sDec
Global $iTimer, $iTime
Global $iCnt = 1000
Global $sHex

[/autoit] [autoit][/autoit] [autoit]

For $i = 1 To $iCnt Step 1
$sDec = _RandomDec(30)
$iTimer = TimerInit()
DecToBin($sDec) ; Einfach mal ohne Return. Ist ja nur zum Test
$iTime += TimerDiff($iTimer)
ToolTip($i & @CRLF)
;~ ConsoleWrite($sDec & ' -> ' & $sHex & @CRLF)
Next
ToolTip('')
ConsoleWrite('Time: ' & Round(1000*$iTime/$iCnt,0) & ' µs' & @CRLF)

[/autoit] [autoit][/autoit] [autoit]

Func _RandomDec($iLen)
Local $sRet = ''
For $i = 1 To $iLen Step 1
$sRet &= Random(0, 9, 1)
Next
Return $sRet
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func DecToBin($sNumber)
Local $aiBit[Ceiling(StringLen($sNumber)*0.41524101186092)], $product, $aDec = StringSplit($sNumber, ''), $u = 0
For $i = 1 To $aDec[0]
$carry = $aDec[$i]
For $n = 0 To $u
$product = $aiBit[$n] * 10 + $carry
$aiBit[$n] = BitAND($product, 255)
$carry = BitAND($product, 65280) / 256
Next
If $carry Then
$u += 1
$aiBit[$u] = $carry
EndIf
Next
If UBound($aiBit) > $u Then ReDim $aiBit[$u + 1]
Return StringReverse(StringFromASCIIArray($aiBit, 0, -1, 1))
EndFunc

[/autoit]

Die Komplexität ist leider Quadratisch (schätze ich jedenfalls. ggf auch n*logn, das kann ich mit Wolfram Alpha nicht richtig fitten...
[Blockierte Grafik: http://i.imgur.com/AkSe3vc.png]

lg
M

**eukalyptus**

Ich hab jetzt meine BigNum Version in ASM umgesetzt

Für eine etwa 40.000 stellige Dezimalzahl braucht es ca ~~25ms~~:
Edit: Durch kleines Speedupdate nu ca 20ms

Spoiler anzeigen

[autoit]

#AutoIt3Wrapper_UseX64=n

[/autoit] [autoit][/autoit] [autoit]

;#include "FASM.au3"

[/autoit] [autoit][/autoit] [autoit]

;Global $bOPCode = _FASM_Compile("_ASM_DecToHex32")
Global $_pASM_DecToHex = _FASM_StructCreateBCA16("0x5589E583EC048B75088B4D0C8B551089F7F30F6F3AF30F6F7210F30F6F6A20660FEFE4F30F6F5A3031DB909090909090F30F6F06660FFAC7660F6FC8660F60C4660FF5C5660F3840C3660F3802C0660F3802C0660FDBCE660F73D908660FFEC1660F7E0783C30183C60983C70483E9097FBE8B750889F789D9890C24BB00CA9A3B9090909090909090909090909090908B0C2489FE31C090909090909090909031D2F7E3030683D200891683C60483E9017FED890783C704832C24017FD283C4045DC20C00")
;$bOPCode = _FASM_Compile("_ASM_HexToStr32")
Global $_pASM_HexToStr = _FASM_StructCreateBCA16("0x8B7424048B4C24088B7C240C01CE66BBF00F83EE018A0688C46621D8C0E8043C0A7C020407043080FC0A7C0380C40780C43066890783C70283E9017FD5C20C00")
;$bOPCode = _FASM_Compile("_ASM_HexToBinStr32")
Global $_pASM_HexToBinStr = _FASM_StructCreateBCA16("0x8B7424048B4C24088B7C240C01CE66BBF00F83EE018A0688C46621D8C0E804BA30303030A801740681CA00000001A802740681CA00000100A804740681CA00010000A808740383CA01891783C704BA30303030F6C401740681CA00000001F6C402740681CA00000100F6C404740681CA00010000F6C408740383CA01891783C70483E9017F8CC20C00")

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

$sDec = "1234567890"

[/autoit] [autoit][/autoit] [autoit]

For $i = 1 To 12
$sDec &= $sDec
Next

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

ConsoleWrite("! Dec Len: " & StringLen($sDec) & @CRLF & "> " & $sDec & @CRLF & @CRLF)

[/autoit] [autoit][/autoit] [autoit]

Global $iTimer = TimerInit()
$sHex = _BigDecToHex($sDec)
ConsoleWrite("! Time: " & TimerDiff($iTimer) & @CRLF & @CRLF)
ConsoleWrite("> " & $sHex & @CRLF & @CRLF)

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func _BigDecToHex(ByRef $sDec, $iMode = 2)
Local $iLen = StringLen($sDec)
If Mod($iLen, 9) Then
$iLen += 9 - Mod($iLen, 9)
$sDec = StringRight("000000000" & $sDec, $iLen)
EndIf
Local $tDec = DllStructCreate("char[" & $iLen & "]; byte[16];")
DllStructSetData($tDec, 1, $sDec)

[/autoit] [autoit][/autoit] [autoit]

Local $tVal = DllStructCreate("byte[64];")
DllStructSetData($tVal, 1, "0x303030303030303030303030303030300000000000000000FF000000000000001027E80364000A001027E80364000A0010270000102700000100000001000000")

[/autoit] [autoit][/autoit] [autoit]

DllCallAddress("none", $_pASM_DecToHex, "struct*", $tDec, "uint", $iLen, "struct*", $tVal)

[/autoit] [autoit][/autoit] [autoit]

Switch $iMode
Case 1 ;Hex String
Local $tHex = DllStructCreate("char[" & $iLen & "];")
DllCallAddress("none", $_pASM_HexToStr, "struct*", $tDec, "uint", $iLen / 18 * 8, "struct*", $tHex)
Return StringRegExpReplace(DllStructGetData($tHex, 1), "^0+([^0]|0$)", "\1", 1)

[/autoit] [autoit][/autoit] [autoit]

Case 2 ;Bin String
Local $tBin = DllStructCreate("char[" & $iLen * 4 & "];")
DllCallAddress("none", $_pASM_HexToBinStr, "struct*", $tDec, "uint", $iLen / 18 * 8, "struct*", $tBin)
Return StringRegExpReplace(DllStructGetData($tBin, 1), "^0+([^0]|0$)", "\1", 1)

[/autoit] [autoit][/autoit] [autoit]

Case Else ;Hex
Local $tHex = DllStructCreate("byte[" & Ceiling($iLen / 18 * & "];", DllStructGetPtr($tDec))
Return DllStructGetData($tHex, 1)

[/autoit] [autoit][/autoit] [autoit]

EndSwitch
EndFunc ;==>_BigDecToHex

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

#ASM _ASM_DecToHex32
# use32

[/autoit] [autoit][/autoit] [autoit]

# push ebp
# mov ebp, esp
# sub esp, 4

[/autoit] [autoit][/autoit] [autoit]

;#######################################################
;# Char to NumberArray
;#######################################################

[/autoit] [autoit][/autoit] [autoit]

# mov esi, [ebp+8]
# mov ecx, [ebp+12]
# mov edx, [ebp+16]

[/autoit] [autoit][/autoit] [autoit]

# mov edi, esi

[/autoit] [autoit][/autoit] [autoit]

# movdqu xmm7, [edx]
# movdqu xmm6, [edx+16]
# movdqu xmm5, [edx+32]
# pxor xmm4, xmm4
# movdqu xmm3, [edx+48]

[/autoit] [autoit][/autoit] [autoit]

;xmm7 = 0x30303030303030303030303030303030
;xmm6 = 0x0000000000000000FF00000000000000
;xmm5 = 10000, 1000, 100, 10, 10000, 1000, 100, 10
;xmm4 = 0, 0, 0, 0
;xmm3 = 10000, 10000, 1, 1

[/autoit] [autoit][/autoit] [autoit]

# xor ebx, ebx
# align 16
# _LoopChar:
# movdqu xmm0, [esi]
# psubd xmm0, xmm7
# movdqa xmm1, xmm0

[/autoit] [autoit][/autoit] [autoit]

# punpcklbw xmm0, xmm4 ;Char 1-8
# pmaddwd xmm0, xmm5
# pmulld xmm0, xmm3
# phaddd xmm0, xmm0
# phaddd xmm0, xmm0 ;12345678.

[/autoit] [autoit][/autoit] [autoit]

# pand xmm1, xmm6
# psrldq xmm1, 8
# paddd xmm0, xmm1 ;123456789

[/autoit] [autoit][/autoit] [autoit]

# movd [edi], xmm0

[/autoit] [autoit][/autoit] [autoit]

# add ebx, 1
# add esi, 9
# add edi, 4
# sub ecx, 9
# jg _LoopChar

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

;#######################################################
;# BigDiv
;#######################################################

[/autoit] [autoit][/autoit] [autoit]

# mov esi, [ebp+8]
# mov edi, esi
# mov ecx, ebx

[/autoit] [autoit][/autoit] [autoit]

# mov [esp], ecx
# mov ebx, 1000000000

[/autoit] [autoit][/autoit] [autoit]

;eax = Number/Result
;ebx = MulFactor
;ecx = Count
;edx = Result

[/autoit] [autoit][/autoit] [autoit]

# align 16
# _LoopDiv:
# mov ecx, [esp]
# mov esi, edi

[/autoit] [autoit][/autoit] [autoit]

# xor eax, eax ;Tmp = 0

[/autoit] [autoit][/autoit] [autoit]

# align 16
# _LoopBigDiv:
# xor edx, edx ;???
# mul ebx ;carry * 100000000

[/autoit] [autoit][/autoit] [autoit]

# add eax, [esi]
# adc edx, 0

[/autoit] [autoit][/autoit] [autoit]

# mov [esi], edx

[/autoit] [autoit][/autoit] [autoit]

# add esi, 4
# sub ecx, 1
# jg _LoopBigDiv

[/autoit] [autoit][/autoit] [autoit]

# mov [edi], eax ;write carry

[/autoit] [autoit][/autoit] [autoit]

# add edi, 4 ;next ArrayIndex
# sub dword[esp], 1
# jg _LoopDiv

[/autoit] [autoit][/autoit] [autoit]

# add esp, 4
# pop ebp

[/autoit] [autoit][/autoit] [autoit]

# ret 12
#ASMEND

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

#ASM _ASM_HexToBinStr32
# use32

[/autoit] [autoit][/autoit] [autoit]

# mov esi, [esp+4]
# mov ecx, [esp+8]
# mov edi, [esp+12]

[/autoit] [autoit][/autoit] [autoit]

# add esi, ecx
# mov bx, 0x0FF0

[/autoit] [autoit][/autoit] [autoit]

# _Loop:
# sub esi, 1
# mov al, [esi]

[/autoit] [autoit][/autoit] [autoit]

# mov ah, al
# and ax, bx
# shr al, 4

[/autoit] [autoit][/autoit] [autoit]

# mov edx, 0x30303030
# test al, 1
# jz _L2
# or edx, 0x01000000
# _L2:
# test al, 2
# jz _L4
# or edx, 0x00010000
# _L4:
# test al, 4
# jz _L8
# or edx, 0x00000100
# _L8:
# test al, 8
# jz _H1
# or edx, 0x00000001
# _H1:

[/autoit] [autoit][/autoit] [autoit]

# mov [edi], edx
# add edi, 4

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

# mov edx, 0x30303030
# test ah, 1
# jz _H2
# or edx, 0x01000000
# _H2:
# test ah, 2
# jz _H4
# or edx, 0x00010000
# _H4:
# test ah, 4
# jz _H8
# or edx, 0x00000100
# _H8:
# test ah, 8
# jz _HN
# or edx, 0x00000001
# _HN:

[/autoit] [autoit][/autoit] [autoit]

# mov [edi], edx
# add edi, 4

[/autoit] [autoit][/autoit] [autoit]

# sub ecx, 1
# jg _Loop

[/autoit] [autoit][/autoit] [autoit]

# ret 12
#ASMEND

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

#ASM _ASM_HexToStr32
# use32

[/autoit] [autoit][/autoit] [autoit]

# mov esi, [esp+4]
# mov ecx, [esp+8]
# mov edi, [esp+12]

[/autoit] [autoit][/autoit] [autoit]

# add esi, ecx
# mov bx, 0x0FF0

[/autoit] [autoit][/autoit] [autoit]

# _Loop:
# sub esi, 1
# mov al, [esi]

[/autoit] [autoit][/autoit] [autoit]

# mov ah, al
# and ax, bx
# shr al, 4

[/autoit] [autoit][/autoit] [autoit]

# cmp al, 0xA
# jl _Dec
# add al, 7
# _Dec:
# add al, 0x30

[/autoit] [autoit][/autoit] [autoit]

# cmp ah, 0xA
# jl _Dec2
# add ah, 7
# _Dec2:
# add ah, 0x30

[/autoit] [autoit][/autoit] [autoit]

# mov [edi], ax
# add edi, 2

[/autoit] [autoit][/autoit] [autoit]

# sub ecx, 1
# jg _Loop

[/autoit] [autoit][/autoit] [autoit]

# ret 12
#ASMEND

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

;#cs
Func _FASM_StructCreateBCA16($bBinaryCode)
Local $iSize = BinaryLen($bBinaryCode)
Local $aResult = DllCall("kernel32.dll", "ptr", "VirtualAlloc", "ptr", 0, "ulong_ptr", $iSize + 16, "dword", 0x00001000, "dword", 0x00000040)
If @error Or Not $aResult[0] Then Return SetError(1, 0, False)
Local $pStruct = Number($aResult[0])
$pStruct = $pStruct + 16 - Mod($pStruct, 16)
Local $tStruct = DllStructCreate("byte[" & $iSize & "];", $pStruct)
DllStructSetData($tStruct, 1, $bBinaryCode)
Return $pStruct
EndFunc ;==>_FASM_StructCreateBCA16
;#ce

[/autoit]

Um die Ergebnisse zu überprüfen, verwende ich übrigens: http://www.mobilefish.com/services/big_number/big_number.php

E

**Andy**

eukalyptus hat mal wieder gerockt...
Wie bereits gezeigt ist die Umwandlung von HEX nach BIN völlig zeitunkritisch!
Die größte Zeit wird von DEC nach HEX benötigt. Mal sehen, ob mein Code, der (wie sehr schön von eukalyptus gezeigt) das vermeidbare DIV benutzt, einige Takte schneller ist.
Ich hoffe, am Wochenende etwas verwertbares vorzeigen zu können^^

**eukalyptus**

Halleluja!
Der 64Bit Modus gibt ordentlich Gas!

Eine Dezimalzahl mit 327680 benötigt auf meinem Rechner mit der X86 Variante über 1 Sekunde für die Umwandlung.
Der X64-Code ist bereits nach guten 200ms fertig!

Und ich denke, es gibt noch etwas Optimierungspotenzial

Zitat von Andy

...der (wie sehr schön von eukalyptus gezeigt) das vermeidbare DIV benutzt...

Das ist passiert und war eigentlich keine Absicht
Ich wollte schon durch 2^24 dividieren, da ich vorerst nicht wusste, wie ich durch 2^32 dividieren soll - bis es mir plötzlich wie Schuppen von den Augen fiel...

E

**Mars**

läuft leider auf meinem Intel Atom 330 läuft der Code leider nicht.
Auf nem anderen Rechner (mit i5) teste ich das später, hab jetzt leider keine Zeit...

lg
M

**eukalyptus**

Ich verwende mit pmulld mindestens einen Befehl von SSEv4.1
Ältere Prozessoren werden das noch nicht unterstützen!

~~Ich könnte auch eine SSEv3.3 oder im extremfall eine SSEv2 basteln; wenn gewünscht...~~

Edit: Eine alternative Version benutzt nur SSEv2 Befehle und sollte auf älteren Prozessoren laufen... Siehe Post 38

E