testing value of last digit of an integer.

[David McKen]

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