testing value of last digit of an integer.
DTAshley at aol.com
DTAshley at aol.com
Sun Apr 4 17:39:05 CEST 2004
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
More information about the gmp-discuss
mailing list