Need help speeding up division

[Thorbenn]

Hi all,

i am writing a Program with lots of divisions. I am trying to speed things up by avoiding divisions by replacing them with an own Sub.
I remember from School that there was a way to calculate the numbers after the komma from a double number but i can't think of how it worked.

So far my Code works like a Modulo that it gives you the result (the whole number of the division) and a rest. Would be really neat if someone could help me solve this little problem :)

Code: Select all

Sub Division(ByVal number As Double,ByVal divider As Double,ByRef result As Double, ByRef rest As Double)
   
   If divider <> 0 Then
      result = 0
      rest = 0
   
      While divider <= number
         number -= divider
         result += 1
      Wend
   
      rest = number
   EndIf

End Sub

Dim As Double number
number = 3.0

Dim As Double divider
divider = 2.5

Dim As Double result,rest

Division(number,divider,result,rest)
Print result
Print rest
sleep


Greetings Thorbenn :)

[marcov]

Replace all "double" with "single" :-)

[rolliebollocks]

This speed test indicates your code is (very slightly) slower than FB division. If you don't need the remainder, you can use integer division like this:

10 \ 6 = 1
10 / 6 = 1.666666...

Code: Select all

    Sub Division(ByVal number As Double,ByVal divider As Double,ByRef result As Double, ByRef rest As Double)
       
        If divider <> 0 Then
            result = 0
            rest = 0
       
            While divider <= number
                number -= divider
                result += 1
            Wend
       
            rest = number
        EndIf

    End Sub

    Dim As Double number
    number = 3.0

    Dim As Double divider
    divider = 2.5

    Dim As Double result,rest

    dim as double tnow
   
    tnow = timer
    for i as integer = 1 to 10000:Division(number,divider,result,rest):next
    ? timer - tnow
   
    tnow = timer
    for i as integer = 1 to 10000:result = number/divider:next
    ? timer-tnow
    sleep
   
   
    Print result
    Print rest
    sleep
     

[counting_pine]

For faster integer division, use unsigned operands if you can. I don't know if that's faster than float division though.

[Thorbenn]

okay thanks. I need the Double Values and thought that it might speed things up when using an own sub for Division. Since it is always said that Division always costs alot.

I guess that I will just have to accept that my Program wil be a tiny bit slower :)

Thanks anyways :)

[marcov]

Then try you need the SSE2 divpd instruction (and afaik AVX has a 4 way one). You can then do two (or four) divisions in one instruction.

It is mostly useful if you do divides on whole arrays though.

[rolliebollocks]

Your function gets exponentially slower the greater the difference between 'number' and 'divider.' I've tried a million times, a million ways, to beat the standard functions in FB. Never succeeded though.

Code: Select all

        Sub Division(ByVal number As Double,ByVal divider As Double,ByRef result As Double, ByRef rest As Double)
           
            If divider = 0 Then exit sub
           
                While divider <= number
                    number -= divider
                    result += 1
                Wend
           
                rest = number
               
        End Sub

        Dim As Double number
        number = 3.0^10

        Dim As Double divider
        divider = 2.5

        Dim As Double result,rest

        dim as double tnow
       
        tnow = timer
        for i as integer = 1 to 10000:Division(number,divider,result,rest):next
        ? timer - tnow
       
        tnow = timer
        for i as integer = 1 to 10000:result = number/divider:next
        ? timer-tnow
        sleep
       
       
        Print result
        Print rest
        sleep
         

[anonymous1337]

Test.bas:

Code: Select all

dim as double x = 200000000, y = 50, result

' Result = x / y
result = x / y

' Result = y / x
result = y / x

Compiled with fbc -r -g test.bas

From test.asm:

Code: Select all

##
##' Result = x / y
##result = x / y
   fld qword ptr [ebp-8]
   fdiv qword ptr [ebp-16]
   fstp qword ptr [ebp-24]
.stabn 68,0,4,.Lt_0008-_fb_ctor__test
.Lt_0009:
##
##' Result = y / x
##result = y / x
   fld qword ptr [ebp-16]
   fdiv qword ptr [ebp-8]
   fstp qword ptr [ebp-24]

Are you going to beat such low-level instructions by making procedure calls and pushing/popping on the stack while doing so?

[rolliebollocks]

If you make all the numbers you are working with a multiple of 2 then you can use shl/shr and that should give you a bit of a boost.. (i think) right?

[MichaelW]

Running on a P4 Northwood the scalar version DIVSD is marginally faster than a normal floating-point divide. Note that this code requires SSE2 support.

Code: Select all

dim as double t,n,d,r
n = 3.0
d = 2.5

r = n/d
print r
asm
    movq  xmm0, [n]
    divsd xmm0, [d]
    movq  [r], xmm0
end asm
print r
asm
    movq  xmm0, [n]
    movq  xmm1, [d]
    divpd xmm0, xmm1
    movq  [r], xmm0
end asm
print r
print

sleep 5000

for i as integer = 1 to 3

    t = timer
    for i as integer = 1 to 1000000
        r = n/d
    next
    print timer-t

    t = timer
    for i as integer = 1 to 1000000
        asm
            movq  xmm0, [n]
            divsd xmm0, [d]
            movq  [r], xmm0
        end asm
    next
    print timer-t

    t = timer
    for i as integer = 1 to 1000000
        asm
            movq  xmm0, [n]
            movq  xmm1, [d]
            divpd xmm0, xmm1
            movq  [r], xmm0
        end asm
    next
    print timer-t

    print
next

sleep


Code: Select all

 1.2
 1.2
 1.2

 0.01438552796114578
 0.01271497762720841
 0.023087288683314

 0.01438700764802192
 0.01271282159229514
 0.02307940104137174

 0.01439686285660713
 0.01271731010467647
 0.02307431236945234


[tinram]

@rollie
Yes, SHR should be the fastest way to divide by powers of 2, without resorting to ASM.
Ages ago, when I compared in FBC 0.18b (?), SHR was ~15% faster than using the equivalent division operator.

Multiplying by the reciprocal of the divisor is another way to avoid slow division.

[rolliebollocks]

Multiplying by reciprocal only works when you sent a raw integer/float to * operator and preprocess the division in your head. Otherwise you have to 1/somenum * anothernum and that would probably be 80-90% slower, rough guess wise.

You're best bet here is manufacture data that is always a power of two and use shift left/shift right.

[MichaelW]

This code tests two methods of speeding up floating-point division, see Agner Fog’s optimizing_assembly.pdf for the details, available here, and note that the document also covers integer division. And note that this code requires SSE2 support.

Code: Select all

''=============================================================================
#define FPC_24BITS &b0000000000
#define FPC_53BITS &b1000000000
#define FPC_64BITS &b1100000000

''-------------------------------------------------------------------------
'' This macro sets the FPU precision control bits in the FPU control word
'' to one of the above values. The precision control setting determines
'' the precision that the FPU maintains internally. In the initialized
'' state the precision is set to 64 bits. Windows sets the precision to
'' 53 bits when it launches an application. A lower precision setting will
'' allow FPU divides and sqrts to cycle faster.
''-------------------------------------------------------------------------

#macro FSETPC(pc)
    #ifndef __fpu__cw__
        dim as ushort __fpu__cw__
    #endif
    asm
        fstcw [__fpu__cw__]
        mov ax, pc
        and WORD PTR [__fpu__cw__], ~ FPC_64BITS
        or [__fpu__cw__], ax
        fldcw [__fpu__cw__]
    end asm
#endmacro

''=============================================================================

sub ShowPC
    dim as ushort fpucw
    asm
        fstcw [fpucw]
    end asm
    fpucw and= FPC_64BITS
    print "PC = ";
    select case fpucw
        case FPC_24BITS
            print "24 bits"
        case FPC_53BITS
            print "53 bits"
        case FPC_64BITS
            print "64 bits"
    end select
end sub

''=============================================================================

dim as double rd,nd=5.4321,dd=1.2345,t

dim as single r,n=5.4321,d=1.2345

ShowPC

rd = nd/dd
print using "#.###############";rd
print

FSETPC(FPC_53BITS)

ShowPC

rd = nd/dd
print using "#.###############";rd
print

FSETPC(FPC_24BITS)

ShowPC

rd = nd/dd
print using "#.###############";rd
print

print "Using multiply with 12-bit precision reciprocal:"
asm
    movd  xmm1, [d]
    rcpss xmm0, xmm1
    mulss xmm0, [n]
    movd  [r], xmm0
end asm

print using "#.###############";r
print

print "Using multiply with reciprocal extended to 23-bit precision:"
asm
    movd  xmm1, [d]
    rcpss xmm0, xmm1
    mulss xmm1, xmm0
    mulss xmm1, xmm0
    addss xmm0, xmm0
    subss xmm0, xmm1
    mulss xmm0, [n]
    movd  [r], xmm0
end asm

print using "#.###############";r
print
print

sleep 5000

FSETPC(FPC_64BITS)

ShowPC
t = timer
for i as integer = 1 to 10000000
    rd = nd/dd
next
print timer-t;" seconds"
print

FSETPC(FPC_53BITS)

ShowPC
t = timer
for i as integer = 1 to 10000000
    rd = nd/dd
next
print timer-t;" seconds"
print

FSETPC(FPC_24BITS)

ShowPC
t = timer
for i as integer = 1 to 10000000
    rd = nd/dd
next
print timer-t;" seconds"
print

print "Using multiply with 12-bit precision reciprocal:"
t = timer
for i as integer = 1 to 10000000
    asm
        movd  xmm1, [d]
        rcpss xmm0, xmm1
        mulss xmm0, [n]
        movd  [r], xmm0
    end asm
next
print timer-t;" seconds"
print

print "Using multiply with reciprocal extended to 23-bit precision:"
t = timer
for i as integer = 1 to 10000000
    asm
        movd  xmm1, [d]
        rcpss xmm0, xmm1
        mulss xmm1, xmm0
        mulss xmm1, xmm0
        addss xmm0, xmm0
        subss xmm0, xmm1
        mulss xmm0, [n]
        movd  [r], xmm0
    end asm
next
print timer-t;" seconds"
sleep


Running on a P4 Northwood:

Code: Select all

PC = 64 bits
4.400243013365736

PC = 53 bits
4.400243013365736

PC = 24 bits
4.400242805480957

Using multiply with 12-bit precision reciprocal:
4.399655818939209

Using multiply with reciprocal extended to 23-bit precision:
4.400242805480957


PC = 64 bits
 0.1631717336153855 seconds

PC = 53 bits
 0.1302028878562851 seconds

PC = 24 bits
 0.078125 seconds

Using multiply with 12-bit precision reciprocal:
 0.03125 seconds

Using multiply with reciprocal extended to 23-bit precision:
 0.0859375 seconds