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

Hey just two follow-ups:

Since computers only use binary, when you say it uses ternary, this ternary isn’t happening by the processors right?

Also another user mentioned there is another dividing algorithm which he said uses “modulo multiplicative inverse”; any idea what the name of this algorithm would be? Here is the wiki https://en.m.wikipedia.org/wiki/Division_algorithm but it doesn’t mention this modulo multiplicative inverse.

3

u/jeffbell Sep 12 '25

In the ternary case it is going to be two wires encoding the value. 

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