Searching \ for '[pic]: 9' in subject line. ()
Help us get a faster server
FAQ page: www.piclist.com/techref/microchip/devices.htm?key=pic
Search entire site for: '9'.

Exact match. Not showing close matches.
'[pic]: 9'
2001\06\07@154220 by

Let's turn all of this amateur mathematical rambling about repeating 9's into
something useful:

What's the most efficient PIC code (execution time) to determine if a number is
evenly divisible by 9?

I think it can be done in 12 instructions, right Dmitry.

Scott

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

On Thu, Jun 07, 2001 at 02:55:29PM -0500, Scott Dattalo wrote:
> Let's turn all of this amateur mathematical rambling about repeating 9's into
> something useful:
>
>  What's the most efficient PIC code (execution time) to determine if a number is
> evenly divisible by 9?
>
> I think it can be done in 12 instructions, right Dmitry.

What's that range of the number?

BAJ

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

At 02:55 PM 6/7/01 -0500, Scott Dattalo wrote:
>Let's turn all of this amateur mathematical rambling about repeating 9's into
>something useful:
>
> What's the most efficient PIC code (execution time) to determine if a
number is
>evenly divisible by 9?
>
>I think it can be done in 12 instructions, right Dmitry.
>
>Scott

Notice that to divide by 9 implies dividing by 3 followed by another divide
by 3.  This rings a bell: check the archives for the Payson/Reid/Dattalo
method of determining if a # is divisible by 3 and read up on how to do it.

Being simple minded and easily impressed, I saved that particular posting
and dug it out just now.  Here it is for those who missed it the first time:

From: Scott Dattalo <sdattalounix.SRI.COM>
Organization: SRI Intl.
Subject:      Re: determine if # divisible by 3 - PDB3WRM
To: PICLISTMITVMA.MIT.EDU

Dwayne Reid wrote:

> I am looking for a way to determine if a byte value is divisible by 3 and
> was about to appeal for help when I remembered that Andy Warren had started
> a discussion on that very topic about a year ago.  I went looking in my mail
> archives and found something that looked quite good written by John Payson.
> I tried the shorter of the 2 routines that John posted and found problems
> with it.  The longer (but faster) routine worked just fine.  I spent a
> couple of hours with the problem routine and made changes which seem to work
> just fine.

I was fascinated with John's algorithm when he first posted it.
However, I did not take the time until last weekend to really understand
how it works. Since there is some interesting number theory, algorithm
analysis, and PIC code, I think there may be several of you who are
interested in the results.

John's "divisible-by-three" algorithm plus Dwayne's modifications is
very similar to the "casting-out-nines" algorithm. The "casting-out-
nines" algorithm tests for whether a number is divisible by 9 by
summing up the individual (base-10) digits of the number and checking
whether the sum is divisible by 9. For example, 2+3+4=9 is divisible
by 9 so we know that 234 is too (and so is 243,342,324,423,432).

A "casting-out-threes" algorithm in base-4 is conceptually identical
to the "casting-out-nines" in base-10. For example, if we had 1221 in
base-4 we know it's divisible by 3 since 1+2+2+1 = 6 is divisible by 3.
Here's the "proof". A base-4 number can be written as:
____
\
N = /___ a_i * 4^i

where the a_i's are the base-4 digits (0,1,2,3) of the number.

____
\
N = /___ (a_i * (4^i - 1) + a_i )

If N is divisible by three, then N mod 3 is equal to 0. So take the
'mod 3' of each side:

____
\
N mod 3 = /___ (((a_i * (4^i - 1)) mod 3) + (a_i mod 3))

Two observations:
a) 4^i - 1 is divisible by 3. This can be seen by re-writing

4^i-1 = 3*4^(i-1) + 3*4^(i-2) + ... + 3*4^0
Since each term in the sum is divisible by three, then the sum
is divisible by three too.

b) a_i mod 3 = a_i or 0 (because a_i = 0,1,2,3). Since we are looking
for the result of N mod 3 = 0, we can replace a_i mod 3 with a_i.

Combining these two observations:

____
\
N mod 3=  /___ a_i    (mod 3)

If this sum is greater than 3, then we can repeat the algorithm.

PDB3WRM algorithm:
Now we are ready to look at John's "divide-by-three" PIC algorithm.
For brevity, let's write the input Number as a generic 4-digit
base-4 number:

Number = a*64 + b*16 + c*4 + d

Here's John's routine with Dwayne's modifications. I've added the
details
of how the routine modifies Number:

>         swapf   Number,w        ; split #, add 2 halves, keep Most Sig
Nybble
W = c*64 + d*16 + a*4 + b

>         addwf   Number,f        ; Note [MSN of Number] % 3 == old Number % 3
Number = (a+c)*64 + (b+d)*16 + (a+c)*4 + (b+d)

>         rrf     Number,w        ; We want to add what are now upper and
lower
W = (a+c)*32 + (b+d)*8 + (a+c)*2 + (b+d)>>1
carry = (b+d)&1    ;i.e. lsb of the sum of b and d is in the carry

>         rlf     Number,f        ;   two bits of MSN; 00 or 11 would be good.
Number = (a+c)*128 + (b+d)*32 + (a+c)*8 + (b+d)*2 + (b+d)&1

>         addwf   Number,w        ; If bits 6&7 are 1, # is divisible by 3
W = (a+c)*128 + (a+b+c+d)*32 + (a+b+c+d)*8 + (a+b+c+d)*2 +
(b+d)>>1 + (b+d)&1

>         addlw   b'00100000'     ; treat bits 6&7 as 2 bit #, increment
>         andlw   b'01000000'
>         skpz
>          retlw  0               ; Return "nope"
>         retlw   1               ; Return "yep"

In the last equation it can be seen that the 4 digits are added
together.
Unfortunately, there's complicated interaction between the sums.
Furthermore
there's that annoying business with b and d at the end. However after
closer inspection, it can be shown that there are only 14 unique cases
that
need to be analyzed. 13 cases are due to the sum of the digits ranging
from
0 to 12 (the numbers are in binary):

(a+b+c+d)   |  (a+b+c+d)*32 + (a+b+c+d)*8 + (a+b+c+d)*2
-------------+------------------------------------------
==> 0000     |    00000000
0001     |    00101010
0010     |    01010100
==> 0011     |    01111110
0100     |    10101000
0101     |    11010010
==> 0110     |    11111100
0111     |    00100110
1000     |    01010000
==> 1001     |    01111010
1010     |    10100100
1011     |    11001110
==> 1100     |    11111000

All rows marked with '==>' correspond to a sum of base-4 digits that
is divisible by three. The key thing to note is that bits 5 & 6 are
the same value in the second column for those numbers divisible by 3.
The last four lines of the PIC program cleverly detect this.

We have one more case to consider that concerns the expression
(b+d)>>1 + (b+d)&1
that the PIC algorithm adds to the second column of data in the table.
This expression evaluates to either 0,1,2, or 3. Adding these numbers
to the second column of data only affects bits 5 & 6 for the case
when the sum of the digits is 0011. And even there it has the effect of
changing those bits from highs to lows. So the condition that "bits 5
& 6 are the same" is unchanged.

Oh btw, the state of the carry bit upon entry has no effect on the
result.

One more observation. The expression in the second column of the table
can be re-written:
(a+b+c+d)*32 + (a+b+c+d)*8 + (a+b+c+d)*2 = (a+b+c+d)*42
And the last four steps in the program check bits 5&6 for mod 3'ness.
This can be expressed like so:

Number mod 3 = ((a+b+c+d)*21)/16 mod 3

where Number = a*64+b*16+c*4+d
Which I guess is a concise way of stating the "Payson-divisible-by-3-
with-the-Reid-Modification" or PDB3WRM algorithm.

> Some really neat concepts came out of that discussion that Andy started back
> then.

Yeah, he has a knack for that. Hey Andy, where have you been?

Scott
--
"The problem with television is not the resolution."
Hugh. F. Frohbach

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

On Thu, 7 Jun 2001, Byron A Jeff wrote:

> On Thu, Jun 07, 2001 at 02:55:29PM -0500, Scott Dattalo wrote:
> > Let's turn all of this amateur mathematical rambling about repeating 9's into
> > something useful:
> >
> >  What's the most efficient PIC code (execution time) to determine if a number is
> > evenly divisible by 9?
> >
> > I think it can be done in 12 instructions, right Dmitry.
>
> What's that range of the number?

Oh, I guess that might be important - 1 byte - although for about 8 more
instructions you can handle 2 bytes.

Scott

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

I'm too busy now to tackle the problem (end of school,
and as a teacher I am inundated with work!), but
I offer this observation: The sum of the digits of any
multiple of nine will always add up to nine. If you get

For example, the digits in 2736 add up to 18. The digits
in 18 add up to 9, so 2736 is an integer multiple of 9.

Fr. Tom Mcgahee

{Original Message removed}
> > >  What's the most efficient PIC code (execution time) to determine if a
number is
> > > evenly divisible by 9?
> > >
> > > I think it can be done in 12 instructions, right Dmitry.

I expect a quick table lookup is the most efficient PIC code (execution
time) ;-)

Bob Ammerman
RAm Systems
(contract development of high performance, high function, low-level
software)

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

>For example, the digits in 2736 add up to 18. The digits
>in 18 add up to 9, so 2736 is an integer multiple of 9.

This might be able to be done in 12 instructions, but any more than 8 or 9
bits might be a stretch.

Scott, if you can't offer a solution to your own question, especially in
this area, then we're all in trouble :)

--Andrew
_________________________________________________________________

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

On Thu, 7 Jun 2001, Drew Vassallo wrote:

> >For example, the digits in 2736 add up to 18. The digits
> >in 18 add up to 9, so 2736 is an integer multiple of 9.
>
> This might be able to be done in 12 instructions, but any more than 8 or 9
> bits might be a stretch.
>
> Scott, if you can't offer a solution to your own question, especially in
> this area, then we're all in trouble :)

Hint:

16 = 18 - 2

:)

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

On Thu, 7 Jun 2001, Drew Vassallo wrote:

> Scott, if you can't offer a solution to your own question, especially in
> this area, then we're all in trouble :)

I was guessing it would take 12 instructions based of course on Dmitry's Law
(all complicated, highly optimized snippets take exactly 12 instructions). After
getting it down to 12, I quit working on it.

;;----------------------------------------------------
;; Check to see if a number is evenly divisible by 9
;; (e.g. N%9 == 0)
;;
;;
;; An 8-bit number can be written like:
;;
;;   N = abcdefgh
;;     = a*128 + bcde*8  + fgh
;;     = a*128 + bcde*(9-1) + fgh
;;     = a*128 + bcde*9 - bcde + fgh
;;
;; Evaluate N%9:
;;
;; N%9 = (a*128 + bcde*9 - bcde + fgh) % 9
;;
;; Let's look at the first tow terms in the expression:
;;
;;  a*128 % 9 = a*2 % 9  ( because 128 = 126 +2)
;;
;;  (bcde * 9) % 9 = 0
;;
;; re-writing:
;;
;; N%9 = (a*2 - bcde +fgh)
;;
;;
;; Enter: W contains the number to test
;; Exit:  Z is set if the number is evenly divisble by 9

movwf   temp    ;shift left by 2
;and bcde into the upper nibble
andlw   7       ;grab the lower three bits
skpnc           ;if the MSB ('a') was set then
addlw  2       ;a*2 == 2, W = a*2 + fgh.
swapf   temp,f  ;put bcde into the lower nibble
subwf   temp,w  ;W = bcde - (a*2 +fgh)

;at this point, if N%9 is zero, then W contains -9,0,9
;so just check these three cases

skpdc           ;If W is less than 0
andlw   0x0f    ;If W was/is zero then set Z
skpz            ;If W is greater than 0
addlw  -9      ; then subtract 9

Works in gpsim.

Scott

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

Hi Scott,

Here is my long version (15 cycles/instructions):

;w holds input 8-bit value

movwf temp
andlw 0x0F
xorwf temp, f
swapf temp, f
clrc
rlf temp, f
subwf temp, w
skpz
xorlw 247
skpz
xorlw 247^9
skpz
xorlw 9^18
skpz
xorlw 18^27

;Z - w divides by 9
;NZ - doesn't

Any other ideas? :)

Nikolai

---- Original Message ----
From: Scott Dattalo <scottDATTALO.COM>
Sent: Friday, June 08, 2001 2:24:43
To: PICLISTMITVMA.MIT.EDU
Subj: [pic]: 9

{Quote hidden}

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

All hail Scott, a true Wizard!

This thing contains several great tricks.

>         movwf   temp    ;shift left by 2
>                         ;and bcde into the upper nibble

Very nice way to isolate the pieces needed.

>         andlw   7       ;grab the lower three bits
>         skpnc           ;if the MSB ('a') was set then

Depends on the carry set two instructions ago.

>          addlw  2       ;a*2 == 2, W = a*2 + fgh.
>         swapf   temp,f  ;put bcde into the lower nibble
>         subwf   temp,w  ;W = bcde - (a*2 +fgh)

The comment doesn't say so, but of course the high nibble of
W is trash right now, but ....

>   ;at this point, if N%9 is zero, then W contains -9,0,9
>   ;so just check these three cases
>
>         skpdc           ;If W is less than 0

...it doesn't matter because we use the digit carry instead of the full
carry!

>         andlw   0x0f    ;If W was/is zero then set Z

...and then (and only then!) get rid of the high order bits.

>         skpz            ;If W is greater than 0
>          addlw  -9      ; then subtract 9

Very, very nice!

[and I would be most surprised if anyone could improve on 12 instructions]

Bob Ammerman
RAm Systems
(contract development of high performance, high function, low-level
software)

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

Similarly, an old accountant's trick: If something doesn't balance, try
dividing the error by three. If it IS divisible by three, it's probably a
couple transposed digits.

For example:

12345 - 12435 = -90, which is divisible by three.

Also, to tell if a number is divisible by three, add the digits. If the
sum is divisible by three, so is the original number.

Harold

On Thu, 7 Jun 2001 16:54:01 -0400 Thomas McGahee
<tom_mcgaheeSIGMAIS.COM> writes:
{Quote hidden}

> {Original Message removed}
>         Also, to tell if a number is divisible by three, add the digits.
If the
> sum is divisible by three, so is the original number.

Even better.
If the sum is more than one digit, add all the digits of the answer.
Repeat this until you have only 1 digit.
Answer should be 3, 6 or 9 if original number was divisible by 3.

RM

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email listservmitvma.mit.edu with SET PICList DIGEST in the body

> Also, to tell if a number is divisible by three, add the digits.  If the
> sum is divisible by three, so is the original number.

I've never quite understood how to prove this sort of thing.  Entirely too
discrete, or something.  Furthermore...  Does this HELP any if you have a
binary number in a computer?  After all, you'd have to derive the decimal
digits of the number, which (usually) involves successive and multiple
divisions by 10, which is a lot harder than just dividing by three in
the first place...

I suppose that if you have an easy way to convert to base 9, then all
the numbers divisible by 9 will end in zero, right?

BillW

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email listservmitvma.mit.edu with SET PICList DIGEST in the body

William Chops Westfield:
>> Also, to tell if a number is divisible by three, add the digits.  If the
>> sum is divisible by three, so is the original number.

> I've never quite understood how to prove this sort of thing.  Entirely too
> discrete, or something.

This method works because of a regularity in the remainder after
dividing each digit (or a bit in binary) by 3. For example:

1/3 = 1/3
10/3 = 3 + 1/3
100/3 = 33 + 1/3
1000/3 = 333 + 1/3

See, the remainder for each digit is 1/3. The integer portion of the
result can be ignored, because it divides evenly.

A number can be represented as a sum of its digits multiplied by their
weights (ones, hundreds, thousands, etc.). E.g. 1245 = 1000 + 200 + 40
+ 5. But we know the remainder of dividing each digit, and it can be
simply accumulated, giving a next shot at the remainder:

1245   1000 + 200 + 40 + 5
---- = ------------------- = 1 * (333 + 1/3) + 2 * (33 + 1/3) + 4 * (3
3            3

+ 1/3) + 5 * (1/3) =

Then we separate the evenly divided numbers:

= (1*333 + 2*33 + 4*3) * 1/3 + (1 + 2 + 4 + 5) * 1/3

The left half of that can be ignored, and the current remainder value (not
always final because of multiplication by digit values) is (1 + 2 + 4
+ 5)=12, or the sum of all digits. Then a question is: does the sum
divide by 3? Sum again all digits! 1+2=3. Yes, it really does.

Another example:

1234572457152345 % 3 ?

1+2+3+4+5+7+2+4+5+7+1+5+2+3+4+5=60

Next step: 6+0=6.

Answer: it divides, 1234572457152345 % 3 = 0

The same method works in binary:

1/3 = 1/3
2/3 = 2/3
4/3 = 1 + 1/3
8/3 = 2 + 2/3
16/3 = 5 + 1/3
etc.

The pattern repeats each two bits. Each even bit (2^0, 2^2, 2^4,...)
is multiplied by 1, each odd bit (2^1, 2^3, 2^5,...) multiplied by
two, and it all is added together until you get a 2-bit result.
In other words, break a binary number in strings of 2 bits and add them
together!

Example:
101011b = 43d

10b+10b+11b = 111b

1b+11b=100b

1b+00b=1b

The remainder is 1. The number doesn't divide by 3.

A variation of this method is also done when finding a modulo 9
result, but the pattern is tricker.

1/9=1/9
2/9=2/9
4/9=4/9
8/9=8/9=1-1/9
16/9=1+7/9=2-2/9
32/9=3+5/9=4-4/9
64/9=7+1/9=8-8/9
128/9=14+2/9=16-16/9

There are a number of ways you can calculate this. Given bits
abcdefgh, it can be one of:

ab-cde+fgh
a-2*bcd+efgh
-abcd+efgh
....

Now we need Scott to select the best one! :)

> Furthermore...  Does this HELP any if you have a
> binary number in a computer?  After all, you'd have to derive the decimal
> digits of the number, which (usually) involves successive and multiple
> divisions by 10, which is a lot harder than just dividing by three in
> the first place...

Of course it helps. Who cares about decimal? :)

> I suppose that if you have an easy way to convert to base 9, then all
> the numbers divisible by 9 will end in zero, right?

Yes, that's what is actually done. We find a remainder and check its
value.

Nikolai

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestmitvma.mit.edu

The theorem that 'a number is divisible by 3 if the sum of its digits is
divisible by 3' is not valid in base 2 and afaik in no other base than 10.

Peter

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestmitvma.mit.edu

From: "Peter L. Peres" <plpACTCOM.CO.IL>
To: <PICLISTMITVMA.MIT.EDU>
Sent: Sunday, June 10, 2001 3:38 PM
Subject: Re: [pic]: 9

> The theorem that 'a number is divisible by 3 if the sum of its digits is
> divisible by 3' is not valid in base 2 and afaik in no other base than 10.

I believe it is valid in any  base 3N+1, when N is a positive integer.

It is in particular valid in base 4, which is the basis behind the rather
elegant divide-by-three check tha was mentioned here in the past few days.

Bob Ammerman
RAm Systems
(contract development of high performance, high function, low-level
software)

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestmitvma.mit.edu

Forwarded for Scott who's ISP is belly up.

jamesnewtonpiclist.com
1-619-652-0593 phone
http://www.piclist.com

{Original Message removed}
Peter L. Peres <plpACTCOM.CO.IL> wrote:

> > The theorem that 'a number is divisible by 3 if the sum of its
> > digits is divisible by 3' is not valid in base 2 and afaik in no
> > other base than 10.

and Bob Ammerman <PICLISTMITVMA.MIT.EDU> replied:

> I believe it is valid in any  base 3N+1, when N is a positive
> integer.

Correct.  To generalize it further, the rule is:

A non-zero number in base ax+1, where a and x are integers,
is divisible by x if the sum of its digits is divisible by
x.

Even the weird cases like base 1 (if you define "divisible by 0"
as true for 0) and base 2 work.

This, by the way, makes it easy to test for divisibility by 7
(for which no base-10 rule exists) in base 8:

Test decimal 84 for divisibility by 7:

84 decimal = 124 octal

1 + 2 + 4 = 7

7 is divisible by 7, therefore 124 octal is divisible by
7, therefore 84 decimal is divisible by 7.

The base-10 test for divisibility by 11 can also be generalized
for other bases:

A non-zero number in base ax-1 is divisible by x if the sum
of its even-numbered digits differs from the sum of its
odd-numbered digits by a number diviible by x or equal to 0.

An example in base 10:

Test decimal 1353 for divisibility by 11:

1 + 5 = 6, 3 + 3 = 6
6 - 6 = 0
Therefore, 1353 is divisible by 11.

An example in base 21, (21 = ax-1 where a = 2 and x = 11):

In base 21, test 1353 decimal for divisibility by 11:

1353 decimal = 319 base 21
3 + 9 = C base 21 (12 decimal), 1 = 1
C base 21 - 1 = B base 21 (11 decimal)

B base 21 is divisible by 11 decimal, so 319 base 21 is
divisible by 11 decimal.

Base 21 is sorta useless, but this test IS useful for testing
divisibility by 3 in base 2:

201 decimal = 11001001 binary

1 + 0 + 1 + 0 = 10, 1 + 0 + 0 + 1 = 10
10 - 10 = 0

Therefore, 11001001 binary is divisible by 3.

-Andy

=== Andrew Warren - fastfwdix.netcom.com
=== Fast Forward Engineering - San Diego, CA
=== http://www.geocities.com/SiliconValley/2499

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestmitvma.mit.edu

Scott Dattalo wrote:
...
>> ab-cde+fgh
>> a-2*bcd+efgh
>> -abcd+efgh

> Actually, the last one should be
>  -2*abcd + efgh

Yes, thanks for noticing.

{Quote hidden}

This calculates -2*abcd + efgh, doesn't it? I can't see a
multiplication by 7. But this is a neat idea! Using the DC flag for
keeping the sum in the lower 4 bits. Extending it further:

> movwf temp
> swapf temp,w
> subwf temp,f
> skpdc
;> addlw 7 - comment this out
;convenient DC flag polarity, as after subtraction
skpdc            ;if overflowed again, subtract 16 % 9 = 7 or

> subwf temp,w
> skpdc
> andlw 0x0f
> skpz

That's 1 instruction too much though.

Nikolai

--