Carl Love

Carl Love

28035 Reputation

25 Badges

12 years, 319 days
Himself
Wayland, Massachusetts, United States
My name was formerly Carl Devore.

MaplePrimes Activity


These are replies submitted by Carl Love

Please don't post Questions in inappropriate places. This Question has nothing to do with C-means clustering, so I've reposted it as a separate Question.

@jgray07m You need the proper Maple syntax for the fundamental constants. It should be

z1:= exp(Pi*I/3);  z2:= exp(-Pi*I/3);

So note that Pi and I are capitalized, and is replaced by the exponential function, exp.

@HS I used syntax new to Maple 2019. What Maple version do you have? The following will work as long as your Maple has index (Maple 2017?):

`mod/Generators`:= proc(q::RootOf, p::prime)
    local 
        x, n:= p^degree(op(q))-1, 
        Ns:= n/~NumberTheory:-PrimeFactors(n):
    select(
        e-> not 1 in Expand~(e^~Ns) mod p,
        index~(Roots(x^n-1, q) mod p, 1)
    )
end proc:

Check if your Maple has index. If not, I'll need to modify the above.

The command to look up in help is index, not index~. The ~ is the elementwise operator, which you can read about on help page ?elementwise. Basically, it makes any command act on the objects in a container individually rather than acting on the container itself.

If your Maple version is earlier than Maple 2018, then I'll also need to change the until clause that appears later in the worksheet.

Regarding syntax highlighting, the Code Edit Regions in Maple 2019 have it. Maybe Maple 2018 also.

@HS I think that there's a possibility that you may be confusing finite fields of non-prime order (which are of course constructed with polynomials) with the rings of polynomials defined over those fields. GF is an efficient choice (although the user interface is clunky) for computations in the fields themselves, and mod works for this also--still efficient, but not quite as efficient as GF[*1]. But GF (as far as I know) doesn't work with the rings of polynomials defined over those fields; mod does.

[*1] because GF avoids some unnecessary conversions from/to external format to/from the much-more efficient zppoly format. 

@HS You wrote:

  • Your way  for computing Gcd over non prime order fields does not work since your not moding out by an irreducible polynomial of degree 2 it won't even recognize when your polynomial is 0.

What you wrote there is totally wrong. You don't know what you're talking about, and I suspect that you have an attitude problem that's blocking your ability to learn. Do you think that I faked the output in that Answer? Do you see any q coefficients of degree 2 or higher in my gcd? The "modding out" that you refer to happens in the background, so you don't notice it.

Here's an example of computing generators and inverses in GF(7,3):
 

restart
:

(p,d):= (7,3): #characteristic and degree of field

irr:= Randprime(d,z) mod p; #random irreducible polynomial

z^3+5*z^2+5*z+2

#This is the key step that I think that you're failing to understand:
#After I
#do this, I never need to look at that irreducible polynomial again,
#let alone explicitly "mod it out". It all happens in the background.
alias(q = RootOf(irr, z))
:

#Procedure that computes all generators {of a reasonably small field):
`mod/Generators`:= (q::RootOf, p::prime)->
    local
        x, n:= p^degree(op(q))-1,
        Ns:= n/~NumberTheory:-PrimeFactors(n):
    select(
        e-> not 1 in Expand~(e^~Ns) mod p,
        index~(Roots(x^n-1, q) mod p, 1)
    )
:

G:= Generators(q) mod p;

[6*q^2+2, q+2, 6*q^2+4*q+3, 5*q+6, 6*q^2+q+5, 4*q^2+4*q+6, 2*q^2+q, q^2+2*q+2, 3*q^2+3*q+6, 6*q^2+4*q+4, 2*q^2+3*q, 3*q+1, q^2+4*q+3, 5*q^2+5*q+5, 3*q^2+6*q+4, 3*q^2+6*q+5, 4*q^2+3*q, 6*q^2+q+1, 5*q^2, 2*q^2+5*q+6, 6*q^2, 5*q^2+q+3, 5*q^2+2*q+2, 4*q^2+3*q+5, 2*q^2+4*q+4, 3*q^2, 5*q^2+4, 6*q^2+6*q, 4*q+1, 2*q^2+3*q+6, 3*q^2+1, 4*q, 3*q^2+3*q, q^2+5*q+3, 3*q^2+q+1, 6*q^2+3*q+3, 6*q^2+4*q+1, 5*q^2+2*q+3, q^2+5*q+4, 5*q^2+q+6, 6*q^2+6, 4*q^2+2*q+5, 2*q^2+3*q+1, 5*q^2+5*q+3, 5*q^2+6*q+6, 3*q^2+3, 5*q+4, 3*q^2+5*q+6, q, 6*q^2+4*q+5, 6*q^2+6*q+5, 2*q, 3*q^2+3*q+3, 3*q^2+4*q+4, 3*q^2+2*q+6, 6*q+3, 2*q^2+2*q+3, 6*q^2+2*q+2, 6*q^2+3*q+1, 2*q+4, q^2+6*q+5, 3*q+2, 2*q^2+5*q+3, 6*q^2+5*q+2, 6*q^2+6*q+6, 4*q^2+6*q, 3*q+5, 5*q^2+6*q+3, 5*q^2+3*q+4, 5*q^2+q+2, 3*q^2+2*q+1, q^2+6*q, 5*q^2+5, 6*q^2+3*q+5, 4*q^2+2*q, 3*q^2+5*q+5, 6*q^2+5*q+3, 4*q^2+6*q+2, 4*q^2+q+1, 5*q^2+5*q, 6*q^2+4*q+6, 3*q^2+2*q+5, 3*q^2+2*q+2, 5*q^2+3*q+6, 4*q^2+6*q+5, 3*q^2+2*q+3, 3*q^2+5*q+4, 6*q+4, 5*q^2+q+5, 3*q^2+2*q+4, 3*q^2+6*q+1, 3*q^2+4*q+6, 6*q+2, 6*q^2+4*q+2, 6*q^2+5*q+1, 2*q^2+q+6, 5*q^2+3*q+2, 5*q^2+4*q+4, q^2+5*q, 4*q^2+3*q+6, 5*q+1, 2*q^2+5*q, q^2+4*q, q^2+6*q+3, 5*q^2+6*q+2, q^2+q+5, 5*q^2+q+4, 5*q^2+q+1]

#Pick one at random:
g:= combinat:-randcomb(G,1)[];

4*q

#Compute its powers until we get 1:
x:= 1: for k do x:= Expand(x*g) mod p until x= 1:

#Verify that we went through every nonzero field element:
k = p^d-1;

342 = 342

#Compute an inverse:
g1:= Expand(1/g) mod p;

6*q^2+2*q+2

Expand(g*g1) mod p;

1

 


 

Download GF73.mw

@HS There are packages for high-speed computations with univariate and bivariate polynomials over finite fields. These are called modp1 and modp2. Most of the functionality of these packages is available through end-user-level commands, for example, mod. But, sometimes you want to work at the nitty-gritty level and need these packages directly. ConvertIn is a command in these packages (and of Maple modules (not algebraic modules) created with GF). I'll agree that the documentation of these is sketchy. See ?modp1 and ?GF. There is a fundamental Maple data structure called zppoly used by these, which is mentioned.in the original Question. 

I don't have an answer for you, but I just wanted to praise you for a very well-asked Question from a first-timer.

I added tag Physics, which is always a good idea for Questions regarding that package. 

@acer Indeed the time difference is disturbing! There's something in both the original code and mine that takes significantly longer in Maple 2016+.

Regarding RAM, I could write it to use less memory at the expense of some time by using an iterator for combinat:-choose. But I'm hoping for an intermediate-sized test case before I do that. 

@Magma There's a bug in older 2D input such that it can't handle some instances of (). You can change that to or anything else. The entries of that table are insignificant; only the indices matter. It's a tactic that I often use: I use () when the entries of a table don't matter. Anything could be used. Most people write NULL.

Do you have an intermediate-sized example, larger than 5x6 but smaller than the one immediately above?

Why do you use overload?

@Magma I'm beginning to work on your procedure now. The first phase is to change the things that are slow due to idiosyncracies of Maple. However, the algorithm itself (as contrasted with simply its Maple implementation) appears to have 5-deep nested loops. I may not be able to overcome that to handle 32x32 input in reasonable time.

@ActiveUser For output, you can use any Unicode symbol. You can even use a Chinese character. Amazingly, this even works in the command-line interface. You just need the Unicode byte values of the character, which you can find on Wikipedia. 

@Kitonum I was supposing 0 points for unanswered questions, so -9 comes from 9 incorrect answers and 1 unanswered. 

@666 jvbasha Sorry, I can't help you. Hopefully someone else can.

@666 jvbasha Sorry, but I don't have sufficient background to begin reading the paper at Eq. 16 and understand it. Perhaps if I had the whole paper, I could.

And why does the plot's caption say "3rd- and 4th-order approximation" whereas its legend says "13th-, 14th-, 15th-order approximation"?

First 237 238 239 240 241 242 243 Last Page 239 of 708