Divide and Modulo with one operation?

[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

My Question:
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()

[Little John]

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

[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!

[NicTheQuick]

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?

[wilbert]

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

[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.

[r-i-v-e-r]

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.

[Little John]

How cool is that?!
Thanks to wilbert and r-i-v-e-r for the information!

[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

[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.

[SMaag]

So we have to check the remainder
If remainder > HalfOfDivider Then Add 1

Do you think that's correct!

[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)