As I said before, mossmoss, there *IS* no divide instruction for the Z-80. Similarly, there is no compiler. This is being done in pure assembly language. The way the hardware is configured, things are laid out in multiples of 12. I need a FAST way of determining whether an object is directly ON one of those boundaries. Right now it''s doing the subtraction method, but I was seeing if there was a pattern to multiples of 12 that I could use shifts for.

Vyvyan

I would use a binary search.

Example:

{
Answer = BIGGEST_POSSIBLE_NUMBER;
unit = Answer;

Test = 1;

while(Test!=0)
{
Test = Answer * 12 - Number
unit <<= 2;
if(Test < 0)
Answer += unit;
if(Test > 0)
Answer -= unit;
}

}

This function should work, and you can optimize the Answer*12 part. I would think it would work pretty fast. (This is psuedo-code, so it might not work, but it''s the idea that counts.)

-----------------------------
C++ is great, but when is B-
coming out?

I was looking at what MicahJon wrote, and I thought he was on to something, if you took a recursive approach...

int Divide( int num, int denom ){ // numerator, denominator int exp, powerOfTwo; powerOfTwo = GetLesserPower( denom, &exp ); // returns largest power of two less than denom int newNum, newDenom; newNum = ( denom - powerOfTwo ) * num; newDenom = denom << exp; if( newNum < 0 || newDenom < 0 ){ cout << num << "/" << (1 << exp) << " - [overflow]"; return ( num >> exp ); } else if( newNum <= newDenom ){ cout << num << "/" << (1 << exp) << " ( - "<< newNum << "/" << newDenom << ")"; return ( num >> exp ); } else{ cout << num << "/" << (1 << exp) << " - "; cout.flush(); getch(); return ( num >> exp ) - Divide( newNum, newDenom ); }}

Here's some output:

37/6= 37/4 - 74/16 - 592/256 ( - 75776/98304)= 7correct result: 6--74/11= 74/8 - 222/64 ( - 5328/5632)= 6correct result: 6--456/13= 456/8 - 2280/64 - 91200/4096 - 233472000/16777216 ( - 0/0)= 31correct result: 35--81/3= 81/2 - 81/4 - 162/16 - 1296/256 - 165888/65536 - [overflow]= 27correct result: 27--3105/73= 3105/64 - 27945/4096 ( - 16096320/19136512)= 42correct result: 42  

As you can see, the result is often off by 1 or more, and it easily overflows, but SO WHAT, at least all the divisions are powers of two!

Edit: Hmmm, pacman runs on a z-80, doesn't it... probably not that many z-80 developers in Austin... just made a connection here... ha, that's kinda funny!

Edited by - Eric on November 17, 2000 9:52:48 PM

This is the Radix-2 division algorithm for unsigned integers:

Given three registers with n bits:
A, B, P

Divide:
a / b

Move a into A
Move b into B
Move 0 into P

Loop n times
BEGIN
Shift PA left 1 (A's high bit goes to P's lowbit)
Signed Subtract B from P, store answer in P
If P is negative:
Set A's low order bit to 0.
Set P to B + P
Else:
Set A's low order bit to 1.
END

When complete:
Register A contains the quotient
Register P contains the remainder

On an Intel Machine with inline asm (I don't know Z-80 Instructions) it looks like this:

int divide(int a, int b){	const int mask1 = ~1;	int result;	__asm	{		mov eax, a;		mov edx, 0;		mov ebx, b;		mov ecx, 32;loophere:		shld edx,eax,1;		shl eax,1;		sub edx,ebx;		js restore;		or eax,1;		jmp next;restore:		and eax,mask1;		add edx,ebx;next:		dec ecx;		jnz loophere;		mov result,eax;	}	return result;}  

Edited by - WMiller on November 17, 2000 10:49:08 PM

WMillers algorith is esentially an optimized version of the algorithm I gave you earlier. Which was not so very well optimized, because c++ has it's limitations when writing low level code. Mainly two register shifts, and setting a specific bit.

Doing a litle reasearch if found out it's called the restoring division algorithm. But also note that it may require extra bits to prevent overflow. It requires n shifts, n substracts and an average of n/2 adds. There are however a non-restoring variant, which can eliminate the n/2 adds, but two more subtracts and one add.

A variant of the non-restoring algorithm is called SRT division algorithm. It improves the runtime even further by requiring only an average of n/2.67 substracts or adds.

For more information look here and look for sequential and srt divison.

Edited by - fredizzimo on November 18, 2000 1:59:49 PM

If you don''t have a shift left double you should have a rotate with carry that can accomplish the same thing. You have to start by clearing the carry on a shift left because it will be shifted into the low order bit. The high order bit gets shifted into the carry and you then rotate that with the next higher word. If you shift right then you have to set the carry to the sign, i.e. 1 is negative, 0 positive, if the value being shifted is signed.

If you have trouble understanding the algorithm it is basically the same as you would do it by hand only it is with base 2 rather than base 10 numbers. That reduces it to going in zero or one times. Since it was zero or one times you either subtract the divisor or don''t rather than multiplying it by the number of times it goes in before the substraction. At least that is my understanding of it. Looking at the algorithm I''m not so sure, but I assume any differances is just optimization.

Who are you answering to, LilBudyWizer?

He was responding to me. That''s a very efficient, general division method, which may find it''s way into a subroutine. Thanks!

Vyvyan

You should really take a look at the SRT algorithm. It''s a bit harder to implement, but on the other hand it''s faster.