Dividing by divisors.

[BlindSniper]

Hi all,
I'm Writing a program and I'm curious about something. If you have a value and you are always dividing by a divisor, is there something faster than Integer division ? Like some sort of bit manipulation ?


EDIT:
I just realized that Integer Division is just one instruction, it would be hard to beat it by using more instructions, but in the case of me being wrong, I'll leave the thread open.

[jemidiah]

Well... if the divisor is a power of 2, you can of course bit shift, which might be faster.

In the case of gigantic numbers, you could store the prime factorization instead of the number itself, canceling the relevant factors in a division operation. That would probably be faster than a general-purpose BigInt with a huge number of digits, but again it depends on the specifics of your program--are there other gains from storing prime factorizations, or is it wildly inefficient, for instance because of lots of add operations?

One other thing to consider is that a single instruction can take multiple clock cycles to complete, so one instruction is not always the fastest possible. I don't know how many cycles integer division takes, though it can be pipelined, so in a loop it effectively takes 1 cycle (with a huge number of case-specific caveats I'm not qualified to discuss).

You might get more informed opinions on another board. This is not really a math question.

[Lenggries]

Generally speaking, multiplication is much faster than division, so instead of dividing, you can multiply by the reciprocal. For example, 12.5 / 10 = 1.25 is slower than 12.5 * 0.1 = 1.25

Thus, if you can cheaply compute the reciprocal, than just use that.

[formlesstree4]

Generally speaking, multiplication is much faster than division, so instead of dividing, you can multiply by the reciprocal. For example, 12.5 / 10 = 1.25 is slower than 12.5 * 0.1 = 1.25

Thus, if you can cheaply compute the reciprocal, than just use that.

The easiest way I know of to calculate a reciprocal is to simply raise the number to a power of -1. So, I decided to test out your theory Leggrines in a quick C# console application. The results were as assumed: multiplication is faster than division.

I tested two equations:
1) 5 / 9
2) 5 * (9 ^ - 1)

I ran those equations 100,000,000 times to see which one went "faster". These tests were run multiple times, and here are the results

Trial 1
Equation 1:

• Average: 81 ticks
• Total Ticks: 816643

Equation 2:

• Average: 78 ticks
• Total Ticks: 787932

Trial 2
Equation 1:

• Average: 81 ticks
• Total Ticks: 811916

Equation 2:

• Average: 78 ticks
• Total Ticks: 787409

Trial 3
Equation 1:

• Average: 81 ticks
• Total Ticks: 814381

Equation 2:

• Average: 78 ticks
• Total Ticks: 783546

The results are pretty conclusive. Although slim, using reciprocal multiplication does in fact yield faster results than regular division (in C# on my machine; results may vary).

[formlesstree4]

Just a side note, I went ahead and changed a few variables to make the fraction more..."simple". Instead of 9, I changed to an 8 so I could add in Decimal Multiplication to see if I can go even faster. Apparently no, I cannot. Reciprocal multiplication is still the fastest method given.

[boops boops]

What if the divisor is repeated? It might save time to precalculate the reciprocal. So Formless, how does this equation perform in your test:
3) 5 * 0.111111111111

BB

[formlesstree4]

What if the divisor is repeated? It might save time to precalculate the reciprocal. So Formless, how does this equation perform in your test:
3) 5 * 0.111111111111

BB

I remember running a floating point test with a repeating divisor; I believe calculating the reciprocal was averaging the same time as just multiplying by the decimal value. I'll run a few more tests to confirm.

[BlindSniper]

I ran a few tests and in my case Integer Division is Always faster than multiplying with the reciprocal.
Some Conditions:
I start out with a Integer.
I divide with a integer (Which is always a divisor of the first one)
I need the Result as a Integer.

The code I used:

Sub Main()
        While True
            Dim st As New Stopwatch
            Dim result As Integer = 0
            Dim Counter As Long = 0
            For i = 1 To 1000
                st.Start()
                result = 20 \ 4
                st.Stop()
                Counter += st.ElapsedTicks
                st.Reset()
            Next
            st.Reset()
            Console.WriteLine("Integer division Average {0} Total {1}", (Counter / 1000).ToString, Counter.ToString)
 
 
            Dim result2 As Integer = 0
            Dim Counter2 As Long = 0
            Dim reciprocal As Double
            st.Start()
            reciprocal = 4 ^ -1 'Can't forget to time this.
            st.Stop()
            For i = 1 To 1000
                st.Start()
                result2 = CInt(20 * reciprocal)
                st.Stop()
                Counter2 += st.ElapsedTicks
                st.Reset()
            Next
            st.Reset()
            Console.WriteLine("Multiplication Average {0} Total {1}", (Counter2 / 1000).ToString, Counter2.ToString)
            Console.ReadLine()
        End While
 
    End Sub

Results :
Integer Division is almost always about 45 ticks faster than multiplication with a reciprocal

[Milk]

Be careful with drawing concrete conclusions from these sort of tests. Compilers even the JIT compiler utilise some cunning tricks to optimise your code and as such it can be difficult to tell exactly what you are testing. For example A Mod 256 might appear to be as fast as A And 255 where in truth Mod is slower but the compiler substituted the Mod for an And.

Have you come across SIMD? There are a bunch of SIMD instructions in X86. AFAIK there is no SIMD support in Net but you might come across them if you dabble in C/C++. There is no division at all in SIMD, to achieve it you have to use other means.

With integers if your numbers are relatively small you can approximate division with a multiplication followed by a left shift. For example if my divisor was 119 and my numbers never exceed 65535 I can approximate the division by multiplying by 17623 and then left shifting 21 spaces.

[BlindSniper]

Well i'm actually programming in assembly, but i'm still very new so I don't know how to time my code.
Can you explain how your division method works please ?

[Milk]

It is only an approximation.

Say you have a bunch of numbers that you want divide.

multiplier = (1 << shift) / divisor.

for each number in bunchONumbers
result = (number * multiplier) >> shift.

the key is finding a highest shift you can use without overflow.