testing value of last digit of an integer.

[DTAshley at aol.com]

Hi,

The method you've proposed won't work.

There is a famous theorem in math, about reachability.  It goes something 
like:

i * m + j * n = k * gcd(m,n)

What it means is that with two integers m and n that are fixed for the 
problem, and two integers i and j that you may vary, you cannot form a sum that is 
not a multiple of the gcd of m and n.

You can also prove that all values of k can be attained by a suitable choice 
of i and j--perhaps with one being negative.

You can use the expression above to handle modulo arithmetic.  So, if I 
choose m=2 and j=5, it follows immediately that I can do modulo 2 arithmetic by a 
suitably negative choice of i.

What does this mean for you?

Testing the lower order bits of an integer--no matter how many you test if 
your test is confined to lower-order bits only--won't work because gcd(2,5) = 1, 
gcd(4,5) = 1, gcd(8,5) = 1, etc.  You can prove from the above that if you 
keep adding 5 to an integer, sooner or later you will see every possible 
combination of the lower-order bits.

However, that does not rule out the possibility that there is some low-cost 
test that considers all of the bits, but perhaps in a cheap way.  I'm not a 
strong enough mathematician to know the basis for such tests.

Let me give you two examples in base 10.

First, assume you want to test for divisibility by 5.  Since GCD(10,5) > 1, 
you can do this.  The test is easy.  Just look at the last digit.  This comes 
about from "reachability"--not every final digit is "reachable".

Second, assume you want to test for divisiblity by 3.  You can show 
mathematically, because gcd(10,3) = 1, that no matter how many final digits you 
consider, if you add 3 enough times you will get that pattern.  For example, if you 
only check the last two digits, you can show that if you add 3 enough times, 
you will get any final pattern.

gcd(5,2) = 1.  That is the issue.

However, that does not rule out the possibility that by considering ALL bits 
of the number, you can do it somehow cheaply.  A base 10 analogy is the adding 
of all digits to determine divisibility by 3.

But, I'm not a good enough mathematician to know whether such a test exists 
or how to find it.

Best regards, Dave.

In a message dated 4/4/2004 1:24:32 AM Eastern Daylight Time, 
cic_3_b at yahoo.com writes:


> I want to check if the last digit of an integer is 5.
> 
> I am contemplating using the mpz_tstbit function to test for the
> binary
> representation of 5 which is 0 1 0 1. The leading zero is to prevent
> 13 from
> accidentally being detected. Any further out and the binary digits
> would not
> affect the last digit.
> 
> Does anyone know any other way I can do this?
> 
> The numbers are quite large (about 300 digits) and it is already
> known that
> the numbers are odd.
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: /list-archives/gmp-discuss/attachments/20040404/58f4a637/attachment.htm