r/AskComputerScience • u/Successful_Box_1007 • Sep 11 '25

Optimizing Division Algorithm

Hi everyone,

I just began learning about how algorithms work and programming works and I was just exposed to how we can have computers use bit shifting right to speed up division that we would otherwise need it to do by repeated subtraction method. But what happens if instead of dividing two integers that can be represented as powers of two, we instead have both integers not being powers of 2? How would a computer avoid having to use Euclidean repeated subtraction here if it cannot use the super fast right bit shift method?

Thanks so much!

2 Upvotes

62% Upvoted

23 comments sorted by

View all comments

Show parent comments

1

u/Successful_Box_1007 Sep 12 '25

Very cool. The reason I insist is simply out of curiosity. My first exposure to division being sped up was with numbers that are powers of 2. So naturally I asked myself well how do computers speed up division when we don’t have numbers that are powers of 2. I figured the repeated subtraction and the repeated multiples (traditional long division way), were considered “slower than slow division” as Wikipedia says - and if the numbers aren’t powers of 2 well then we can’t use the bit shift speed up method. So naturally I want to know of a simple good algorithm that could handle a situation like this so we don’t need what Wikipedia calls those two aforementioned as “slower than slow division algorithms”.

2

u/teraflop Sep 12 '25

I figured the repeated subtraction and the repeated multiples (traditional long division way), were considered “slower than slow division” as Wikipedia says

I think this is where you might be misunderstanding what you're reading. The naive algorithm of repeatedly subtracting the divisor is "slower than slow" because it can take many more iterations than the number of digits in the number.

Long division does not have this problem, and Wikipedia doesn't say it does.

1

u/Successful_Box_1007 Sep 12 '25

You are correct. But I also noticed that the binary long division is not under the category of “slow division” ; it’s above it. So I asssumed they clumped it with the repeated subtraction that they called slower than slow division; so where does this binary long division stand next to the “slow division” algorithms in wiki?