Page 1 of 1
Divide and Modulo with one operation?
Posted: Fri Sep 06, 2024 10:30 am
by SMaag
If I need from a Division the Result and the Remainder I have to do 2 operations in PB
Code: Select all
Result = Var / 10
Remainder = Var % 10
This results in the ASM Code in 2 seperate divisions. But a division creates always result and remainder in 1 operation
RAX contains the Result and RDX contains the Remainder.
I tried a few combinations of arranging Result= Var / 10 and Remainder= Var % 10
But it results always 2 Division operations.
The C-Backend I guess optimize it to 1 division, as you can see at the timing Demo!
In Assembler for me it is no problem to do it, and I did it like that!
Code: Select all
Result =Var/10
!MOV [v_Remainder], RDX
Is there any possiblity for force PB, with PB Code only, to get Result and Remainder wiht only 1 devision?
Timing Demo - try it in ASM and C-Backend to see the difference
Code: Select all
EnableExplicit
Define Result, Remainder
Define I, t1, sum
#Mio = 1000000
#Loops = 100 *#Mio
t1 = ElapsedMilliseconds()
For I = 0 To #Loops
Result =I/10
Remainder = I%10
sum = sum +Result +Remainder
Next
t1 = ElapsedMilliseconds() - t1
OpenConsole()
PrintN("Sum = " +Str(sum))
Print("")
PrintN("Time ms = " + Str(t1))
PrintN("")
PrintN("Press ENTER")
Input()
Re: Divide and Modulo with one operation?
Posted: Fri Sep 06, 2024 12:59 pm
by Little John
SMaag wrote: Fri Sep 06, 2024 10:30 am
My Question:
Is there any possiblity for force PB, with PB Code only, to get Result and Remainder wiht only 1 devision?
The solution with only 1 division follows from the definition of “remainder”:
Code: Select all
; e.g. PB 6.04 LTS
Macro DivRem (_x_, _n_)
result.q = IntQ((_x_)/(_n_))
remainder.q = (_x_) - result * (_n_)
EndMacro
;-- Demo
DivRem(50, 6)
Debug result
Debug remainder
Re: Divide and Modulo with one operation?
Posted: Fri Sep 06, 2024 2:15 pm
by SMaag
Madre mia!
Sometimes complicated things become very easy!
Thanks!
One note on C-Backend optimizing!
C-Backend removes the DIV completely and use inverse mulitplication alogorithm!
Re: Divide and Modulo with one operation?
Posted: Fri Sep 06, 2024 3:28 pm
by NicTheQuick
SMaag wrote: Fri Sep 06, 2024 2:15 pm
One note on C-Backend optimizing!
C-Backend removes the DIV completely and use inverse mulitplication alogorithm!
How is an inverse multiplication working with integers?
Re: Divide and Modulo with one operation?
Posted: Fri Sep 06, 2024 3:41 pm
by wilbert
NicTheQuick wrote: Fri Sep 06, 2024 3:28 pm
How is an inverse multiplication working with integers?
Code: Select all
For i = 1 To 1000
div10.q = ($1999999A * i) >> 32
mod10.q = i - div10*10
Debug Str(i)+" /10="+Str(div10)+" %10="+Str(mod10)
Next
Usually it works within a certain range.
For 100
Code: Select all
div100.q = ($28F5C29 * i) >> 32
mod100.q = i - div100*100
and 1000
Code: Select all
div1000.q = ($418938 * i) >> 32
mod1000.q = i - div1000*1000
Re: Divide and Modulo with one operation?
Posted: Fri Sep 06, 2024 4:43 pm
by NicTheQuick
Cool, I wrote a small snippet to check all the possibilities and tried to find suitable values that never produce wrong values.
Of course such a code only makes sense if your divisor is constant.
Code: Select all
#div_resolution = 24
#div_divisor = 5
#div_inverse_factor = (1 << #div_resolution) / #div_divisor + 1
#div_highest_dividend = (1 << (#div_resolution - 3))
Debug "Resolution: " + #div_resolution
Debug "Highest dividend: " + #div_highest_dividend
Debug "Inverse factor: " + #div_inverse_factor
Debug ""
Debug "Wrong values (checked from 0.." + #div_highest_dividend + "):"
For i = 0 To #div_highest_dividend
div.q = (#div_inverse_factor * i) >> #div_resolution
exact_div.q = i / #div_divisor
mod.q = (i - div * #div_divisor) % #div_divisor
exact_mod.q = i % #div_divisor
If div <> exact_div Or mod <> exact_mod
Debug Str(i) + " / " + #div_divisor + " = " + Str(div) + " R" + Str(mod) + " (exact: " + Str(exact_div) + " R" + Str(exact_mod) + ")"
EndIf
Next
Debug "done."
Edit: I just found out that the accuracy of the calculation is highly dependent of the divisor. So I guess one has to find a better way here.
Re: Divide and Modulo with one operation?
Posted: Fri Sep 06, 2024 6:34 pm
by r-i-v-e-r
NicTheQuick wrote: Fri Sep 06, 2024 4:43 pm
Edit: I just found out that the accuracy of the calculation is highly dependent of the divisor. So I guess one has to find a better way here.
This topic has some insights on superfast integer division tricks, if that's something
really dominating the hot path.
If you're interested in speeding up cases where the divisor isn't constant (or just how the magic constants are calculated),
libdivide is neat. The author of that library has detailed things in a
series of blogposts as well.
Re: Divide and Modulo with one operation?
Posted: Fri Sep 06, 2024 10:01 pm
by Little John
How cool is that?!
Thanks to wilbert and r-i-v-e-r for the information!
Re: Divide and Modulo with one operation?
Posted: Mon Sep 09, 2024 9:19 am
by SMaag
If I got it right, this is the mathemaic behind the inverse devision!
Code: Select all
; Inverse Division for devisor d, and div_resolution n in bits
; X * 2^n X << n 1 << n
; InvDevision : ---------- = ---------- >> n = ( -------- * X ) >> n
; d * 2^n d d
; => InvFactor = (1<<n)/d
; for devisor = 10
; X * 2^n X << n 1 << n
; InvDevision : ---------- = ---------- >> n = ( -------- * X ) >> n
; 10 * 2^n 10 10
Code: Select all
Procedure InverseDivsionFactor(Divisor, div_resolution_bit, *outHighestDividend.Integer=0)
If *outHighestDividend
*outHighestDividend\i = (1 << (div_resolution_bit - 3))
EndIf
ProcedureReturn (1 << div_resolution_bit) / Divisor + 1
EndProcedure
Define invFact
Define I
#DivResolutionBits = 32
Debug "inverse devison factors for div resolution bits=" + #DivResolutionBits
Debug ""
For I = 3 To 100
invFact = InverseDivsionFactor(I,#DivResolutionBits)
Debug Str(I) + " : $" + Hex(invFact) + " : " + Str(invFact)
Next
Re: Divide and Modulo with one operation?
Posted: Mon Sep 09, 2024 9:55 am
by wilbert
Not exactly.
For 32 bit shift and division by 8,
$100000000 / 8 is exactly $2000000.
There's no remainder and the value to use would be $2000000.
For 32 bit shift and division by 10,
$100000000 / 10 is $1999999 with a remainder of 6.
Because of this remainder you have to use $199999A ($1999999+1) instead of $1999999.
Re: Divide and Modulo with one operation?
Posted: Mon Sep 09, 2024 11:15 am
by SMaag
So we have to check the remainder
If remainder > HalfOfDivider Then Add 1
Do you think that's correct!
Re: Divide and Modulo with one operation?
Posted: Mon Sep 09, 2024 11:47 am
by SMaag
I made some tests and it seems we have to add 1 if the remainder is not 0!
I used a fix resolution of 32 and 64 Bit.
Code: Select all
EnableExplicit
Procedure InverseDivsionFactor_x64(Divisor)
; (1<<64)/Divisor
!XOR RAX, RAX
!MOV RDX, 1 ; (1<<64)
!MOV RCX, [p.v_Divisor]
!DIV RCX ; RDX:RAX / Divisor
!Test RDX, RDX
!JZ @f ; Jump if Zero
!INC RAX ; + 1
!@@:
ProcedureReturn
EndProcedure
Procedure.i InvDivision_x64(Value, invDivFact)
!MOV RAX, [p.v_Value]
!CDQ
!MOV RCX, [p.v_invDivFact]
!IMUL RCX
; because of a resolution of 64 Bit we did a 128Bit Operation and get the Result in RDX
!MOV RAX, RDX
ProcedureReturn
EndProcedure
Procedure.i InverseDivsionFactor_x32(Divisor)
Protected ret.q
Protected SHL.q = 1<<32
ret = SHL/Divisor
If (SHL % Divisor)
ret + 1
EndIf
ProcedureReturn ret
EndProcedure
Procedure.i InvDivision_x32(Value, invDivFact)
Protected ret.q ; we have to calcualte it as Quad
ret = (Value * invDivFact) >> 32
ProcedureReturn ret ; at x32 Quad is converted back to Int
EndProcedure
#Divisor = 11
#Dividend = #Divisor * 100
Define invFx64, inFx32, res
invFx64 = InverseDivsionFactor_x64(#Divisor)
Debug "$"+Hex(invFx64) + " : " + Str(invFx64)
res = InvDivision_x64(#Dividend, invFx64)
Debug "InvDivision_x64 = " + Str(res)
res = InvDivision_x64(-#Dividend, invFx64-1)
Debug "InvDivision_x64 = " + Str(res)
inFx32 = InverseDivsionFactor_x32(#Divisor)
res = InvDivision_x32(#Dividend, inFx32)
Debug "InvDivision_x32 = " + Str(res)