Post your code optimizations
- Thread starter KimB
- Start date
Simon F said:I think someone has much too much spare time
Nah, I just love math, especially abstract algebra and number theory.
I forgot to mention the best known example of an Extension Field, one that DiGuru is probably aware of, but doesn't realize it.
Let Q be the field of rational numbers. Let Q[x] be the field of polynomials with rational coefficients. Now we can form polynomials like
f(x) = x^2 + 1
And ask if this polynomial has any zeros in Q, e.g. does x in Q exist such that f(x) = 0?
Of course, the answer is no. Now, you will of course know from regular algebra that one solution is to introduce the sqrt(-1), and extend the field to include imaginary numbers. But, this isn't needed.
Instead, one could pick an irreducible polynomial p(x) and form the Extension Field Q[x]/<p(x)>. x^2+1 is already one such polynomial, so we create a new field Q[x]/<x^2 + 1>. This new field contains the field Q[x], but also contains a zero for the polymomial x^2 + 1. All without introducing imaginary numbers. Say what!?
This theory also can be used to prove that there exists no general formula ot solve polynomials of degree 5 or higher (e.g. no quadratic formula-like solution), as well as no solution to trisecting an angle or squaring a circle with straightedge and compass.
As a side note, the inventor of Abstract Algebra and Field theory, Galois, died at age 19 from a gunshot wound in a duel.
Chalnoth said:
Sort, like saying that addition in the integers and addition modulo m is a "redefinition". Skip to the end if you want the quick answer.
If you have a ring R, and a subring A, then if for every element r in R, and every element a in A, ra is in A, then A is called an Ideal of R. A is said to "absorb" elements of R, since multiplying any element in R by an element in the subset of A yields an element in the subset.
Example: 4Z. If Z is the integers, then 4Z is all integers multiple 4, e.g. 0, 4, 8, 12, 16, 20, ... Now, if you take any element in Z and multiply it by an element in 4Z, you get an element in 4Z. Therefore, the elements multiple 4 form an Ideal of the ring of integers. They "absorb" integers like ice-9 and turn them into 4-integers.
Now, given the definition of ideals, we can create things called "factor rings", which I will write Z/4Z defined as so, given R/A, the set S = { for every r in R, r + A }. That is, the set of cosets of A under addition. Addition is defined as given (x+A) + (y+A) = (x+y) + A, and multiplication is given as (x+A)*(y+A) = (x*y) + A. Rememer, (x+A) means coset, so it represents the set defined by x + every element of A.
Example using Z/4Z:
This says that the elements in the new factor ring Z/4Z will be the cosets: 0 + 4Z, 1+4Z, 2+4Z, 3+4Z, 4+4Z, 5+4Z,.... infinity. However, 4+4Z is the same as 0+4Z and 5+4Z is the same as 1+4Z, etc. So the new set only contains 4 elements: 0+4Z, 1 + 4Z, 2+4Z, 3+4Z.
Note that if I add two elements, like (1+4Z) and (2+4Z) I just do (1+2) + 4Z = 3+4Z, and if I multiply two elements, I do, (2+4Z)*(3+4Z) = 6+4Z. You can verify yourself that this definition of addition and multiplication works properly (e.g. take all multiples of 4, add 1, and add multiplies of 4, add 2, add them together, and you'll see its equivalent to all multiplies of 4 with 3 added).
Phew. Ok, now, what does Q[x]/<x^2+1> mean? Well, Q[x] is the ring of all polynomials with rational coefficients, e.g. 3x^2 + 2/3 x + 9. We definately know that x^2 + 1 has no zero in this ring. The question is, does it have a zero in Q[x]/<x^2+1> and what the heck is this?
First, what is <x^2 + 1>? It's an ideal of Q[x], formed by taking every element of function f(x) over Q[x] and multiplying it by (x^2 + 1). e.g. functions like 1, x, 1+x, x+42x, x^2 + 666, etc and multiplying them by x^2 + 1. Why is it an ideal? For the same reason that 4Z is an ideal. Any polynomial in Q[x] when multiplied by an element of <x^2 + 1> will be a multiple of x^2+1 and therefore inside (absorbed) by the ideal <x^2 + 1>
Now we are finallly prepared to discuss what is Q[x]/<x^2+1>. It is simply put, the set of cosets of Q[x] formed by taking every function q(x) in Q[x] and adding it to elements in <x^2 + 1>, just like we did with the Z/4Z example.
I'll now show you why f(x)=x^2 + 1 has zero in this field, whereas it doesn't in Q[x]. Consider the element x + <x^2+1> in Q[x]/<x^2 + 1>. This is simply, all functions in ideal <x^2 + 1> with x added to them. Plug this into our f(x).
f(x) = x^2 + 1
f(x + <x^2 + 1>) = (x + <x^2+1> )^2 + 1
by the definition of ideal this multiplication operation above is
f(x+<x^2+1>) = (x * x) + <x^2 + 1> + 1
rewrite as
f(x + <x^2 + 1>) = (x^2 + 1) + <x^2 + 1>
but this can be rewritten as
f(x + <x^2 + 1>) = 0 + <x^2 + 1>
just like 4 + 4Z can be rewritten as 0 + 4Z.
Phew! Ok, if you hadn't noticed it yet, factor rings look like a modulus operation. That is, Z/4Z is isomorphic to the integers mod 4. And Q[x]/<x^2 + 1> is isomorphic to...drum roll... the set of all polynomials with rational coefficients modulo x^2 + 1 That is, you take every q(x) in Q[x], perform polynomial long division with x^2 + 1 as the divisor, and the remainders are isomorphic to the elements of Q[x]/<x^2 + 1>
It turns out that R[x]/<x^2 + 1> is isomorphic to the complex numbers. The reason for the long winded explanation is that there are lots of other fields which are not isomorphic to complex numbers, and there extension fields which don't look like "modulus"
Therefore, if you give me any irreducible polynomial in a particular field, like Z_3[x], or Q[x], I can create a new field which contains Z_3[x] or Q[x] in its entirety, preserves their operations, and contains a subring which is isomorphic to those fields *PLUS* it contains a zero for this irreducible polynomial.
Mate Kovacs
Newcomer
As a sidenote to the "evaluation order" discussion: I've just found a warning option called "-Wsequence-point" in GCC.
Unfortunately, it doesn't seem to apply for G++.
Unfortunately, it doesn't seem to apply for G++.