Re: [stella] disassemblies and other stuff

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