If we accept this thread as dealing with a general purpose algo for any integer as the numerator and denominator, the use of the FPU is out of the picture since standard FPUs cannot handle integers with more than 64 bits. It is immaterial that the FPU can deal with numbers between 2^-32767 and 2^+32767 because only the first 64 bits of those numbers could be used with some exponent.

The only way is the subtract and shift, the number of cycles required being equal to the difference in bits between the numerator and denominator. The number of instructions in each cycle will depend on the size (in bits) of the numerator. At present, on most PCs, only chunks of 32 bits could be handled at a time, unless the MMX could be used for some of the work (anybody familiar with the MMX functions?).

Long ago, I have done something similar (in some way) by extracting the square root of any number (almost) with up to 9999 decimals in the answer, using BCD instructions and "shifts".

Raymond
Posted on 2002-12-18 19:57:34 by Raymond
hi

you might want to take a look at my lame bignum lib that implements bignumber division (http://www.effervescence.com, archives section)
Posted on 2002-12-23 04:09:53 by roy
Thanks ROY, You probably mean the thing you call:

biglib v.0.01e an asm bignum library, it is quite slow and might be bugged

Why do you promote something that you give this description???
Posted on 2002-12-23 04:30:52 by davidsimple
One of most popular algorismist in Russia - Shen
give this discription in the first page of his algo book
"Most likely you'd find this book uselless and boring,
so close it as fast as possible"

And at the same time promisses for miracle in most western books just make me sick.
Posted on 2002-12-23 13:59:28 by The Svin
I understand Svin. Sorry to bother you with this excellent reply, but I think it is very goods use of your time
to read this, this line contains namely nothing of value for you.

Just keep on smiling and the world will be better just when you want to cry.
Posted on 2002-12-24 02:14:09 by davidsimple
Dunno if this will help, or even if it will be read, but:

if the difference in the two numbers is great, then perhaps a powers-of approach may be beneficial?

e.g.

32 = 3x3x3 + 3 + 2

therefore 32/3 = (3x3+1)x3 + 2, i.e. 32/3 = 10r2

I'm no expert in programming or math, but you guys seem to think multiplication is faster than division, and multiplication is faster than multiple additions, so surely you could come up with a suitable algorithm. I think it may be faster in some cases, as it proceeds exponentially (could you inline many power functions?)

I've no idea of the performance benefit, if any, but it's something I've been thinking of. Maybe one of you geniuses can come up with an algorithm, and show me that it's no good?

Regards,
Lyceus
Posted on 2002-12-26 20:17:36 by lyceus
hi

well, there are plenty resources on big integer division on the net, i implemented an easy algorithm, 'coz i just wanted to be able to do some modulo computations, anyway, you can just google a bit and you'll find several division algorithms
Posted on 2002-12-29 15:55:48 by roy
I believe there are various large number algorithms explained in the Handbook of Appled Cryptography, which you can download freely off the net, here: http://www.cacr.math.uwaterloo.ca/hac/
Chapter 14 is the one you want.
Posted on 2003-12-09 16:36:45 by Bruce-li
Hi all,

Knuth Vol II discussed about the arbitrary division of integers, I suppose it is one of the best method available and also pretty fast. I have implemented division of arbitrary ints. using this algo. It's fast and cool also.
However HAC also discuss about the division. Many options are there all u have choose one of them

regards
cult
Posted on 2003-12-09 22:43:14 by cult

I believe there are various large number algorithms explained in the Handbook of Appled Cryptography, which you can download freely off the net, here: http://www.cacr.math.uwaterloo.ca/hac/
Chapter 14 is the one you want.

Woah University of Waterloo, damn school is full of walking brains.
Posted on 2003-12-10 21:07:04 by x86asm