How can 2*q*y be computed without multiplication in divide algorithm?

[Rather Iffy]

I learned a lot about recursion by trying to figure out how divide algorithm does the computation.
Every recursive call of divide is done with greater values of y , and y eventually hits the ceiling x .
It took some time to see that this is a complicated way to count down to zero.
Also the +1 in "else 2 * q + 1" also took some time to figure out.

But i fail to see how to avoid the multiplication of "2*q"  by "y" in the the test "(x-2*q*y) < y" .
I would appreciate some help on this.

I am losing speed in finishing the Jack OS, 2 days by now, alas !
--Chrit

[cadet1620]

Rather Iffy wrote

But i fail to see how to avoid the multiplication of "2*q"  by "y" in the the test "(x-2*q*y) < y" .
I would appreciate some help on this.

I am losing speed in finishing the Jack OS, 2 days by now, alas !

For now, I'd suggest coding it as it's written -- using 2*q*y. That's what I did. Then I came back to it after I got the OS finished.

The aha! insight I had was that q is computed on the way out from the recursive calls. The returned q from the deepest call is always 0, so the 2*q*y from that return is 0 as well.

After divide() returns q to the next level up divide(), it updates q without the need for multiplication -- either q+q or q+q+1 -- and returns q. At the same time, it can update a 'qy2' variable that maintains 2*q*y value that corresponds to q. This update can also be done using just addition.

E-mail me if you want more details,
--Mark

[Rather Iffy]

Figuring out the pattern in the courses of values of the '2*q*y' , q and y variables was quite a job.
I found it difficult to imagine the courses of the values of all these variables in relation to each other through all the recursion steps. But that way i found the addition-only solution.

I used Math.bit( y+y,15 ) to test the most significant bit of the next sum y+y : a 1 signifying that the sum of two positive integers is a negative integer, meaning in this context: 'Overflow' .
I found that more natural than testing overflow with the condition y + y < 0 .

First i thought it easy to repair overflow but i have given that up , so now Math.divide only reports 'Overflow' and returns 0 (why zero?) because it has to return an integer.

And it works ! So far.

Thnx Cadet for the tip on the '2*q*y' variable.

--Chrit