Split Division Algorithm Help

matricSys

New member
Joined
Aug 6, 2019
Messages
1
Hello,

I am a programmer and I got stuck with this problem. I have to solve division Q = Z / D, where Z and D are 4k-bit numbers. However, I need to do this operation in smaller parts, for example, in k-bit modules. I have found multiplication algorithms for this purpose, such as Karatsuba, Toom, Fourier Division but I cannot seem to find one based purely on division. Is it not possible to do this? Any help will be appreciated.
 

Subhotosh Khan

Super Moderator
Staff member
Joined
Jun 18, 2007
Messages
18,572
Hello,

I am a programmer and I got stuck with this problem. I have to solve division Q = Z / D, where Z and D are 4k-bit numbers. However, I need to do this operation in smaller parts, for example, in k-bit modules. I have found multiplication algorithms for this purpose, such as Karatsuba, Toom, Fourier Division but I cannot seem to find one based purely on division. Is it not possible to do this? Any help will be appreciated.
My guess (I am not a programmer) would be to subtract 'D' from 'Z' - then subtract 'D' from 'Z-D' - then subtract 'D' from 'Z - 2 *D' and so on....
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,395
I don't know a lot about this; I presume you have searched with terms like "arbitrary precision division algorithms", and have found what is said here in Wikipedia:

For these large integers, more efficient division algorithms transform the problem to use a small number of multiplications, which can then be done using an asymptotically efficient multiplication algorithm such as the Karatsuba algorithm, Toom–Cook multiplication or the Schönhage–Strassen algorithm.​

Is there a reason you don't want to accept what others have found most efficient? (Frankly, I'd expect a division algorithm to involve multiplications, just as ordinary long division does!)
 
Top