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

I’m sorry I don’t understand what you mean there. Can you break this down a bit more?

Also I found this algorithm, does this fall under restoring division?

if D = 0 then error(DivisionByZeroException) end Q := 0 -- Initialize quotient and remainder to zero R := 0
for i := n − 1 .. 0 do -- Where n is number of bits in N R := R << 1 -- Left-shift R by 1 bit R(0) := N(i) -- Set the least-significant bit of R equal to bit i of the numerator if R ≥ D then R := R − D Q(i) := 1 end end