Hi
i found some examples where
we want to divide eax by 10,
and they do this:
mov edx, 0CCCCCCCDh ;= 3435973837
mul edx
shr edx, 03h
and we get edx = quotient and
the magic number is 0CCCCCCCDh = 3435973837.
What is the magic number if we want to divide by 100
and what to do ?
I have a Magic Divider app that I downloaded somewhere and it's been so long that I don't recall where. For a divider of 10 it returns:
MagicNumber = 3435973837
mov eax,X
mov edx, MagicNumber
mul edx
SHR edx, 3
And for 100:
MagicNumber = 2748779069
mov eax,X
mov edx, MagicNumber
inc eax
mul edx
SHR edx, 6
Try searching for magic divider svin.
And IIRC Agner Fog explains the method in his optimization manuals (http://www.agner.org/optimize/).
the app was written by qWord
he also wrote a set of macros
http://www.masmforum.com/archive2012/6717_MagicNumber64.zip (http://www.masmforum.com/archive2012/6717_MagicNumber64.zip)
for a divisor of 10, in 32-bit mode, it gives:
mov eax,X
mov edx,0CCCCCCCDh
mul edx
shr edx,3
; edx = quotient
if you want the remainder, you can add a little code...
mov ecx,X
mov eax,0CCCCCCCDh
mul ecx
shr edx,3
; edx = quotient
imul eax,edx,10
sub ecx,eax
; ecx = remainder
about 20 clock cycles, i think
for a divisor of 100.....
mov ecx,X
mov eax,51EB851Fh
mul ecx
shr edx,5
; edx = quotient
imul eax,edx,100
sub ecx,eax
; ecx = remainder
RuiLoureiro,
I think we are talking about expscale? 0<=|expscale|<= 4932
so I use MagicNumber=232/100=42949672.96=42949673
mov eax,expscale
mov esi,eax
mov edx,42949673;2^32/100
mul edx
imul edx,100;edx = quotient*100
sub esi,edx;esi = remainder of the division by 100
right Mikl - that won't work over the entire range, but it will work to 4932 (9999, i think) :P
makes the code a little simpler if you put the multiplier in EAX, though...
mov ecx,expscale
mov eax,42949673 ;2^32/100
mul ecx ;edx = quotient
imul eax,edx,100 ;eax = quotient*100
sub ecx,eax ;ecx = remainder of the division by 100
~18 cycles
all code.data
table0 db "000102030405060708091011121314151617181920212223242526272829"
db "303132333435363738394041424344454647484950515253545556575859"
db "606162636465666768697071727374757677787980818283848586878889"
db "90919293949596979899"
.code
mov word ptr [edi+21],'+E'
mov eax,iExp
mov edx,eax
sar edx,31
xor eax,edx
sub eax,edx; neg eax
and edx,2
add byte ptr [edi+22],dl; "+" or "-"
mov esi,eax
mov edx,42949673;2^32/100
mul edx
mov ax,word ptr table0[edx*2] ;edx = quotient of the division by 100
mov word ptr [edi+23],ax
lea eax,[edx*4]
shl edx,2
lea edx,[edx+edx*2]
lea edx,[eax+edx*8] ;edx = quotient*100
sub esi,edx ;esi = remainder of the division by 100
mov ax,word ptr table0[esi*2]
mov word ptr [edi+25],ax
in 2008-2009
here is the original thread, with the attachment missing...
http://www.masmforum.com/board/index.php?topic=9937.0 (http://www.masmforum.com/board/index.php?topic=9937.0)
I downloaded the one that I have not later than 2004.
this is the one i use
http://www.masmforum.com/archive2012/6717_MagicNumber64.zip (http://www.masmforum.com/archive2012/6717_MagicNumber64.zip)
but, if you look at the old archive sites, there are a few files with the word "magic" :P
For 32 bits
http://win32assembly.programminghorizon.com/source.html (http://win32assembly.programminghorizon.com/source.html)
Quote from: ToutEnMasm on May 13, 2013, 02:59:16 PM
For 32 bits
http://win32assembly.programminghorizon.com/source.html (http://win32assembly.programminghorizon.com/source.html)
That's the one I have.
Well, this trick (I would call it some kind of fix point arithmetic) is surly not new - the source code from AMD's optimization manuals reference papers from 1988 and 1994.
Henry S. Warren Jr. wrote in book «Hacker's delight» about this trick
i think the method pre-dates the IBM PC :biggrin:
i seem to recall some 6502 code to do this
Hi,
When i read the code from Mikl__ i saw that
his magic number was
42949673 ;2^32/100
So we could get the magic for 10 = 2^32/10 = 429496730
The question was:
is this correct ? The answer is:
NO ! So the next
DivideREGby10 and
DivideREGby100 are not correct.
. Well we may use
DivideREGby10 if number is <
1073741829 . But we CANNOT use DivideREGby100 because it is wrong
at least for numbers 10 to 129 ... and much much more !
Thanks all of you :t
Please try it may be i have made something wrong.
Quote
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
DivideREGby10 MACRO ireg
; note: we may use it but ...
mov ecx, ireg
mov eax, 429496730 ; =2^32/10
mul ecx
; ---------------
; edx = quotient
; ---------------
imul eax, edx,10
; -------------
; ecx=remainder
; -------------
sub ecx, eax
ENDM
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
DivideREGby100 MACRO ireg
; note: this is wrong
mov ecx, ireg
mov eax, 42949673 ;2^32/100
mul ecx
; ---------------
; edx = quotient
; ---------------
imul eax, edx,100 ; here it was 10 but the result is the same
; -------------
; ecx=remainder
; -------------
sub ecx, eax
ENDM
we get this:Division by 101073741829
40000005
*** STOP - NOT EQUAL --- E N D ---***
---------------------------------------------------
Division by 100
*** STOP - NOT EQUAL ---*** 10
0000000A
*** STOP - NOT EQUAL ---*** 11
0000000B
*** STOP - NOT EQUAL ---*** 12
0000000C
*** STOP - NOT EQUAL ---*** 13
0000000D
*** STOP - NOT EQUAL ---*** 14
0000000E
*** STOP - NOT EQUAL ---*** 15
0000000F
*** STOP - NOT EQUAL ---*** 16
00000010
*** STOP - NOT EQUAL ---*** 17
00000011
*** STOP - NOT EQUAL ---*** 18
00000012
*** STOP - NOT EQUAL ---*** 19
00000013
*** STOP - NOT EQUAL ---*** 20
00000014
*** STOP - NOT EQUAL ---*** 21
00000015
*** STOP - NOT EQUAL ---*** 22
00000016
*** STOP - NOT EQUAL ---*** 23
00000017
*** STOP - NOT EQUAL ---*** 24
00000018
*** STOP - NOT EQUAL ---*** 25
00000019
*** STOP - NOT EQUAL ---*** 26
0000001A
*** STOP - NOT EQUAL ---*** 27
0000001B
*** STOP - NOT EQUAL ---*** 28
0000001C
*** STOP - NOT EQUAL ---*** 29
0000001D
*** STOP - NOT EQUAL ---*** 30
0000001E
*** STOP - NOT EQUAL ---*** 31
0000001F
*** STOP - NOT EQUAL ---*** 32
00000020
*** STOP - NOT EQUAL ---*** 33
00000021
*** STOP - NOT EQUAL ---*** 34
00000022
*** STOP - NOT EQUAL ---*** 35
00000023
*** STOP - NOT EQUAL ---*** 36
00000024
*** STOP - NOT EQUAL ---*** 37
00000025
*** STOP - NOT EQUAL ---*** 38
00000026
*** STOP - NOT EQUAL ---*** 39
00000027
*** STOP - NOT EQUAL ---*** 40
00000028
*** STOP - NOT EQUAL ---*** 41
00000029
*** STOP - NOT EQUAL ---*** 42
0000002A
*** STOP - NOT EQUAL ---*** 43
0000002B
*** STOP - NOT EQUAL ---*** 44
0000002C
*** STOP - NOT EQUAL ---*** 45
0000002D
*** STOP - NOT EQUAL ---*** 46
0000002E
*** STOP - NOT EQUAL ---*** 47
0000002F
*** STOP - NOT EQUAL ---*** 48
00000030
*** STOP - NOT EQUAL ---*** 49
00000031
*** STOP - NOT EQUAL ---*** 50
00000032
*** STOP - NOT EQUAL ---*** 51
00000033
*** STOP - NOT EQUAL ---*** 52
00000034
*** STOP - NOT EQUAL ---*** 53
00000035
*** STOP - NOT EQUAL ---*** 54
00000036
*** STOP - NOT EQUAL ---*** 55
00000037
*** STOP - NOT EQUAL ---*** 56
00000038
*** STOP - NOT EQUAL ---*** 57
00000039
*** STOP - NOT EQUAL ---*** 58
0000003A
*** STOP - NOT EQUAL ---*** 59
0000003B
*** STOP - NOT EQUAL ---*** 60
0000003C
*** STOP - NOT EQUAL ---*** 61
0000003D
*** STOP - NOT EQUAL ---*** 62
0000003E
*** STOP - NOT EQUAL ---*** 63
0000003F
*** STOP - NOT EQUAL ---*** 64
00000040
*** STOP - NOT EQUAL ---*** 65
00000041
*** STOP - NOT EQUAL ---*** 66
00000042
*** STOP - NOT EQUAL ---*** 67
00000043
*** STOP - NOT EQUAL ---*** 68
00000044
*** STOP - NOT EQUAL ---*** 69
00000045
*** STOP - NOT EQUAL ---*** 70
00000046
*** STOP - NOT EQUAL ---*** 71
00000047
*** STOP - NOT EQUAL ---*** 72
00000048
*** STOP - NOT EQUAL ---*** 73
00000049
*** STOP - NOT EQUAL ---*** 74
0000004A
*** STOP - NOT EQUAL ---*** 75
0000004B
*** STOP - NOT EQUAL ---*** 76
0000004C
*** STOP - NOT EQUAL ---*** 77
0000004D
*** STOP - NOT EQUAL ---*** 78
0000004E
*** STOP - NOT EQUAL ---*** 79
0000004F
*** STOP - NOT EQUAL ---*** 80
00000050
*** STOP - NOT EQUAL ---*** 81
00000051
*** STOP - NOT EQUAL ---*** 82
00000052
*** STOP - NOT EQUAL ---*** 83
00000053
*** STOP - NOT EQUAL ---*** 84
00000054
*** STOP - NOT EQUAL ---*** 85
00000055
*** STOP - NOT EQUAL ---*** 86
00000056
*** STOP - NOT EQUAL ---*** 87
00000057
*** STOP - NOT EQUAL ---*** 88
00000058
*** STOP - NOT EQUAL ---*** 89
00000059
*** STOP - NOT EQUAL ---*** 90
0000005A
*** STOP - NOT EQUAL ---*** 91
0000005B
*** STOP - NOT EQUAL ---*** 92
0000005C
*** STOP - NOT EQUAL ---*** 93
0000005D
*** STOP - NOT EQUAL ---*** 94
0000005E
*** STOP - NOT EQUAL ---*** 95
0000005F
*** STOP - NOT EQUAL ---*** 96
00000060
*** STOP - NOT EQUAL ---*** 97
00000061
*** STOP - NOT EQUAL ---*** 98
00000062
*** STOP - NOT EQUAL ---*** 99
00000063
*** STOP - NOT EQUAL ---*** 100
00000064
*** STOP - NOT EQUAL ---*** 101
00000065
*** STOP - NOT EQUAL ---*** 102
00000066
*** STOP - NOT EQUAL ---*** 103
00000067
*** STOP - NOT EQUAL ---*** 104
00000068
*** STOP - NOT EQUAL ---*** 105
00000069
*** STOP - NOT EQUAL ---*** 106
0000006A
*** STOP - NOT EQUAL ---*** 107
0000006B
*** STOP - NOT EQUAL ---*** 108
0000006C
*** STOP - NOT EQUAL ---*** 109
0000006D
*** STOP - NOT EQUAL ---*** 110
0000006E
*** STOP - NOT EQUAL ---*** 111
0000006F
*** STOP - NOT EQUAL ---*** 112
00000070
*** STOP - NOT EQUAL ---*** 113
00000071
*** STOP - NOT EQUAL ---*** 114
00000072
*** STOP - NOT EQUAL ---*** 115
00000073
*** STOP - NOT EQUAL ---*** 116
00000074
*** STOP - NOT EQUAL ---*** 117
00000075
*** STOP - NOT EQUAL ---*** 118
00000076
*** STOP - NOT EQUAL ---*** 119
00000077
*** STOP - NOT EQUAL ---*** 120
00000078
*** STOP - NOT EQUAL ---*** 121
00000079
*** STOP - NOT EQUAL ---*** 122
0000007A
*** STOP - NOT EQUAL ---*** 123
0000007B
*** STOP - NOT EQUAL ---*** 124
0000007C
*** STOP - NOT EQUAL ---*** 125
0000007D
*** STOP - NOT EQUAL ---*** 126
0000007E
*** STOP - NOT EQUAL ---*** 127
0000007F
*** STOP - NOT EQUAL ---*** 128
00000080
*** STOP - NOT EQUAL ---*** 129
00000081
*** STOP - NOT EQUAL --- E N D ---***
:
; File: TestMagic10_1.asm
; by RuiLoureiro
;-----------------------------------
include \masm32\include\masm32rt.inc
.686
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
include Macros10.inc
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
.data
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
.code
;==============================================================================
start:
jmp _stop
print "Division by 10", 13, 10
mov esi, 0
jmp _next
_loop:
DivideREGby10 esi ; edx = quotient ecx=remainder
push ecx
push edx
;
mov eax, esi
xor edx, edx
mov ecx, 10
div ecx
;
pop ebx
pop ecx
cmp ebx, eax
jne _erro1
cmp ecx, edx
jne _erro1
_next: add esi, 1
or esi, esi
jns _loop
inkey " *** STOP - ALL EQUAL --- E N D ---*** "
jmp _stop
_erro1: print str$(esi),13,10
print hex$(esi),13,10
inkey " *** STOP - NOT EQUAL --- E N D ---*** "
;------------------------------------------------------------------------------
_stop: xor edi, edi ; cases
print "Division by 100", 13, 10
mov esi, 0
jmp _next1
_loop1:
DivideREGby100 esi ; edx = quotient ecx=remainder
push ecx
push edx
;
mov eax, esi
xor edx, edx
mov ecx, 10
div ecx
;
pop ebx
pop ecx
cmp ebx, eax
jne _erro2
cmp ecx, edx
jne _erro2
;
_next1: add esi, 1
or esi, esi
jns _loop1
inkey " *** STOP - ALL EQUAL --- E N D ---*** "
jmp _end
_erro2: print " *** STOP - NOT EQUAL ---*** "
print str$(esi),13,10
print hex$(esi),13,10
;
add esi, 1
add edi, 1
cmp edi, 120
jb _loop1
inkey " *** STOP - NOT EQUAL --- E N D ---*** "
_end:
exit
;*********************************************************************
end start
http://www.masmforum.com/board/index.php?topic=17027.msg142029#msg142029 (http://www.masmforum.com/board/index.php?topic=17027.msg142029#msg142029)
Quote
The simplified version...
For divide by 11, the magic reciprocal is 232 / 11 = 390451572 (remainder 4)
and multiplying by this number gives 12345 * 390451572 = 4820124656340
which doesn't look right, until you realize what we actually did what multiply by 232 and then divide by 11.
So, for the result, we can just divide by 232 again - which would be the same as just dividing by 11 in the first place.
Luckily for us, the result of a mul is naturally split into edx and eax, where edx represents the upper part multiplied by 232, so we just take edx directly as the result.
Sure enough...
12345 / 11 = 1122.27
12345 * 390451572 = 4820124656340 = 1122 * 232 + 1171350228 => 1122
That's the simplified version because we didn't take the 4 remainder into account, which leads to accumulated errors depending on what values you're dividing. As Dave said, it depends on the range you want to include.
To increase accuracy, you'd shift the magic value and add on a proportion of the remainder. Then shift the result back again to correct for the inherent shift in the magic value, which can effectively give you a few decimal places of accuracy (rounded, naturally.)
here's a piece of code that was originally written by Drizz and modified by me to squeeze out a couple clock cycles
(one of my favorite pieces of "Drizz code")
;EAX = 0 to 9999
mov edx,4294968 ;2^32/1000
mov ebx,10 ;per digit
mul edx ;extend first digit
mov ecx,edx ;digit 1 in CL
mul ebx ;second digit
mov ch,dl ;digit 2 in CH
mul ebx ;third digit
bswap ecx ;digits 1 & 2 up high
mov ch,dl ;digit 3 in CH
mul ebx ;digit 4 in DL
lea ecx,[edx+ecx+'0000'] ;combine and make ASCII
bswap ecx ;re-order bytes
;ECX = "0000" to "9999"
this is a good example of what we are talking about because we use a "magic" number that works over a certain range
it works for dividends in the 0 to 9999 range, but will undoubtedly fail for larger dividends
the reason for using a multiplier that only works over a certain range is so that we do not have to shift the result
if we wanted to divide by 1000, and work over the full range of the dword in EAX....
mov eax,X
mov edx,10624DD3h ;2^38 / 1000
mul edx
shr edx,6
; edx = quotient
notice that the multiplier is 2^38 / 1000
the 32-bit register displacement of EDX:EAX takes care of 32 of the shifts
the SHR EDX,6 takes care of the remaining 6 shifts
i have, in the past, written loops to test divider constants over the desired range to verify they work :P
you perform the divide with the constant, and with DIV, and compare the results
i usually start at low dividends and work up, and write the loop to exit on first failure
that's ok for 32-bit code, but can't be done for 64-bit dividers (it would take 400 years to loop)
Hey,
sometimes Dave has some good ideas
and he doesnt say anything :greensml:
That code, Dave, is good ! ;)
What about your health ?
I hope fine !!! :t
I think the tricky part of this algorithm is to adjust the constant factor such it has the required precision for the whole input range. We can maximize the precision by calculating 232/x in arbitrary precision and then normalize the result to bit 231 (of course correctly rounded). Due the normalization, these extra shifts come up.
For 1/1000 this could be:
232/1000 << 9 = 2199023263
Remarks that the algorithm from AMD increase the precision only as far as needed to reduce the shift count (IIRC).
Quote from: dedndave on May 14, 2013, 03:42:22 AM
here's a piece of code that was originally written by Drizz and modified by me to squeeze out a couple clock cycles
(one of my favorite pieces of "Drizz code")
Dave i tested your code, and
it is correct and we gain 130 cycles
more or less :t
credit to Drizz on that one :t
My programm division by 100
; masm windows console #
include \masm32\include\masm32rt.inc
.686
.code
start: mov esi,1000000000
mov ebx,100
@@: mov eax,42949673
mul esi
mov edi,edx
xor edx,edx
mov eax,esi
div ebx
cmp edi,eax
jne error
dec esi
jnz @b
inkey " *** STOP - ALL EQUAL --- E N D ---*** "
exit
error: print str$(esi),13,10
print str$(edi),13,10
print str$(eax),13,10
inkey " *** STOP - NOT EQUAL --- E N D ---*** "
exit
end startQuote*** STOP - ALL EQUAL --- E N D ---***
to calculate the exponential of this range is enough
This is my test program.
using DivideREGby100 or not
i get quotient NOT EQUAL
By the way, in my last test i did div by 10 not by 100. Sorry !
; File: TestMagic10_1x.asm
; by RuiLoureiro
;-----------------------------------
include \masm32\include\masm32rt.inc
.686
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
DivideREGby100 MACRO ireg
mov ecx, ireg
;42949673 Mikl
mov eax, 42949673 ;2^32/100 ----
mul ecx
; ---------------
; edx = quotient
; ---------------
;imul eax, edx,100
; -------------
; ecx=remainder
; -------------
;sub ecx, eax
ENDM
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
.code
;==============================================================================
start:
xor edi, edi ; cases
print "Division by 100", 13, 10
mov esi, 0
jmp _next1
_loop1:
mov eax,42949673 ; this is from
mul esi ; Mikl__
;mov edi,edx ;
;DivideREGby100 esi ; edx = quotient ecx=remainder
;push ecx
push edx
; -------------------------
; Divide EDX:EAX by 100=ecx
; -------------------------
mov eax, esi
xor edx, edx
mov ecx, 100
div ecx ; eax= quotient edx=remainder
;
pop ebx ; ebx = quotient ecx=remainder
;pop ecx
cmp ebx, eax ; quotient
jne _erro2
;
;cmp ecx, edx ; remainder
;jne _erro3
;
_next1: add esi, 1
jns _loop1
inkey " *** STOP - ALL EQUAL --- E N D ---*** "
jmp _end
_erro2: print " *** STOP - quotient NOT EQUAL ---*** "
print str$(esi),13,10
print hex$(esi),13,10
;
add esi, 1
add edi, 1
cmp edi, 120
jb _loop1
inkey " *** STOP - NOT EQUAL --- E N D ---*** "
jmp _end
_erro3: print " *** STOP - remainder NOT EQUAL ---*** "
print str$(esi),13,10
print hex$(esi),13,10
;
add esi, 1
add edi, 1
cmp edi, 120
jb _loop1
inkey " *** STOP - NOT EQUAL --- E N D ---*** "
jmp _end
_end:
exit
;***********************************************************************************************
end start
Division by 100
*** STOP - quotient NOT EQUAL ---*** 1073741899
4000004B
*** STOP - quotient NOT EQUAL ---*** 1073741999
400000AF
*** STOP - quotient NOT EQUAL ---*** 1073742099
40000113
*** STOP - quotient NOT EQUAL ---*** 1073742199
40000177
*** STOP - quotient NOT EQUAL ---*** 1073742299
400001DB
*** STOP - quotient NOT EQUAL ---*** 1073742399
4000023F
*** STOP - quotient NOT EQUAL ---*** 1073742499
400002A3
*** STOP - quotient NOT EQUAL ---*** 1073742599
40000307
*** STOP - quotient NOT EQUAL ---*** 1073742699
4000036B
*** STOP - quotient NOT EQUAL ---*** 1073742799
400003CF
*** STOP - quotient NOT EQUAL ---*** 1073742899
40000433
*** STOP - quotient NOT EQUAL ---*** 1073742999
40000497
*** STOP - quotient NOT EQUAL ---*** 1073743099
400004FB
*** STOP - quotient NOT EQUAL ---*** 1073743199
4000055F
*** STOP - quotient NOT EQUAL ---*** 1073743299
400005C3
*** STOP - quotient NOT EQUAL ---*** 1073743399
40000627
*** STOP - quotient NOT EQUAL ---*** 1073743499
4000068B
*** STOP - quotient NOT EQUAL ---*** 1073743599
400006EF
*** STOP - quotient NOT EQUAL ---*** 1073743699
40000753
*** STOP - quotient NOT EQUAL ---*** 1073743799
400007B7
*** STOP - quotient NOT EQUAL ---*** 1073743899
4000081B
*** STOP - quotient NOT EQUAL ---*** 1073743999
4000087F
*** STOP - quotient NOT EQUAL ---*** 1073744099
400008E3
*** STOP - quotient NOT EQUAL ---*** 1073744199
40000947
*** STOP - quotient NOT EQUAL ---*** 1073744299
400009AB
*** STOP - quotient NOT EQUAL ---*** 1073744399
40000A0F
*** STOP - quotient NOT EQUAL ---*** 1073744499
40000A73
*** STOP - quotient NOT EQUAL ---*** 1073744599
40000AD7
*** STOP - quotient NOT EQUAL ---*** 1073744699
40000B3B
*** STOP - quotient NOT EQUAL ---*** 1073744799
40000B9F
*** STOP - quotient NOT EQUAL ---*** 1073744899
40000C03
*** STOP - quotient NOT EQUAL ---*** 1073744999
40000C67
*** STOP - quotient NOT EQUAL ---*** 1073745099
40000CCB
*** STOP - quotient NOT EQUAL ---*** 1073745199
40000D2F
*** STOP - quotient NOT EQUAL ---*** 1073745299
40000D93
*** STOP - quotient NOT EQUAL ---*** 1073745399
40000DF7
*** STOP - quotient NOT EQUAL ---*** 1073745499
40000E5B
*** STOP - quotient NOT EQUAL ---*** 1073745599
40000EBF
*** STOP - quotient NOT EQUAL ---*** 1073745699
40000F23
*** STOP - quotient NOT EQUAL ---*** 1073745799
40000F87
*** STOP - quotient NOT EQUAL ---*** 1073745899
40000FEB
*** STOP - quotient NOT EQUAL ---*** 1073745999
4000104F
*** STOP - quotient NOT EQUAL ---*** 1073746099
400010B3
*** STOP - quotient NOT EQUAL ---*** 1073746199
40001117
*** STOP - quotient NOT EQUAL ---*** 1073746299
4000117B
*** STOP - quotient NOT EQUAL ---*** 1073746399
400011DF
*** STOP - quotient NOT EQUAL ---*** 1073746499
40001243
*** STOP - quotient NOT EQUAL ---*** 1073746599
400012A7
*** STOP - quotient NOT EQUAL ---*** 1073746699
4000130B
*** STOP - quotient NOT EQUAL ---*** 1073746799
4000136F
*** STOP - quotient NOT EQUAL ---*** 1073746899
400013D3
*** STOP - quotient NOT EQUAL ---*** 1073746999
40001437
*** STOP - quotient NOT EQUAL ---*** 1073747099
4000149B
*** STOP - quotient NOT EQUAL ---*** 1073747199
400014FF
*** STOP - quotient NOT EQUAL ---*** 1073747299
40001563
*** STOP - quotient NOT EQUAL ---*** 1073747399
400015C7
*** STOP - quotient NOT EQUAL ---*** 1073747499
4000162B
*** STOP - quotient NOT EQUAL ---*** 1073747599
4000168F
*** STOP - quotient NOT EQUAL ---*** 1073747699
400016F3
*** STOP - quotient NOT EQUAL ---*** 1073747799
40001757
*** STOP - quotient NOT EQUAL ---*** 1073747899
400017BB
*** STOP - quotient NOT EQUAL ---*** 1073747999
4000181F
*** STOP - quotient NOT EQUAL ---*** 1073748099
40001883
*** STOP - quotient NOT EQUAL ---*** 1073748199
400018E7
*** STOP - quotient NOT EQUAL ---*** 1073748299
4000194B
*** STOP - quotient NOT EQUAL ---*** 1073748399
400019AF
*** STOP - quotient NOT EQUAL ---*** 1073748499
40001A13
*** STOP - quotient NOT EQUAL ---*** 1073748599
40001A77
*** STOP - quotient NOT EQUAL ---*** 1073748699
40001ADB
*** STOP - quotient NOT EQUAL ---*** 1073748799
40001B3F
*** STOP - quotient NOT EQUAL ---*** 1073748899
40001BA3
*** STOP - quotient NOT EQUAL ---*** 1073748999
40001C07
*** STOP - quotient NOT EQUAL ---*** 1073749099
40001C6B
*** STOP - quotient NOT EQUAL ---*** 1073749199
40001CCF
*** STOP - quotient NOT EQUAL ---*** 1073749299
40001D33
*** STOP - quotient NOT EQUAL ---*** 1073749399
40001D97
*** STOP - quotient NOT EQUAL ---*** 1073749499
40001DFB
*** STOP - quotient NOT EQUAL ---*** 1073749599
40001E5F
*** STOP - quotient NOT EQUAL ---*** 1073749699
40001EC3
*** STOP - quotient NOT EQUAL ---*** 1073749799
40001F27
*** STOP - quotient NOT EQUAL ---*** 1073749899
40001F8B
*** STOP - quotient NOT EQUAL ---*** 1073749999
40001FEF
*** STOP - quotient NOT EQUAL ---*** 1073750099
40002053
*** STOP - quotient NOT EQUAL ---*** 1073750199
400020B7
*** STOP - quotient NOT EQUAL ---*** 1073750299
4000211B
*** STOP - quotient NOT EQUAL ---*** 1073750399
4000217F
*** STOP - quotient NOT EQUAL ---*** 1073750499
400021E3
*** STOP - quotient NOT EQUAL ---*** 1073750599
40002247
*** STOP - quotient NOT EQUAL ---*** 1073750699
400022AB
*** STOP - quotient NOT EQUAL ---*** 1073750799
4000230F
*** STOP - quotient NOT EQUAL ---*** 1073750899
40002373
*** STOP - quotient NOT EQUAL ---*** 1073750999
400023D7
*** STOP - quotient NOT EQUAL ---*** 1073751099
4000243B
*** STOP - quotient NOT EQUAL ---*** 1073751199
4000249F
*** STOP - quotient NOT EQUAL ---*** 1073751299
40002503
*** STOP - quotient NOT EQUAL ---*** 1073751399
40002567
*** STOP - quotient NOT EQUAL ---*** 1073751499
400025CB
*** STOP - quotient NOT EQUAL ---*** 1073751599
4000262F
*** STOP - quotient NOT EQUAL ---*** 1073751699
40002693
*** STOP - quotient NOT EQUAL ---*** 1073751799
400026F7
*** STOP - quotient NOT EQUAL ---*** 1073751899
4000275B
*** STOP - quotient NOT EQUAL ---*** 1073751999
400027BF
*** STOP - quotient NOT EQUAL ---*** 1073752099
40002823
*** STOP - quotient NOT EQUAL ---*** 1073752199
40002887
*** STOP - quotient NOT EQUAL ---*** 1073752299
400028EB
*** STOP - quotient NOT EQUAL ---*** 1073752399
4000294F
*** STOP - quotient NOT EQUAL ---*** 1073752499
400029B3
*** STOP - quotient NOT EQUAL ---*** 1073752599
40002A17
*** STOP - quotient NOT EQUAL ---*** 1073752699
40002A7B
*** STOP - quotient NOT EQUAL ---*** 1073752799
40002ADF
*** STOP - quotient NOT EQUAL ---*** 1073752899
40002B43
*** STOP - quotient NOT EQUAL ---*** 1073752999
40002BA7
*** STOP - quotient NOT EQUAL ---*** 1073753099
40002C0B
*** STOP - quotient NOT EQUAL ---*** 1073753199
40002C6F
*** STOP - quotient NOT EQUAL ---*** 1073753299
40002CD3
*** STOP - quotient NOT EQUAL ---*** 1073753399
40002D37
*** STOP - quotient NOT EQUAL ---*** 1073753499
40002D9B
*** STOP - quotient NOT EQUAL ---*** 1073753599
40002DFF
*** STOP - quotient NOT EQUAL ---*** 1073753699
40002E63
*** STOP - quotient NOT EQUAL ---*** 1073753799
40002EC7
*** STOP - NOT EQUAL --- E N D ---***
Your test program do only
one step esi=0FFFFFFFFh
then dec esi do esi=0FFFFFFFEh and it has SIGN
so EXIT. It is very very very FAST ! ;)
Quote
; masm windows console #
include \masm32\include\masm32rt.inc
.686
.code
start: mov esi,0FFFFFFFFh
mov ebx,100
@@: mov eax,42949673
mul esi
mov edi,edx
;
xor edx,edx
mov eax,esi
div ebx
;
cmp edi,eax
jne error
dec esi
jns @b ;<---- your error is HERE
inkey " *** STOP - ALL EQUAL --- E N D ---*** "
exit
error: print str$(esi),13,10
print str$(edi),13,10
print str$(eax),13,10
inkey " *** STOP - NOT EQUAL --- E N D ---*** "
exit
end start
Your result should be this:
-97
42949672
2
*** STOP - NOT EQUAL --- E N D ---***
Hi,
RuiLoureiro!
QuoteYour test program do only one step esi=0FFFFFFFFh
I've seen this error, thank you!
But in the rang from 1000000000 to 0 my test is working correctly!
Quote from: Mikl__ on May 14, 2013, 07:32:26 PM
Hi, RuiLoureiro!
QuoteYour test program do only one step esi=0FFFFFFFFh
I've seen this error, thank you!
But in the rang from 1000000000 to 0 my test is working correctly!
you should use this:
mov eax,X
mov edx,051EB851Fh
mul edx
shr edx,05h <- more this instruction only
; edx = quotient
i think that i tested it in that range and it works well, yes.
Quote from: dedndave on May 14, 2013, 09:18:21 AM
credit to Drizz on that one :t
credit to Dave, i say. I did it because Dave post it :t
well, Drizz takes a little one ;)
thank you Dave
Quote from: Mikl__ on May 14, 2013, 04:57:02 PM
My programm division by 100
...
to calculate the exponential of this range is enough
Yes, very well, it is
exactly correct.
I put the question to myself for all cases
because i wanted to save the procedure as a macro
for future use. And i found out that i can save it
but with some notes ! See my reply 15
the original post
http://www.masmforum.com/board/index.php?topic=12234.msg93696#msg93696 (http://www.masmforum.com/board/index.php?topic=12234.msg93696#msg93696)
Drizz writes some fast stuff :P
he used push/pop and shl 16
i replaced those with a couple bswap's and squeezed 2 clock cycles - lol
Quote from: dedndave on May 14, 2013, 11:14:51 PM
the original post
http://www.masmforum.com/board/index.php?topic=12234.msg93696#msg93696 (http://www.masmforum.com/board/index.php?topic=12234.msg93696#msg93696)
Drizz writes some fast stuff :P
he used push/pop and shl 16
i replaced those with a couple bswap's and squeezed 2 clock cycles - lol
well what bsawp does ? i dont know. Does it exchange the "e" part of eax with ax for instance ?
sort of
it reverses the 4 bytes of a dword register
;EAX = 1A2B3C4Dh
bswap eax
;EAX = 4D3C2B1Ah
Ok :t
Quote from: Tedd on May 14, 2013, 01:51:57 AM
http://www.masmforum.com/board/index.php?topic=17027.msg142029#msg142029 (http://www.masmforum.com/board/index.php?topic=17027.msg142029#msg142029)
Quote
The simplified version...
For divide by 11, the magic reciprocal is 232 / 11 = 390451572 (remainder 4)
and multiplying by this number gives 12345 * 390451572 = 4820124656340
which doesn't look right, until you realize what we actually did what multiply by 232 and then divide by 11.
So, for the result, we can just divide by 232 again - which would be the same as just dividing by 11 in the first place.
Luckily for us, the result of a mul is naturally split into edx and eax, where edx represents the upper part multiplied by 232, so we just take edx directly as the result.
Sure enough...
12345 / 11 = 1122.27
12345 * 390451572 = 4820124656340 = 1122 * 232 + 1171350228 => 1122
That's the simplified version because we didn't take the 4 remainder into account, which leads to accumulated errors depending on what values you're dividing. As Dave said, it depends on the range you want to include.
To increase accuracy, you'd shift the magic value and add on a proportion of the remainder. Then shift the result back again to correct for the inherent shift in the magic value, which can effectively give you a few decimal places of accuracy (rounded, naturally.)
Hi Tedd,
only today i had time to answer you
thanks for the explanation, i think very good :t
i think i have some more questions about this
one day i will return here, i think
Thanks, Tedd
Tedd,
as far as i understood, the idea behind the so called
"magic numbers" comes from this (it seems):
if we want to divide the integer N by the integer k
we may do this:
N N * f N f
----- = ------ = --- * ---- =(N * mn) / f
k k * f f k
where mn = f/k
If we use f=2^32 and eax=N, we get the reuslt in edx and
we dont need to divide by f.
Meanwhile, when we want to divide by 2,4,8,16,..., 2^n
we may use shift right to do it instead of div.
In the same way we may replace log(2).
If we have the exponent N2 of base 2 and if we want
the exponent N10 of base 10 we need to solve this:
2^N2 = 10^N10 => N10 = N2 * log(2)
In many cases it seems that it works well if we use f=2^16
log(2)*2^16
N10= N2 --------------- mn= integer of [log(2)*2^16]
2^16
In this case we need to do the shift right to get N10.
Thanks Tedd :t
Bom dia, RuiLoureiro!
Eu escrevi há muito tempo
Quotedefinition of an integer value log10 can be done without any fyl2x -- try to use integer multiplication of the order on the magic integer constant 4D10h = log10 (2) * 65536
This method is used in the crt_sprintf function.
it's really simple :P
let's say we want to divide by 25
rather than dividing by 25, we can multiply by 1/25, and get the same result
however, we cannot easily work with binary fractions
so, we also multiply by a power of 2 (2^N), then divide that same power of 2 out at the end
when we multiply a dword by a dword, we get a result that may be as large as a qword
more accurately, the number of bits in the result will be the number of bits in the multiplier,
plus the number of bits in the multiplicand
anyways, the result of the MUL instruction is always in EDX:EAX
we can divide the result by 2^32 by simply discarding EAX
we lose some precision when we do this, but the bits we discard are usually un-wanted
(actually, you can recover the remainder from these bits)
mov ecx,X
mov eax,1374389535 ;2^35/25
mul ecx
shr edx,3 ;EDX = quotient
we can multiply the "leftover" bits by the same constant to recover the remainder
however, it's usually faster to multiply the quotient by the divisor, and subtract that from the dividend
imul eax,edx,25
sub ecx,eax ;ECX = remainder