A better algorithm would be comparing the first and the last digit, then the second one and the second from the end etc. That has an advantage of giving a faster answer in case of a non-palindrome (which is a typical case).

That can be implemented as follows,

f:=proc(n)
    local a, k, len, m;
    a:=n;
    for len from length(a)-2 by -2 to 0 do
        a:=iquo(a,10,'k');
        a:=irem(a,10^len,'m');
        if not k=m then return false fi 
        od; 
    true 
end;

It is faster than F, but still slower than StringTools:-IsPalindrome,

time(seq(f(n),n=1..100000));
                                0.702

String operations, in general, are rather fast. In particular, the (slightly modified) g procedure has about the same speed as this f,

g := proc(n)
    local s;
    s := ""||n;
    evalb(s = StringTools:-Reverse(s));
end:

time(seq(g(n),n=1..100000));
                                0.717

Applying that algorithm to strings doesn't seem to make it work faster,

G:=proc(n)
    local i, s;
    s := ""||n;
    for i to length(s)/2 do
        if not s[i]=s[-i] then return false fi 
        od; 
    true 
end;

time(seq(G(n),n=1..100000));
                                0.717

Compiler:-Compile can't be used, in general, because the integers can be greater than integer[4] or integer[8].

Alec

A better algorithm would be comparing the first and the last digit, then the second one and the second from the end etc. That has an advantage of giving a faster answer in case of a non-palindrome (which is a typical case).

That can be implemented as follows,

f:=proc(n)
    local a, k, len, m;
    a:=n;
    for len from length(a)-2 by -2 to 0 do
        a:=iquo(a,10,'k');
        a:=irem(a,10^len,'m');
        if not k=m then return false fi 
        od; 
    true 
end;

It is faster than F, but still slower than StringTools:-IsPalindrome,

time(seq(f(n),n=1..100000));
                                0.702

String operations, in general, are rather fast. In particular, the (slightly modified) g procedure has about the same speed as this f,

g := proc(n)
    local s;
    s := ""||n;
    evalb(s = StringTools:-Reverse(s));
end:

time(seq(g(n),n=1..100000));
                                0.717

Applying that algorithm to strings doesn't seem to make it work faster,

G:=proc(n)
    local i, s;
    s := ""||n;
    for i to length(s)/2 do
        if not s[i]=s[-i] then return false fi 
        od; 
    true 
end;

time(seq(G(n),n=1..100000));
                                0.717

Compiler:-Compile can't be used, in general, because the integers can be greater than integer[4] or integer[8].

Alec

Instead of ceil(log[10](1.0*n)), one can use length(n). It is a built-in command, so should work faster.

In the current form, F is 40 times slower than StringTools:-IsPalindrome in the following time test,

time(seq(F(n),n=1..100000));
                                11.887

time(seq(StringTools:-IsPalindrome(""||n),
    n=1..100000));
                                0.280

Alec

Instead of ceil(log[10](1.0*n)), one can use length(n). It is a built-in command, so should work faster.

In the current form, F is 40 times slower than StringTools:-IsPalindrome in the following time test,

time(seq(F(n),n=1..100000));
                                11.887

time(seq(StringTools:-IsPalindrome(""||n),
    n=1..100000));
                                0.280

Alec

A slash, i.e. / should work as a separator OK in all cases. If it doesn't work, then the standard in Windows backslash \ can be used. However, it is an escape character inside Maple strings, so it can not be used alone - it has to be entered as \\ -then the first backslash works as an escape character allowing to display the second backslash as it is.

The safest way of entering the paths (in Windows) is using \\ rather than /. I just prefer / because it is shorter and looks better, and use \\ only if / is not working.

The mixing of \\ and / looks strange, but can be explained by the way the string was produced - as a concatenation of 2 strings, the main Maple location (with backslashes), and the library location under it, "/lib".

Alec

A slash, i.e. / should work as a separator OK in all cases. If it doesn't work, then the standard in Windows backslash \ can be used. However, it is an escape character inside Maple strings, so it can not be used alone - it has to be entered as \\ -then the first backslash works as an escape character allowing to display the second backslash as it is.

The safest way of entering the paths (in Windows) is using \\ rather than /. I just prefer / because it is shorter and looks better, and use \\ only if / is not working.

The mixing of \\ and / looks strange, but can be explained by the way the string was produced - as a concatenation of 2 strings, the main Maple location (with backslashes), and the library location under it, "/lib".

Alec

It is correct.

Alec

It is correct.

Alec

First, the correct assignments look like p:=P[i]; without the additional bracket after that. Second, I can't test that because you didn't post all the commands - in particular, the values of P, Q, F, and A.

Alec

First, the correct assignments look like p:=P[i]; without the additional bracket after that. Second, I can't test that because you didn't post all the commands - in particular, the values of P, Q, F, and A.

Alec

Let's suppose you have a 16-bit number 1001101100011001. If you divide it by 1024=2^10 =10000000000₂, the quotient will be (in base 2) the first six bits, 100110, and the remainder will be the last (the lowest) 10 bits, 1100011001 (in base 2).

So, the highest 6 bits don't matter - any of them will give the same number mod 1024.

These 6 bits are the result of the operation AND on the highest 6 bits in part 1, and the highest 6 bits in the part 3, total 12 bits, which can be anything. They give 12 places filled with 0s and 1s, 2 choices for every place, total 2^12 choices.

Now, for the remainder, 1100011001 in this example, every 1 can be obtained only 1 way, as 1 AND 1, and every 0 can be obtained 3 ways, so the total number of choices, which is the product of the number of choices for every bit (by the so-called product rule), is 1*1*3*3*3*1*1*3*3*1=3^5, i.e. 3 in the power of the number of 0s in that remainder, which I denoted z(n).

Is it more clear now?

Alec

Let's suppose you have a 16-bit number 1001101100011001. If you divide it by 1024=2^10 =10000000000₂, the quotient will be (in base 2) the first six bits, 100110, and the remainder will be the last (the lowest) 10 bits, 1100011001 (in base 2).

So, the highest 6 bits don't matter - any of them will give the same number mod 1024.

These 6 bits are the result of the operation AND on the highest 6 bits in part 1, and the highest 6 bits in the part 3, total 12 bits, which can be anything. They give 12 places filled with 0s and 1s, 2 choices for every place, total 2^12 choices.

Now, for the remainder, 1100011001 in this example, every 1 can be obtained only 1 way, as 1 AND 1, and every 0 can be obtained 3 ways, so the total number of choices, which is the product of the number of choices for every bit (by the so-called product rule), is 1*1*3*3*3*1*1*3*3*1=3^5, i.e. 3 in the power of the number of 0s in that remainder, which I denoted z(n).

Is it more clear now?

Alec

Axel,

You are right!

Well, except she didn't take it - I gave it to her (as a gift of love.) But I really like it.

Alec

In this case, it would have sense to give prizes to 3 or 4 people instead of one (so that I also had a chance :). Perhaps, with smaller prizes - the monthly ones.

Alec

This is a simple calculation.

A 16-bit number mod 1024 = 2^10 is just the lowest 10 bit of it. The highest 6 bits are not used, so the 12 bits that they are made from, can be anything - that gives multiplier 2^12 to the number of IP addresses corresponding to the given result (from 0 to 1023).

Now, 0 bit can be obtained in 3 cases of using AND - 0 & 1, 1 & 0, and 0 & 0, and 1 only in one case, as 1&1.

Let z(n) be the number of 0s in the 10 bits of the number n from 0 to 1023. For example, z(0)=10, z(1)=9, and z(1023)=0.

Since every 0 bit can be obtained in 3 cases, and 1 - in 1 case, by the product rule, the number of IP addresses mapping to n equals 3^z(n)*2^12.

That tells that the algorithm is very bad - for example, 3^10*2^12 IP addresses are mapped to 0, and only 2^12 IP addresses are mapped to 1023.

A "good" algorithm can be constructed by choosing an operation producing 2 0s and 2 1s instead of AND - for example, a (bitwise) xor. That would lead to a mapping of 2^22 IP addresses to every number from 0 to 1023.

Alec