Need help speeding up division

New to FreeBASIC? Post your questions here.
Thorbenn
Posts: 41
Joined: Dec 10, 2011 13:27

Need help speeding up division

Postby Thorbenn » Mar 31, 2014 15:02

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
Posts: 2348
Joined: Jun 16, 2005 9:45
Location: Eindhoven, NL
Contact:

Re: Need help speeding up division

Postby marcov » Mar 31, 2014 15:18

Replace all "double" with "single" :-)
rolliebollocks
Posts: 2655
Joined: Aug 28, 2008 10:54
Location: new york

Re: Need help speeding up division

Postby rolliebollocks » Mar 31, 2014 15:33

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
Site Admin
Posts: 5793
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Re: Need help speeding up division

Postby counting_pine » Mar 31, 2014 15:59

For faster integer division, use unsigned operands if you can. I don't know if that's faster than float division though.
Thorbenn
Posts: 41
Joined: Dec 10, 2011 13:27

Re: Need help speeding up division

Postby Thorbenn » Mar 31, 2014 16:27

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
Posts: 2348
Joined: Jun 16, 2005 9:45
Location: Eindhoven, NL
Contact:

Re: Need help speeding up division

Postby marcov » Mar 31, 2014 19:12

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
Posts: 2655
Joined: Aug 28, 2008 10:54
Location: new york

Re: Need help speeding up division

Postby rolliebollocks » Mar 31, 2014 20:33

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
         
Pritchard
Posts: 5425
Joined: Sep 12, 2005 20:06
Location: Ohio, USA

Re: Need help speeding up division

Postby Pritchard » Mar 31, 2014 21:42

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
Posts: 2655
Joined: Aug 28, 2008 10:54
Location: new york

Re: Need help speeding up division

Postby rolliebollocks » Mar 31, 2014 21:55

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
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Re: Need help speeding up division

Postby MichaelW » Mar 31, 2014 22:36

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
Posts: 86
Joined: Nov 30, 2006 13:35
Location: UK

Re: Need help speeding up division

Postby tinram » Mar 31, 2014 22:57

@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
Posts: 2655
Joined: Aug 28, 2008 10:54
Location: new york

Re: Need help speeding up division

Postby rolliebollocks » Apr 01, 2014 0:14

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
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Re: Need help speeding up division

Postby MichaelW » Apr 01, 2014 8:07

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

Return to “Beginners”

Who is online

Users browsing this forum: No registered users and 3 guests