Dividing by 20 (and 12)

[+johnnywc]

Hello all,

 

I'm looking for a fast way to divide by 20 and 12. The trick is I need to also know if the division yields no remainder. I've implemented a lookup table (after dividing by 8 ) for computing the div 20 and div 12, but this only gives me the integer portion (of course). What methods are people using to divide by these quirky numbers? I'd like to stay away from a bunch of huge tables (I think I would need 4 tables, 2 for both divide by 20 and 12, one with the integer part and the other with the remainder).

 

Any ideas are greatly welcomed.

 

Thanks,

Edited September 12, 2005 by johnnywc

[Cybergoth]

Hi there!

 

So what are the ranges for the input values?

 

Greetings,

Manuel

[+johnnywc]

Hi there!

 

So what are the ranges for the input values?

 

Greetings,

Manuel

930004[/snapback]

 

Hi,

 

I'm basically doing a re-write of Wizard of Wor and I'm trying to implement the maze movement logic. After reading some suggestions, it would appear that the best way is to check for "possible" moves at an intersection and to store these possible intersections in a table. I'll need to know whether the values are exactly at an intersection (the remainders), and, if so, what value to look up in the table based on the cell values (I think this is the best way to do it).

 

The WoW maze is 11x6, with each "cell" 12 pixels wide by 20 pixels high (for a 132x120 range). Actually, since I'm using a 2LK my Y values will only range from 0-60 (not 0-120), so the ranges are 0-131 for the X and 0-59 for the Y. The Y value will need to be divided by 10 (not 20).

 

Thanks!

[+batari]

Hello all,

 

I'm looking for a fast way to divide by 20 and 12.  The trick is I need to also know if the division yields no remainder.  I've implemented a lookup table (after dividing by 8 ) for computing the div 20 and div 12, but this only gives me the integer portion (of course).  What methods are people using to divide by these quirky numbers?  I'd like to stay away from a bunch of huge tables (I think I would need 4 tables, 2 for both divide by 20 and 12, one with the integer part and the other with the remainder). 

 

Any ideas are greatly welcomed.

 

Thanks,

929997[/snapback]

Any reason why you can't do a successive subtraction loop? It's very simple code-wise, you can easily get a remainder, and by 20 or 12 there shouldn't be too many loop iterations.

[+johnnywc]

Hello all,

 

I'm looking for a fast way to divide by 20 and 12.  The trick is I need to also know if the division yields no remainder.  I've implemented a lookup table (after dividing by 8 ) for computing the div 20 and div 12, but this only gives me the integer portion (of course).  What methods are people using to divide by these quirky numbers?  I'd like to stay away from a bunch of huge tables (I think I would need 4 tables, 2 for both divide by 20 and 12, one with the integer part and the other with the remainder). 

 

Any ideas are greatly welcomed.

 

Thanks,

929997[/snapback]

Any reason why you can't do a successive subtraction loop? It's very simple code-wise, you can easily get a remainder, and by 20 or 12 there shouldn't be too many loop iterations.

930046[/snapback]

 

Thanks for the tip - I've thought about that but I thought I had read somewhere that it was the slowest way to go. But you're correct - a div by 20 or 12 can only go so many loops. Perhaps I'll start with that and see how i'm doing cycle-wise. I can always optimize (with lookups) when and if the time comes (which I'm sure it will!)

 

Thanks again,

[supercat]

Thanks for the tip - I've thought about that but I thought I had read somewhere that it was the slowest way to go.  But you're correct - a div by 20 or 12 can only go so many loops.  Perhaps I'll start with that and see how i'm doing cycle-wise.  I can always optimize (with lookups) when and if the time comes (which I'm sure it will!)

 

It's probably not a bad idea to include a check at the start to kill off half the range, especially since you can do so pretty cheaply.

 

I'd suggest doing something like this:

; Divide acc [value 0-131] by 12
 ldy #6
 sec
 sbc #72
 bcc isneg
 ldy #11
 sbc #60 ; Note: Carry will be clear
isneg:
 dey
 adc #12
 bcc isneg

Note that by subtracting until the number goes negative, and then adding until it goes positive, the value that's left in the accumulator will be the positive modulus. Note that if the first 'bcc' is taken, the second loop will execute 1-6 times; otherwise, it will execute 1-5 times. Note that the loop will execute an excessive number of times if the input accumulator value was 132 or more. Values in the range 132-143 may be handled by adding a "bcs exit" after the "sbc #60".

[Thomas Jentzsch]

Or divide by 8 (shift!) and then use a lookup table.

[+johnnywc]

Or divide by 8 (shift!) and then use a lookup table.

930370[/snapback]

 

Hello Thomas,

 

Thanks for the idea - I actually am using this already and it's great for getting the integer part. Any ideas on a quick way to get the fractional part besides a huge lookup table or division by subtraction?

 

Thanks again!

[Heaven/TQA]

well... you can use fixed point maths and use a lookup table as well? thomas helped me for an similar problem in my Boinxx Game... have a look into another thread...