Split Division Algorithm Help

[matricSys]

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.

 

[Deleted member 4993]

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]

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!)