Wheel problem

I was thinking about maps, zips, and other "functions to list" operations, and I though, "Is there any way to combine one list with itself using a wheel procedure". Lets assume we have one unknown size list and a function that receives 2 parameters and returns one (for example an addition of 2 numbers), and we want to combine 1rst element with 2ond, 2ond with 3rd and so on until the last element is combined with the first one again.
Here there is an example
List = [1,2,3] f = function(a,b)
R:=[f(3,1),f(1,2),f(2,3)];

I thought it was really easy to solve it by multiple ways using a complexity of 2*n. For example first counting list size (Complexity n) and then combine elements (Complexity n). But then I thought how this complexity could be reduced. Moreover I realized I was doing this procedure by hand just with Complexity n so it could be possible to implement it. Then I thought this solution

function wheel2(L,f,&last)
if (L.tail eq []) then
last:=L.head;
return [];
else
return Append(wheel2(L.tail,f,last), f(L.head,L.tail.head));
end if;
end function;

function wheel(L,f);
return Append(wheel2(L,f,last), f(last,L.head));
end function;

I didn't find any way to solve the "last" parameter, but I will think about it. If anyone think there is a better solution feel free to post it, I will be really pleased to comment different solutions.

Magma & Sage : software mathematical packages

Magma (http://magma.maths.usyd.edu.au/magma/) is a private software designed to solve computationally hard problems in algebra, number theory, geometry and combinatorics. It uses the best algorithms known at the moment, which makes it really potent.
I use this application to construct and calculate a high variety of codes. It is easy to use and its help is well explained.
Magma makes your live easier when you are working in mathematics problems, it provides quick and easy to use functions to solve a lot of calculations over codes, matrix, vector spaces...
It is also well supported for discrete mathematics, futhermore it has a lot of libraries including cryptography, algebra, all kind of groups and more useful functionalities.

However, Magma is a private software, and I must give another free-software option. This one is Sage .

Sage (http://www.sagemath.org/) is a software for studying a huge range of mathematics, including algebra, calculus, elementary to very advanced number theory, cryptography, numerical computation, commutative algebra, group theory, combinatorics, graph theory, and exact linear algebra.
It tries to be a an open source option to sum up those mathematical applications which are nowadays in the market, like private ones (Mathematica, Magma, Matlab, Maple, ...) or free ones (GAP, Maxima, ...). Sage also have an interface to use those programs (if you have them installed) while you are using sage. It is programed in python but fortunatley (for developers), you have applications to convert other programming languages to python.
Sage is an initiative of profesor William Stein from Washington University. At the moment I am working to convert some applications we use in University to include them in SAGE.

Intersection Array Program

I have told about Intersection Array before, now I will post a program to compute it.
This program has been developed by CCG group, directed by Jaume Pujol and programed by me.
There are various options to use the program:
The program is under GPLv3 license and you can download it from CCGroup
The zip is composed by the source code, the documentation (with some exemples) and a binary.
All you can expect to know is explained on the documentation, in fact, I will sum up the uses of the program.
You can use it to compute the intersection array of a given vector in a code. It will show only the column corresponding to the distance of the vector.
You can also try all the posible distance if you know the covering radius of the code. Then the program will search a vector for each distance lesser than covering radius, and it will compute the intersection array.
You can use it to know if a code is completly regular. When this option is set, you must specify a hamming weight, then it will try all the posible vectors of the same weight and check if they have the same intersection array, until the specified weight or until the word length (there can't exist a vector with hamming weiht > word length). This is an important option, because the problem of knowing if a code is completly regular is a non-polynomial problem. This is, a completly regular code is a code which all the vectors at the same distance to the code, have the same intersection array.

Intersection Array

The intersection array of a vector "V" in a code "C", is a distance d counter of how many vectors "W" where Wi = V + Ei (Ei are all the correctable error vectors in the code). For example if we have a Hamming code (covering radius 1) and we have a vector in the code (d=0), we must compute the distance to the code for each vector W where W are V plus the cosset leaders (except 0 vector).
The first row of the array called A, is the number of W which have the same distance as V that is d(W)=d(V).
The second row of the array called B, is the number of W which have d(W) = d(V)+1.
The third row of the intersection array called C, is the number of W which have d(W) = d(V)-1.
There are more rows, it depends on the covering radius of the code. Is is posible to have 2 * coveringRadius + 1 diferent rows, but the most important are A,B and C.
The columns are the diferent distances of V d(V). So the first column will be for those vectors in the code d(V)=0, the second for those that d(V)=1 etc.

In our example, imagine a Hamming code of length 15. A Hamming Code has covering radius 1 so we will have 3 rows.
We have a vector V which d(V) = 0 we also have 15 diferent Ei vectors so 15 Wi and all will be at d(Wi) = 1 so we will have something like that:
A0 = 0
B0 = 15
C0 = 0
We have a vector V which d(V) = 1 we try all Wi (15 posibilities) and we get that:
A1 = 14
B1 = 0
C1 = 1
We are using a Hamming Code (Covering Radius 1) so we have finished, because interesection array is used with d(V) <= Covering Radius.
We can show all complet intersection array for a Hamming 15 code
( 0 14 )
( 15 0 )
( 0 1 )

And why is that important?
Because we can use intersection array to compute if a code is completly regular.

Reading vectors from a file & representing a code

Here is an example of how to use NTL library. This is a function I have used to read codes. I use the following format to save and load the code, I have tried to save the minium parameters necesaries to respresent code as standard way.

- int base of the code
- int word length
- int cardinal of the code (number of words)
- 1 line for each vector. form --> ( int int int int int )

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Reading Code from file
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
vec_ZZ_p io_read(list &code)
{
FILE *f;//File to read From
int i,j;
char c;
if (( f = fopen(filepath, "r+")) == NULL )
{
perror("This file can not be opened\n");
}

fscanf(f, "%d\n",&base);

/////////////// Definition used for the list of vectors ///////////////////
ZZ p; //Modulus of the vector
p = base;
ZZ_p::init(p); //Ring/Field definition
vec_ZZ_p v; //vector used to compute Intersection Array over ZZ_p
///////////////////////////////////////////////////////////////////////////////////////////

fscanf(f, "%d\n",&wordlength);
fscanf(f, "%d\n",&codecardinal);

v.SetLength(wordlength);

for (i = 0;i < codecardinal;i++)
{
for (j = 0;j < wordlength;j++)
{
fseek(f,1,SEEK_CUR);// jump the blckspace and the "(" character
c = fgetc(f); // get the character we want
v[j] = c-ASCII_CONVERSION;
}
fseek(f,2,SEEK_CUR);// jump the last chars of the string
code.push_back(v);
}
fclose(f);
return v;
}

NTL: A Library for doing Number Theory

NTL is a very interesting free software library for C++ developers who are working on number theory. It provides a hight variety of structures like vectors and matrices thought to be used with big integers, floating point numbers and module mathematics.
It is very powerful, using the best algorithms known at the moment to do fast internal operations, transparents to programmers so it makes it easy to use.
As all "general function software" you can think that you can do it better, while you're doing more specific operations or just using a little part of these functions. In fact, there is always a time/optimization relationship and I really think that it's fast enought to be used with all kind of problems that involves these structures.
I haven't used all the fuctionalities given by this library. At the moment I have tried just module numbers and module numbers vectors, and i have to say that it works really fine. So I have decided to beguin all my programs using NTL, I will write in the future my advances with this library and the problems that I'll see.
At the moment, I am using it to represent codewords of codes over finite fields and over rings.
The worst thing is, that it is compiled using C++ language, so you can use it with C code but you will have to use a C++ compiler; I think it is easier to use C++ for all the code, you'll have the same functionalities of C and easier use, in fact you will lose some time because of the higher-level language that C++ represent.
I'll write an example to use it when I'll explain the C++ aplication I am working on.

You can find information, examples and download the library in http://shoup.net/ntl/

Hello everybody

I have decided to create a blog of programming, here you will find algorithms&code from those aplications i'm developing. The idea is to share with the comunity my interests and my work to discusse posible solutions of programming problems. At the moment my principals lines of work are based on coding theory and cryptology.
Someone said "if I have an idea and you have another one, if we share, we will have two ideas"