## 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

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   EndIfEnd SubDim As Double numbernumber = 3.0Dim As Double dividerdivider = 2.5Dim As Double result,restDivision(number,divider,result,rest)Print resultPrint restsleep`

Greetings Thorbenn :)
marcov
Posts: 2792
Joined: Jun 16, 2005 9:45
Location: Eindhoven, NL
Contact:

### Re: Need help speeding up division

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

### Re: Need help speeding up division

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

### Re: Need help speeding up division

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

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

### Re: Need help speeding up division

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

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

### Re: Need help speeding up division

Test.bas:

Code: Select all

`dim as double x = 200000000, y = 50, result' Result = x / yresult = x / y' Result = y / xresult = 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

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

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,rn = 3.0d = 2.5r = n/dprint rasm    movq  xmm0, [n]    divsd xmm0, [d]    movq  [r], xmm0end asmprint rasm    movq  xmm0, [n]    movq  xmm1, [d]    divpd xmm0, xmm1    movq  [r], xmm0end asmprint rprintsleep 5000for 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    printnextsleep`

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

### Re: Need help speeding up division

@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

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

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 selectend sub''=============================================================================dim as double rd,nd=5.4321,dd=1.2345,tdim as single r,n=5.4321,d=1.2345ShowPCrd = nd/ddprint using "#.###############";rdprintFSETPC(FPC_53BITS)ShowPCrd = nd/ddprint using "#.###############";rdprintFSETPC(FPC_24BITS)ShowPCrd = nd/ddprint using "#.###############";rdprintprint "Using multiply with 12-bit precision reciprocal:"asm    movd  xmm1, [d]    rcpss xmm0, xmm1    mulss xmm0, [n]    movd  [r], xmm0end asmprint using "#.###############";rprintprint "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], xmm0end asmprint using "#.###############";rprintprintsleep 5000FSETPC(FPC_64BITS)ShowPCt = timerfor i as integer = 1 to 10000000    rd = nd/ddnextprint timer-t;" seconds"printFSETPC(FPC_53BITS)ShowPCt = timerfor i as integer = 1 to 10000000    rd = nd/ddnextprint timer-t;" seconds"printFSETPC(FPC_24BITS)ShowPCt = timerfor i as integer = 1 to 10000000    rd = nd/ddnextprint timer-t;" seconds"printprint "Using multiply with 12-bit precision reciprocal:"t = timerfor i as integer = 1 to 10000000    asm        movd  xmm1, [d]        rcpss xmm0, xmm1        mulss xmm0, [n]        movd  [r], xmm0    end asmnextprint timer-t;" seconds"printprint "Using multiply with reciprocal extended to 23-bit precision:"t = timerfor 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 asmnextprint timer-t;" seconds"sleep`

Running on a P4 Northwood:

Code: Select all

`PC = 64 bits4.400243013365736PC = 53 bits4.400243013365736PC = 24 bits4.400242805480957Using multiply with 12-bit precision reciprocal:4.399655818939209Using multiply with reciprocal extended to 23-bit precision:4.400242805480957PC = 64 bits 0.1631717336153855 secondsPC = 53 bits 0.1302028878562851 secondsPC = 24 bits 0.078125 secondsUsing multiply with 12-bit precision reciprocal: 0.03125 secondsUsing multiply with reciprocal extended to 23-bit precision: 0.0859375 seconds`