@Gene & Lucifer: Great thinking. For binary integers, you can
calculate the states of the finite automaton as you go, without ever
storing it. The following code returns true if and only if the
arbitrary integer n is divisible by the arbitrary nonzero integer k.
int IsDivisibleBy( int n, int k )
// for arbitrary integer n and arbitrary nonzero integer k,
// IsDivisibleBy returns the truth value of the statement
// "n is divisible by k"
{
int state = 0;
if( k < 0 ) k = -k; // k = abs(k)
if( n < 0 ) n = -n; // n = abs(n)
while( n )
{
state += state + (n & 1);
if( state >= k ) state -= k;
n >>= 1;
}
return state == 0;
}
As I've shown before, you can do better for special cases, such as
divisibility by a fixed constant that is a power of 2 or a power of 2
plus or minus 1. But this code is sufficiently efficient that it may
not be worth the trouble to go with customized codes for special cases
except in the most computationally intensive situations.
BTW: If you change the name to IsMultipleOf, the code works even for k
= 0; it returns true for n == 0 and false otherwise.
Dave
On Jan 22, 9:36 am, Gene <gene.ress...@gmail.com> wrote:
> You can extend this thinking to finding the value mod M of any string
> of base B digits. (In this case M=5, B=2, and you are looking for a
> mod 5 value of zero.) Construct a finite automaton with M states 0 to
> M-1. The current state of the automaton tells you the value mod M of
> the digits seen so far. For current state m and new digit d, the
> automaton's next state table has value (m * B + d) mod M. Of course
> you don't compute this value while reading the string. It's stored
> explicitly in the table. For this problem the next state table looks
> like this:
>
> d
> m 0, 1
> 0 => {0, 1}
> 1 => {2, 3}
> 2 => {4, 0}
> 3 => {1, 2}
> 4 => {3, 4}
>
> Then the algorithm is just:
>
> state = 0;
> while another digit remains
> d = next digit
> state = next_state[state, d]
> end;
> return state;
>
> For this particular problem you'd check that the return value is zero.
>
> On Jan 22, 10:26 am, Lucifer <sourabhd2...@gmail.com> wrote:
>
>
>
> > @above...
>
> > The above explanation is based on the answer that i gave to the
> > following question asked:
>
> > Given an infinite stream of bits, at any given point of time u have
> > tell whether the no. formed by the bits sent till now is divisible by
> > 3.
>
> > The catch in the above question is that you can't store the integral
> > value formed by the bit pattern. At any given point of time u will
> > only have the current bit. Hence, we need to preprocess the bits sent
> > to us and then generate the answer.
>
> > The same approach can be applied here..
> > 2^0, 2^1 gives remainder 1 and 2(-1) when divided by 3.
>
> > Code:
>
> > int r[2]= {1,2};
> > int i =0;
> > While(there is an incoming bit X)
> > {
> > if(X&1)
> > {
> > currRem += r[i%2];
> > if (currRem >=3) currRem -=3;
> > }
> > ++i;
>
> > }
>
> > -------------------------------------------------
> > Hence, the actual question can be changed saying that given an
> > infinite stream of bits, at any given point of time we need to figure
> > out whether its divisible by 5.
> > The above given code will work for this case as well.
>
> > On Jan 22, 12:19 pm, Lucifer <sourabhd2...@gmail.com> wrote:
>
> > > @another approach..
>
> > > The remainders when the following nos. are divided by 5 are :
> > > Numbers Remainder
> > > 2^0 1
> > > 2^1 2
> > > 2^2 4 (-1)
> > > 2^3 3 (-2)
>
> > > Now, we know that given a product of nos. a1, a2, ... aN when divided
> > > by a no. K, the remainder is:
> > > the product of (a1 mod K).... (aN mod K) i.e
>
> > > [ Lets call this as NumTheoProp1]
> > > a1* a2* a3*...*aN = x*K + (a1 mod K)*(a2 mod K)*....*(aN mod K)..
> > > [ the above can be proved by representing ai = xi * K + (ai mod K),
> > > and then multiplying all the ai's..]
>
> > > We can then recursively apply the same approach to the product of
> > > remainders until and unless the remainder is smaller than K.
> > > But a complete reduction into a value < K is not the point here. We
> > > are going to use the above fact for the following:
>
> > > Say, the given no. is 2^R ...
> > > Now, the above can be interpreted as,
> > > 2^R = 2^(4q) * 2^r, where R = 4q + r and 0<=r < 4
>
> > > Now we know that, 2^4 when divided by 5 gives a remainder 1..
>
> > > Hence applying the [NumTheoProp1] :
>
> > > 2^(4q) = (2^4)*(2^4)*... (q times)..
>
> > > when 2^(4q) = x*5 + (2^4 mod 5)^q..
> > > = x* 5 + 1..
>
> > > Hence,
> > > 2^R = 2^(4q) * 2^r
> > > = x*5 + (2^4q mod 5)*(2^r mod 5)
> > > = x*5 + (2^r mod 5)..
>
> > > Now, as 0<=r < 4, based on the remainder jolted at the starting..
> > > 2^r mod 5 = one of (1, 2, 4, 3)..
>
> > > But if you closely observe there is a pattern..
> > > For any no. 2^R where R>= 4 we can reduce it to 2^r where r < 4 by
> > > using [NumTheoProp1]
> > > Hence,
> > > No.( 2^r) Remainder
> > > 0 1
> > > 1 2
> > > 2 4
> > > 3 3
> > > 4 1
> > > 5 2
> > > 6 4
> > > 7 3
> > > .... and the cycle continues..
>
> > > Now. say a no. N is given, then it can be represented as,
> > > N = b0* (2^0) + b1* (2^1) + .... + bN* (2^logN)..
> > > where bi is either 0 or 1 [ basically it mimics the bit pattern)
>
> > > N mod 5 = ( [sum over all i ( (bi* (2^i)) mod 5 )] mod 5)
>
> > > Now, the inner mod 5 can be directly calculated based on the index of
> > > i (as there is a pattern). Btw it also depends on the value of bi. If
> > > bi =0, then the remainder will be 0 otherwise we will get the
> > > remainder based on the pattern..
>
> > > The outer mod 5, can be handled by following an incremental process,
> > > i.e whenever the current remainder becomes >=5 we will subtract 5 from
> > > it.
>
> > > Code:
>
> > > int N; // given number..
> > > int r[4] = {1, 2, 4, 3};
> > > int currRem = 0;
> > > int i = 0;
> > > while (N)
> > > {
> > > if (N&1)
> > > {
> > > currRem += r[i%4];
> > > if (currRem >=5)
> > > currRem -=5;
> > > }
> > > ++i;
> > > N >>= 1;}
>
> > > if ( currRem == 0)
> > > {
> > > printf("N is divisible by 5");
>
> > > }
>
> > > On Jan 22, 2:42 am, Dave <dave_and_da...@juno.com> wrote:
>
> > > > @Arun: Proof that n = 4*a + b is a multiple of 5 if and only if a - b
> > > > is a multiple of 5:
>
> > > > Given n, write it as n = 4*a + b where 0 <= b <= 3.
> > > > Note that 5*a is a multiple of 5, and 5*a - n = 5*a - (4*a + b) = a -
> > > > b.
> > > > If n is a multiple of 5, then 5*a - n is a multiple of 5, so a - b is
> > > > a multiple of 5.
> > > > Similarly if n is not a multiple of 5.
>
> > > > QED
>
> > > > Dave
>
> > > > On Jan 21, 11:57 am, Arun Vishwanathan <aaron.nar...@gmail.com> wrote:
>
> > > > > @dave: thanks for that..but i just wanted to know as to how u thot of
> > > > > converting n to a-b in the iteration. when u say 4a +b is a multiple
> > > > > of 5
> > > > > iff a-b is a muliple of 5 i was able to get that only when i tried an
> > > > > example...if they ask divisbility by 3 or 6 or 7 how wud the logic
> > > > > change??
>
> > > > > On Sat, Jan 21, 2012 at 9:34 AM, karthikeyan muthu <
>
> > > > > keyankarthi1...@gmail.com> wrote:
> > > > > > check the last char ... it should be 0 or 5 , int to string without
> > > > > > mod
>
> > > > > > On Sat, Jan 21, 2012 at 10:05 PM, Dave <dave_and_da...@juno.com>
> > > > > > wrote:
>
> > > > > >> @Karthikeyan: Is this supposed to relate to the question of
> > > > > >> determining divisibility by 5?
>
> > > > > >> Dave
>
> > > > > >> On Jan 21, 9:25 am, karthikeyan muthu <keyankarthi1...@gmail.com>
> > > > > >> wrote:
> > > > > >> > @dave
>
> > > > > >> > int no=10;
> > > > > >> > char ans[100];
> > > > > >> > sprintf(ans,"%d",no);
> > > > > >> > cout<<ans;
>
> > > > > >> > On Fri, Jan 20, 2012 at 10:29 PM, Arun Vishwanathan
> > > > > >> > <aaron.nar...@gmail.com>wrote:
>
> > > > > >> > > @dave or anyone: can u pls explain the logic of n&3 in dave's
> > > > > >> solution?
> > > > > >> > > why is it subtracted from n(which is divided by 4 using >>2)
> > > > > >> > > and what
> > > > > >> does
> > > > > >> > > n& 3 indicate?
>
> > > > > >> > > On Sat, May 7, 2011 at 9:38 AM, Dave <dave_and_da...@juno.com>
> > > > > >> > > wrote:
>
> > > > > >> > >> @Umer: Do you suppose that you can convert an int into a
> > > > > >> > >> string
> > > > > >> > >> without using division or mod, either directly or indirectly?
>
> > > > > >> > >> Dave
>
> > > > > >> > >> On May 4, 1:12 am, Umer Farooq <the.um...@gmail.com> wrote:
> > > > > >> > >> > I'm surprised to see that why are you guys making this
> > > > > >> > >> > problem so
> > > > > >> > >> complex.
> > > > > >> > >> > This problem can be solved in two steps only.
>
> > > > > >> > >> > 1- Convert the given int into string
> > > > > >> > >> > 2- Check if the last character is 0 or 5. // it yes, then
> > > > > >> > >> > return
> > > > > >> true
> > > > > >> > >> else
> > > > > >> > >> > return false
>
> > > > > >> > >> > for e.g.
>
> > > > > >> > >> > 125 (last character is 5 ... therefore it is divisible by 5)
> > > > > >> > >> > 120 (last character is 0 ... therefore it is divisible by 5)
> > > > > >> > >> > 111 (last character is 1 ... therefore it is not divisible
> > > > > >> > >> > by 5)
>
> > > > > >> > >> > The pseudo-code has been written in my above email.
>
> > > > > >> > >> > On Wed, May 4, 2011 at 1:49 AM, Dave
> > > > > >> > >> > <dave_and_da...@juno.com>
> > > > > >> wrote:
> > > > > >> > >> > > @anshu: Spoiler alert... I was thinking of something more
> > > > > >> > >> > > along
> > > > > >> the
> > > > > >> > >> > > line
>
> > > > > >> > >> > > int DivisibleBy5 (int n)
> > > > > >> > >> > > {
> > > > > >> > >> > > n = n > 0 ? n : -n;
> > > > > >> > >> > > while( n > 0 )
> > > > > >> > >> > > n = (n >> 2) - (n & 3);
> > > > > >> > >> > > return (n == 0);
> > > > > >> > >> > > }
>
> > > > > >> > >> > > To see that it works, write n as n = 4*a + b, where 0 <=
> > > > > >> > >> > > b <= 3.
> > > > > >> Then
> > > > > >> > >> > > the iteration replaces n by a - b. Consider (4*a + b) +
> > > > > >> > >> > > (a - b),
> > > > > >> the
> > > > > >> > >> > > sum of two consecutive values of n. This simplifies to
> > > > > >> > >> > > 5*a,
> > > > > >> which is a
> > > > > >> > >> > > multiple of 5. Thus, n is a multiple of 5 before an
> > > > > >> > >> > > iteration if
> > > > > >> and
> > > > > >> > >> > > only if it also is a multiple of 5 afterwards,
>
> > > > > >> > >> > > It is clearly log n because n is replaced by a number no
> > > > > >> > >> > > greater
> > > > > >> than
> > > > > >> > >> > > n/4 on each iteration.
>
> > > > > >> > >> > > Examples:
> > > > > >> > >> > > n = 125. The sequence of iterates is 30, 5, 0. Ergo, 125
> > > > > >> > >> > > is a
> > > > > >> multiple
> > > > > >> > >> > > of 5.
> > > > > >> > >> > > n = 84. The sequence of iterates is 21, 4, -1. Ergo, 84
> > > > > >> > >> > > is not a
> > > > > >> > >> > > multiple of 5.
>
> > > > > >> > >> > > Dave
>
> > > > > >> > >> > > On May 3, 3:13 am, anshu <anshumishra6...@gmail.com>
> > > > > >> > >> > > wrote:
> > > > > >> > >> > > > algorithm:
>
> > > > > >> > >> > > > if any number(a) is divisible by 5 it can be wriiten as
> > > > > >> > >> > > > 4*b +
> > > > > >> b -->
> > > > > >> > >> > > > this cleary shows the last two bit of a & b will be
> > > > > >> > >> > > > same.
>
> > > > > >> > >> > > > lets understand by an example (35)10 = (100011)2
>
> > > > > >> > >> > > > xx1100
> > > > > >> > >> > > > + xx11
> > > > > >> > >> > > > ---------
> > > > > >> > >> > > > 100011
>
> > > > > >> > >> > > > now this clearly shows we can calculate the unknowns(x)
> > > > > >> > >> > > > by
> > > > > >> > >> traversing
> > > > > >> > >> > > > right to left
>
> > > > > >> > >> > > > code:
>
> > > > > >> > >> > > > int main()
> > > > > >> > >> > > > {
> > > > > >> > >> > > > int n, m;
> > > > > >> > >> > > > cin >> n;
> > > > > >> > >> > > > m = n;
>
> > > > > >> > >> > > > int a, b;
> > > > > >> > >> > > > int i=2;
>
> > > > > >> > >> > > > a = (m&3)<<2;
> > > > > >> > >> > > > b = (m&3);
> > > > > >> > >> > > > m >>= 2;
>
> > > > > >> > >> > > > bool rem = 0,s,r;
>
> > > > > >> > >> > > > while (m>3)
> > > > > >> > >> > > > {
> > > > > >> > >> > > > r = a&(1<<i);
> > > > > >> > >> > > > s = r^(m&1)^rem;
> > > > > >> > >> > > > b =
>
> > ...
>
> > read more »- Hide quoted text -
>
> > - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
