Subject: Re: [stella] disassemblies and other stuff From: "Andrew Davie" <adavie@xxxxxxxxxxxxx> Date: Tue, 9 Jan 2001 13:29:40 +1100 |
> So I'm thinking, what's an easy way to figure out if a number is divisible > (evenly) by another number? For division by exact powers of 2 ie: 2^n, the low n bits will be 0 when an exact divisor is found. That is, if you AND with (2^n)-1 and the answer is 0, then you have a divisor. In your example, testing for divisibility by 8 (=2^3), your low 3 bits are always 0 when a divisor is found, so you just have to AND with 7 (binary 111) to test for divisibility by 8. ie: LDA number AND #7 BEQ isdivisibleby8 For non powers of two, the quickest way is table-lookup; you "only" need a 256+n byte table. ie: divisibility by 5... LDY number LDA divisibleby5,Y BEQ isdivisibleby5 divisibleby5 I = 0 WHILE (I<256) { DB (I%5) I = I + 1 } You'll have to adjust the table generation to your particular assember. (I%5) is I modulus 5 (ie: the remainder on division by 5). If you're dividing by an even number, you can right-shift first (divide by two) and halve your table requirements... eg: division by 3 LDA number LSR A TAY LDA divisibleby3,Y BEQ isdivisibleby6 Finally, if you can factor your divisor then you can re-use tables. For example, division by 15 would be first a divide by 5 and then by 3 (or vice versa). If both are zero-remaindered, then you know your number is divisible by 15. > I played around with Nick's LSR/AND stuff but I don't quite understand what > it's doing, as I'm thinking more in terms of decimal rather than bitwise or > binary math. You really REALLY need to start thinking in binary. Putting the explanation in decimal, though... a number is (for example) divisible by 1000 if and only if the last three digits of the number are 000. That is, 212000 is divisible by 1000... you didn't need to actually do the division, right... you just saw that it ends in 000... it is an even number of thousands (212 to be exact :)... well, the same for binary numbers.... let's just put a % in front of it.... a number is (for example) divisible by %1000 (ie: decimal 8) if and only if the last three digits of the number are %000. So, to TEST for divisibility by 8, we need to MASK OFF (or isolate) those three bits. The AND instruction will mask off bits, and the bits we need are 2^0, 2^1 and 2^2. So, telling the processor to mask these, we use 7 (2^0+2^2+2^2) as the mask. It's exactly analogous to how we do it mentally for powers of 10. Just think in powers of two instead. Cheers A -- _ _ _| _ _ _| _ * _ _ , (_|| )(_|( (/_\/\/ (_|(_|\/(_(/_ ,~' L_|\ ,-' \ see my Museum of Soviet Calculators at ( \ http://www.taswegian.com/MOSCOW/soviet.html \ __ / L,~' "\__/ @--> v -- Archives (includes files) at http://www.biglist.com/lists/stella/archives/ Unsub & more at http://www.biglist.com/lists/stella/
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [stella] disassemblies and othe, Rob | Thread | Re: [stella] disassemblies and othe, Andrew Davie |
Re: [stella] Tetris brainstorming, Andrew Davie | Date | Re: [stella] disassemblies and othe, Andrew Davie |
Month |