Re: A possible optimization in Bignum/Division?

> Vimal wrote:
> > Hi all
> > I feel that there could be a possible optimization in the Bignum/Division
> > algorithm implemented in Ruby 1.8.5.
> > The numbers are stored in 32 bit arrays in hex-format. And, division in the
> > domain of binary numbers is really easy, as the possible value of quotient
> > could be just 0 or 1. The basic idea here is:
> > 
> > quotient = "0000..." zero filled to appropriate length.
> > 
> > Dividend = 100010101000 say
> > Divisor = 1011 say.
> > 
> > Consider leftshifting the Divisor , so that the Divisor and Dividend have
> > equal lengths. This is an easy and fast operation.
> > 
> > Dividend = 100010101000
> > Divisor =    100110000000
> > 
> > Now, try to subtract. You cannot, since divisor is > Dividend. So, right
> > shift Divisor by 1.
> > 
> > Dividend = 100010101000
> > Divisor =    010011000000 Left shift count position = K BITS say.
> > 
> > Now subtract. So, the QUO[K] = 1. Kth bit is set to 1.
> > 
> > Dividend = 001111101000
> > Divisor =    001001100000 (After shifting again).
> > 
> > Again subtract. And keep looping.
> > 
> > I feel this is more efficient than the one implemented in the code. Or
> > is it
> > the same? Or am I wrong? Would love to hear comments :-)
Now its same. unless divisor fits to BDIGIT (at most platforms unsigned int). when we do
BDIGIT_DBL x
for i=size...0
x=(x%divisor)<<BITSPERDIG+dividend[i]
result[i]=x/divisor

I plan try these variants if we can speedup by not testing which is greater. Like always substracting that they have same lenghts and handle when result is negative. or substracting that divisor always has one digit less
> > 
> > Regards
> > Vimal
> > 
> 
> IIRC a long time ago someone compared Ruby's native Bignum arithmetic
> with that provided by the "optimized" GMP library. For numbers less than
> a certain size, Ruby's was faster and over that size, GMP was faster.
I know this one. Benchmark is at ruby GMP binding.
Cause is that TYPE(y)==T_BIGNUM is five times faster than rb_is_kind_of.(perhas calling non_core class method is slower but I didn't test this one)

I dont understand license issue when GMP is LGPLed

> You could probably find that with Google. In any event, for very large
> numbers there are lots of well-known algorithms.
> 

My bignums are almost complete I miss only faster division. 
GMP uses recursive division that we have so big radix that dividend is 4 digits long and divisor 2 digits and use classic division at that numbers.
I found article about newton inversion. Idea is that if we do it with floats we can compute x/y by computing inv=1/y and multipling x by z.
So we compute z as 2<<(size x+size y)/y and multiply.x by it. We have aproximation of x/y which differs most by 1. We multiply it by y  and substract x,correct aprox and compute remainder.
Trick is that 2<<(size x+size y)/y can be done with newton inversion which doesn't use division. Mayor advantage is that we can do newton inv of y once and then divide many numbers by y each cost 2 multiplications.(faster from 2000 digits -natural use is numeric ring ) Dividing one number with another by newt inversion is faster from 1500000 digits.(compared to recursive alg).