From: Vimal <j.vimal@...>
Date: 2006-10-17T20:35:03+09:00
Subject: A possible optimization in Bignum/Division?

------=_Part_152118_113334.1161084899889
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

------=_Part_152118_113334.1161084899889--