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

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

hi

you might want to take a look at my lame bignum lib that implements bignumber division (http://www.effervescence.com, archives section)

you might want to take a look at my lame bignum lib that implements bignumber division (http://www.effervescence.com, archives section)

Thanks ROY, You probably mean the thing you call:

Why do you promote something that you give this description???

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???

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.

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.

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.

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.

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

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

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

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

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.

Chapter 14 is the one you want.

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

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

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.