testing value of last digit of an integer.
David McKen
cic_3_b at yahoo.com
Sun Apr 4 20:25:55 CEST 2004
I see.
I was hoping to optimize a function.
Guess I have to look elsewhere in the algorithm for optimizations.
----- Original Message -----
From: DTAshley at aol.com
To: cic_3_b at yahoo.com ; gmp-discuss at swox.com
Sent: Sunday, April 04, 2004 11:39 AM
Subject: Re: testing value of last digit of an integer.
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.
---------------------------------
Do you Yahoo!?
Yahoo! Small Business $15K Web Design Giveaway - Enter today
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /list-archives/gmp-discuss/attachments/20040404/daad646f/attachment.htm
More information about the gmp-discuss
mailing list