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 :-)
> 
> 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.
You could probably find that with Google. In any event, for very large
numbers there are lots of well-known algorithms.